Mercurial > dropbear
changeset 1659:d32bcb5c557d
Add Ed25519 support (#91)
* Add support for Ed25519 as a public key type
Ed25519 is a elliptic curve signature scheme that offers
better security than ECDSA and DSA and good performance. It may be
used for both user and host keys.
OpenSSH key import and fuzzer are not supported yet.
Initially inspired by Peter Szabo.
* Add curve25519 and ed25519 fuzzers
* Add import and export of Ed25519 keys
| author | Vladislav Grishenko <themiron@users.noreply.github.com> |
|---|---|
| date | Wed, 11 Mar 2020 21:09:45 +0500 |
| parents | 7402218141d4 |
| children | 26e07f7f682a |
| files | .travis.yml FUZZER-NOTES.md LICENSE Makefile.in README cli-kex.c common-algo.c common-kex.c curve25519-donna.c curve25519.c curve25519.h default_options.h dropbear.8 dropbearkey.c ed25519.c ed25519.h filelist.txt fuzz-common.c fuzz-hostkeys.c fuzzer-kexcurve25519.c gened25519.c gened25519.h gensignkey.c keyimport.c signkey.c signkey.h ssh.h svr-kex.c svr-runopts.c sysoptions.h |
| diffstat | 30 files changed, 1288 insertions(+), 945 deletions(-) [+] |
line wrap: on
line diff
--- a/.travis.yml Fri Oct 18 23:48:16 2019 +0800 +++ b/.travis.yml Wed Mar 11 21:09:45 2020 +0500 @@ -57,6 +57,7 @@ - ~/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:
--- a/FUZZER-NOTES.md Fri Oct 18 23:48:16 2019 +0800 +++ b/FUZZER-NOTES.md Wed Mar 11 21:09:45 2020 +0500 @@ -72,3 +72,6 @@ - [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.
--- a/LICENSE Fri Oct 18 23:48:16 2019 +0800 +++ b/LICENSE Wed Mar 11 21:09:45 2020 +0500 @@ -90,52 +90,25 @@ ===== -curve25519-donna: +crypto25519.c: +crypto26619.h: + +Modified TweetNaCl version 20140427, a self-contained public-domain C library. +https://tweetnacl.cr.yp.to/ -/* 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 <[email protected]> - * - * Derived from public domain C code by Daniel J. Bernstein <[email protected]> - * - * 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. - */ +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.
--- a/Makefile.in Fri Oct 18 23:48:16 2019 +0800 +++ b/Makefile.in Wed Mar 11 21:09:45 2020 +0500 @@ -36,8 +36,9 @@ 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 @@ 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 @@ ## 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-kexecdh: fuzzer-kexecdh.o fuzz-harness.o $(CXX) $(CXXFLAGS) [email protected] $(LDFLAGS) $(svrfuzzobjs) -o $@$(EXEEXT) $(LIBTOM_LIBS) $(LIBS) $(FUZZLIB) @CRYPTLIB@ +fuzzer-kexcurve25519: fuzzer-kexcurve25519.o fuzz-harness.o + $(CXX) $(CXXFLAGS) [email protected] $(LDFLAGS) $(svrfuzzobjs) -o $@$(EXEEXT) $(LIBTOM_LIBS) $(LIBS) $(FUZZLIB) @CRYPTLIB@ + fuzzer-%.options: Makefile echo "[libfuzzer]" > $@ echo "max_len = 50000" >> $@ @@ -313,7 +317,9 @@ 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
--- a/README Fri Oct 18 23:48:16 2019 +0800 +++ b/README Wed Mar 11 21:09:45 2020 +0500 @@ -55,6 +55,7 @@ ./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
--- a/cli-kex.c Fri Oct 18 23:48:16 2019 +0800 +++ b/cli-kex.c Wed Mar 11 21:09:45 2020 +0500 @@ -81,7 +81,7 @@ } 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 }
--- a/common-algo.c Fri Oct 18 23:48:16 2019 +0800 +++ b/common-algo.c Wed Mar 11 21:09:45 2020 +0500 @@ -222,6 +222,9 @@ }; 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},
--- a/common-kex.c Fri Oct 18 23:48:16 2019 +0800 +++ b/common-kex.c Wed Mar 11 21:09:45 2020 +0500 @@ -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 @@ #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 @@ 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");
--- a/curve25519-donna.c Fri Oct 18 23:48:16 2019 +0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -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 <[email protected]> - * - * Derived from public domain C code by Daniel J. Bernstein <[email protected]> - * - * 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; -}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/curve25519.c Wed Mar 11 21:09:45 2020 +0500 @@ -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 */
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/curve25519.h Wed Mar 11 21:09:45 2020 +0500 @@ -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 */
--- a/default_options.h Fri Oct 18 23:48:16 2019 +0800 +++ b/default_options.h Wed Mar 11 21:09:45 2020 +0500 @@ -22,6 +22,7 @@ #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 @@ * 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 @@ * 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.
--- a/dropbear.8 Fri Oct 18 23:48:16 2019 +0800 +++ b/dropbear.8 Wed Mar 11 21:09:45 2020 +0500 @@ -107,7 +107,7 @@ 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 @@ 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.
--- a/dropbearkey.c Fri Oct 18 23:48:16 2019 +0800 +++ b/dropbearkey.c Wed Mar 11 21:09:45 2020 +0500 @@ -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 @@ #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 @@ #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 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 @@ 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);
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/ed25519.c Wed Mar 11 21:09:45 2020 +0500 @@ -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 */
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/ed25519.h Wed Mar 11 21:09:45 2020 +0500 @@ -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_ */
--- a/filelist.txt Fri Oct 18 23:48:16 2019 +0800 +++ b/filelist.txt Wed Mar 11 21:09:45 2020 +0500 @@ -99,6 +99,10 @@ 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
--- a/fuzz-common.c Fri Oct 18 23:48:16 2019 +0800 +++ b/fuzz-common.c Wed Mar 11 21:09:45 2020 +0500 @@ -112,6 +112,14 @@ 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); }
--- a/fuzz-hostkeys.c Fri Oct 18 23:48:16 2019 +0800 +++ b/fuzz-hostkeys.c Wed Mar 11 21:09:45 2020 +0500 @@ -127,3 +127,13 @@ 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;
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/fuzzer-kexcurve25519.c Wed Mar 11 21:09:45 2020 +0500 @@ -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; +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/gened25519.c Wed Mar 11 21:09:45 2020 +0500 @@ -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 */
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/gened25519.h Wed Mar 11 21:09:45 2020 +0500 @@ -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_ */
--- a/gensignkey.c Fri Oct 18 23:48:16 2019 +0800 +++ b/gensignkey.c Wed Mar 11 21:09:45 2020 +0500 @@ -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 @@ 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 @@ } break; #endif +#if DROPBEAR_ED25519 + case DROPBEAR_SIGNKEY_ED25519: + key->ed25519key = gen_ed25519_priv_key(bits); + break; +#endif default: dropbear_exit("Internal error"); }
--- a/keyimport.c Fri Oct 18 23:48:16 2019 +0800 +++ b/keyimport.c Wed Mar 11 21:09:45 2020 +0500 @@ -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 @@ * 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 @@ 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 @@ 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,22 +461,33 @@ } 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) { errmsg = "Key body not present"; goto error; @@ -474,10 +498,18 @@ 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 @@ } /* + * 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 @@ } #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
--- a/signkey.c Fri Oct 18 23:48:16 2019 +0800 +++ b/signkey.c Wed Mar 11 21:09:45 2020 +0500 @@ -39,8 +39,11 @@ #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 @@ 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 @@ } } #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 @@ } } #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 @@ } } #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 @@ } } #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 @@ } #endif #endif +#if DROPBEAR_ED25519 + ed25519_key_free(key->ed25519key); + key->ed25519key = NULL; +#endif m_free(key->filename); @@ -504,6 +549,11 @@ } } #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 @@ } } #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;
--- a/signkey.h Fri Oct 18 23:48:16 2019 +0800 +++ b/signkey.h Wed Mar 11 21:09:45 2020 +0500 @@ -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 @@ 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 @@ ecc_key * ecckey521; #endif #endif +#if DROPBEAR_ED25519 + dropbear_ed25519_key * ed25519key; +#endif }; typedef struct SIGN_key sign_key;
--- a/ssh.h Fri Oct 18 23:48:16 2019 +0800 +++ b/ssh.h Wed Mar 11 21:09:45 2020 +0500 @@ -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. */
--- a/svr-kex.c Fri Oct 18 23:48:16 2019 +0800 +++ b/svr-kex.c Wed Mar 11 21:09:45 2020 +0500 @@ -123,6 +123,11 @@ 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 @@ { 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;
--- a/svr-runopts.c Fri Oct 18 23:48:16 2019 +0800 +++ b/svr-runopts.c Wed Mar 11 21:09:45 2020 +0500 @@ -57,6 +57,9 @@ #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 @@ #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 @@ } #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 @@ #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 @@ #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."); }
--- a/sysoptions.h Fri Oct 18 23:48:16 2019 +0800 +++ b/sysoptions.h Wed Mar 11 21:09:45 2020 +0500 @@ -145,7 +145,8 @@ #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 @@ /* 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 @@ #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