diff options
| -rw-r--r-- | .travis.yml | 1 | ||||
| -rw-r--r-- | FUZZER-NOTES.md | 3 | ||||
| -rw-r--r-- | LICENSE | 71 | ||||
| -rw-r--r-- | Makefile.in | 12 | ||||
| -rw-r--r-- | README | 1 | ||||
| -rw-r--r-- | cli-kex.c | 2 | ||||
| -rw-r--r-- | common-algo.c | 3 | ||||
| -rw-r--r-- | common-kex.c | 14 | ||||
| -rw-r--r-- | curve25519-donna.c | 860 | ||||
| -rw-r--r-- | curve25519.c | 502 | ||||
| -rw-r--r-- | curve25519.h | 37 | ||||
| -rw-r--r-- | default_options.h | 7 | ||||
| -rw-r--r-- | dropbear.8 | 6 | ||||
| -rw-r--r-- | dropbearkey.c | 25 | ||||
| -rw-r--r-- | ed25519.c | 184 | ||||
| -rw-r--r-- | ed25519.h | 54 | ||||
| -rw-r--r-- | filelist.txt | 4 | ||||
| -rw-r--r-- | fuzz-common.c | 8 | ||||
| -rw-r--r-- | fuzz-hostkeys.c | 10 | ||||
| -rw-r--r-- | fuzzer-kexcurve25519.c | 72 | ||||
| -rw-r--r-- | gened25519.c | 47 | ||||
| -rw-r--r-- | gened25519.h | 36 | ||||
| -rw-r--r-- | gensignkey.c | 10 | ||||
| -rw-r--r-- | keyimport.c | 158 | ||||
| -rw-r--r-- | signkey.c | 60 | ||||
| -rw-r--r-- | signkey.h | 7 | ||||
| -rw-r--r-- | ssh.h | 2 | ||||
| -rw-r--r-- | svr-kex.c | 8 | ||||
| -rw-r--r-- | svr-runopts.c | 24 | ||||
| -rw-r--r-- | sysoptions.h | 7 |
30 files changed, 1289 insertions, 946 deletions
diff --git a/.travis.yml b/.travis.yml index 9bcbce4..99499c8 100644 --- a/.travis.yml +++ b/.travis.yml @@ -57,6 +57,7 @@ script: - ~/inst/bin/dropbearkey -t ecdsa -f testec256 -s 256 - ~/inst/bin/dropbearkey -t ecdsa -f testec384 -s 384 - ~/inst/bin/dropbearkey -t ecdsa -f testec521 -s 521 + - ~/inst/bin/dropbearkey -t ed25519 -f tested25519 - test -z $DO_FUZZ || ./fuzzers_test.sh branches: diff --git a/FUZZER-NOTES.md b/FUZZER-NOTES.md index 7b88238..4967eba 100644 --- a/FUZZER-NOTES.md +++ b/FUZZER-NOTES.md @@ -72,3 +72,6 @@ Current fuzzers are - [fuzzer-kexecdh](fuzzer-kexecdh.c) - test Elliptic Curve Diffie-Hellman key exchange like fuzzer-kexdh. This is testing libtommath ECC routines. + +- [fuzzer-kexcurve25519](fuzzer-kexcurve25519.c) - test Curve25519 Elliptic Curve Diffie-Hellman key exchange + like fuzzer-kexecdh. This is testing `dropbear_curve25519_scalarmult()` and other libtommath routines. @@ -90,52 +90,25 @@ WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. ===== -curve25519-donna: - -/* Copyright 2008, Google Inc. - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions are - * met: - * - * * Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * * Redistributions in binary form must reproduce the above - * copyright notice, this list of conditions and the following disclaimer - * in the documentation and/or other materials provided with the - * distribution. - * * Neither the name of Google Inc. nor the names of its - * contributors may be used to endorse or promote products derived from - * this software without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS - * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT - * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR - * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT - * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, - * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT - * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, - * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY - * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE - * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - * - * curve25519-donna: Curve25519 elliptic curve, public key function - * - * http://code.google.com/p/curve25519-donna/ - * - * Adam Langley <agl@imperialviolet.org> - * - * Derived from public domain C code by Daniel J. Bernstein <djb@cr.yp.to> - * - * More information about curve25519 can be found here - * http://cr.yp.to/ecdh.html - * - * djb's sample implementation of curve25519 is written in a special assembly - * language called qhasm and uses the floating point registers. - * - * This is, almost, a clean room reimplementation from the curve25519 paper. It - * uses many of the tricks described therein. Only the crecip function is taken - * from the sample implementation. - */ +crypto25519.c: +crypto26619.h: + +Modified TweetNaCl version 20140427, a self-contained public-domain C library. +https://tweetnacl.cr.yp.to/ + +Contributors (alphabetical order) +Daniel J. Bernstein, University of Illinois at Chicago and Technische +Universiteit Eindhoven +Bernard van Gastel, Radboud Universiteit Nijmegen +Wesley Janssen, Radboud Universiteit Nijmegen +Tanja Lange, Technische Universiteit Eindhoven +Peter Schwabe, Radboud Universiteit Nijmegen +Sjaak Smetsers, Radboud Universiteit Nijmegen + +Acknowledgments +This work was supported by the U.S. National Science Foundation under grant +1018836. "Any opinions, findings, and conclusions or recommendations expressed +in this material are those of the author(s) and do not necessarily reflect the +views of the National Science Foundation." +This work was supported by the Netherlands Organisation for Scientific +Research (NWO) under grant 639.073.005 and Veni 2013 project 13114. diff --git a/Makefile.in b/Makefile.in index bc55b7d..aaf7b3b 100644 --- a/Makefile.in +++ b/Makefile.in @@ -36,8 +36,9 @@ COMMONOBJS=dbutil.o buffer.o dbhelpers.o \ queue.o \ atomicio.o compat.o fake-rfc2553.o \ ltc_prng.o ecc.o ecdsa.o crypto_desc.o \ + curve25519.o ed25519.o \ dbmalloc.o \ - gensignkey.o gendss.o genrsa.o + gensignkey.o gendss.o genrsa.o gened25519.o SVROBJS=svr-kex.o svr-auth.o sshpty.o \ svr-authpasswd.o svr-authpubkey.o svr-authpubkeyoptions.o svr-session.o svr-service.o \ @@ -52,7 +53,7 @@ CLIOBJS=cli-main.o cli-auth.o cli-authpasswd.o cli-kex.o \ CLISVROBJS=common-session.o packet.o common-algo.o common-kex.o \ common-channel.o common-chansession.o termcodes.o loginrec.o \ tcp-accept.o listener.o process-packet.o dh_groups.o \ - common-runopts.o circbuffer.o curve25519-donna.o list.o netio.o + common-runopts.o circbuffer.o list.o netio.o KEYOBJS=dropbearkey.o @@ -264,7 +265,7 @@ tidy: ## Fuzzing targets # list of fuzz targets -FUZZ_TARGETS=fuzzer-preauth fuzzer-pubkey fuzzer-verify fuzzer-preauth_nomaths fuzzer-kexdh fuzzer-kexecdh +FUZZ_TARGETS=fuzzer-preauth fuzzer-pubkey fuzzer-verify fuzzer-preauth_nomaths fuzzer-kexdh fuzzer-kexecdh fuzzer-kexcurve25519 FUZZER_OPTIONS = $(addsuffix .options, $(FUZZ_TARGETS)) @@ -303,6 +304,9 @@ fuzzer-kexdh: fuzzer-kexdh.o fuzz-harness.o fuzzer-kexecdh: fuzzer-kexecdh.o fuzz-harness.o $(CXX) $(CXXFLAGS) $@.o $(LDFLAGS) $(svrfuzzobjs) -o $@$(EXEEXT) $(LIBTOM_LIBS) $(LIBS) $(FUZZLIB) @CRYPTLIB@ +fuzzer-kexcurve25519: fuzzer-kexcurve25519.o fuzz-harness.o + $(CXX) $(CXXFLAGS) $@.o $(LDFLAGS) $(svrfuzzobjs) -o $@$(EXEEXT) $(LIBTOM_LIBS) $(LIBS) $(FUZZLIB) @CRYPTLIB@ + fuzzer-%.options: Makefile echo "[libfuzzer]" > $@ echo "max_len = 50000" >> $@ @@ -313,7 +317,9 @@ fuzz-hostkeys: dropbearkey -t rsa -f keyr dropbearkey -t dss -f keyd dropbearkey -t ecdsa -size 256 -f keye + dropbearkey -t ed25519 -f keyed25519 echo > hostkeys.c /usr/bin/xxd -i -a keyr >> hostkeys.c /usr/bin/xxd -i -a keye >> hostkeys.c /usr/bin/xxd -i -a keyd >> hostkeys.c + /usr/bin/xxd -i -a keyed25519 >> hostkeys.c @@ -55,6 +55,7 @@ To run the server, you need to generate server keys, this is one-off: ./dropbearkey -t rsa -f dropbear_rsa_host_key ./dropbearkey -t dss -f dropbear_dss_host_key ./dropbearkey -t ecdsa -f dropbear_ecdsa_host_key +./dropbearkey -t ed25519 -f dropbear_ed25519_host_key or alternatively convert OpenSSH keys to Dropbear: ./dropbearconvert openssh dropbear /etc/ssh/ssh_host_dsa_key dropbear_dss_host_key @@ -81,7 +81,7 @@ void send_msg_kexdh_init() { } cli_ses.curve25519_param = gen_kexcurve25519_param(); } - buf_putstring(ses.writepayload, (const char*)cli_ses.curve25519_param->pub, CURVE25519_LEN); + buf_putstring(ses.writepayload, cli_ses.curve25519_param->pub, CURVE25519_LEN); break; #endif } diff --git a/common-algo.c b/common-algo.c index 2f896ab..558aad2 100644 --- a/common-algo.c +++ b/common-algo.c @@ -222,6 +222,9 @@ algo_type ssh_nocompress[] = { }; algo_type sshhostkey[] = { +#if DROPBEAR_ED25519 + {"ssh-ed25519", DROPBEAR_SIGNKEY_ED25519, NULL, 1, NULL}, +#endif #if DROPBEAR_ECDSA #if DROPBEAR_ECC_256 {"ecdsa-sha2-nistp256", DROPBEAR_SIGNKEY_ECDSA_NISTP256, NULL, 1, NULL}, diff --git a/common-kex.c b/common-kex.c index d4933dd..16b7e27 100644 --- a/common-kex.c +++ b/common-kex.c @@ -36,6 +36,7 @@ #include "dbrandom.h" #include "runopts.h" #include "ecc.h" +#include "curve25519.h" #include "crypto_desc.h" static void kexinitialise(void); @@ -703,23 +704,18 @@ void kexecdh_comb_key(struct kex_ecdh_param *param, buffer *pub_them, #endif /* DROPBEAR_ECDH */ #if DROPBEAR_CURVE25519 -struct kex_curve25519_param *gen_kexcurve25519_param () { +struct kex_curve25519_param *gen_kexcurve25519_param() { /* Per http://cr.yp.to/ecdh.html */ struct kex_curve25519_param *param = m_malloc(sizeof(*param)); const unsigned char basepoint[32] = {9}; genrandom(param->priv, CURVE25519_LEN); - param->priv[0] &= 248; - param->priv[31] &= 127; - param->priv[31] |= 64; - - curve25519_donna(param->pub, param->priv, basepoint); + dropbear_curve25519_scalarmult(param->pub, param->priv, basepoint); return param; } -void free_kexcurve25519_param(struct kex_curve25519_param *param) -{ +void free_kexcurve25519_param(struct kex_curve25519_param *param) { m_burn(param->priv, CURVE25519_LEN); m_free(param); } @@ -736,7 +732,7 @@ void kexcurve25519_comb_key(const struct kex_curve25519_param *param, const buff dropbear_exit("Bad curve25519"); } - curve25519_donna(out, param->priv, buf_pub_them->data); + dropbear_curve25519_scalarmult(out, param->priv, buf_pub_them->data); if (constant_time_memcmp(zeroes, out, CURVE25519_LEN) == 0) { dropbear_exit("Bad curve25519"); diff --git a/curve25519-donna.c b/curve25519-donna.c deleted file mode 100644 index ef0b6d1..0000000 --- a/curve25519-donna.c +++ /dev/null @@ -1,860 +0,0 @@ -/* Copyright 2008, Google Inc. - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions are - * met: - * - * * Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * * Redistributions in binary form must reproduce the above - * copyright notice, this list of conditions and the following disclaimer - * in the documentation and/or other materials provided with the - * distribution. - * * Neither the name of Google Inc. nor the names of its - * contributors may be used to endorse or promote products derived from - * this software without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS - * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT - * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR - * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT - * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, - * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT - * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, - * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY - * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE - * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - * - * curve25519-donna: Curve25519 elliptic curve, public key function - * - * http://code.google.com/p/curve25519-donna/ - * - * Adam Langley <agl@imperialviolet.org> - * - * Derived from public domain C code by Daniel J. Bernstein <djb@cr.yp.to> - * - * More information about curve25519 can be found here - * http://cr.yp.to/ecdh.html - * - * djb's sample implementation of curve25519 is written in a special assembly - * language called qhasm and uses the floating point registers. - * - * This is, almost, a clean room reimplementation from the curve25519 paper. It - * uses many of the tricks described therein. Only the crecip function is taken - * from the sample implementation. */ - -#include <string.h> -#include <stdint.h> - -#ifdef _MSC_VER -#define inline __inline -#endif - -typedef uint8_t u8; -typedef int32_t s32; -typedef int64_t limb; - -/* Field element representation: - * - * Field elements are written as an array of signed, 64-bit limbs, least - * significant first. The value of the field element is: - * x[0] + 2^26·x[1] + x^51·x[2] + 2^102·x[3] + ... - * - * i.e. the limbs are 26, 25, 26, 25, ... bits wide. */ - -/* Sum two numbers: output += in */ -static void fsum(limb *output, const limb *in) { - unsigned i; - for (i = 0; i < 10; i += 2) { - output[0+i] = output[0+i] + in[0+i]; - output[1+i] = output[1+i] + in[1+i]; - } -} - -/* Find the difference of two numbers: output = in - output - * (note the order of the arguments!). */ -static void fdifference(limb *output, const limb *in) { - unsigned i; - for (i = 0; i < 10; ++i) { - output[i] = in[i] - output[i]; - } -} - -/* Multiply a number by a scalar: output = in * scalar */ -static void fscalar_product(limb *output, const limb *in, const limb scalar) { - unsigned i; - for (i = 0; i < 10; ++i) { - output[i] = in[i] * scalar; - } -} - -/* Multiply two numbers: output = in2 * in - * - * output must be distinct to both inputs. The inputs are reduced coefficient - * form, the output is not. - * - * output[x] <= 14 * the largest product of the input limbs. */ -static void fproduct(limb *output, const limb *in2, const limb *in) { - output[0] = ((limb) ((s32) in2[0])) * ((s32) in[0]); - output[1] = ((limb) ((s32) in2[0])) * ((s32) in[1]) + - ((limb) ((s32) in2[1])) * ((s32) in[0]); - output[2] = 2 * ((limb) ((s32) in2[1])) * ((s32) in[1]) + - ((limb) ((s32) in2[0])) * ((s32) in[2]) + - ((limb) ((s32) in2[2])) * ((s32) in[0]); - output[3] = ((limb) ((s32) in2[1])) * ((s32) in[2]) + - ((limb) ((s32) in2[2])) * ((s32) in[1]) + - ((limb) ((s32) in2[0])) * ((s32) in[3]) + - ((limb) ((s32) in2[3])) * ((s32) in[0]); - output[4] = ((limb) ((s32) in2[2])) * ((s32) in[2]) + - 2 * (((limb) ((s32) in2[1])) * ((s32) in[3]) + - ((limb) ((s32) in2[3])) * ((s32) in[1])) + - ((limb) ((s32) in2[0])) * ((s32) in[4]) + - ((limb) ((s32) in2[4])) * ((s32) in[0]); - output[5] = ((limb) ((s32) in2[2])) * ((s32) in[3]) + - ((limb) ((s32) in2[3])) * ((s32) in[2]) + - ((limb) ((s32) in2[1])) * ((s32) in[4]) + - ((limb) ((s32) in2[4])) * ((s32) in[1]) + - ((limb) ((s32) in2[0])) * ((s32) in[5]) + - ((limb) ((s32) in2[5])) * ((s32) in[0]); - output[6] = 2 * (((limb) ((s32) in2[3])) * ((s32) in[3]) + - ((limb) ((s32) in2[1])) * ((s32) in[5]) + - ((limb) ((s32) in2[5])) * ((s32) in[1])) + - ((limb) ((s32) in2[2])) * ((s32) in[4]) + - ((limb) ((s32) in2[4])) * ((s32) in[2]) + - ((limb) ((s32) in2[0])) * ((s32) in[6]) + - ((limb) ((s32) in2[6])) * ((s32) in[0]); - output[7] = ((limb) ((s32) in2[3])) * ((s32) in[4]) + - ((limb) ((s32) in2[4])) * ((s32) in[3]) + - ((limb) ((s32) in2[2])) * ((s32) in[5]) + - ((limb) ((s32) in2[5])) * ((s32) in[2]) + - ((limb) ((s32) in2[1])) * ((s32) in[6]) + - ((limb) ((s32) in2[6])) * ((s32) in[1]) + - ((limb) ((s32) in2[0])) * ((s32) in[7]) + - ((limb) ((s32) in2[7])) * ((s32) in[0]); - output[8] = ((limb) ((s32) in2[4])) * ((s32) in[4]) + - 2 * (((limb) ((s32) in2[3])) * ((s32) in[5]) + - ((limb) ((s32) in2[5])) * ((s32) in[3]) + - ((limb) ((s32) in2[1])) * ((s32) in[7]) + - ((limb) ((s32) in2[7])) * ((s32) in[1])) + - ((limb) ((s32) in2[2])) * ((s32) in[6]) + - ((limb) ((s32) in2[6])) * ((s32) in[2]) + - ((limb) ((s32) in2[0])) * ((s32) in[8]) + - ((limb) ((s32) in2[8])) * ((s32) in[0]); - output[9] = ((limb) ((s32) in2[4])) * ((s32) in[5]) + - ((limb) ((s32) in2[5])) * ((s32) in[4]) + - ((limb) ((s32) in2[3])) * ((s32) in[6]) + - ((limb) ((s32) in2[6])) * ((s32) in[3]) + - ((limb) ((s32) in2[2])) * ((s32) in[7]) + - ((limb) ((s32) in2[7])) * ((s32) in[2]) + - ((limb) ((s32) in2[1])) * ((s32) in[8]) + - ((limb) ((s32) in2[8])) * ((s32) in[1]) + - ((limb) ((s32) in2[0])) * ((s32) in[9]) + - ((limb) ((s32) in2[9])) * ((s32) in[0]); - output[10] = 2 * (((limb) ((s32) in2[5])) * ((s32) in[5]) + - ((limb) ((s32) in2[3])) * ((s32) in[7]) + - ((limb) ((s32) in2[7])) * ((s32) in[3]) + - ((limb) ((s32) in2[1])) * ((s32) in[9]) + - ((limb) ((s32) in2[9])) * ((s32) in[1])) + - ((limb) ((s32) in2[4])) * ((s32) in[6]) + - ((limb) ((s32) in2[6])) * ((s32) in[4]) + - ((limb) ((s32) in2[2])) * ((s32) in[8]) + - ((limb) ((s32) in2[8])) * ((s32) in[2]); - output[11] = ((limb) ((s32) in2[5])) * ((s32) in[6]) + - ((limb) ((s32) in2[6])) * ((s32) in[5]) + - ((limb) ((s32) in2[4])) * ((s32) in[7]) + - ((limb) ((s32) in2[7])) * ((s32) in[4]) + - ((limb) ((s32) in2[3])) * ((s32) in[8]) + - ((limb) ((s32) in2[8])) * ((s32) in[3]) + - ((limb) ((s32) in2[2])) * ((s32) in[9]) + - ((limb) ((s32) in2[9])) * ((s32) in[2]); - output[12] = ((limb) ((s32) in2[6])) * ((s32) in[6]) + - 2 * (((limb) ((s32) in2[5])) * ((s32) in[7]) + - ((limb) ((s32) in2[7])) * ((s32) in[5]) + - ((limb) ((s32) in2[3])) * ((s32) in[9]) + - ((limb) ((s32) in2[9])) * ((s32) in[3])) + - ((limb) ((s32) in2[4])) * ((s32) in[8]) + - ((limb) ((s32) in2[8])) * ((s32) in[4]); - output[13] = ((limb) ((s32) in2[6])) * ((s32) in[7]) + - ((limb) ((s32) in2[7])) * ((s32) in[6]) + - ((limb) ((s32) in2[5])) * ((s32) in[8]) + - ((limb) ((s32) in2[8])) * ((s32) in[5]) + - ((limb) ((s32) in2[4])) * ((s32) in[9]) + - ((limb) ((s32) in2[9])) * ((s32) in[4]); - output[14] = 2 * (((limb) ((s32) in2[7])) * ((s32) in[7]) + - ((limb) ((s32) in2[5])) * ((s32) in[9]) + - ((limb) ((s32) in2[9])) * ((s32) in[5])) + - ((limb) ((s32) in2[6])) * ((s32) in[8]) + - ((limb) ((s32) in2[8])) * ((s32) in[6]); - output[15] = ((limb) ((s32) in2[7])) * ((s32) in[8]) + - ((limb) ((s32) in2[8])) * ((s32) in[7]) + - ((limb) ((s32) in2[6])) * ((s32) in[9]) + - ((limb) ((s32) in2[9])) * ((s32) in[6]); - output[16] = ((limb) ((s32) in2[8])) * ((s32) in[8]) + - 2 * (((limb) ((s32) in2[7])) * ((s32) in[9]) + - ((limb) ((s32) in2[9])) * ((s32) in[7])); - output[17] = ((limb) ((s32) in2[8])) * ((s32) in[9]) + - ((limb) ((s32) in2[9])) * ((s32) in[8]); - output[18] = 2 * ((limb) ((s32) in2[9])) * ((s32) in[9]); -} - -/* Reduce a long form to a short form by taking the input mod 2^255 - 19. - * - * On entry: |output[i]| < 14*2^54 - * On exit: |output[0..8]| < 280*2^54 */ -static void freduce_degree(limb *output) { - /* Each of these shifts and adds ends up multiplying the value by 19. - * - * For output[0..8], the absolute entry value is < 14*2^54 and we add, at - * most, 19*14*2^54 thus, on exit, |output[0..8]| < 280*2^54. */ - output[8] += output[18] << 4; - output[8] += output[18] << 1; - output[8] += output[18]; - output[7] += output[17] << 4; - output[7] += output[17] << 1; - output[7] += output[17]; - output[6] += output[16] << 4; - output[6] += output[16] << 1; - output[6] += output[16]; - output[5] += output[15] << 4; - output[5] += output[15] << 1; - output[5] += output[15]; - output[4] += output[14] << 4; - output[4] += output[14] << 1; - output[4] += output[14]; - output[3] += output[13] << 4; - output[3] += output[13] << 1; - output[3] += output[13]; - output[2] += output[12] << 4; - output[2] += output[12] << 1; - output[2] += output[12]; - output[1] += output[11] << 4; - output[1] += output[11] << 1; - output[1] += output[11]; - output[0] += output[10] << 4; - output[0] += output[10] << 1; - output[0] += output[10]; -} - -#if (-1 & 3) != 3 -#error "This code only works on a two's complement system" -#endif - -/* return v / 2^26, using only shifts and adds. - * - * On entry: v can take any value. */ -static inline limb -div_by_2_26(const limb v) -{ - /* High word of v; no shift needed. */ - const uint32_t highword = (uint32_t) (((uint64_t) v) >> 32); - /* Set to all 1s if v was negative; else set to 0s. */ - const int32_t sign = ((int32_t) highword) >> 31; - /* Set to 0x3ffffff if v was negative; else set to 0. */ - const int32_t roundoff = ((uint32_t) sign) >> 6; - /* Should return v / (1<<26) */ - return (v + roundoff) >> 26; -} - -/* return v / (2^25), using only shifts and adds. - * - * On entry: v can take any value. */ -static inline limb -div_by_2_25(const limb v) -{ - /* High word of v; no shift needed*/ - const uint32_t highword = (uint32_t) (((uint64_t) v) >> 32); - /* Set to all 1s if v was negative; else set to 0s. */ - const int32_t sign = ((int32_t) highword) >> 31; - /* Set to 0x1ffffff if v was negative; else set to 0. */ - const int32_t roundoff = ((uint32_t) sign) >> 7; - /* Should return v / (1<<25) */ - return (v + roundoff) >> 25; -} - -/* Reduce all coefficients of the short form input so that |x| < 2^26. - * - * On entry: |output[i]| < 280*2^54 */ -static void freduce_coefficients(limb *output) { - unsigned i; - - output[10] = 0; - - for (i = 0; i < 10; i += 2) { - limb over = div_by_2_26(output[i]); - /* The entry condition (that |output[i]| < 280*2^54) means that over is, at - * most, 280*2^28 in the first iteration of this loop. This is added to the - * next limb and we can approximate the resulting bound of that limb by - * 281*2^54. */ - output[i] -= over << 26; - output[i+1] += over; - - /* For the first iteration, |output[i+1]| < 281*2^54, thus |over| < - * 281*2^29. When this is added to the next limb, the resulting bound can - * be approximated as 281*2^54. - * - * For subsequent iterations of the loop, 281*2^54 remains a conservative - * bound and no overflow occurs. */ - over = div_by_2_25(output[i+1]); - output[i+1] -= over << 25; - output[i+2] += over; - } - /* Now |output[10]| < 281*2^29 and all other coefficients are reduced. */ - output[0] += output[10] << 4; - output[0] += output[10] << 1; - output[0] += output[10]; - - output[10] = 0; - - /* Now output[1..9] are reduced, and |output[0]| < 2^26 + 19*281*2^29 - * So |over| will be no more than 2^16. */ - { - limb over = div_by_2_26(output[0]); - output[0] -= over << 26; - output[1] += over; - } - - /* Now output[0,2..9] are reduced, and |output[1]| < 2^25 + 2^16 < 2^26. The - * bound on |output[1]| is sufficient to meet our needs. */ -} - -/* A helpful wrapper around fproduct: output = in * in2. - * - * On entry: |in[i]| < 2^27 and |in2[i]| < 2^27. - * - * output must be distinct to both inputs. The output is reduced degree - * (indeed, one need only provide storage for 10 limbs) and |output[i]| < 2^26. */ -static void -fmul(limb *output, const limb *in, const limb *in2) { - limb t[19]; - fproduct(t, in, in2); - /* |t[i]| < 14*2^54 */ - freduce_degree(t); - freduce_coefficients(t); - /* |t[i]| < 2^26 */ - memcpy(output, t, sizeof(limb) * 10); -} - -/* Square a number: output = in**2 - * - * output must be distinct from the input. The inputs are reduced coefficient - * form, the output is not. - * - * output[x] <= 14 * the largest product of the input limbs. */ -static void fsquare_inner(limb *output, const limb *in) { - output[0] = ((limb) ((s32) in[0])) * ((s32) in[0]); - output[1] = 2 * ((limb) ((s32) in[0])) * ((s32) in[1]); - output[2] = 2 * (((limb) ((s32) in[1])) * ((s32) in[1]) + - ((limb) ((s32) in[0])) * ((s32) in[2])); - output[3] = 2 * (((limb) ((s32) in[1])) * ((s32) in[2]) + - ((limb) ((s32) in[0])) * ((s32) in[3])); - output[4] = ((limb) ((s32) in[2])) * ((s32) in[2]) + - 4 * ((limb) ((s32) in[1])) * ((s32) in[3]) + - 2 * ((limb) ((s32) in[0])) * ((s32) in[4]); - output[5] = 2 * (((limb) ((s32) in[2])) * ((s32) in[3]) + - ((limb) ((s32) in[1])) * ((s32) in[4]) + - ((limb) ((s32) in[0])) * ((s32) in[5])); - output[6] = 2 * (((limb) ((s32) in[3])) * ((s32) in[3]) + - ((limb) ((s32) in[2])) * ((s32) in[4]) + - ((limb) ((s32) in[0])) * ((s32) in[6]) + - 2 * ((limb) ((s32) in[1])) * ((s32) in[5])); - output[7] = 2 * (((limb) ((s32) in[3])) * ((s32) in[4]) + - ((limb) ((s32) in[2])) * ((s32) in[5]) + - ((limb) ((s32) in[1])) * ((s32) in[6]) + - ((limb) ((s32) in[0])) * ((s32) in[7])); - output[8] = ((limb) ((s32) in[4])) * ((s32) in[4]) + - 2 * (((limb) ((s32) in[2])) * ((s32) in[6]) + - ((limb) ((s32) in[0])) * ((s32) in[8]) + - 2 * (((limb) ((s32) in[1])) * ((s32) in[7]) + - ((limb) ((s32) in[3])) * ((s32) in[5]))); - output[9] = 2 * (((limb) ((s32) in[4])) * ((s32) in[5]) + - ((limb) ((s32) in[3])) * ((s32) in[6]) + - ((limb) ((s32) in[2])) * ((s32) in[7]) + - ((limb) ((s32) in[1])) * ((s32) in[8]) + - ((limb) ((s32) in[0])) * ((s32) in[9])); - output[10] = 2 * (((limb) ((s32) in[5])) * ((s32) in[5]) + - ((limb) ((s32) in[4])) * ((s32) in[6]) + - ((limb) ((s32) in[2])) * ((s32) in[8]) + - 2 * (((limb) ((s32) in[3])) * ((s32) in[7]) + - ((limb) ((s32) in[1])) * ((s32) in[9]))); - output[11] = 2 * (((limb) ((s32) in[5])) * ((s32) in[6]) + - ((limb) ((s32) in[4])) * ((s32) in[7]) + - ((limb) ((s32) in[3])) * ((s32) in[8]) + - ((limb) ((s32) in[2])) * ((s32) in[9])); - output[12] = ((limb) ((s32) in[6])) * ((s32) in[6]) + - 2 * (((limb) ((s32) in[4])) * ((s32) in[8]) + - 2 * (((limb) ((s32) in[5])) * ((s32) in[7]) + - ((limb) ((s32) in[3])) * ((s32) in[9]))); - output[13] = 2 * (((limb) ((s32) in[6])) * ((s32) in[7]) + - ((limb) ((s32) in[5])) * ((s32) in[8]) + - ((limb) ((s32) in[4])) * ((s32) in[9])); - output[14] = 2 * (((limb) ((s32) in[7])) * ((s32) in[7]) + - ((limb) ((s32) in[6])) * ((s32) in[8]) + - 2 * ((limb) ((s32) in[5])) * ((s32) in[9])); - output[15] = 2 * (((limb) ((s32) in[7])) * ((s32) in[8]) + - ((limb) ((s32) in[6])) * ((s32) in[9])); - output[16] = ((limb) ((s32) in[8])) * ((s32) in[8]) + - 4 * ((limb) ((s32) in[7])) * ((s32) in[9]); - output[17] = 2 * ((limb) ((s32) in[8])) * ((s32) in[9]); - output[18] = 2 * ((limb) ((s32) in[9])) * ((s32) in[9]); -} - -/* fsquare sets output = in^2. - * - * On entry: The |in| argument is in reduced coefficients form and |in[i]| < - * 2^27. - * - * On exit: The |output| argument is in reduced coefficients form (indeed, one - * need only provide storage for 10 limbs) and |out[i]| < 2^26. */ -static void -fsquare(limb *output, const limb *in) { - limb t[19]; - fsquare_inner(t, in); - /* |t[i]| < 14*2^54 because the largest product of two limbs will be < - * 2^(27+27) and fsquare_inner adds together, at most, 14 of those - * products. */ - freduce_degree(t); - freduce_coefficients(t); - /* |t[i]| < 2^26 */ - memcpy(output, t, sizeof(limb) * 10); -} - -/* Take a little-endian, 32-byte number and expand it into polynomial form */ -static void -fexpand(limb *output, const u8 *input) { -#define F(n,start,shift,mask) \ - output[n] = ((((limb) input[start + 0]) | \ - ((limb) input[start + 1]) << 8 | \ - ((limb) input[start + 2]) << 16 | \ - ((limb) input[start + 3]) << 24) >> shift) & mask; - F(0, 0, 0, 0x3ffffff); - F(1, 3, 2, 0x1ffffff); - F(2, 6, 3, 0x3ffffff); - F(3, 9, 5, 0x1ffffff); - F(4, 12, 6, 0x3ffffff); - F(5, 16, 0, 0x1ffffff); - F(6, 19, 1, 0x3ffffff); - F(7, 22, 3, 0x1ffffff); - F(8, 25, 4, 0x3ffffff); - F(9, 28, 6, 0x1ffffff); -#undef F -} - -#if (-32 >> 1) != -16 -#error "This code only works when >> does sign-extension on negative numbers" -#endif - -/* s32_eq returns 0xffffffff iff a == b and zero otherwise. */ -static s32 s32_eq(s32 a, s32 b) { - a = ~(a ^ b); - a &= a << 16; - a &= a << 8; - a &= a << 4; - a &= a << 2; - a &= a << 1; - return a >> 31; -} - -/* s32_gte returns 0xffffffff if a >= b and zero otherwise, where a and b are - * both non-negative. */ -static s32 s32_gte(s32 a, s32 b) { - a -= b; - /* a >= 0 iff a >= b. */ - return ~(a >> 31); -} - -/* Take a fully reduced polynomial form number and contract it into a - * little-endian, 32-byte array. - * - * On entry: |input_limbs[i]| < 2^26 */ -static void -fcontract(u8 *output, limb *input_limbs) { - int i; - int j; - s32 input[10]; - s32 mask; - - /* |input_limbs[i]| < 2^26, so it's valid to convert to an s32. */ - for (i = 0; i < 10; i++) { - input[i] = input_limbs[i]; - } - - for (j = 0; j < 2; ++j) { - for (i = 0; i < 9; ++i) { - if ((i & 1) == 1) { - /* This calculation is a time-invariant way to make input[i] - * non-negative by borrowing from the next-larger limb. */ - const s32 mask = input[i] >> 31; - const s32 carry = -((input[i] & mask) >> 25); - input[i] = input[i] + (carry << 25); - input[i+1] = input[i+1] - carry; - } else { - const s32 mask = input[i] >> 31; - const s32 carry = -((input[i] & mask) >> 26); - input[i] = input[i] + (carry << 26); - input[i+1] = input[i+1] - carry; - } - } - - /* There's no greater limb for input[9] to borrow from, but we can multiply - * by 19 and borrow from input[0], which is valid mod 2^255-19. */ - { - const s32 mask = input[9] >> 31; - const s32 carry = -((input[9] & mask) >> 25); - input[9] = input[9] + (carry << 25); - input[0] = input[0] - (carry * 19); - } - - /* After the first iteration, input[1..9] are non-negative and fit within - * 25 or 26 bits, depending on position. However, input[0] may be - * negative. */ - } - - /* The first borrow-propagation pass above ended with every limb - except (possibly) input[0] non-negative. - - If input[0] was negative after the first pass, then it was because of a - carry from input[9]. On entry, input[9] < 2^26 so the carry was, at most, - one, since (2**26-1) >> 25 = 1. Thus input[0] >= -19. - - In the second pass, each limb is decreased by at most one. Thus the second - borrow-propagation pass could only have wrapped around to decrease - input[0] again if the first pass left input[0] negative *and* input[1] - through input[9] were all zero. In that case, input[1] is now 2^25 - 1, - and this last borrow-propagation step will leave input[1] non-negative. */ - { - const s32 mask = input[0] >> 31; - const s32 carry = -((input[0] & mask) >> 26); - input[0] = input[0] + (carry << 26); - input[1] = input[1] - carry; - } - - /* All input[i] are now non-negative. However, there might be values between - * 2^25 and 2^26 in a limb which is, nominally, 25 bits wide. */ - for (j = 0; j < 2; j++) { - for (i = 0; i < 9; i++) { - if ((i & 1) == 1) { - const s32 carry = input[i] >> 25; - input[i] &= 0x1ffffff; - input[i+1] += carry; - } else { - const s32 carry = input[i] >> 26; - input[i] &= 0x3ffffff; - input[i+1] += carry; - } - } - - { - const s32 carry = input[9] >> 25; - input[9] &= 0x1ffffff; - input[0] += 19*carry; - } - } - - /* If the first carry-chain pass, just above, ended up with a carry from - * input[9], and that caused input[0] to be out-of-bounds, then input[0] was - * < 2^26 + 2*19, because the carry was, at most, two. - * - * If the second pass carried from input[9] again then input[0] is < 2*19 and - * the input[9] -> input[0] carry didn't push input[0] out of bounds. */ - - /* It still remains the case that input might be between 2^255-19 and 2^255. - * In this case, input[1..9] must take their maximum value and input[0] must - * be >= (2^255-19) & 0x3ffffff, which is 0x3ffffed. */ - mask = s32_gte(input[0], 0x3ffffed); - for (i = 1; i < 10; i++) { - if ((i & 1) == 1) { - mask &= s32_eq(input[i], 0x1ffffff); - } else { - mask &= s32_eq(input[i], 0x3ffffff); - } - } - - /* mask is either 0xffffffff (if input >= 2^255-19) and zero otherwise. Thus - * this conditionally subtracts 2^255-19. */ - input[0] -= mask & 0x3ffffed; - - for (i = 1; i < 10; i++) { - if ((i & 1) == 1) { - input[i] -= mask & 0x1ffffff; - } else { - input[i] -= mask & 0x3ffffff; - } - } - - input[1] <<= 2; - input[2] <<= 3; - input[3] <<= 5; - input[4] <<= 6; - input[6] <<= 1; - input[7] <<= 3; - input[8] <<= 4; - input[9] <<= 6; -#define F(i, s) \ - output[s+0] |= input[i] & 0xff; \ - output[s+1] = (input[i] >> 8) & 0xff; \ - output[s+2] = (input[i] >> 16) & 0xff; \ - output[s+3] = (input[i] >> 24) & 0xff; - output[0] = 0; - output[16] = 0; - F(0,0); - F(1,3); - F(2,6); - F(3,9); - F(4,12); - F(5,16); - F(6,19); - F(7,22); - F(8,25); - F(9,28); -#undef F -} - -/* Input: Q, Q', Q-Q' - * Output: 2Q, Q+Q' - * - * x2 z3: long form - * x3 z3: long form - * x z: short form, destroyed - * xprime zprime: short form, destroyed - * qmqp: short form, preserved - * - * On entry and exit, the absolute value of the limbs of all inputs and outputs - * are < 2^26. */ -static void fmonty(limb *x2, limb *z2, /* output 2Q */ - limb *x3, limb *z3, /* output Q + Q' */ - limb *x, limb *z, /* input Q */ - limb *xprime, limb *zprime, /* input Q' */ - const limb *qmqp /* input Q - Q' */) { - limb origx[10], origxprime[10], zzz[19], xx[19], zz[19], xxprime[19], - zzprime[19], zzzprime[19], xxxprime[19]; - - memcpy(origx, x, 10 * sizeof(limb)); - fsum(x, z); - /* |x[i]| < 2^27 */ - fdifference(z, origx); /* does x - z */ - /* |z[i]| < 2^27 */ - - memcpy(origxprime, xprime, sizeof(limb) * 10); - fsum(xprime, zprime); - /* |xprime[i]| < 2^27 */ - fdifference(zprime, origxprime); - /* |zprime[i]| < 2^27 */ - fproduct(xxprime, xprime, z); - /* |xxprime[i]| < 14*2^54: the largest product of two limbs will be < - * 2^(27+27) and fproduct adds together, at most, 14 of those products. - * (Approximating that to 2^58 doesn't work out.) */ - fproduct(zzprime, x, zprime); - /* |zzprime[i]| < 14*2^54 */ - freduce_degree(xxprime); - freduce_coefficients(xxprime); - /* |xxprime[i]| < 2^26 */ - freduce_degree(zzprime); - freduce_coefficients(zzprime); - /* |zzprime[i]| < 2^26 */ - memcpy(origxprime, xxprime, sizeof(limb) * 10); - fsum(xxprime, zzprime); - /* |xxprime[i]| < 2^27 */ - fdifference(zzprime, origxprime); - /* |zzprime[i]| < 2^27 */ - fsquare(xxxprime, xxprime); - /* |xxxprime[i]| < 2^26 */ - fsquare(zzzprime, zzprime); - /* |zzzprime[i]| < 2^26 */ - fproduct(zzprime, zzzprime, qmqp); - /* |zzprime[i]| < 14*2^52 */ - freduce_degree(zzprime); - freduce_coefficients(zzprime); - /* |zzprime[i]| < 2^26 */ - memcpy(x3, xxxprime, sizeof(limb) * 10); - memcpy(z3, zzprime, sizeof(limb) * 10); - - fsquare(xx, x); - /* |xx[i]| < 2^26 */ - fsquare(zz, z); - /* |zz[i]| < 2^26 */ - fproduct(x2, xx, zz); - /* |x2[i]| < 14*2^52 */ - freduce_degree(x2); - freduce_coefficients(x2); - /* |x2[i]| < 2^26 */ - fdifference(zz, xx); /* does zz = xx - zz */ - /* |zz[i]| < 2^27 */ - memset(zzz + 10, 0, sizeof(limb) * 9); - fscalar_product(zzz, zz, 121665); - /* |zzz[i]| < 2^(27+17) */ - /* No need to call freduce_degree here: - fscalar_product doesn't increase the degree of its input. */ - freduce_coefficients(zzz); - /* |zzz[i]| < 2^26 */ - fsum(zzz, xx); - /* |zzz[i]| < 2^27 */ - fproduct(z2, zz, zzz); - /* |z2[i]| < 14*2^(26+27) */ - freduce_degree(z2); - freduce_coefficients(z2); - /* |z2|i| < 2^26 */ -} - -/* Conditionally swap two reduced-form limb arrays if 'iswap' is 1, but leave - * them unchanged if 'iswap' is 0. Runs in data-invariant time to avoid - * side-channel attacks. - * - * NOTE that this function requires that 'iswap' be 1 or 0; other values give - * wrong results. Also, the two limb arrays must be in reduced-coefficient, - * reduced-degree form: the values in a[10..19] or b[10..19] aren't swapped, - * and all all values in a[0..9],b[0..9] must have magnitude less than - * INT32_MAX. */ -static void -swap_conditional(limb a[19], limb b[19], limb iswap) { - unsigned i; - const s32 swap = (s32) -iswap; - - for (i = 0; i < 10; ++i) { - const s32 x = swap & ( ((s32)a[i]) ^ ((s32)b[i]) ); - a[i] = ((s32)a[i]) ^ x; - b[i] = ((s32)b[i]) ^ x; - } -} - -/* Calculates nQ where Q is the x-coordinate of a point on the curve - * - * resultx/resultz: the x coordinate of the resulting curve point (short form) - * n: a little endian, 32-byte number - * q: a point of the curve (short form) */ -static void -cmult(limb *resultx, limb *resultz, const u8 *n, const limb *q) { - limb a[19] = {0}, b[19] = {1}, c[19] = {1}, d[19] = {0}; - limb *nqpqx = a, *nqpqz = b, *nqx = c, *nqz = d, *t; - limb e[19] = {0}, f[19] = {1}, g[19] = {0}, h[19] = {1}; - limb *nqpqx2 = e, *nqpqz2 = f, *nqx2 = g, *nqz2 = h; - - unsigned i, j; - - memcpy(nqpqx, q, sizeof(limb) * 10); - - for (i = 0; i < 32; ++i) { - u8 byte = n[31 - i]; - for (j = 0; j < 8; ++j) { - const limb bit = byte >> 7; - - swap_conditional(nqx, nqpqx, bit); - swap_conditional(nqz, nqpqz, bit); - fmonty(nqx2, nqz2, - nqpqx2, nqpqz2, - nqx, nqz, - nqpqx, nqpqz, - q); - swap_conditional(nqx2, nqpqx2, bit); - swap_conditional(nqz2, nqpqz2, bit); - - t = nqx; - nqx = nqx2; - nqx2 = t; - t = nqz; - nqz = nqz2; - nqz2 = t; - t = nqpqx; - nqpqx = nqpqx2; - nqpqx2 = t; - t = nqpqz; - nqpqz = nqpqz2; - nqpqz2 = t; - - byte <<= 1; - } - } - - memcpy(resultx, nqx, sizeof(limb) * 10); - memcpy(resultz, nqz, sizeof(limb) * 10); -} - -/* ----------------------------------------------------------------------------- - * Shamelessly copied from djb's code - * ----------------------------------------------------------------------------- */ -static void -crecip(limb *out, const limb *z) { - limb z2[10]; - limb z9[10]; - limb z11[10]; - limb z2_5_0[10]; - limb z2_10_0[10]; - limb z2_20_0[10]; - limb z2_50_0[10]; - limb z2_100_0[10]; - limb t0[10]; - limb t1[10]; - int i; - - /* 2 */ fsquare(z2,z); - /* 4 */ fsquare(t1,z2); - /* 8 */ fsquare(t0,t1); - /* 9 */ fmul(z9,t0,z); - /* 11 */ fmul(z11,z9,z2); - /* 22 */ fsquare(t0,z11); - /* 2^5 - 2^0 = 31 */ fmul(z2_5_0,t0,z9); - - /* 2^6 - 2^1 */ fsquare(t0,z2_5_0); - /* 2^7 - 2^2 */ fsquare(t1,t0); - /* 2^8 - 2^3 */ fsquare(t0,t1); - /* 2^9 - 2^4 */ fsquare(t1,t0); - /* 2^10 - 2^5 */ fsquare(t0,t1); - /* 2^10 - 2^0 */ fmul(z2_10_0,t0,z2_5_0); - - /* 2^11 - 2^1 */ fsquare(t0,z2_10_0); - /* 2^12 - 2^2 */ fsquare(t1,t0); - /* 2^20 - 2^10 */ for (i = 2;i < 10;i += 2) { fsquare(t0,t1); fsquare(t1,t0); } - /* 2^20 - 2^0 */ fmul(z2_20_0,t1,z2_10_0); - - /* 2^21 - 2^1 */ fsquare(t0,z2_20_0); - /* 2^22 - 2^2 */ fsquare(t1,t0); - /* 2^40 - 2^20 */ for (i = 2;i < 20;i += 2) { fsquare(t0,t1); fsquare(t1,t0); } - /* 2^40 - 2^0 */ fmul(t0,t1,z2_20_0); - - /* 2^41 - 2^1 */ fsquare(t1,t0); - /* 2^42 - 2^2 */ fsquare(t0,t1); - /* 2^50 - 2^10 */ for (i = 2;i < 10;i += 2) { fsquare(t1,t0); fsquare(t0,t1); } - /* 2^50 - 2^0 */ fmul(z2_50_0,t0,z2_10_0); - - /* 2^51 - 2^1 */ fsquare(t0,z2_50_0); - /* 2^52 - 2^2 */ fsquare(t1,t0); - /* 2^100 - 2^50 */ for (i = 2;i < 50;i += 2) { fsquare(t0,t1); fsquare(t1,t0); } - /* 2^100 - 2^0 */ fmul(z2_100_0,t1,z2_50_0); - - /* 2^101 - 2^1 */ fsquare(t1,z2_100_0); - /* 2^102 - 2^2 */ fsquare(t0,t1); - /* 2^200 - 2^100 */ for (i = 2;i < 100;i += 2) { fsquare(t1,t0); fsquare(t0,t1); } - /* 2^200 - 2^0 */ fmul(t1,t0,z2_100_0); - - /* 2^201 - 2^1 */ fsquare(t0,t1); - /* 2^202 - 2^2 */ fsquare(t1,t0); - /* 2^250 - 2^50 */ for (i = 2;i < 50;i += 2) { fsquare(t0,t1); fsquare(t1,t0); } - /* 2^250 - 2^0 */ fmul(t0,t1,z2_50_0); - - /* 2^251 - 2^1 */ fsquare(t1,t0); - /* 2^252 - 2^2 */ fsquare(t0,t1); - /* 2^253 - 2^3 */ fsquare(t1,t0); - /* 2^254 - 2^4 */ fsquare(t0,t1); - /* 2^255 - 2^5 */ fsquare(t1,t0); - /* 2^255 - 21 */ fmul(out,t1,z11); -} - -int -curve25519_donna(u8 *mypublic, const u8 *secret, const u8 *basepoint) { - limb bp[10], x[10], z[11], zmone[10]; - uint8_t e[32]; - int i; - - for (i = 0; i < 32; ++i) e[i] = secret[i]; - e[0] &= 248; - e[31] &= 127; - e[31] |= 64; - - fexpand(bp, basepoint); - cmult(x, z, e, bp); - crecip(zmone, z); - fmul(z, x, zmone); - fcontract(mypublic, z); - return 0; -} diff --git a/curve25519.c b/curve25519.c new file mode 100644 index 0000000..4b83776 --- /dev/null +++ b/curve25519.c @@ -0,0 +1,502 @@ +/* + * Dropbear - a SSH2 server + * + * Copyright (c) 2002,2003 Matt Johnston + * All rights reserved. + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. */ + +#include "includes.h" +#include "dbrandom.h" +#include "curve25519.h" + +#if DROPBEAR_CURVE25519 || DROPBEAR_ED25519 + +/* Modified TweetNaCl version 20140427, a self-contained public-domain C library. + * https://tweetnacl.cr.yp.to/ */ + +#define FOR(i,n) for (i = 0;i < n;++i) +#define sv static void + +typedef unsigned char u8; +typedef unsigned long u32; +typedef unsigned long long u64; +typedef long long i64; +typedef i64 gf[16]; + +#if DROPBEAR_CURVE25519 +static const gf + _121665 = {0xDB41,1}; +#endif /* DROPBEAR_CURVE25519 */ +#if DROPBEAR_ED25519 +static const gf + gf0, + gf1 = {1}, + D2 = {0xf159, 0x26b2, 0x9b94, 0xebd6, 0xb156, 0x8283, 0x149a, 0x00e0, 0xd130, 0xeef3, 0x80f2, 0x198e, 0xfce7, 0x56df, 0xd9dc, 0x2406}, + X = {0xd51a, 0x8f25, 0x2d60, 0xc956, 0xa7b2, 0x9525, 0xc760, 0x692c, 0xdc5c, 0xfdd6, 0xe231, 0xc0a4, 0x53fe, 0xcd6e, 0x36d3, 0x2169}, + Y = {0x6658, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666}; +#if DROPBEAR_SIGNKEY_VERIFY +static const gf + D = {0x78a3, 0x1359, 0x4dca, 0x75eb, 0xd8ab, 0x4141, 0x0a4d, 0x0070, 0xe898, 0x7779, 0x4079, 0x8cc7, 0xfe73, 0x2b6f, 0x6cee, 0x5203}, + I = {0xa0b0, 0x4a0e, 0x1b27, 0xc4ee, 0xe478, 0xad2f, 0x1806, 0x2f43, 0xd7a7, 0x3dfb, 0x0099, 0x2b4d, 0xdf0b, 0x4fc1, 0x2480, 0x2b83}; +#endif /* DROPBEAR_SIGNKEY_VERIFY */ +#endif /* DROPBEAR_ED25519 */ + +#if DROPBEAR_ED25519 +#if DROPBEAR_SIGNKEY_VERIFY +static int vn(const u8 *x,const u8 *y,u32 n) +{ + u32 i,d = 0; + FOR(i,n) d |= x[i]^y[i]; + return (1 & ((d - 1) >> 8)) - 1; +} + +static int crypto_verify_32(const u8 *x,const u8 *y) +{ + return vn(x,y,32); +} +#endif /* DROPBEAR_SIGNKEY_VERIFY */ + +sv set25519(gf r, const gf a) +{ + int i; + FOR(i,16) r[i]=a[i]; +} +#endif /* DROPBEAR_ED25519 */ + +sv car25519(gf o) +{ + int i; + i64 c; + FOR(i,16) { + o[i]+=(1LL<<16); + c=o[i]>>16; + o[(i+1)*(i<15)]+=c-1+37*(c-1)*(i==15); + o[i]-=c<<16; + } +} + +sv sel25519(gf p,gf q,int b) +{ + i64 t,i,c=~(b-1); + FOR(i,16) { + t= c&(p[i]^q[i]); + p[i]^=t; + q[i]^=t; + } +} + +sv pack25519(u8 *o,const gf n) +{ + int i,j,b; + gf m,t; + FOR(i,16) t[i]=n[i]; + car25519(t); + car25519(t); + car25519(t); + FOR(j,2) { + m[0]=t[0]-0xffed; + for(i=1;i<15;i++) { + m[i]=t[i]-0xffff-((m[i-1]>>16)&1); + m[i-1]&=0xffff; + } + m[15]=t[15]-0x7fff-((m[14]>>16)&1); + b=(m[15]>>16)&1; + m[14]&=0xffff; + sel25519(t,m,1-b); + } + FOR(i,16) { + o[2*i]=t[i]&0xff; + o[2*i+1]=t[i]>>8; + } +} + +#if DROPBEAR_ED25519 +#if DROPBEAR_SIGNKEY_VERIFY +static int neq25519(const gf a, const gf b) +{ + u8 c[32],d[32]; + pack25519(c,a); + pack25519(d,b); + return crypto_verify_32(c,d); +} +#endif /* DROPBEAR_SIGNKEY_VERIFY */ + +static u8 par25519(const gf a) +{ + u8 d[32]; + pack25519(d,a); + return d[0]&1; +} +#endif /* DROPBEAR_ED25519 */ + +sv unpack25519(gf o, const u8 *n) +{ + int i; + FOR(i,16) o[i]=n[2*i]+((i64)n[2*i+1]<<8); + o[15]&=0x7fff; +} + +sv A(gf o,const gf a,const gf b) +{ + int i; + FOR(i,16) o[i]=a[i]+b[i]; +} + +sv Z(gf o,const gf a,const gf b) +{ + int i; + FOR(i,16) o[i]=a[i]-b[i]; +} + +sv M(gf o,const gf a,const gf b) +{ + i64 i,j,t[31]; + FOR(i,31) t[i]=0; + FOR(i,16) FOR(j,16) t[i+j]+=a[i]*b[j]; + FOR(i,15) t[i]+=38*t[i+16]; + FOR(i,16) o[i]=t[i]; + car25519(o); + car25519(o); +} + +sv S(gf o,const gf a) +{ + M(o,a,a); +} + +sv inv25519(gf o,const gf i) +{ + gf c; + int a; + FOR(a,16) c[a]=i[a]; + for(a=253;a>=0;a--) { + S(c,c); + if(a!=2&&a!=4) M(c,c,i); + } + FOR(a,16) o[a]=c[a]; +} + +#if DROPBEAR_ED25519 && DROPBEAR_SIGNKEY_VERIFY +sv pow2523(gf o,const gf i) +{ + gf c; + int a; + FOR(a,16) c[a]=i[a]; + for(a=250;a>=0;a--) { + S(c,c); + if(a!=1) M(c,c,i); + } + FOR(a,16) o[a]=c[a]; +} +#endif /* DROPBEAR_ED25519 && DROPBEAR_SIGNKEY_VERIFY */ + +#if DROPBEAR_CURVE25519 +int dropbear_curve25519_scalarmult(u8 *q,const u8 *n,const u8 *p) +{ + u8 z[32]; + i64 x[80],r,i; + gf a,b,c,d,e,f; + FOR(i,31) z[i]=n[i]; + z[31]=(n[31]&127)|64; + z[0]&=248; + unpack25519(x,p); + FOR(i,16) { + b[i]=x[i]; + d[i]=a[i]=c[i]=0; + } + a[0]=d[0]=1; + for(i=254;i>=0;--i) { + r=(z[i>>3]>>(i&7))&1; + sel25519(a,b,r); + sel25519(c,d,r); + A(e,a,c); + Z(a,a,c); + A(c,b,d); + Z(b,b,d); + S(d,e); + S(f,a); + M(a,c,a); + M(c,b,e); + A(e,a,c); + Z(a,a,c); + S(b,a); + Z(c,d,f); + M(a,c,_121665); + A(a,a,d); + M(c,c,a); + M(a,d,f); + M(d,b,x); + S(b,e); + sel25519(a,b,r); + sel25519(c,d,r); + } + FOR(i,16) { + x[i+16]=a[i]; + x[i+32]=c[i]; + x[i+48]=b[i]; + x[i+64]=d[i]; + } + inv25519(x+32,x+32); + M(x+16,x+16,x+32); + pack25519(q,x+16); + return 0; +} +#endif /* DROPBEAR_CURVE25519 */ + +#if DROPBEAR_ED25519 +static int crypto_hash(u8 *out,const u8 *m,u64 n) +{ + hash_state hs; + + sha512_init(&hs); + sha512_process(&hs, m, n); + return sha512_done(&hs, out); +} + +sv add(gf p[4],gf q[4]) +{ + gf a,b,c,d,t,e,f,g,h; + + Z(a, p[1], p[0]); + Z(t, q[1], q[0]); + M(a, a, t); + A(b, p[0], p[1]); + A(t, q[0], q[1]); + M(b, b, t); + M(c, p[3], q[3]); + M(c, c, D2); + M(d, p[2], q[2]); + A(d, d, d); + Z(e, b, a); + Z(f, d, c); + A(g, d, c); + A(h, b, a); + + M(p[0], e, f); + M(p[1], h, g); + M(p[2], g, f); + M(p[3], e, h); +} + +sv cswap(gf p[4],gf q[4],u8 b) +{ + int i; + FOR(i,4) + sel25519(p[i],q[i],b); +} + +sv pack(u8 *r,gf p[4]) +{ + gf tx, ty, zi; + inv25519(zi, p[2]); + M(tx, p[0], zi); + M(ty, p[1], zi); + pack25519(r, ty); + r[31] ^= par25519(tx) << 7; +} + +sv scalarmult(gf p[4],gf q[4],const u8 *s) +{ + int i; + set25519(p[0],gf0); + set25519(p[1],gf1); + set25519(p[2],gf1); + set25519(p[3],gf0); + for (i = 255;i >= 0;--i) { + u8 b = (s[i/8]>>(i&7))&1; + cswap(p,q,b); + add(q,p); + add(p,p); + cswap(p,q,b); + } +} + +sv scalarbase(gf p[4],const u8 *s) +{ + gf q[4]; + set25519(q[0],X); + set25519(q[1],Y); + set25519(q[2],gf1); + M(q[3],X,Y); + scalarmult(p,q,s); +} + +int dropbear_ed25519_make_key(u8 *pk,u8 *sk) +{ + u8 d[64]; + gf p[4]; + + genrandom(sk, 32); + + crypto_hash(d, sk, 32); + d[0] &= 248; + d[31] &= 127; + d[31] |= 64; + + scalarbase(p,d); + pack(pk,p); + + return 0; +} + +static const u64 L[32] = {0xed, 0xd3, 0xf5, 0x5c, 0x1a, 0x63, 0x12, 0x58, 0xd6, 0x9c, 0xf7, 0xa2, 0xde, 0xf9, 0xde, 0x14, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0x10}; + +sv modL(u8 *r,i64 x[64]) +{ + i64 carry,i,j; + for (i = 63;i >= 32;--i) { + carry = 0; + for (j = i - 32;j < i - 12;++j) { + x[j] += carry - 16 * x[i] * L[j - (i - 32)]; + carry = (x[j] + 128) >> 8; + x[j] -= carry << 8; + } + x[j] += carry; + x[i] = 0; + } + carry = 0; + FOR(j,32) { + x[j] += carry - (x[31] >> 4) * L[j]; + carry = x[j] >> 8; + x[j] &= 255; + } + FOR(j,32) x[j] -= carry * L[j]; + FOR(i,32) { + x[i+1] += x[i] >> 8; + r[i] = x[i] & 255; + } +} + +sv reduce(u8 *r) +{ + i64 x[64],i; + FOR(i,64) x[i] = (u64) r[i]; + FOR(i,64) r[i] = 0; + modL(r,x); +} + +int dropbear_ed25519_sign(const u8 *m,u32 mlen,u8 *s,u32 *slen,const u8 *sk, const u8 *pk) +{ + hash_state hs; + u8 d[64],h[64],r[64]; + i64 x[64]; + gf p[4]; + u32 i,j; + + crypto_hash(d, sk, 32); + d[0] &= 248; + d[31] &= 127; + d[31] |= 64; + + *slen = 64; + + sha512_init(&hs); + sha512_process(&hs,d + 32,32); + sha512_process(&hs,m,mlen); + sha512_done(&hs,r); + reduce(r); + scalarbase(p,r); + pack(s,p); + + sha512_init(&hs); + sha512_process(&hs,s,32); + sha512_process(&hs,pk,32); + sha512_process(&hs,m,mlen); + sha512_done(&hs,h); + reduce(h); + + FOR(i,64) x[i] = 0; + FOR(i,32) x[i] = (u64) r[i]; + FOR(i,32) FOR(j,32) x[i+j] += h[i] * (u64) d[j]; + modL(s + 32,x); + + return 0; +} + +#if DROPBEAR_SIGNKEY_VERIFY +static int unpackneg(gf r[4],const u8 p[32]) +{ + gf t, chk, num, den, den2, den4, den6; + set25519(r[2],gf1); + unpack25519(r[1],p); + S(num,r[1]); + M(den,num,D); + Z(num,num,r[2]); + A(den,r[2],den); + + S(den2,den); + S(den4,den2); + M(den6,den4,den2); + M(t,den6,num); + M(t,t,den); + + pow2523(t,t); + M(t,t,num); + M(t,t,den); + M(t,t,den); + M(r[0],t,den); + + S(chk,r[0]); + M(chk,chk,den); + if (neq25519(chk, num)) M(r[0],r[0],I); + + S(chk,r[0]); + M(chk,chk,den); + if (neq25519(chk, num)) return -1; + + if (par25519(r[0]) == (p[31]>>7)) Z(r[0],gf0,r[0]); + + M(r[3],r[0],r[1]); + return 0; +} + +int dropbear_ed25519_verify(const u8 *m,u32 mlen,const u8 *s,u32 slen,const u8 *pk) +{ + hash_state hs; + u8 t[32],h[64]; + gf p[4],q[4]; + + if (slen < 64) return -1; + + if (unpackneg(q,pk)) return -1; + + sha512_init(&hs); + sha512_process(&hs,s,32); + sha512_process(&hs,pk,32); + sha512_process(&hs,m,mlen); + sha512_done(&hs,h); + + reduce(h); + scalarmult(p,q,h); + + scalarbase(q,s + 32); + add(p,q); + pack(t,p); + + if (crypto_verify_32(s, t)) + return -1; + + return 0; +} +#endif /* DROPBEAR_SIGNKEY_VERIFY */ + +#endif /* DROPBEAR_ED25519 */ + +#endif /* DROPBEAR_CURVE25519 || DROPBEAR_ED25519 */ diff --git a/curve25519.h b/curve25519.h new file mode 100644 index 0000000..7f75aed --- /dev/null +++ b/curve25519.h @@ -0,0 +1,37 @@ +/* + * Dropbear - a SSH2 server + * + * Copyright (c) 2002,2003 Matt Johnston + * All rights reserved. + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. */ + +#ifndef DROPBEAR_CURVE25519_H +#define DROPBEAR_CURVE25519_H + +int dropbear_curve25519_scalarmult(unsigned char *q, const unsigned char *n, const unsigned char *p); +int dropbear_ed25519_make_key(unsigned char *pk, unsigned char *sk); +int dropbear_ed25519_sign(const unsigned char *m, unsigned long mlen, + unsigned char *s, unsigned long *slen, + const unsigned char *sk, const unsigned char *pk); +int dropbear_ed25519_verify(const unsigned char *m, unsigned long mlen, + const unsigned char *s, unsigned long slen, + const unsigned char *pk); + +#endif /* DROPBEAR_CURVE25519_H */ diff --git a/default_options.h b/default_options.h index 9000fcc..5b232dd 100644 --- a/default_options.h +++ b/default_options.h @@ -22,6 +22,7 @@ IMPORTANT: Some options will require "make clean" after changes */ #define DSS_PRIV_FILENAME "/etc/dropbear/dropbear_dss_host_key" #define RSA_PRIV_FILENAME "/etc/dropbear/dropbear_rsa_host_key" #define ECDSA_PRIV_FILENAME "/etc/dropbear/dropbear_ecdsa_host_key" +#define ED25519_PRIV_FILENAME "/etc/dropbear/dropbear_ed25519_host_key" /* Set NON_INETD_MODE if you require daemon functionality (ie Dropbear listens * on chosen ports and keeps accepting connections. This is the default. @@ -116,11 +117,15 @@ IMPORTANT: Some options will require "make clean" after changes */ * code (either ECDSA or ECDH) increases binary size - around 30kB * on x86-64 */ #define DROPBEAR_ECDSA 1 +/* Ed25519 is faster than ECDSA. Compiling in Ed25519 code increases + binary size - around 7,5kB on x86-64 */ +#define DROPBEAR_ED25519 1 /* RSA must be >=1024 */ #define DROPBEAR_DEFAULT_RSA_SIZE 2048 /* DSS is always 1024 */ /* ECDSA defaults to largest size configured, usually 521 */ +/* Ed25519 is always 256 */ /* Add runtime flag "-R" to generate hostkeys as-needed when the first connection using that key type occurs. @@ -143,7 +148,7 @@ IMPORTANT: Some options will require "make clean" after changes */ * group14 is supported by most implementations. * group16 provides a greater strength level but is slower and increases binary size * curve25519 and ecdh algorithms are faster than non-elliptic curve methods - * curve25519 increases binary size by ~8kB on x86-64 + * curve25519 increases binary size by ~2,5kB on x86-64 * including either ECDH or ECDSA increases binary size by ~30kB on x86-64 * Small systems should generally include either curve25519 or ecdh for performance. @@ -107,7 +107,7 @@ Print the version Authorized Keys ~/.ssh/authorized_keys can be set up to allow remote login with a RSA, -ECDSA, or DSS +ECDSA, Ed25519 or DSS key. Each line is of the form .TP [restrictions] ssh-rsa AAAAB3NzaC1yc2EAAAABIwAAAIgAsp... [comment] @@ -146,8 +146,8 @@ key authentication. Host Key Files Host key files are read at startup from a standard location, by default -/etc/dropbear/dropbear_dss_host_key, /etc/dropbear/dropbear_rsa_host_key, and -/etc/dropbear/dropbear_ecdsa_host_key +/etc/dropbear/dropbear_dss_host_key, /etc/dropbear/dropbear_rsa_host_key, +/etc/dropbear/dropbear_ecdsa_host_key and /etc/dropbear/dropbear_ed25519_host_key If the -r command line option is specified the default files are not loaded. Host key files are of the form generated by dropbearkey. diff --git a/dropbearkey.c b/dropbearkey.c index dd0e697..f881855 100644 --- a/dropbearkey.c +++ b/dropbearkey.c @@ -43,6 +43,10 @@ * mp_int y * mp_int x * + * Ed25519: + * string "ssh-ed25519" + * string k (32 bytes) + A (32 bytes) + * */ #include "includes.h" #include "signkey.h" @@ -51,6 +55,7 @@ #include "genrsa.h" #include "gendss.h" +#include "gened25519.h" #include "ecdsa.h" #include "crypto_desc.h" #include "dbrandom.h" @@ -76,6 +81,9 @@ static void printhelp(char * progname) { #if DROPBEAR_ECDSA " ecdsa\n" #endif +#if DROPBEAR_ED25519 + " ed25519\n" +#endif "-f filename Use filename for the secret key.\n" " ~/.ssh/id_dropbear is recommended for client keys.\n" "-s bits Key size in bits, should be a multiple of 8 (optional)\n" @@ -95,6 +103,9 @@ static void printhelp(char * progname) { #endif "\n" #endif +#if DROPBEAR_ED25519 + " Ed25519 has a fixed size of 256 bits\n" +#endif "-y Just print the publickey and fingerprint for the\n private key in <filename>.\n" #if DEBUG_TRACE "-v verbose\n" @@ -106,6 +117,14 @@ static void printhelp(char * progname) { static void check_signkey_bits(enum signkey_type type, int bits) { switch (type) { +#if DROPBEAR_ED25519 + case DROPBEAR_SIGNKEY_ED25519: + if (bits != 256) { + dropbear_exit("Ed25519 keys have a fixed size of 256 bits\n"); + exit(EXIT_FAILURE); + } + break; +#endif #if DROPBEAR_RSA case DROPBEAR_SIGNKEY_RSA: if (bits < 512 || bits > 4096 || (bits % 8 != 0)) { @@ -224,6 +243,12 @@ int main(int argc, char ** argv) { keytype = DROPBEAR_SIGNKEY_ECDSA_KEYGEN; } #endif +#if DROPBEAR_ED25519 + if (strcmp(typetext, "ed25519") == 0) + { + keytype = DROPBEAR_SIGNKEY_ED25519; + } +#endif if (keytype == DROPBEAR_SIGNKEY_NONE) { fprintf(stderr, "Unknown key type '%s'\n", typetext); diff --git a/ed25519.c b/ed25519.c new file mode 100644 index 0000000..3fb544c --- /dev/null +++ b/ed25519.c @@ -0,0 +1,184 @@ +/* + * Dropbear - a SSH2 server + * + * Copyright (c) 2002,2003 Matt Johnston + * All rights reserved. + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. */ + +/* Perform Ed25519 operations on data, including reading keys, signing and + * verification. */ + +#include "includes.h" +#include "dbutil.h" +#include "buffer.h" +#include "ssh.h" +#include "curve25519.h" +#include "ed25519.h" + +#if DROPBEAR_ED25519 + +/* Load a public ed25519 key from a buffer, initialising the values. + * The key will have the same format as buf_put_ed25519_key. + * These should be freed with ed25519_key_free. + * Returns DROPBEAR_SUCCESS or DROPBEAR_FAILURE */ +int buf_get_ed25519_pub_key(buffer *buf, dropbear_ed25519_key *key) { + + unsigned int len; + + TRACE(("enter buf_get_ed25519_pub_key")) + dropbear_assert(key != NULL); + + buf_incrpos(buf, 4+SSH_SIGNKEY_ED25519_LEN); /* int + "ssh-ed25519" */ + + len = buf_getint(buf); + if (len != CURVE25519_LEN || buf->len - buf->pos < len) { + TRACE(("leave buf_get_ed25519_pub_key: failure")) + return DROPBEAR_FAILURE; + } + + m_burn(key->priv, CURVE25519_LEN); + memcpy(key->pub, buf_getptr(buf, CURVE25519_LEN), CURVE25519_LEN); + buf_incrpos(buf, CURVE25519_LEN); + + TRACE(("leave buf_get_ed25519_pub_key: success")) + return DROPBEAR_SUCCESS; +} + +/* Same as buf_get_ed25519_pub_key, but reads private key at the end. + * Loads a public and private ed25519 key from a buffer + * Returns DROPBEAR_SUCCESS or DROPBEAR_FAILURE */ +int buf_get_ed25519_priv_key(buffer *buf, dropbear_ed25519_key *key) { + + unsigned int len; + + TRACE(("enter buf_get_ed25519_priv_key")) + dropbear_assert(key != NULL); + + buf_incrpos(buf, 4+SSH_SIGNKEY_ED25519_LEN); /* int + "ssh-ed25519" */ + + len = buf_getint(buf); + if (len != CURVE25519_LEN*2 || buf->len - buf->pos < len) { + TRACE(("leave buf_get_ed25519_priv_key: failure")) + return DROPBEAR_FAILURE; + } + + memcpy(key->priv, buf_getptr(buf, CURVE25519_LEN), CURVE25519_LEN); + buf_incrpos(buf, CURVE25519_LEN); + memcpy(key->pub, buf_getptr(buf, CURVE25519_LEN), CURVE25519_LEN); + buf_incrpos(buf, CURVE25519_LEN); + + TRACE(("leave buf_get_ed25519_pub_key: success")) + return DROPBEAR_SUCCESS; +} + +/* Clear and free the memory used by a public or private key */ +void ed25519_key_free(dropbear_ed25519_key *key) { + + TRACE2(("enter ed25519_key_free")) + + if (key == NULL) { + TRACE2(("leave ed25519_key_free: key == NULL")) + return; + } + m_burn(key->priv, CURVE25519_LEN); + m_free(key); + + TRACE2(("leave rsa_key_free")) +} + +/* Put the public ed25519 key into the buffer in the required format */ +void buf_put_ed25519_pub_key(buffer *buf, const dropbear_ed25519_key *key) { + + TRACE(("enter buf_put_ed25519_pub_key")) + dropbear_assert(key != NULL); + + buf_putstring(buf, SSH_SIGNKEY_ED25519, SSH_SIGNKEY_ED25519_LEN); + buf_putstring(buf, key->pub, CURVE25519_LEN); + + TRACE(("leave buf_put_ed25519_pub_key")) +} + +/* Put the public and private ed25519 key into the buffer in the required format */ +void buf_put_ed25519_priv_key(buffer *buf, const dropbear_ed25519_key *key) { + + TRACE(("enter buf_put_ed25519_priv_key")) + dropbear_assert(key != NULL); + + buf_putstring(buf, SSH_SIGNKEY_ED25519, SSH_SIGNKEY_ED25519_LEN); + buf_putint(buf, CURVE25519_LEN*2); + buf_putbytes(buf, key->priv, CURVE25519_LEN); + buf_putbytes(buf, key->pub, CURVE25519_LEN); + + TRACE(("leave buf_put_ed25519_priv_key")) +} + +/* Sign the data presented with key, writing the signature contents + * to the buffer */ +void buf_put_ed25519_sign(buffer* buf, const dropbear_ed25519_key *key, const buffer *data_buf) { + + unsigned char s[64]; + unsigned long slen = sizeof(s); + + TRACE(("enter buf_put_ed25519_sign")) + dropbear_assert(key != NULL); + + if (dropbear_ed25519_sign(data_buf->data, data_buf->len, + s, &slen, key->priv, key->pub) == 0) { + buf_putstring(buf, SSH_SIGNKEY_ED25519, SSH_SIGNKEY_ED25519_LEN); + buf_putstring(buf, s, slen); + } + + TRACE(("leave buf_put_ed25519_sign")) +} + +#if DROPBEAR_SIGNKEY_VERIFY +/* Verify a signature in buf, made on data by the key given. + * Returns DROPBEAR_SUCCESS or DROPBEAR_FAILURE */ +int buf_ed25519_verify(buffer *buf, const dropbear_ed25519_key *key, const buffer *data_buf) { + + int ret = DROPBEAR_FAILURE; + unsigned char *s; + unsigned long slen; + + TRACE(("enter buf_ed25519_verify")) + dropbear_assert(key != NULL); + + slen = buf_getint(buf); + if (slen != 64 || buf->len - buf->pos < slen) { + TRACE(("bad size")) + goto out; + } + s = buf_getptr(buf, slen); + + if (dropbear_ed25519_verify(data_buf->data, data_buf->len, + s, slen, key->pub) == 0) { + /* signature is valid */ + TRACE(("success!")) + ret = DROPBEAR_SUCCESS; + } + +out: + TRACE(("leave buf_ed25519_verify: ret %d", ret)) + return ret; +} + +#endif /* DROPBEAR_SIGNKEY_VERIFY */ + +#endif /* DROPBEAR_ED25519 */ diff --git a/ed25519.h b/ed25519.h new file mode 100644 index 0000000..16c0d7b --- /dev/null +++ b/ed25519.h @@ -0,0 +1,54 @@ +/* + * Dropbear - a SSH2 server + * + * Copyright (c) 2002,2003 Matt Johnston + * All rights reserved. + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. */ + +#ifndef DROPBEAR_ED25519_H_ +#define DROPBEAR_ED25519_H_ + +#include "includes.h" +#include "buffer.h" + +#if DROPBEAR_ED25519 + +#define CURVE25519_LEN 32 + +typedef struct { + + unsigned char priv[CURVE25519_LEN]; + unsigned char pub[CURVE25519_LEN]; + +} dropbear_ed25519_key; + +void buf_put_ed25519_sign(buffer* buf, const dropbear_ed25519_key *key, const buffer *data_buf); +#if DROPBEAR_SIGNKEY_VERIFY +int buf_ed25519_verify(buffer * buf, const dropbear_ed25519_key *key, const buffer *data_buf); +#endif +int buf_get_ed25519_pub_key(buffer* buf, dropbear_ed25519_key *key); +int buf_get_ed25519_priv_key(buffer* buf, dropbear_ed25519_key *key); +void buf_put_ed25519_pub_key(buffer* buf, const dropbear_ed25519_key *key); +void buf_put_ed25519_priv_key(buffer* buf, const dropbear_ed25519_key *key); +void ed25519_key_free(dropbear_ed25519_key *key); + +#endif /* DROPBEAR_ED25519 */ + +#endif /* DROPBEAR_ED25519_H_ */ diff --git a/filelist.txt b/filelist.txt index 8281c14..3b9bb67 100644 --- a/filelist.txt +++ b/filelist.txt @@ -99,6 +99,10 @@ rsa.c RSA asymmetric crypto routines dss.c DSS asymmetric crypto routines +ed25519.c Ed25519 asymmetric crypto routines + +gened25519.c Ed25519 key generation + gendss.c DSS key generation genrsa.c RSA key generation diff --git a/fuzz-common.c b/fuzz-common.c index 5c90c45..b1b00f6 100644 --- a/fuzz-common.c +++ b/fuzz-common.c @@ -112,6 +112,14 @@ static void load_fixed_hostkeys(void) { dropbear_exit("failed fixed ecdsa hostkey"); } + buf_setlen(b, 0); + buf_putbytes(b, keyed25519, keyed25519_len); + buf_setpos(b, 0); + type = DROPBEAR_SIGNKEY_ED25519; + if (buf_get_priv_key(b, svr_opts.hostkey, &type) == DROPBEAR_FAILURE) { + dropbear_exit("failed fixed ed25519 hostkey"); + } + buf_free(b); } diff --git a/fuzz-hostkeys.c b/fuzz-hostkeys.c index dc1615d..3fff5cb 100644 --- a/fuzz-hostkeys.c +++ b/fuzz-hostkeys.c @@ -127,3 +127,13 @@ unsigned char keyd[] = { 0xf9, 0x39 }; unsigned int keyd_len = 458; +unsigned char keyed25519[] = { + 0x00, 0x00, 0x00, 0x0b, 0x73, 0x73, 0x68, 0x2d, 0x65, 0x64, 0x32, 0x35, + 0x35, 0x31, 0x39, 0x00, 0x00, 0x00, 0x40, 0x10, 0xb3, 0x79, 0x06, 0xe5, + 0x9b, 0xe7, 0xe4, 0x6e, 0xec, 0xfe, 0xa5, 0x39, 0x21, 0x7c, 0xf6, 0x66, + 0x8c, 0x0b, 0x6a, 0x01, 0x09, 0x05, 0xc7, 0x4f, 0x64, 0xa8, 0x24, 0xd2, + 0x8d, 0xbd, 0xdd, 0xc6, 0x3c, 0x99, 0x1b, 0x2d, 0x3e, 0x33, 0x90, 0x19, + 0xa4, 0xd5, 0xe9, 0x23, 0xfe, 0x8e, 0xd6, 0xd4, 0xf9, 0xb1, 0x11, 0x69, + 0x7c, 0x57, 0x52, 0x0e, 0x41, 0xdb, 0x1b, 0x12, 0x87, 0xfa, 0xc9 +}; +unsigned int keyed25519_len = 83; diff --git a/fuzzer-kexcurve25519.c b/fuzzer-kexcurve25519.c new file mode 100644 index 0000000..f2eab14 --- /dev/null +++ b/fuzzer-kexcurve25519.c @@ -0,0 +1,72 @@ +#include "fuzz.h" +#include "session.h" +#include "fuzz-wrapfd.h" +#include "debug.h" +#include "runopts.h" +#include "algo.h" +#include "bignum.h" + +int LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size) { + static int once = 0; + static struct key_context* keep_newkeys = NULL; + /* number of generated parameters is limited by the timeout for the first run. + TODO move this to the libfuzzer initialiser function instead if the timeout + doesn't apply there */ + #define NUM_PARAMS 20 + static struct kex_curve25519_param *curve25519_params[NUM_PARAMS]; + + if (!once) { + fuzz_common_setup(); + fuzz_svr_setup(); + + keep_newkeys = (struct key_context*)m_malloc(sizeof(struct key_context)); + keep_newkeys->algo_kex = fuzz_get_algo(sshkex, "curve25519-sha256"); + keep_newkeys->algo_hostkey = DROPBEAR_SIGNKEY_ED25519; + ses.newkeys = keep_newkeys; + + /* Pre-generate parameters */ + int i; + for (i = 0; i < NUM_PARAMS; i++) { + curve25519_params[i] = gen_kexcurve25519_param(); + } + + once = 1; + } + + if (fuzz_set_input(Data, Size) == DROPBEAR_FAILURE) { + return 0; + } + + m_malloc_set_epoch(1); + + if (setjmp(fuzz.jmp) == 0) { + /* Based on recv_msg_kexdh_init()/send_msg_kexdh_reply() + with DROPBEAR_KEX_CURVE25519 */ + ses.newkeys = keep_newkeys; + + /* Choose from the collection of curve25519 params */ + unsigned int e = buf_getint(fuzz.input); + struct kex_curve25519_param *curve25519_param = curve25519_params[e % NUM_PARAMS]; + + buffer * ecdh_qs = buf_getstringbuf(fuzz.input); + + ses.kexhashbuf = buf_new(KEXHASHBUF_MAX_INTS); + kexcurve25519_comb_key(curve25519_param, ecdh_qs, svr_opts.hostkey); + + mp_clear(ses.dh_K); + m_free(ses.dh_K); + buf_free(ecdh_qs); + + buf_free(ses.hash); + buf_free(ses.session_id); + /* kexhashbuf is freed in kexdh_comb_key */ + + m_malloc_free_epoch(1, 0); + } else { + m_malloc_free_epoch(1, 1); + TRACE(("dropbear_exit longjmped")) + /* dropbear_exit jumped here */ + } + + return 0; +} diff --git a/gened25519.c b/gened25519.c new file mode 100644 index 0000000..a027914 --- /dev/null +++ b/gened25519.c @@ -0,0 +1,47 @@ +/* + * Dropbear - a SSH2 server + * + * Copyright (c) 2002,2003 Matt Johnston + * All rights reserved. + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. */ + +#include "includes.h" +#include "dbutil.h" +#include "dbrandom.h" +#include "curve25519.h" +#include "gened25519.h" + +#if DROPBEAR_ED25519 + +dropbear_ed25519_key * gen_ed25519_priv_key(unsigned int size) { + + dropbear_ed25519_key *key; + + if (size != 256) { + dropbear_exit("Ed25519 keys have a fixed size of 256 bits"); + } + + key = m_malloc(sizeof(*key)); + dropbear_ed25519_make_key(key->pub, key->priv); + + return key; +} + +#endif /* DROPBEAR_ED25519 */ diff --git a/gened25519.h b/gened25519.h new file mode 100644 index 0000000..8058310 --- /dev/null +++ b/gened25519.h @@ -0,0 +1,36 @@ +/* + * Dropbear - a SSH2 server + * + * Copyright (c) 2002,2003 Matt Johnston + * All rights reserved. + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. */ + +#ifndef DROPBEAR_GENED25519_H_ +#define DROPBEAR_GENED25519_H_ + +#include "ed25519.h" + +#if DROPBEAR_ED25519 + +dropbear_ed25519_key * gen_ed25519_priv_key(unsigned int size); + +#endif /* DROPBEAR_ED25519 */ + +#endif /* DROPBEAR_GENED25519_H_ */ diff --git a/gensignkey.c b/gensignkey.c index 34b6f5a..674d81f 100644 --- a/gensignkey.c +++ b/gensignkey.c @@ -4,6 +4,7 @@ #include "ecdsa.h" #include "genrsa.h" #include "gendss.h" +#include "gened25519.h" #include "signkey.h" #include "dbrandom.h" @@ -69,6 +70,10 @@ static int get_default_bits(enum signkey_type keytype) case DROPBEAR_SIGNKEY_ECDSA_NISTP256: return 256; #endif +#if DROPBEAR_ED25519 + case DROPBEAR_SIGNKEY_ED25519: + return 256; +#endif default: return 0; } @@ -119,6 +124,11 @@ int signkey_generate(enum signkey_type keytype, int bits, const char* filename, } break; #endif +#if DROPBEAR_ED25519 + case DROPBEAR_SIGNKEY_ED25519: + key->ed25519key = gen_ed25519_priv_key(bits); + break; +#endif default: dropbear_exit("Internal error"); } diff --git a/keyimport.c b/keyimport.c index 7304e58..ad0c530 100644 --- a/keyimport.c +++ b/keyimport.c @@ -35,6 +35,15 @@ #include "buffer.h" #include "dbutil.h" #include "ecc.h" +#include "ssh.h" + +static const unsigned char OSSH_PKEY_BLOB[] = + "openssh-key-v1\0" /* AUTH_MAGIC */ + "\0\0\0\4none" /* cipher name*/ + "\0\0\0\4none" /* kdf name */ + "\0\0\0\0" /* kdf */ + "\0\0\0\1"; /* key num */ +#define OSSH_PKEY_BLOBLEN (sizeof(OSSH_PKEY_BLOB) - 1) #if DROPBEAR_ECDSA static const unsigned char OID_SEC256R1_BLOB[] = {0x2a, 0x86, 0x48, 0xce, 0x3d, 0x03, 0x01, 0x07}; @@ -352,7 +361,7 @@ struct mpint_pos { void *start; int bytes; }; * Code to read and write OpenSSH private keys. */ -enum { OSSH_DSA, OSSH_RSA, OSSH_EC }; +enum { OSSH_DSA, OSSH_RSA, OSSH_EC, OSSH_PKEY }; struct openssh_key { int type; int encrypted; @@ -364,11 +373,12 @@ struct openssh_key { static struct openssh_key *load_openssh_key(const char *filename) { struct openssh_key *ret; + buffer *buf = NULL; FILE *fp = NULL; char buffer[256]; char *errmsg = NULL, *p = NULL; int headers_done; - unsigned long len, outlen; + unsigned long len; ret = (struct openssh_key*)m_malloc(sizeof(struct openssh_key)); ret->keyblob = NULL; @@ -397,12 +407,15 @@ static struct openssh_key *load_openssh_key(const char *filename) ret->type = OSSH_DSA; else if (!strcmp(buffer, "-----BEGIN EC PRIVATE KEY-----\n")) ret->type = OSSH_EC; + else if (!strcmp(buffer, "-----BEGIN OPENSSH PRIVATE KEY-----\n")) + ret->type = OSSH_PKEY; else { errmsg = "Unrecognised key type"; goto error; } headers_done = 0; + buf = buf_new(0); while (1) { if (!fgets(buffer, sizeof(buffer), fp)) { errmsg = "Unexpected end of file"; @@ -448,20 +461,31 @@ static struct openssh_key *load_openssh_key(const char *filename) } else { headers_done = 1; len = strlen(buffer); - outlen = len*4/3; - if (ret->keyblob_len + outlen > ret->keyblob_size) { - ret->keyblob_size = ret->keyblob_len + outlen + 256; - ret->keyblob = (unsigned char*)m_realloc(ret->keyblob, - ret->keyblob_size); - } - outlen = ret->keyblob_size - ret->keyblob_len; - if (base64_decode((const unsigned char *)buffer, len, - ret->keyblob + ret->keyblob_len, &outlen) != CRYPT_OK){ - errmsg = "Error decoding base64"; - goto error; - } - ret->keyblob_len += outlen; + buf = buf_resize(buf, buf->size + len); + buf_putbytes(buf, buffer, len); + } + } + + if (buf && buf->len) { + ret->keyblob_size = ret->keyblob_len + buf->len*4/3 + 256; + ret->keyblob = (unsigned char*)m_realloc(ret->keyblob, ret->keyblob_size); + len = ret->keyblob_size; + if (base64_decode((const unsigned char *)buf->data, buf->len, + ret->keyblob, &len) != CRYPT_OK){ + errmsg = "Error decoding base64"; + goto error; + } + ret->keyblob_len = len; + } + + if (ret->type == OSSH_PKEY) { + if (ret->keyblob_len < OSSH_PKEY_BLOBLEN || + memcmp(ret->keyblob, OSSH_PKEY_BLOB, OSSH_PKEY_BLOBLEN)) { + errmsg = "Error decoding OpenSSH key"; + goto error; } + ret->keyblob_len -= OSSH_PKEY_BLOBLEN; + memmove(ret->keyblob, ret->keyblob + OSSH_PKEY_BLOBLEN, ret->keyblob_len); } if (ret->keyblob_len == 0 || !ret->keyblob) { @@ -474,10 +498,18 @@ static struct openssh_key *load_openssh_key(const char *filename) goto error; } + if (buf) { + buf_burn(buf); + buf_free(buf); + } m_burn(buffer, sizeof(buffer)); return ret; error: + if (buf) { + buf_burn(buf); + buf_free(buf); + } m_burn(buffer, sizeof(buffer)); if (ret) { if (ret->keyblob) { @@ -570,6 +602,57 @@ static sign_key *openssh_read(const char *filename, const char * UNUSED(passphra } /* + * Now we have a decrypted key blob, which contains OpenSSH + * encoded private key. We must now untangle the OpenSSH format. + */ + if (key->type == OSSH_PKEY) { + blobbuf = buf_new(key->keyblob_len); + buf_putbytes(blobbuf, key->keyblob, key->keyblob_len); + buf_setpos(blobbuf, 0); + + /* limit length of private key blob */ + len = buf_getint(blobbuf); + buf_setlen(blobbuf, blobbuf->pos + len); + + type = DROPBEAR_SIGNKEY_ANY; + if (buf_get_pub_key(blobbuf, retkey, &type) + != DROPBEAR_SUCCESS) { + errmsg = "Error parsing OpenSSH key"; + goto ossh_error; + } + + /* restore full length */ + buf_setlen(blobbuf, key->keyblob_len); + + if (type != DROPBEAR_SIGNKEY_NONE) { + retkey->type = type; + /* limit length of private key blob */ + len = buf_getint(blobbuf); + buf_setlen(blobbuf, blobbuf->pos + len); +#if DROPBEAR_ED25519 + if (type == DROPBEAR_SIGNKEY_ED25519) { + buf_incrpos(blobbuf, 8); + buf_eatstring(blobbuf); + buf_eatstring(blobbuf); + buf_incrpos(blobbuf, -SSH_SIGNKEY_ED25519_LEN-4); + if (buf_get_ed25519_priv_key(blobbuf, retkey->ed25519key) + == DROPBEAR_SUCCESS) { + errmsg = NULL; + retval = retkey; + goto error; + } + } +#endif + } + + errmsg = "Unsupported OpenSSH key type"; + ossh_error: + sign_key_free(retkey); + retkey = NULL; + goto error; + } + + /* * Now we have a decrypted key blob, which contains an ASN.1 * encoded private key. We must now untangle the ASN.1. * @@ -1129,6 +1212,51 @@ static int openssh_write(const char *filename, sign_key *key, } #endif +#if DROPBEAR_ED25519 + if (key->type == DROPBEAR_SIGNKEY_ED25519) { + buffer *buf = buf_new(300); + keyblob = buf_new(100); + extrablob = buf_new(200); + + /* private key blob w/o header */ + buf_put_priv_key(keyblob, key, key->type); + buf_setpos(keyblob, 0); + buf_incrpos(keyblob, buf_getint(keyblob)); + len = buf_getint(keyblob); + + /* header */ + buf_putbytes(buf, OSSH_PKEY_BLOB, OSSH_PKEY_BLOBLEN); + + /* public key */ + buf_put_pub_key(buf, key, key->type); + + /* private key */ + buf_incrwritepos(extrablob, 4); + buf_put_pub_key(extrablob, key, key->type); + buf_putstring(extrablob, buf_getptr(keyblob, len), len); + /* comment */ + buf_putstring(extrablob, "", 0); + /* padding to cipher block length */ + len = (extrablob->len+8) & ~7; + for (i = 1; len - extrablob->len > 0; i++) + buf_putbyte(extrablob, i); + buf_setpos(extrablob, 0); + buf_putbytes(extrablob, "\0\0\0\0\0\0\0\0", 8); + buf_putbufstring(buf, extrablob); + + outlen = len = pos = buf->len; + outblob = (unsigned char*)m_malloc(outlen); + memcpy(outblob, buf->data, buf->len); + + buf_burn(buf); + buf_free(buf); + buf = NULL; + + header = "-----BEGIN OPENSSH PRIVATE KEY-----\n"; + footer = "-----END OPENSSH PRIVATE KEY-----\n"; + } +#endif + /* * Padding on OpenSSH keys is deterministic. The number of * padding bytes is always more than zero, and always at most @@ -39,8 +39,11 @@ static const char * const signkey_names[DROPBEAR_SIGNKEY_NUM_NAMED] = { #if DROPBEAR_ECDSA "ecdsa-sha2-nistp256", "ecdsa-sha2-nistp384", - "ecdsa-sha2-nistp521" + "ecdsa-sha2-nistp521", #endif /* DROPBEAR_ECDSA */ +#if DROPBEAR_ED25519 + "ssh-ed25519", +#endif /* DROPBEAR_ED25519 */ }; /* malloc a new sign_key and set the dss and rsa keys to NULL */ @@ -107,6 +110,10 @@ Be sure to check both (ret != NULL) and (*ret != NULL) */ void ** signkey_key_ptr(sign_key *key, enum signkey_type type) { switch (type) { +#if DROPBEAR_ED25519 + case DROPBEAR_SIGNKEY_ED25519: + return (void**)&key->ed25519key; +#endif #if DROPBEAR_ECDSA #if DROPBEAR_ECC_256 case DROPBEAR_SIGNKEY_ECDSA_NISTP256: @@ -200,6 +207,17 @@ int buf_get_pub_key(buffer *buf, sign_key *key, enum signkey_type *type) { } } #endif +#if DROPBEAR_ED25519 + if (keytype == DROPBEAR_SIGNKEY_ED25519) { + ed25519_key_free(key->ed25519key); + key->ed25519key = m_malloc(sizeof(*key->ed25519key)); + ret = buf_get_ed25519_pub_key(buf, key->ed25519key); + if (ret == DROPBEAR_FAILURE) { + m_free(key->ed25519key); + key->ed25519key = NULL; + } + } +#endif TRACE2(("leave buf_get_pub_key")) @@ -270,6 +288,17 @@ int buf_get_priv_key(buffer *buf, sign_key *key, enum signkey_type *type) { } } #endif +#if DROPBEAR_ED25519 + if (keytype == DROPBEAR_SIGNKEY_ED25519) { + ed25519_key_free(key->ed25519key); + key->ed25519key = m_malloc(sizeof(*key->ed25519key)); + ret = buf_get_ed25519_priv_key(buf, key->ed25519key); + if (ret == DROPBEAR_FAILURE) { + m_free(key->ed25519key); + key->ed25519key = NULL; + } + } +#endif TRACE2(("leave buf_get_priv_key")) @@ -303,6 +332,11 @@ void buf_put_pub_key(buffer* buf, sign_key *key, enum signkey_type type) { } } #endif +#if DROPBEAR_ED25519 + if (type == DROPBEAR_SIGNKEY_ED25519) { + buf_put_ed25519_pub_key(pubkeys, key->ed25519key); + } +#endif if (pubkeys->len == 0) { dropbear_exit("Bad key types in buf_put_pub_key"); } @@ -342,6 +376,13 @@ void buf_put_priv_key(buffer* buf, sign_key *key, enum signkey_type type) { } } #endif +#if DROPBEAR_ED25519 + if (type == DROPBEAR_SIGNKEY_ED25519) { + buf_put_ed25519_priv_key(buf, key->ed25519key); + TRACE(("leave buf_put_priv_key: ed25519 done")) + return; + } +#endif dropbear_exit("Bad key types in put pub key"); } @@ -380,6 +421,10 @@ void sign_key_free(sign_key *key) { } #endif #endif +#if DROPBEAR_ED25519 + ed25519_key_free(key->ed25519key); + key->ed25519key = NULL; +#endif m_free(key->filename); @@ -504,6 +549,11 @@ void buf_put_sign(buffer* buf, sign_key *key, enum signkey_type type, } } #endif +#if DROPBEAR_ED25519 + if (type == DROPBEAR_SIGNKEY_ED25519) { + buf_put_ed25519_sign(sigblob, key->ed25519key, data_buf); + } +#endif if (sigblob->len == 0) { dropbear_exit("Non-matching signing type"); } @@ -555,6 +605,14 @@ int buf_verify(buffer * buf, sign_key *key, const buffer *data_buf) { } } #endif +#if DROPBEAR_ED25519 + if (type == DROPBEAR_SIGNKEY_ED25519) { + if (key->ed25519key == NULL) { + dropbear_exit("No Ed25519 key to verify signature"); + } + return buf_ed25519_verify(buf, key->ed25519key, data_buf); + } +#endif dropbear_exit("Non-matching signing type"); return DROPBEAR_FAILURE; @@ -28,6 +28,7 @@ #include "buffer.h" #include "dss.h" #include "rsa.h" +#include "ed25519.h" enum signkey_type { #if DROPBEAR_RSA @@ -41,6 +42,9 @@ enum signkey_type { DROPBEAR_SIGNKEY_ECDSA_NISTP384, DROPBEAR_SIGNKEY_ECDSA_NISTP521, #endif /* DROPBEAR_ECDSA */ +#if DROPBEAR_ED25519 + DROPBEAR_SIGNKEY_ED25519, +#endif DROPBEAR_SIGNKEY_NUM_NAMED, DROPBEAR_SIGNKEY_ECDSA_KEYGEN = 70, /* just "ecdsa" for keygen */ DROPBEAR_SIGNKEY_ANY = 80, @@ -78,6 +82,9 @@ struct SIGN_key { ecc_key * ecckey521; #endif #endif +#if DROPBEAR_ED25519 + dropbear_ed25519_key * ed25519key; +#endif }; typedef struct SIGN_key sign_key; @@ -105,6 +105,8 @@ #define SSH_SIGNKEY_DSS_LEN 7 #define SSH_SIGNKEY_RSA "ssh-rsa" #define SSH_SIGNKEY_RSA_LEN 7 +#define SSH_SIGNKEY_ED25519 "ssh-ed25519" +#define SSH_SIGNKEY_ED25519_LEN 11 /* Agent commands. These aren't part of the spec, and are defined * only on the openssh implementation. */ @@ -123,6 +123,11 @@ static void svr_ensure_hostkey() { fn = ECDSA_PRIV_FILENAME; break; #endif +#if DROPBEAR_ED25519 + case DROPBEAR_SIGNKEY_ED25519: + fn = ED25519_PRIV_FILENAME; + break; +#endif default: dropbear_assert(0); } @@ -219,7 +224,8 @@ static void send_msg_kexdh_reply(mp_int *dh_e, buffer *ecdh_qs) { { struct kex_curve25519_param *param = gen_kexcurve25519_param(); kexcurve25519_comb_key(param, ecdh_qs, svr_opts.hostkey); - buf_putstring(ses.writepayload, (const char*)param->pub, CURVE25519_LEN); + + buf_putstring(ses.writepayload, param->pub, CURVE25519_LEN); free_kexcurve25519_param(param); } break; diff --git a/svr-runopts.c b/svr-runopts.c index d7a0d5a..d430825 100644 --- a/svr-runopts.c +++ b/svr-runopts.c @@ -57,6 +57,9 @@ static void printhelp(const char * progname) { #if DROPBEAR_ECDSA " - ecdsa %s\n" #endif +#if DROPBEAR_ED25519 + " - ed25519 %s\n" +#endif #if DROPBEAR_DELAY_HOSTKEY "-R Create hostkeys as required\n" #endif @@ -117,6 +120,9 @@ static void printhelp(const char * progname) { #if DROPBEAR_ECDSA ECDSA_PRIV_FILENAME, #endif +#if DROPBEAR_ED25519 + ED25519_PRIV_FILENAME, +#endif MAX_AUTH_TRIES, DROPBEAR_MAX_PORTS, DROPBEAR_DEFPORT, DROPBEAR_PIDFILE, DEFAULT_RECV_WINDOW, DEFAULT_KEEPALIVE, DEFAULT_IDLE_TIMEOUT); @@ -538,6 +544,13 @@ static void loadhostkey(const char *keyfile, int fatal_duplicate) { } #endif #endif /* DROPBEAR_ECDSA */ + +#if DROPBEAR_ED25519 + if (type == DROPBEAR_SIGNKEY_ED25519) { + loadhostkey_helper("ed25519", (void**)&read_key->ed25519key, (void**)&svr_opts.hostkey->ed25519key, fatal_duplicate); + } +#endif + sign_key_free(read_key); TRACE(("leave loadhostkey")) } @@ -579,6 +592,9 @@ void load_all_hostkeys() { #if DROPBEAR_ECDSA loadhostkey(ECDSA_PRIV_FILENAME, 0); #endif +#if DROPBEAR_ED25519 + loadhostkey(ED25519_PRIV_FILENAME, 0); +#endif } #if DROPBEAR_RSA @@ -642,6 +658,14 @@ void load_all_hostkeys() { #endif #endif /* DROPBEAR_ECDSA */ +#if DROPBEAR_ED25519 + if (!svr_opts.delay_hostkey && !svr_opts.hostkey->ed25519key) { + disablekey(DROPBEAR_SIGNKEY_ED25519); + } else { + any_keys = 1; + } +#endif + if (!any_keys) { dropbear_exit("No hostkeys available. 'dropbear -R' may be useful or run dropbearkey."); } diff --git a/sysoptions.h b/sysoptions.h index cfd5469..2c27caf 100644 --- a/sysoptions.h +++ b/sysoptions.h @@ -145,7 +145,8 @@ If you test it please contact the Dropbear author */ #define DROPBEAR_SHA384 (DROPBEAR_ECC_384) /* LTC SHA384 depends on SHA512 */ #define DROPBEAR_SHA512 ((DROPBEAR_SHA2_512_HMAC) || (DROPBEAR_ECC_521) \ - || (DROPBEAR_SHA384) || (DROPBEAR_DH_GROUP16)) + || (DROPBEAR_SHA384) || (DROPBEAR_DH_GROUP16) \ + || (DROPBEAR_ED25519)) #define DROPBEAR_MD5 (DROPBEAR_MD5_HMAC) #define DROPBEAR_DH_GROUP14 ((DROPBEAR_DH_GROUP14_SHA256) || (DROPBEAR_DH_GROUP14_SHA1)) @@ -186,7 +187,7 @@ If you test it please contact the Dropbear author */ /* For a 4096 bit DSS key, empirically determined */ #define MAX_PRIVKEY_SIZE 1700 -#define MAX_HOSTKEYS 3 +#define MAX_HOSTKEYS 4 /* The maximum size of the bignum portion of the kexhash buffer */ /* Sect. 8 of the transport rfc 4253, K_S + e + f + K */ @@ -252,7 +253,7 @@ If you test it please contact the Dropbear author */ #error "At least one encryption algorithm must be enabled. AES128 is recommended." #endif -#if !(DROPBEAR_RSA || DROPBEAR_DSS || DROPBEAR_ECDSA) +#if !(DROPBEAR_RSA || DROPBEAR_DSS || DROPBEAR_ECDSA || DROPBEAR_ED25519) #error "At least one hostkey or public-key algorithm must be enabled; RSA is recommended." #endif |