projects / openwrt / staging / dedeckeh.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
history | raw | HEAD
lantiq: fritz7312: set maximum speed to 100 mbit on 5.4
[openwrt/staging/dedeckeh.git] / package / network / services / dropbear / patches / 020-backport-ed25519-support.patch
1 From 3d12521735e7ef7e48be217af0f27d68e23050a7 Mon Sep 17 00:00:00 2001
2 From: Vladislav Grishenko <themiron@users.noreply.github.com>
3 Date: Wed, 11 Mar 2020 21:09:45 +0500
4 Subject: [PATCH] Add Ed25519 support (#91)
5
6 * Add support for Ed25519 as a public key type
7
8 Ed25519 is a elliptic curve signature scheme that offers
9 better security than ECDSA and DSA and good performance. It may be
10 used for both user and host keys.
11
12 OpenSSH key import and fuzzer are not supported yet.
13
14 Initially inspired by Peter Szabo.
15
16 * Add curve25519 and ed25519 fuzzers
17
18 * Add import and export of Ed25519 keys
19 ---
20 .travis.yml | 1 +
21 FUZZER-NOTES.md | 3 +
22 LICENSE | 71 ++--
23 Makefile.in | 12 +-
24 README | 1 +
25 cli-kex.c | 2 +-
26 common-algo.c | 3 +
27 common-kex.c | 14 +-
28 curve25519-donna.c | 860 -----------------------------------------
29 curve25519.c | 502 ++++++++++++++++++++++++
30 curve25519.h | 37 ++
31 default_options.h | 7 +-
32 dropbear.8 | 6 +-
33 dropbearkey.c | 25 ++
34 ed25519.c | 184 +++++++++
35 ed25519.h | 54 +++
36 filelist.txt | 4 +
37 fuzz-common.c | 8 +
38 fuzz-hostkeys.c | 10 +
39 fuzzer-kexcurve25519.c | 72 ++++
40 gened25519.c | 47 +++
41 gened25519.h | 36 ++
42 gensignkey.c | 10 +
43 keyimport.c | 158 +++++++-
44 signkey.c | 60 ++-
45 signkey.h | 7 +
46 ssh.h | 2 +
47 svr-kex.c | 8 +-
48 svr-runopts.c | 24 ++
49 sysoptions.h | 7 +-
50 30 files changed, 1289 insertions(+), 946 deletions(-)
51 delete mode 100644 curve25519-donna.c
52 create mode 100644 curve25519.c
53 create mode 100644 curve25519.h
54 create mode 100644 ed25519.c
55 create mode 100644 ed25519.h
56 create mode 100644 fuzzer-kexcurve25519.c
57 create mode 100644 gened25519.c
58 create mode 100644 gened25519.h
59
60 diff --git a/.travis.yml b/.travis.yml
61 index 9bcbce4..99499c8 100644
62 --- a/.travis.yml
63 +++ b/.travis.yml
64 @@ -57,6 +57,7 @@ script:
65 - ~/inst/bin/dropbearkey -t ecdsa -f testec256 -s 256
66 - ~/inst/bin/dropbearkey -t ecdsa -f testec384 -s 384
67 - ~/inst/bin/dropbearkey -t ecdsa -f testec521 -s 521
68 + - ~/inst/bin/dropbearkey -t ed25519 -f tested25519
69 - test -z $DO_FUZZ || ./fuzzers_test.sh
70
71 branches:
72 diff --git a/FUZZER-NOTES.md b/FUZZER-NOTES.md
73 index 7b88238..4967eba 100644
74 --- a/FUZZER-NOTES.md
75 +++ b/FUZZER-NOTES.md
76 @@ -72,3 +72,6 @@ Current fuzzers are
77
78 - [fuzzer-kexecdh](fuzzer-kexecdh.c) - test Elliptic Curve Diffie-Hellman key exchange like fuzzer-kexdh.
79 This is testing libtommath ECC routines.
80 +
81 +- [fuzzer-kexcurve25519](fuzzer-kexcurve25519.c) - test Curve25519 Elliptic Curve Diffie-Hellman key exchange
82 + like fuzzer-kexecdh. This is testing `dropbear_curve25519_scalarmult()` and other libtommath routines.
83 diff --git a/LICENSE b/LICENSE
84 index c400d94..a4849ff 100644
85 --- a/LICENSE
86 +++ b/LICENSE
87 @@ -90,52 +90,25 @@ WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
88
89 =====
90
91 -curve25519-donna:
92 -
93 -/* Copyright 2008, Google Inc.
94 - * All rights reserved.
95 - *
96 - * Redistribution and use in source and binary forms, with or without
97 - * modification, are permitted provided that the following conditions are
98 - * met:
99 - *
100 - * * Redistributions of source code must retain the above copyright
101 - * notice, this list of conditions and the following disclaimer.
102 - * * Redistributions in binary form must reproduce the above
103 - * copyright notice, this list of conditions and the following disclaimer
104 - * in the documentation and/or other materials provided with the
105 - * distribution.
106 - * * Neither the name of Google Inc. nor the names of its
107 - * contributors may be used to endorse or promote products derived from
108 - * this software without specific prior written permission.
109 - *
110 - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
111 - * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
112 - * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
113 - * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
114 - * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
115 - * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
116 - * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
117 - * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
118 - * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
119 - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
120 - * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
121 - *
122 - * curve25519-donna: Curve25519 elliptic curve, public key function
123 - *
124 - * http://code.google.com/p/curve25519-donna/
125 - *
126 - * Adam Langley <agl@imperialviolet.org>
127 - *
128 - * Derived from public domain C code by Daniel J. Bernstein <djb@cr.yp.to>
129 - *
130 - * More information about curve25519 can be found here
131 - * http://cr.yp.to/ecdh.html
132 - *
133 - * djb's sample implementation of curve25519 is written in a special assembly
134 - * language called qhasm and uses the floating point registers.
135 - *
136 - * This is, almost, a clean room reimplementation from the curve25519 paper. It
137 - * uses many of the tricks described therein. Only the crecip function is taken
138 - * from the sample implementation.
139 - */
140 +crypto25519.c:
141 +crypto26619.h:
142 +
143 +Modified TweetNaCl version 20140427, a self-contained public-domain C library.
144 +https://tweetnacl.cr.yp.to/
145 +
146 +Contributors (alphabetical order)
147 +Daniel J. Bernstein, University of Illinois at Chicago and Technische
148 +Universiteit Eindhoven
149 +Bernard van Gastel, Radboud Universiteit Nijmegen
150 +Wesley Janssen, Radboud Universiteit Nijmegen
151 +Tanja Lange, Technische Universiteit Eindhoven
152 +Peter Schwabe, Radboud Universiteit Nijmegen
153 +Sjaak Smetsers, Radboud Universiteit Nijmegen
154 +
155 +Acknowledgments
156 +This work was supported by the U.S. National Science Foundation under grant
157 +1018836. "Any opinions, findings, and conclusions or recommendations expressed
158 +in this material are those of the author(s) and do not necessarily reflect the
159 +views of the National Science Foundation."
160 +This work was supported by the Netherlands Organisation for Scientific
161 +Research (NWO) under grant 639.073.005 and Veni 2013 project 13114.
162 diff --git a/Makefile.in b/Makefile.in
163 index bc55b7d..aaf7b3b 100644
164 --- a/Makefile.in
165 +++ b/Makefile.in
166 @@ -36,8 +36,9 @@ COMMONOBJS=dbutil.o buffer.o dbhelpers.o \
167 queue.o \
168 atomicio.o compat.o fake-rfc2553.o \
169 ltc_prng.o ecc.o ecdsa.o crypto_desc.o \
170 + curve25519.o ed25519.o \
171 dbmalloc.o \
172 - gensignkey.o gendss.o genrsa.o
173 + gensignkey.o gendss.o genrsa.o gened25519.o
174
175 SVROBJS=svr-kex.o svr-auth.o sshpty.o \
176 svr-authpasswd.o svr-authpubkey.o svr-authpubkeyoptions.o svr-session.o svr-service.o \
177 @@ -52,7 +53,7 @@ CLIOBJS=cli-main.o cli-auth.o cli-authpasswd.o cli-kex.o \
178 CLISVROBJS=common-session.o packet.o common-algo.o common-kex.o \
179 common-channel.o common-chansession.o termcodes.o loginrec.o \
180 tcp-accept.o listener.o process-packet.o dh_groups.o \
181 - common-runopts.o circbuffer.o curve25519-donna.o list.o netio.o
182 + common-runopts.o circbuffer.o list.o netio.o
183
184 KEYOBJS=dropbearkey.o
185
186 @@ -264,7 +265,7 @@ tidy:
187 ## Fuzzing targets
188
189 # list of fuzz targets
190 -FUZZ_TARGETS=fuzzer-preauth fuzzer-pubkey fuzzer-verify fuzzer-preauth_nomaths fuzzer-kexdh fuzzer-kexecdh
191 +FUZZ_TARGETS=fuzzer-preauth fuzzer-pubkey fuzzer-verify fuzzer-preauth_nomaths fuzzer-kexdh fuzzer-kexecdh fuzzer-kexcurve25519
192
193 FUZZER_OPTIONS = $(addsuffix .options, $(FUZZ_TARGETS))
194
195 @@ -303,6 +304,9 @@ fuzzer-kexdh: fuzzer-kexdh.o fuzz-harness.o
196 fuzzer-kexecdh: fuzzer-kexecdh.o fuzz-harness.o
197 $(CXX) $(CXXFLAGS) $@.o $(LDFLAGS) $(svrfuzzobjs) -o $@$(EXEEXT) $(LIBTOM_LIBS) $(LIBS) $(FUZZLIB) @CRYPTLIB@
198
199 +fuzzer-kexcurve25519: fuzzer-kexcurve25519.o fuzz-harness.o
200 + $(CXX) $(CXXFLAGS) $@.o $(LDFLAGS) $(svrfuzzobjs) -o $@$(EXEEXT) $(LIBTOM_LIBS) $(LIBS) $(FUZZLIB) @CRYPTLIB@
201 +
202 fuzzer-%.options: Makefile
203 echo "[libfuzzer]" > $@
204 echo "max_len = 50000" >> $@
205 @@ -313,7 +317,9 @@ fuzz-hostkeys:
206 dropbearkey -t rsa -f keyr
207 dropbearkey -t dss -f keyd
208 dropbearkey -t ecdsa -size 256 -f keye
209 + dropbearkey -t ed25519 -f keyed25519
210 echo > hostkeys.c
211 /usr/bin/xxd -i -a keyr >> hostkeys.c
212 /usr/bin/xxd -i -a keye >> hostkeys.c
213 /usr/bin/xxd -i -a keyd >> hostkeys.c
214 + /usr/bin/xxd -i -a keyed25519 >> hostkeys.c
215 diff --git a/README b/README
216 index b8a6fd2..d197ec7 100644
217 --- a/README
218 +++ b/README
219 @@ -55,6 +55,7 @@ To run the server, you need to generate server keys, this is one-off:
220 ./dropbearkey -t rsa -f dropbear_rsa_host_key
221 ./dropbearkey -t dss -f dropbear_dss_host_key
222 ./dropbearkey -t ecdsa -f dropbear_ecdsa_host_key
223 +./dropbearkey -t ed25519 -f dropbear_ed25519_host_key
224
225 or alternatively convert OpenSSH keys to Dropbear:
226 ./dropbearconvert openssh dropbear /etc/ssh/ssh_host_dsa_key dropbear_dss_host_key
227 diff --git a/cli-kex.c b/cli-kex.c
228 index b02cfc7..7cefb5f 100644
229 --- a/cli-kex.c
230 +++ b/cli-kex.c
231 @@ -81,7 +81,7 @@ void send_msg_kexdh_init() {
232 }
233 cli_ses.curve25519_param = gen_kexcurve25519_param();
234 }
235 - buf_putstring(ses.writepayload, (const char*)cli_ses.curve25519_param->pub, CURVE25519_LEN);
236 + buf_putstring(ses.writepayload, cli_ses.curve25519_param->pub, CURVE25519_LEN);
237 break;
238 #endif
239 }
240 diff --git a/common-algo.c b/common-algo.c
241 index 2f896ab..558aad2 100644
242 --- a/common-algo.c
243 +++ b/common-algo.c
244 @@ -222,6 +222,9 @@ algo_type ssh_nocompress[] = {
245 };
246
247 algo_type sshhostkey[] = {
248 +#if DROPBEAR_ED25519
249 + {"ssh-ed25519", DROPBEAR_SIGNKEY_ED25519, NULL, 1, NULL},
250 +#endif
251 #if DROPBEAR_ECDSA
252 #if DROPBEAR_ECC_256
253 {"ecdsa-sha2-nistp256", DROPBEAR_SIGNKEY_ECDSA_NISTP256, NULL, 1, NULL},
254 diff --git a/common-kex.c b/common-kex.c
255 index d4933dd..16b7e27 100644
256 --- a/common-kex.c
257 +++ b/common-kex.c
258 @@ -36,6 +36,7 @@
259 #include "dbrandom.h"
260 #include "runopts.h"
261 #include "ecc.h"
262 +#include "curve25519.h"
263 #include "crypto_desc.h"
264
265 static void kexinitialise(void);
266 @@ -703,23 +704,18 @@ void kexecdh_comb_key(struct kex_ecdh_param *param, buffer *pub_them,
267 #endif /* DROPBEAR_ECDH */
268
269 #if DROPBEAR_CURVE25519
270 -struct kex_curve25519_param *gen_kexcurve25519_param () {
271 +struct kex_curve25519_param *gen_kexcurve25519_param() {
272 /* Per http://cr.yp.to/ecdh.html */
273 struct kex_curve25519_param *param = m_malloc(sizeof(*param));
274 const unsigned char basepoint[32] = {9};
275
276 genrandom(param->priv, CURVE25519_LEN);
277 - param->priv[0] &= 248;
278 - param->priv[31] &= 127;
279 - param->priv[31] |= 64;
280 -
281 - curve25519_donna(param->pub, param->priv, basepoint);
282 + dropbear_curve25519_scalarmult(param->pub, param->priv, basepoint);
283
284 return param;
285 }
286
287 -void free_kexcurve25519_param(struct kex_curve25519_param *param)
288 -{
289 +void free_kexcurve25519_param(struct kex_curve25519_param *param) {
290 m_burn(param->priv, CURVE25519_LEN);
291 m_free(param);
292 }
293 @@ -736,7 +732,7 @@ void kexcurve25519_comb_key(const struct kex_curve25519_param *param, const buff
294 dropbear_exit("Bad curve25519");
295 }
296
297 - curve25519_donna(out, param->priv, buf_pub_them->data);
298 + dropbear_curve25519_scalarmult(out, param->priv, buf_pub_them->data);
299
300 if (constant_time_memcmp(zeroes, out, CURVE25519_LEN) == 0) {
301 dropbear_exit("Bad curve25519");
302 diff --git a/curve25519-donna.c b/curve25519-donna.c
303 deleted file mode 100644
304 index ef0b6d1..0000000
305 --- a/curve25519-donna.c
306 +++ /dev/null
307 @@ -1,860 +0,0 @@
308 -/* Copyright 2008, Google Inc.
309 - * All rights reserved.
310 - *
311 - * Redistribution and use in source and binary forms, with or without
312 - * modification, are permitted provided that the following conditions are
313 - * met:
314 - *
315 - * * Redistributions of source code must retain the above copyright
316 - * notice, this list of conditions and the following disclaimer.
317 - * * Redistributions in binary form must reproduce the above
318 - * copyright notice, this list of conditions and the following disclaimer
319 - * in the documentation and/or other materials provided with the
320 - * distribution.
321 - * * Neither the name of Google Inc. nor the names of its
322 - * contributors may be used to endorse or promote products derived from
323 - * this software without specific prior written permission.
324 - *
325 - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
326 - * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
327 - * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
328 - * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
329 - * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
330 - * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
331 - * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
332 - * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
333 - * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
334 - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
335 - * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
336 - *
337 - * curve25519-donna: Curve25519 elliptic curve, public key function
338 - *
339 - * http://code.google.com/p/curve25519-donna/
340 - *
341 - * Adam Langley <agl@imperialviolet.org>
342 - *
343 - * Derived from public domain C code by Daniel J. Bernstein <djb@cr.yp.to>
344 - *
345 - * More information about curve25519 can be found here
346 - * http://cr.yp.to/ecdh.html
347 - *
348 - * djb's sample implementation of curve25519 is written in a special assembly
349 - * language called qhasm and uses the floating point registers.
350 - *
351 - * This is, almost, a clean room reimplementation from the curve25519 paper. It
352 - * uses many of the tricks described therein. Only the crecip function is taken
353 - * from the sample implementation. */
354 -
355 -#include <string.h>
356 -#include <stdint.h>
357 -
358 -#ifdef _MSC_VER
359 -#define inline __inline
360 -#endif
361 -
362 -typedef uint8_t u8;
363 -typedef int32_t s32;
364 -typedef int64_t limb;
365 -
366 -/* Field element representation:
367 - *
368 - * Field elements are written as an array of signed, 64-bit limbs, least
369 - * significant first. The value of the field element is:
370 - * x[0] + 2^26·x[1] + x^51·x[2] + 2^102·x[3] + ...
371 - *
372 - * i.e. the limbs are 26, 25, 26, 25, ... bits wide. */
373 -
374 -/* Sum two numbers: output += in */
375 -static void fsum(limb *output, const limb *in) {
376 - unsigned i;
377 - for (i = 0; i < 10; i += 2) {
378 - output[0+i] = output[0+i] + in[0+i];
379 - output[1+i] = output[1+i] + in[1+i];
380 - }
381 -}
382 -
383 -/* Find the difference of two numbers: output = in - output
384 - * (note the order of the arguments!). */
385 -static void fdifference(limb *output, const limb *in) {
386 - unsigned i;
387 - for (i = 0; i < 10; ++i) {
388 - output[i] = in[i] - output[i];
389 - }
390 -}
391 -
392 -/* Multiply a number by a scalar: output = in * scalar */
393 -static void fscalar_product(limb *output, const limb *in, const limb scalar) {
394 - unsigned i;
395 - for (i = 0; i < 10; ++i) {
396 - output[i] = in[i] * scalar;
397 - }
398 -}
399 -
400 -/* Multiply two numbers: output = in2 * in
401 - *
402 - * output must be distinct to both inputs. The inputs are reduced coefficient
403 - * form, the output is not.
404 - *
405 - * output[x] <= 14 * the largest product of the input limbs. */
406 -static void fproduct(limb *output, const limb *in2, const limb *in) {
407 - output[0] = ((limb) ((s32) in2[0])) * ((s32) in[0]);
408 - output[1] = ((limb) ((s32) in2[0])) * ((s32) in[1]) +
409 - ((limb) ((s32) in2[1])) * ((s32) in[0]);
410 - output[2] = 2 * ((limb) ((s32) in2[1])) * ((s32) in[1]) +
411 - ((limb) ((s32) in2[0])) * ((s32) in[2]) +
412 - ((limb) ((s32) in2[2])) * ((s32) in[0]);
413 - output[3] = ((limb) ((s32) in2[1])) * ((s32) in[2]) +
414 - ((limb) ((s32) in2[2])) * ((s32) in[1]) +
415 - ((limb) ((s32) in2[0])) * ((s32) in[3]) +
416 - ((limb) ((s32) in2[3])) * ((s32) in[0]);
417 - output[4] = ((limb) ((s32) in2[2])) * ((s32) in[2]) +
418 - 2 * (((limb) ((s32) in2[1])) * ((s32) in[3]) +
419 - ((limb) ((s32) in2[3])) * ((s32) in[1])) +
420 - ((limb) ((s32) in2[0])) * ((s32) in[4]) +
421 - ((limb) ((s32) in2[4])) * ((s32) in[0]);
422 - output[5] = ((limb) ((s32) in2[2])) * ((s32) in[3]) +
423 - ((limb) ((s32) in2[3])) * ((s32) in[2]) +
424 - ((limb) ((s32) in2[1])) * ((s32) in[4]) +
425 - ((limb) ((s32) in2[4])) * ((s32) in[1]) +
426 - ((limb) ((s32) in2[0])) * ((s32) in[5]) +
427 - ((limb) ((s32) in2[5])) * ((s32) in[0]);
428 - output[6] = 2 * (((limb) ((s32) in2[3])) * ((s32) in[3]) +
429 - ((limb) ((s32) in2[1])) * ((s32) in[5]) +
430 - ((limb) ((s32) in2[5])) * ((s32) in[1])) +
431 - ((limb) ((s32) in2[2])) * ((s32) in[4]) +
432 - ((limb) ((s32) in2[4])) * ((s32) in[2]) +
433 - ((limb) ((s32) in2[0])) * ((s32) in[6]) +
434 - ((limb) ((s32) in2[6])) * ((s32) in[0]);
435 - output[7] = ((limb) ((s32) in2[3])) * ((s32) in[4]) +
436 - ((limb) ((s32) in2[4])) * ((s32) in[3]) +
437 - ((limb) ((s32) in2[2])) * ((s32) in[5]) +
438 - ((limb) ((s32) in2[5])) * ((s32) in[2]) +
439 - ((limb) ((s32) in2[1])) * ((s32) in[6]) +
440 - ((limb) ((s32) in2[6])) * ((s32) in[1]) +
441 - ((limb) ((s32) in2[0])) * ((s32) in[7]) +
442 - ((limb) ((s32) in2[7])) * ((s32) in[0]);
443 - output[8] = ((limb) ((s32) in2[4])) * ((s32) in[4]) +
444 - 2 * (((limb) ((s32) in2[3])) * ((s32) in[5]) +
445 - ((limb) ((s32) in2[5])) * ((s32) in[3]) +
446 - ((limb) ((s32) in2[1])) * ((s32) in[7]) +
447 - ((limb) ((s32) in2[7])) * ((s32) in[1])) +
448 - ((limb) ((s32) in2[2])) * ((s32) in[6]) +
449 - ((limb) ((s32) in2[6])) * ((s32) in[2]) +
450 - ((limb) ((s32) in2[0])) * ((s32) in[8]) +
451 - ((limb) ((s32) in2[8])) * ((s32) in[0]);
452 - output[9] = ((limb) ((s32) in2[4])) * ((s32) in[5]) +
453 - ((limb) ((s32) in2[5])) * ((s32) in[4]) +
454 - ((limb) ((s32) in2[3])) * ((s32) in[6]) +
455 - ((limb) ((s32) in2[6])) * ((s32) in[3]) +
456 - ((limb) ((s32) in2[2])) * ((s32) in[7]) +
457 - ((limb) ((s32) in2[7])) * ((s32) in[2]) +
458 - ((limb) ((s32) in2[1])) * ((s32) in[8]) +
459 - ((limb) ((s32) in2[8])) * ((s32) in[1]) +
460 - ((limb) ((s32) in2[0])) * ((s32) in[9]) +
461 - ((limb) ((s32) in2[9])) * ((s32) in[0]);
462 - output[10] = 2 * (((limb) ((s32) in2[5])) * ((s32) in[5]) +
463 - ((limb) ((s32) in2[3])) * ((s32) in[7]) +
464 - ((limb) ((s32) in2[7])) * ((s32) in[3]) +
465 - ((limb) ((s32) in2[1])) * ((s32) in[9]) +
466 - ((limb) ((s32) in2[9])) * ((s32) in[1])) +
467 - ((limb) ((s32) in2[4])) * ((s32) in[6]) +
468 - ((limb) ((s32) in2[6])) * ((s32) in[4]) +
469 - ((limb) ((s32) in2[2])) * ((s32) in[8]) +
470 - ((limb) ((s32) in2[8])) * ((s32) in[2]);
471 - output[11] = ((limb) ((s32) in2[5])) * ((s32) in[6]) +
472 - ((limb) ((s32) in2[6])) * ((s32) in[5]) +
473 - ((limb) ((s32) in2[4])) * ((s32) in[7]) +
474 - ((limb) ((s32) in2[7])) * ((s32) in[4]) +
475 - ((limb) ((s32) in2[3])) * ((s32) in[8]) +
476 - ((limb) ((s32) in2[8])) * ((s32) in[3]) +
477 - ((limb) ((s32) in2[2])) * ((s32) in[9]) +
478 - ((limb) ((s32) in2[9])) * ((s32) in[2]);
479 - output[12] = ((limb) ((s32) in2[6])) * ((s32) in[6]) +
480 - 2 * (((limb) ((s32) in2[5])) * ((s32) in[7]) +
481 - ((limb) ((s32) in2[7])) * ((s32) in[5]) +
482 - ((limb) ((s32) in2[3])) * ((s32) in[9]) +
483 - ((limb) ((s32) in2[9])) * ((s32) in[3])) +
484 - ((limb) ((s32) in2[4])) * ((s32) in[8]) +
485 - ((limb) ((s32) in2[8])) * ((s32) in[4]);
486 - output[13] = ((limb) ((s32) in2[6])) * ((s32) in[7]) +
487 - ((limb) ((s32) in2[7])) * ((s32) in[6]) +
488 - ((limb) ((s32) in2[5])) * ((s32) in[8]) +
489 - ((limb) ((s32) in2[8])) * ((s32) in[5]) +
490 - ((limb) ((s32) in2[4])) * ((s32) in[9]) +
491 - ((limb) ((s32) in2[9])) * ((s32) in[4]);
492 - output[14] = 2 * (((limb) ((s32) in2[7])) * ((s32) in[7]) +
493 - ((limb) ((s32) in2[5])) * ((s32) in[9]) +
494 - ((limb) ((s32) in2[9])) * ((s32) in[5])) +
495 - ((limb) ((s32) in2[6])) * ((s32) in[8]) +
496 - ((limb) ((s32) in2[8])) * ((s32) in[6]);
497 - output[15] = ((limb) ((s32) in2[7])) * ((s32) in[8]) +
498 - ((limb) ((s32) in2[8])) * ((s32) in[7]) +
499 - ((limb) ((s32) in2[6])) * ((s32) in[9]) +
500 - ((limb) ((s32) in2[9])) * ((s32) in[6]);
501 - output[16] = ((limb) ((s32) in2[8])) * ((s32) in[8]) +
502 - 2 * (((limb) ((s32) in2[7])) * ((s32) in[9]) +
503 - ((limb) ((s32) in2[9])) * ((s32) in[7]));
504 - output[17] = ((limb) ((s32) in2[8])) * ((s32) in[9]) +
505 - ((limb) ((s32) in2[9])) * ((s32) in[8]);
506 - output[18] = 2 * ((limb) ((s32) in2[9])) * ((s32) in[9]);
507 -}
508 -
509 -/* Reduce a long form to a short form by taking the input mod 2^255 - 19.
510 - *
511 - * On entry: |output[i]| < 14*2^54
512 - * On exit: |output[0..8]| < 280*2^54 */
513 -static void freduce_degree(limb *output) {
514 - /* Each of these shifts and adds ends up multiplying the value by 19.
515 - *
516 - * For output[0..8], the absolute entry value is < 14*2^54 and we add, at
517 - * most, 19*14*2^54 thus, on exit, |output[0..8]| < 280*2^54. */
518 - output[8] += output[18] << 4;
519 - output[8] += output[18] << 1;
520 - output[8] += output[18];
521 - output[7] += output[17] << 4;
522 - output[7] += output[17] << 1;
523 - output[7] += output[17];
524 - output[6] += output[16] << 4;
525 - output[6] += output[16] << 1;
526 - output[6] += output[16];
527 - output[5] += output[15] << 4;
528 - output[5] += output[15] << 1;
529 - output[5] += output[15];
530 - output[4] += output[14] << 4;
531 - output[4] += output[14] << 1;
532 - output[4] += output[14];
533 - output[3] += output[13] << 4;
534 - output[3] += output[13] << 1;
535 - output[3] += output[13];
536 - output[2] += output[12] << 4;
537 - output[2] += output[12] << 1;
538 - output[2] += output[12];
539 - output[1] += output[11] << 4;
540 - output[1] += output[11] << 1;
541 - output[1] += output[11];
542 - output[0] += output[10] << 4;
543 - output[0] += output[10] << 1;
544 - output[0] += output[10];
545 -}
546 -
547 -#if (-1 & 3) != 3
548 -#error "This code only works on a two's complement system"
549 -#endif
550 -
551 -/* return v / 2^26, using only shifts and adds.
552 - *
553 - * On entry: v can take any value. */
554 -static inline limb
555 -div_by_2_26(const limb v)
556 -{
557 - /* High word of v; no shift needed. */
558 - const uint32_t highword = (uint32_t) (((uint64_t) v) >> 32);
559 - /* Set to all 1s if v was negative; else set to 0s. */
560 - const int32_t sign = ((int32_t) highword) >> 31;
561 - /* Set to 0x3ffffff if v was negative; else set to 0. */
562 - const int32_t roundoff = ((uint32_t) sign) >> 6;
563 - /* Should return v / (1<<26) */
564 - return (v + roundoff) >> 26;
565 -}
566 -
567 -/* return v / (2^25), using only shifts and adds.
568 - *
569 - * On entry: v can take any value. */
570 -static inline limb
571 -div_by_2_25(const limb v)
572 -{
573 - /* High word of v; no shift needed*/
574 - const uint32_t highword = (uint32_t) (((uint64_t) v) >> 32);
575 - /* Set to all 1s if v was negative; else set to 0s. */
576 - const int32_t sign = ((int32_t) highword) >> 31;
577 - /* Set to 0x1ffffff if v was negative; else set to 0. */
578 - const int32_t roundoff = ((uint32_t) sign) >> 7;
579 - /* Should return v / (1<<25) */
580 - return (v + roundoff) >> 25;
581 -}
582 -
583 -/* Reduce all coefficients of the short form input so that |x| < 2^26.
584 - *
585 - * On entry: |output[i]| < 280*2^54 */
586 -static void freduce_coefficients(limb *output) {
587 - unsigned i;
588 -
589 - output[10] = 0;
590 -
591 - for (i = 0; i < 10; i += 2) {
592 - limb over = div_by_2_26(output[i]);
593 - /* The entry condition (that |output[i]| < 280*2^54) means that over is, at
594 - * most, 280*2^28 in the first iteration of this loop. This is added to the
595 - * next limb and we can approximate the resulting bound of that limb by
596 - * 281*2^54. */
597 - output[i] -= over << 26;
598 - output[i+1] += over;
599 -
600 - /* For the first iteration, |output[i+1]| < 281*2^54, thus |over| <
601 - * 281*2^29. When this is added to the next limb, the resulting bound can
602 - * be approximated as 281*2^54.
603 - *
604 - * For subsequent iterations of the loop, 281*2^54 remains a conservative
605 - * bound and no overflow occurs. */
606 - over = div_by_2_25(output[i+1]);
607 - output[i+1] -= over << 25;
608 - output[i+2] += over;
609 - }
610 - /* Now |output[10]| < 281*2^29 and all other coefficients are reduced. */
611 - output[0] += output[10] << 4;
612 - output[0] += output[10] << 1;
613 - output[0] += output[10];
614 -
615 - output[10] = 0;
616 -
617 - /* Now output[1..9] are reduced, and |output[0]| < 2^26 + 19*281*2^29
618 - * So |over| will be no more than 2^16. */
619 - {
620 - limb over = div_by_2_26(output[0]);
621 - output[0] -= over << 26;
622 - output[1] += over;
623 - }
624 -
625 - /* Now output[0,2..9] are reduced, and |output[1]| < 2^25 + 2^16 < 2^26. The
626 - * bound on |output[1]| is sufficient to meet our needs. */
627 -}
628 -
629 -/* A helpful wrapper around fproduct: output = in * in2.
630 - *
631 - * On entry: |in[i]| < 2^27 and |in2[i]| < 2^27.
632 - *
633 - * output must be distinct to both inputs. The output is reduced degree
634 - * (indeed, one need only provide storage for 10 limbs) and |output[i]| < 2^26. */
635 -static void
636 -fmul(limb *output, const limb *in, const limb *in2) {
637 - limb t[19];
638 - fproduct(t, in, in2);
639 - /* |t[i]| < 14*2^54 */
640 - freduce_degree(t);
641 - freduce_coefficients(t);
642 - /* |t[i]| < 2^26 */
643 - memcpy(output, t, sizeof(limb) * 10);
644 -}
645 -
646 -/* Square a number: output = in**2
647 - *
648 - * output must be distinct from the input. The inputs are reduced coefficient
649 - * form, the output is not.
650 - *
651 - * output[x] <= 14 * the largest product of the input limbs. */
652 -static void fsquare_inner(limb *output, const limb *in) {
653 - output[0] = ((limb) ((s32) in[0])) * ((s32) in[0]);
654 - output[1] = 2 * ((limb) ((s32) in[0])) * ((s32) in[1]);
655 - output[2] = 2 * (((limb) ((s32) in[1])) * ((s32) in[1]) +
656 - ((limb) ((s32) in[0])) * ((s32) in[2]));
657 - output[3] = 2 * (((limb) ((s32) in[1])) * ((s32) in[2]) +
658 - ((limb) ((s32) in[0])) * ((s32) in[3]));
659 - output[4] = ((limb) ((s32) in[2])) * ((s32) in[2]) +
660 - 4 * ((limb) ((s32) in[1])) * ((s32) in[3]) +
661 - 2 * ((limb) ((s32) in[0])) * ((s32) in[4]);
662 - output[5] = 2 * (((limb) ((s32) in[2])) * ((s32) in[3]) +
663 - ((limb) ((s32) in[1])) * ((s32) in[4]) +
664 - ((limb) ((s32) in[0])) * ((s32) in[5]));
665 - output[6] = 2 * (((limb) ((s32) in[3])) * ((s32) in[3]) +
666 - ((limb) ((s32) in[2])) * ((s32) in[4]) +
667 - ((limb) ((s32) in[0])) * ((s32) in[6]) +
668 - 2 * ((limb) ((s32) in[1])) * ((s32) in[5]));
669 - output[7] = 2 * (((limb) ((s32) in[3])) * ((s32) in[4]) +
670 - ((limb) ((s32) in[2])) * ((s32) in[5]) +
671 - ((limb) ((s32) in[1])) * ((s32) in[6]) +
672 - ((limb) ((s32) in[0])) * ((s32) in[7]));
673 - output[8] = ((limb) ((s32) in[4])) * ((s32) in[4]) +
674 - 2 * (((limb) ((s32) in[2])) * ((s32) in[6]) +
675 - ((limb) ((s32) in[0])) * ((s32) in[8]) +
676 - 2 * (((limb) ((s32) in[1])) * ((s32) in[7]) +
677 - ((limb) ((s32) in[3])) * ((s32) in[5])));
678 - output[9] = 2 * (((limb) ((s32) in[4])) * ((s32) in[5]) +
679 - ((limb) ((s32) in[3])) * ((s32) in[6]) +
680 - ((limb) ((s32) in[2])) * ((s32) in[7]) +
681 - ((limb) ((s32) in[1])) * ((s32) in[8]) +
682 - ((limb) ((s32) in[0])) * ((s32) in[9]));
683 - output[10] = 2 * (((limb) ((s32) in[5])) * ((s32) in[5]) +
684 - ((limb) ((s32) in[4])) * ((s32) in[6]) +
685 - ((limb) ((s32) in[2])) * ((s32) in[8]) +
686 - 2 * (((limb) ((s32) in[3])) * ((s32) in[7]) +
687 - ((limb) ((s32) in[1])) * ((s32) in[9])));
688 - output[11] = 2 * (((limb) ((s32) in[5])) * ((s32) in[6]) +
689 - ((limb) ((s32) in[4])) * ((s32) in[7]) +
690 - ((limb) ((s32) in[3])) * ((s32) in[8]) +
691 - ((limb) ((s32) in[2])) * ((s32) in[9]));
692 - output[12] = ((limb) ((s32) in[6])) * ((s32) in[6]) +
693 - 2 * (((limb) ((s32) in[4])) * ((s32) in[8]) +
694 - 2 * (((limb) ((s32) in[5])) * ((s32) in[7]) +
695 - ((limb) ((s32) in[3])) * ((s32) in[9])));
696 - output[13] = 2 * (((limb) ((s32) in[6])) * ((s32) in[7]) +
697 - ((limb) ((s32) in[5])) * ((s32) in[8]) +
698 - ((limb) ((s32) in[4])) * ((s32) in[9]));
699 - output[14] = 2 * (((limb) ((s32) in[7])) * ((s32) in[7]) +
700 - ((limb) ((s32) in[6])) * ((s32) in[8]) +
701 - 2 * ((limb) ((s32) in[5])) * ((s32) in[9]));
702 - output[15] = 2 * (((limb) ((s32) in[7])) * ((s32) in[8]) +
703 - ((limb) ((s32) in[6])) * ((s32) in[9]));
704 - output[16] = ((limb) ((s32) in[8])) * ((s32) in[8]) +
705 - 4 * ((limb) ((s32) in[7])) * ((s32) in[9]);
706 - output[17] = 2 * ((limb) ((s32) in[8])) * ((s32) in[9]);
707 - output[18] = 2 * ((limb) ((s32) in[9])) * ((s32) in[9]);
708 -}
709 -
710 -/* fsquare sets output = in^2.
711 - *
712 - * On entry: The |in| argument is in reduced coefficients form and |in[i]| <
713 - * 2^27.
714 - *
715 - * On exit: The |output| argument is in reduced coefficients form (indeed, one
716 - * need only provide storage for 10 limbs) and |out[i]| < 2^26. */
717 -static void
718 -fsquare(limb *output, const limb *in) {
719 - limb t[19];
720 - fsquare_inner(t, in);
721 - /* |t[i]| < 14*2^54 because the largest product of two limbs will be <
722 - * 2^(27+27) and fsquare_inner adds together, at most, 14 of those
723 - * products. */
724 - freduce_degree(t);
725 - freduce_coefficients(t);
726 - /* |t[i]| < 2^26 */
727 - memcpy(output, t, sizeof(limb) * 10);
728 -}
729 -
730 -/* Take a little-endian, 32-byte number and expand it into polynomial form */
731 -static void
732 -fexpand(limb *output, const u8 *input) {
733 -#define F(n,start,shift,mask) \
734 - output[n] = ((((limb) input[start + 0]) | \
735 - ((limb) input[start + 1]) << 8 | \
736 - ((limb) input[start + 2]) << 16 | \
737 - ((limb) input[start + 3]) << 24) >> shift) & mask;
738 - F(0, 0, 0, 0x3ffffff);
739 - F(1, 3, 2, 0x1ffffff);
740 - F(2, 6, 3, 0x3ffffff);
741 - F(3, 9, 5, 0x1ffffff);
742 - F(4, 12, 6, 0x3ffffff);
743 - F(5, 16, 0, 0x1ffffff);
744 - F(6, 19, 1, 0x3ffffff);
745 - F(7, 22, 3, 0x1ffffff);
746 - F(8, 25, 4, 0x3ffffff);
747 - F(9, 28, 6, 0x1ffffff);
748 -#undef F
749 -}
750 -
751 -#if (-32 >> 1) != -16
752 -#error "This code only works when >> does sign-extension on negative numbers"
753 -#endif
754 -
755 -/* s32_eq returns 0xffffffff iff a == b and zero otherwise. */
756 -static s32 s32_eq(s32 a, s32 b) {
757 - a = ~(a ^ b);
758 - a &= a << 16;
759 - a &= a << 8;
760 - a &= a << 4;
761 - a &= a << 2;
762 - a &= a << 1;
763 - return a >> 31;
764 -}
765 -
766 -/* s32_gte returns 0xffffffff if a >= b and zero otherwise, where a and b are
767 - * both non-negative. */
768 -static s32 s32_gte(s32 a, s32 b) {
769 - a -= b;
770 - /* a >= 0 iff a >= b. */
771 - return ~(a >> 31);
772 -}
773 -
774 -/* Take a fully reduced polynomial form number and contract it into a
775 - * little-endian, 32-byte array.
776 - *
777 - * On entry: |input_limbs[i]| < 2^26 */
778 -static void
779 -fcontract(u8 *output, limb *input_limbs) {
780 - int i;
781 - int j;
782 - s32 input[10];
783 - s32 mask;
784 -
785 - /* |input_limbs[i]| < 2^26, so it's valid to convert to an s32. */
786 - for (i = 0; i < 10; i++) {
787 - input[i] = input_limbs[i];
788 - }
789 -
790 - for (j = 0; j < 2; ++j) {
791 - for (i = 0; i < 9; ++i) {
792 - if ((i & 1) == 1) {
793 - /* This calculation is a time-invariant way to make input[i]
794 - * non-negative by borrowing from the next-larger limb. */
795 - const s32 mask = input[i] >> 31;
796 - const s32 carry = -((input[i] & mask) >> 25);
797 - input[i] = input[i] + (carry << 25);
798 - input[i+1] = input[i+1] - carry;
799 - } else {
800 - const s32 mask = input[i] >> 31;
801 - const s32 carry = -((input[i] & mask) >> 26);
802 - input[i] = input[i] + (carry << 26);
803 - input[i+1] = input[i+1] - carry;
804 - }
805 - }
806 -
807 - /* There's no greater limb for input[9] to borrow from, but we can multiply
808 - * by 19 and borrow from input[0], which is valid mod 2^255-19. */
809 - {
810 - const s32 mask = input[9] >> 31;
811 - const s32 carry = -((input[9] & mask) >> 25);
812 - input[9] = input[9] + (carry << 25);
813 - input[0] = input[0] - (carry * 19);
814 - }
815 -
816 - /* After the first iteration, input[1..9] are non-negative and fit within
817 - * 25 or 26 bits, depending on position. However, input[0] may be
818 - * negative. */
819 - }
820 -
821 - /* The first borrow-propagation pass above ended with every limb
822 - except (possibly) input[0] non-negative.
823 -
824 - If input[0] was negative after the first pass, then it was because of a
825 - carry from input[9]. On entry, input[9] < 2^26 so the carry was, at most,
826 - one, since (2**26-1) >> 25 = 1. Thus input[0] >= -19.
827 -
828 - In the second pass, each limb is decreased by at most one. Thus the second
829 - borrow-propagation pass could only have wrapped around to decrease
830 - input[0] again if the first pass left input[0] negative *and* input[1]
831 - through input[9] were all zero. In that case, input[1] is now 2^25 - 1,
832 - and this last borrow-propagation step will leave input[1] non-negative. */
833 - {
834 - const s32 mask = input[0] >> 31;
835 - const s32 carry = -((input[0] & mask) >> 26);
836 - input[0] = input[0] + (carry << 26);
837 - input[1] = input[1] - carry;
838 - }
839 -
840 - /* All input[i] are now non-negative. However, there might be values between
841 - * 2^25 and 2^26 in a limb which is, nominally, 25 bits wide. */
842 - for (j = 0; j < 2; j++) {
843 - for (i = 0; i < 9; i++) {
844 - if ((i & 1) == 1) {
845 - const s32 carry = input[i] >> 25;
846 - input[i] &= 0x1ffffff;
847 - input[i+1] += carry;
848 - } else {
849 - const s32 carry = input[i] >> 26;
850 - input[i] &= 0x3ffffff;
851 - input[i+1] += carry;
852 - }
853 - }
854 -
855 - {
856 - const s32 carry = input[9] >> 25;
857 - input[9] &= 0x1ffffff;
858 - input[0] += 19*carry;
859 - }
860 - }
861 -
862 - /* If the first carry-chain pass, just above, ended up with a carry from
863 - * input[9], and that caused input[0] to be out-of-bounds, then input[0] was
864 - * < 2^26 + 2*19, because the carry was, at most, two.
865 - *
866 - * If the second pass carried from input[9] again then input[0] is < 2*19 and
867 - * the input[9] -> input[0] carry didn't push input[0] out of bounds. */
868 -
869 - /* It still remains the case that input might be between 2^255-19 and 2^255.
870 - * In this case, input[1..9] must take their maximum value and input[0] must
871 - * be >= (2^255-19) & 0x3ffffff, which is 0x3ffffed. */
872 - mask = s32_gte(input[0], 0x3ffffed);
873 - for (i = 1; i < 10; i++) {
874 - if ((i & 1) == 1) {
875 - mask &= s32_eq(input[i], 0x1ffffff);
876 - } else {
877 - mask &= s32_eq(input[i], 0x3ffffff);
878 - }
879 - }
880 -
881 - /* mask is either 0xffffffff (if input >= 2^255-19) and zero otherwise. Thus
882 - * this conditionally subtracts 2^255-19. */
883 - input[0] -= mask & 0x3ffffed;
884 -
885 - for (i = 1; i < 10; i++) {
886 - if ((i & 1) == 1) {
887 - input[i] -= mask & 0x1ffffff;
888 - } else {
889 - input[i] -= mask & 0x3ffffff;
890 - }
891 - }
892 -
893 - input[1] <<= 2;
894 - input[2] <<= 3;
895 - input[3] <<= 5;
896 - input[4] <<= 6;
897 - input[6] <<= 1;
898 - input[7] <<= 3;
899 - input[8] <<= 4;
900 - input[9] <<= 6;
901 -#define F(i, s) \
902 - output[s+0] |= input[i] & 0xff; \
903 - output[s+1] = (input[i] >> 8) & 0xff; \
904 - output[s+2] = (input[i] >> 16) & 0xff; \
905 - output[s+3] = (input[i] >> 24) & 0xff;
906 - output[0] = 0;
907 - output[16] = 0;
908 - F(0,0);
909 - F(1,3);
910 - F(2,6);
911 - F(3,9);
912 - F(4,12);
913 - F(5,16);
914 - F(6,19);
915 - F(7,22);
916 - F(8,25);
917 - F(9,28);
918 -#undef F
919 -}
920 -
921 -/* Input: Q, Q', Q-Q'
922 - * Output: 2Q, Q+Q'
923 - *
924 - * x2 z3: long form
925 - * x3 z3: long form
926 - * x z: short form, destroyed
927 - * xprime zprime: short form, destroyed
928 - * qmqp: short form, preserved
929 - *
930 - * On entry and exit, the absolute value of the limbs of all inputs and outputs
931 - * are < 2^26. */
932 -static void fmonty(limb *x2, limb *z2, /* output 2Q */
933 - limb *x3, limb *z3, /* output Q + Q' */
934 - limb *x, limb *z, /* input Q */
935 - limb *xprime, limb *zprime, /* input Q' */
936 - const limb *qmqp /* input Q - Q' */) {
937 - limb origx[10], origxprime[10], zzz[19], xx[19], zz[19], xxprime[19],
938 - zzprime[19], zzzprime[19], xxxprime[19];
939 -
940 - memcpy(origx, x, 10 * sizeof(limb));
941 - fsum(x, z);
942 - /* |x[i]| < 2^27 */
943 - fdifference(z, origx); /* does x - z */
944 - /* |z[i]| < 2^27 */
945 -
946 - memcpy(origxprime, xprime, sizeof(limb) * 10);
947 - fsum(xprime, zprime);
948 - /* |xprime[i]| < 2^27 */
949 - fdifference(zprime, origxprime);
950 - /* |zprime[i]| < 2^27 */
951 - fproduct(xxprime, xprime, z);
952 - /* |xxprime[i]| < 14*2^54: the largest product of two limbs will be <
953 - * 2^(27+27) and fproduct adds together, at most, 14 of those products.
954 - * (Approximating that to 2^58 doesn't work out.) */
955 - fproduct(zzprime, x, zprime);
956 - /* |zzprime[i]| < 14*2^54 */
957 - freduce_degree(xxprime);
958 - freduce_coefficients(xxprime);
959 - /* |xxprime[i]| < 2^26 */
960 - freduce_degree(zzprime);
961 - freduce_coefficients(zzprime);
962 - /* |zzprime[i]| < 2^26 */
963 - memcpy(origxprime, xxprime, sizeof(limb) * 10);
964 - fsum(xxprime, zzprime);
965 - /* |xxprime[i]| < 2^27 */
966 - fdifference(zzprime, origxprime);
967 - /* |zzprime[i]| < 2^27 */
968 - fsquare(xxxprime, xxprime);
969 - /* |xxxprime[i]| < 2^26 */
970 - fsquare(zzzprime, zzprime);
971 - /* |zzzprime[i]| < 2^26 */
972 - fproduct(zzprime, zzzprime, qmqp);
973 - /* |zzprime[i]| < 14*2^52 */
974 - freduce_degree(zzprime);
975 - freduce_coefficients(zzprime);
976 - /* |zzprime[i]| < 2^26 */
977 - memcpy(x3, xxxprime, sizeof(limb) * 10);
978 - memcpy(z3, zzprime, sizeof(limb) * 10);
979 -
980 - fsquare(xx, x);
981 - /* |xx[i]| < 2^26 */
982 - fsquare(zz, z);
983 - /* |zz[i]| < 2^26 */
984 - fproduct(x2, xx, zz);
985 - /* |x2[i]| < 14*2^52 */
986 - freduce_degree(x2);
987 - freduce_coefficients(x2);
988 - /* |x2[i]| < 2^26 */
989 - fdifference(zz, xx); /* does zz = xx - zz */
990 - /* |zz[i]| < 2^27 */
991 - memset(zzz + 10, 0, sizeof(limb) * 9);
992 - fscalar_product(zzz, zz, 121665);
993 - /* |zzz[i]| < 2^(27+17) */
994 - /* No need to call freduce_degree here:
995 - fscalar_product doesn't increase the degree of its input. */
996 - freduce_coefficients(zzz);
997 - /* |zzz[i]| < 2^26 */
998 - fsum(zzz, xx);
999 - /* |zzz[i]| < 2^27 */
1000 - fproduct(z2, zz, zzz);
1001 - /* |z2[i]| < 14*2^(26+27) */
1002 - freduce_degree(z2);
1003 - freduce_coefficients(z2);
1004 - /* |z2|i| < 2^26 */
1005 -}
1006 -
1007 -/* Conditionally swap two reduced-form limb arrays if 'iswap' is 1, but leave
1008 - * them unchanged if 'iswap' is 0. Runs in data-invariant time to avoid
1009 - * side-channel attacks.
1010 - *
1011 - * NOTE that this function requires that 'iswap' be 1 or 0; other values give
1012 - * wrong results. Also, the two limb arrays must be in reduced-coefficient,
1013 - * reduced-degree form: the values in a[10..19] or b[10..19] aren't swapped,
1014 - * and all all values in a[0..9],b[0..9] must have magnitude less than
1015 - * INT32_MAX. */
1016 -static void
1017 -swap_conditional(limb a[19], limb b[19], limb iswap) {
1018 - unsigned i;
1019 - const s32 swap = (s32) -iswap;
1020 -
1021 - for (i = 0; i < 10; ++i) {
1022 - const s32 x = swap & ( ((s32)a[i]) ^ ((s32)b[i]) );
1023 - a[i] = ((s32)a[i]) ^ x;
1024 - b[i] = ((s32)b[i]) ^ x;
1025 - }
1026 -}
1027 -
1028 -/* Calculates nQ where Q is the x-coordinate of a point on the curve
1029 - *
1030 - * resultx/resultz: the x coordinate of the resulting curve point (short form)
1031 - * n: a little endian, 32-byte number
1032 - * q: a point of the curve (short form) */
1033 -static void
1034 -cmult(limb *resultx, limb *resultz, const u8 *n, const limb *q) {
1035 - limb a[19] = {0}, b[19] = {1}, c[19] = {1}, d[19] = {0};
1036 - limb *nqpqx = a, *nqpqz = b, *nqx = c, *nqz = d, *t;
1037 - limb e[19] = {0}, f[19] = {1}, g[19] = {0}, h[19] = {1};
1038 - limb *nqpqx2 = e, *nqpqz2 = f, *nqx2 = g, *nqz2 = h;
1039 -
1040 - unsigned i, j;
1041 -
1042 - memcpy(nqpqx, q, sizeof(limb) * 10);
1043 -
1044 - for (i = 0; i < 32; ++i) {
1045 - u8 byte = n[31 - i];
1046 - for (j = 0; j < 8; ++j) {
1047 - const limb bit = byte >> 7;
1048 -
1049 - swap_conditional(nqx, nqpqx, bit);
1050 - swap_conditional(nqz, nqpqz, bit);
1051 - fmonty(nqx2, nqz2,
1052 - nqpqx2, nqpqz2,
1053 - nqx, nqz,
1054 - nqpqx, nqpqz,
1055 - q);
1056 - swap_conditional(nqx2, nqpqx2, bit);
1057 - swap_conditional(nqz2, nqpqz2, bit);
1058 -
1059 - t = nqx;
1060 - nqx = nqx2;
1061 - nqx2 = t;
1062 - t = nqz;
1063 - nqz = nqz2;
1064 - nqz2 = t;
1065 - t = nqpqx;
1066 - nqpqx = nqpqx2;
1067 - nqpqx2 = t;
1068 - t = nqpqz;
1069 - nqpqz = nqpqz2;
1070 - nqpqz2 = t;
1071 -
1072 - byte <<= 1;
1073 - }
1074 - }
1075 -
1076 - memcpy(resultx, nqx, sizeof(limb) * 10);
1077 - memcpy(resultz, nqz, sizeof(limb) * 10);
1078 -}
1079 -
1080 -/* -----------------------------------------------------------------------------
1081 - * Shamelessly copied from djb's code
1082 - * ----------------------------------------------------------------------------- */
1083 -static void
1084 -crecip(limb *out, const limb *z) {
1085 - limb z2[10];
1086 - limb z9[10];
1087 - limb z11[10];
1088 - limb z2_5_0[10];
1089 - limb z2_10_0[10];
1090 - limb z2_20_0[10];
1091 - limb z2_50_0[10];
1092 - limb z2_100_0[10];
1093 - limb t0[10];
1094 - limb t1[10];
1095 - int i;
1096 -
1097 - /* 2 */ fsquare(z2,z);
1098 - /* 4 */ fsquare(t1,z2);
1099 - /* 8 */ fsquare(t0,t1);
1100 - /* 9 */ fmul(z9,t0,z);
1101 - /* 11 */ fmul(z11,z9,z2);
1102 - /* 22 */ fsquare(t0,z11);
1103 - /* 2^5 - 2^0 = 31 */ fmul(z2_5_0,t0,z9);
1104 -
1105 - /* 2^6 - 2^1 */ fsquare(t0,z2_5_0);
1106 - /* 2^7 - 2^2 */ fsquare(t1,t0);
1107 - /* 2^8 - 2^3 */ fsquare(t0,t1);
1108 - /* 2^9 - 2^4 */ fsquare(t1,t0);
1109 - /* 2^10 - 2^5 */ fsquare(t0,t1);
1110 - /* 2^10 - 2^0 */ fmul(z2_10_0,t0,z2_5_0);
1111 -
1112 - /* 2^11 - 2^1 */ fsquare(t0,z2_10_0);
1113 - /* 2^12 - 2^2 */ fsquare(t1,t0);
1114 - /* 2^20 - 2^10 */ for (i = 2;i < 10;i += 2) { fsquare(t0,t1); fsquare(t1,t0); }
1115 - /* 2^20 - 2^0 */ fmul(z2_20_0,t1,z2_10_0);
1116 -
1117 - /* 2^21 - 2^1 */ fsquare(t0,z2_20_0);
1118 - /* 2^22 - 2^2 */ fsquare(t1,t0);
1119 - /* 2^40 - 2^20 */ for (i = 2;i < 20;i += 2) { fsquare(t0,t1); fsquare(t1,t0); }
1120 - /* 2^40 - 2^0 */ fmul(t0,t1,z2_20_0);
1121 -
1122 - /* 2^41 - 2^1 */ fsquare(t1,t0);
1123 - /* 2^42 - 2^2 */ fsquare(t0,t1);
1124 - /* 2^50 - 2^10 */ for (i = 2;i < 10;i += 2) { fsquare(t1,t0); fsquare(t0,t1); }
1125 - /* 2^50 - 2^0 */ fmul(z2_50_0,t0,z2_10_0);
1126 -
1127 - /* 2^51 - 2^1 */ fsquare(t0,z2_50_0);
1128 - /* 2^52 - 2^2 */ fsquare(t1,t0);
1129 - /* 2^100 - 2^50 */ for (i = 2;i < 50;i += 2) { fsquare(t0,t1); fsquare(t1,t0); }
1130 - /* 2^100 - 2^0 */ fmul(z2_100_0,t1,z2_50_0);
1131 -
1132 - /* 2^101 - 2^1 */ fsquare(t1,z2_100_0);
1133 - /* 2^102 - 2^2 */ fsquare(t0,t1);
1134 - /* 2^200 - 2^100 */ for (i = 2;i < 100;i += 2) { fsquare(t1,t0); fsquare(t0,t1); }
1135 - /* 2^200 - 2^0 */ fmul(t1,t0,z2_100_0);
1136 -
1137 - /* 2^201 - 2^1 */ fsquare(t0,t1);
1138 - /* 2^202 - 2^2 */ fsquare(t1,t0);
1139 - /* 2^250 - 2^50 */ for (i = 2;i < 50;i += 2) { fsquare(t0,t1); fsquare(t1,t0); }
1140 - /* 2^250 - 2^0 */ fmul(t0,t1,z2_50_0);
1141 -
1142 - /* 2^251 - 2^1 */ fsquare(t1,t0);
1143 - /* 2^252 - 2^2 */ fsquare(t0,t1);
1144 - /* 2^253 - 2^3 */ fsquare(t1,t0);
1145 - /* 2^254 - 2^4 */ fsquare(t0,t1);
1146 - /* 2^255 - 2^5 */ fsquare(t1,t0);
1147 - /* 2^255 - 21 */ fmul(out,t1,z11);
1148 -}
1149 -
1150 -int
1151 -curve25519_donna(u8 *mypublic, const u8 *secret, const u8 *basepoint) {
1152 - limb bp[10], x[10], z[11], zmone[10];
1153 - uint8_t e[32];
1154 - int i;
1155 -
1156 - for (i = 0; i < 32; ++i) e[i] = secret[i];
1157 - e[0] &= 248;
1158 - e[31] &= 127;
1159 - e[31] |= 64;
1160 -
1161 - fexpand(bp, basepoint);
1162 - cmult(x, z, e, bp);
1163 - crecip(zmone, z);
1164 - fmul(z, x, zmone);
1165 - fcontract(mypublic, z);
1166 - return 0;
1167 -}
1168 diff --git a/curve25519.c b/curve25519.c
1169 new file mode 100644
1170 index 0000000..4b83776
1171 --- /dev/null
1172 +++ b/curve25519.c
1173 @@ -0,0 +1,502 @@
1174 +/*
1175 + * Dropbear - a SSH2 server
1176 + *
1177 + * Copyright (c) 2002,2003 Matt Johnston
1178 + * All rights reserved.
1179 + *
1180 + * Permission is hereby granted, free of charge, to any person obtaining a copy
1181 + * of this software and associated documentation files (the "Software"), to deal
1182 + * in the Software without restriction, including without limitation the rights
1183 + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
1184 + * copies of the Software, and to permit persons to whom the Software is
1185 + * furnished to do so, subject to the following conditions:
1186 + *
1187 + * The above copyright notice and this permission notice shall be included in
1188 + * all copies or substantial portions of the Software.
1189 + *
1190 + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
1191 + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
1192 + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
1193 + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
1194 + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
1195 + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
1196 + * SOFTWARE. */
1197 +
1198 +#include "includes.h"
1199 +#include "dbrandom.h"
1200 +#include "curve25519.h"
1201 +
1202 +#if DROPBEAR_CURVE25519 || DROPBEAR_ED25519
1203 +
1204 +/* Modified TweetNaCl version 20140427, a self-contained public-domain C library.
1205 + * https://tweetnacl.cr.yp.to/ */
1206 +
1207 +#define FOR(i,n) for (i = 0;i < n;++i)
1208 +#define sv static void
1209 +
1210 +typedef unsigned char u8;
1211 +typedef unsigned long u32;
1212 +typedef unsigned long long u64;
1213 +typedef long long i64;
1214 +typedef i64 gf[16];
1215 +
1216 +#if DROPBEAR_CURVE25519
1217 +static const gf
1218 + _121665 = {0xDB41,1};
1219 +#endif /* DROPBEAR_CURVE25519 */
1220 +#if DROPBEAR_ED25519
1221 +static const gf
1222 + gf0,
1223 + gf1 = {1},
1224 + D2 = {0xf159, 0x26b2, 0x9b94, 0xebd6, 0xb156, 0x8283, 0x149a, 0x00e0, 0xd130, 0xeef3, 0x80f2, 0x198e, 0xfce7, 0x56df, 0xd9dc, 0x2406},
1225 + X = {0xd51a, 0x8f25, 0x2d60, 0xc956, 0xa7b2, 0x9525, 0xc760, 0x692c, 0xdc5c, 0xfdd6, 0xe231, 0xc0a4, 0x53fe, 0xcd6e, 0x36d3, 0x2169},
1226 + Y = {0x6658, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666};
1227 +#if DROPBEAR_SIGNKEY_VERIFY
1228 +static const gf
1229 + D = {0x78a3, 0x1359, 0x4dca, 0x75eb, 0xd8ab, 0x4141, 0x0a4d, 0x0070, 0xe898, 0x7779, 0x4079, 0x8cc7, 0xfe73, 0x2b6f, 0x6cee, 0x5203},
1230 + I = {0xa0b0, 0x4a0e, 0x1b27, 0xc4ee, 0xe478, 0xad2f, 0x1806, 0x2f43, 0xd7a7, 0x3dfb, 0x0099, 0x2b4d, 0xdf0b, 0x4fc1, 0x2480, 0x2b83};
1231 +#endif /* DROPBEAR_SIGNKEY_VERIFY */
1232 +#endif /* DROPBEAR_ED25519 */
1233 +
1234 +#if DROPBEAR_ED25519
1235 +#if DROPBEAR_SIGNKEY_VERIFY
1236 +static int vn(const u8 *x,const u8 *y,u32 n)
1237 +{
1238 + u32 i,d = 0;
1239 + FOR(i,n) d |= x[i]^y[i];
1240 + return (1 & ((d - 1) >> 8)) - 1;
1241 +}
1242 +
1243 +static int crypto_verify_32(const u8 *x,const u8 *y)
1244 +{
1245 + return vn(x,y,32);
1246 +}
1247 +#endif /* DROPBEAR_SIGNKEY_VERIFY */
1248 +
1249 +sv set25519(gf r, const gf a)
1250 +{
1251 + int i;
1252 + FOR(i,16) r[i]=a[i];
1253 +}
1254 +#endif /* DROPBEAR_ED25519 */
1255 +
1256 +sv car25519(gf o)
1257 +{
1258 + int i;
1259 + i64 c;
1260 + FOR(i,16) {
1261 + o[i]+=(1LL<<16);
1262 + c=o[i]>>16;
1263 + o[(i+1)*(i<15)]+=c-1+37*(c-1)*(i==15);
1264 + o[i]-=c<<16;
1265 + }
1266 +}
1267 +
1268 +sv sel25519(gf p,gf q,int b)
1269 +{
1270 + i64 t,i,c=~(b-1);
1271 + FOR(i,16) {
1272 + t= c&(p[i]^q[i]);
1273 + p[i]^=t;
1274 + q[i]^=t;
1275 + }
1276 +}
1277 +
1278 +sv pack25519(u8 *o,const gf n)
1279 +{
1280 + int i,j,b;
1281 + gf m,t;
1282 + FOR(i,16) t[i]=n[i];
1283 + car25519(t);
1284 + car25519(t);
1285 + car25519(t);
1286 + FOR(j,2) {
1287 + m[0]=t[0]-0xffed;
1288 + for(i=1;i<15;i++) {
1289 + m[i]=t[i]-0xffff-((m[i-1]>>16)&1);
1290 + m[i-1]&=0xffff;
1291 + }
1292 + m[15]=t[15]-0x7fff-((m[14]>>16)&1);
1293 + b=(m[15]>>16)&1;
1294 + m[14]&=0xffff;
1295 + sel25519(t,m,1-b);
1296 + }
1297 + FOR(i,16) {
1298 + o[2*i]=t[i]&0xff;
1299 + o[2*i+1]=t[i]>>8;
1300 + }
1301 +}
1302 +
1303 +#if DROPBEAR_ED25519
1304 +#if DROPBEAR_SIGNKEY_VERIFY
1305 +static int neq25519(const gf a, const gf b)
1306 +{
1307 + u8 c[32],d[32];
1308 + pack25519(c,a);
1309 + pack25519(d,b);
1310 + return crypto_verify_32(c,d);
1311 +}
1312 +#endif /* DROPBEAR_SIGNKEY_VERIFY */
1313 +
1314 +static u8 par25519(const gf a)
1315 +{
1316 + u8 d[32];
1317 + pack25519(d,a);
1318 + return d[0]&1;
1319 +}
1320 +#endif /* DROPBEAR_ED25519 */
1321 +
1322 +sv unpack25519(gf o, const u8 *n)
1323 +{
1324 + int i;
1325 + FOR(i,16) o[i]=n[2*i]+((i64)n[2*i+1]<<8);
1326 + o[15]&=0x7fff;
1327 +}
1328 +
1329 +sv A(gf o,const gf a,const gf b)
1330 +{
1331 + int i;
1332 + FOR(i,16) o[i]=a[i]+b[i];
1333 +}
1334 +
1335 +sv Z(gf o,const gf a,const gf b)
1336 +{
1337 + int i;
1338 + FOR(i,16) o[i]=a[i]-b[i];
1339 +}
1340 +
1341 +sv M(gf o,const gf a,const gf b)
1342 +{
1343 + i64 i,j,t[31];
1344 + FOR(i,31) t[i]=0;
1345 + FOR(i,16) FOR(j,16) t[i+j]+=a[i]*b[j];
1346 + FOR(i,15) t[i]+=38*t[i+16];
1347 + FOR(i,16) o[i]=t[i];
1348 + car25519(o);
1349 + car25519(o);
1350 +}
1351 +
1352 +sv S(gf o,const gf a)
1353 +{
1354 + M(o,a,a);
1355 +}
1356 +
1357 +sv inv25519(gf o,const gf i)
1358 +{
1359 + gf c;
1360 + int a;
1361 + FOR(a,16) c[a]=i[a];
1362 + for(a=253;a>=0;a--) {
1363 + S(c,c);
1364 + if(a!=2&&a!=4) M(c,c,i);
1365 + }
1366 + FOR(a,16) o[a]=c[a];
1367 +}
1368 +
1369 +#if DROPBEAR_ED25519 && DROPBEAR_SIGNKEY_VERIFY
1370 +sv pow2523(gf o,const gf i)
1371 +{
1372 + gf c;
1373 + int a;
1374 + FOR(a,16) c[a]=i[a];
1375 + for(a=250;a>=0;a--) {
1376 + S(c,c);
1377 + if(a!=1) M(c,c,i);
1378 + }
1379 + FOR(a,16) o[a]=c[a];
1380 +}
1381 +#endif /* DROPBEAR_ED25519 && DROPBEAR_SIGNKEY_VERIFY */
1382 +
1383 +#if DROPBEAR_CURVE25519
1384 +int dropbear_curve25519_scalarmult(u8 *q,const u8 *n,const u8 *p)
1385 +{
1386 + u8 z[32];
1387 + i64 x[80],r,i;
1388 + gf a,b,c,d,e,f;
1389 + FOR(i,31) z[i]=n[i];
1390 + z[31]=(n[31]&127)|64;
1391 + z[0]&=248;
1392 + unpack25519(x,p);
1393 + FOR(i,16) {
1394 + b[i]=x[i];
1395 + d[i]=a[i]=c[i]=0;
1396 + }
1397 + a[0]=d[0]=1;
1398 + for(i=254;i>=0;--i) {
1399 + r=(z[i>>3]>>(i&7))&1;
1400 + sel25519(a,b,r);
1401 + sel25519(c,d,r);
1402 + A(e,a,c);
1403 + Z(a,a,c);
1404 + A(c,b,d);
1405 + Z(b,b,d);
1406 + S(d,e);
1407 + S(f,a);
1408 + M(a,c,a);
1409 + M(c,b,e);
1410 + A(e,a,c);
1411 + Z(a,a,c);
1412 + S(b,a);
1413 + Z(c,d,f);
1414 + M(a,c,_121665);
1415 + A(a,a,d);
1416 + M(c,c,a);
1417 + M(a,d,f);
1418 + M(d,b,x);
1419 + S(b,e);
1420 + sel25519(a,b,r);
1421 + sel25519(c,d,r);
1422 + }
1423 + FOR(i,16) {
1424 + x[i+16]=a[i];
1425 + x[i+32]=c[i];
1426 + x[i+48]=b[i];
1427 + x[i+64]=d[i];
1428 + }
1429 + inv25519(x+32,x+32);
1430 + M(x+16,x+16,x+32);
1431 + pack25519(q,x+16);
1432 + return 0;
1433 +}
1434 +#endif /* DROPBEAR_CURVE25519 */
1435 +
1436 +#if DROPBEAR_ED25519
1437 +static int crypto_hash(u8 *out,const u8 *m,u64 n)
1438 +{
1439 + hash_state hs;
1440 +
1441 + sha512_init(&hs);
1442 + sha512_process(&hs, m, n);
1443 + return sha512_done(&hs, out);
1444 +}
1445 +
1446 +sv add(gf p[4],gf q[4])
1447 +{
1448 + gf a,b,c,d,t,e,f,g,h;
1449 +
1450 + Z(a, p[1], p[0]);
1451 + Z(t, q[1], q[0]);
1452 + M(a, a, t);
1453 + A(b, p[0], p[1]);
1454 + A(t, q[0], q[1]);
1455 + M(b, b, t);
1456 + M(c, p[3], q[3]);
1457 + M(c, c, D2);
1458 + M(d, p[2], q[2]);
1459 + A(d, d, d);
1460 + Z(e, b, a);
1461 + Z(f, d, c);
1462 + A(g, d, c);
1463 + A(h, b, a);
1464 +
1465 + M(p[0], e, f);
1466 + M(p[1], h, g);
1467 + M(p[2], g, f);
1468 + M(p[3], e, h);
1469 +}
1470 +
1471 +sv cswap(gf p[4],gf q[4],u8 b)
1472 +{
1473 + int i;
1474 + FOR(i,4)
1475 + sel25519(p[i],q[i],b);
1476 +}
1477 +
1478 +sv pack(u8 *r,gf p[4])
1479 +{
1480 + gf tx, ty, zi;
1481 + inv25519(zi, p[2]);
1482 + M(tx, p[0], zi);
1483 + M(ty, p[1], zi);
1484 + pack25519(r, ty);
1485 + r[31] ^= par25519(tx) << 7;
1486 +}
1487 +
1488 +sv scalarmult(gf p[4],gf q[4],const u8 *s)
1489 +{
1490 + int i;
1491 + set25519(p[0],gf0);
1492 + set25519(p[1],gf1);
1493 + set25519(p[2],gf1);
1494 + set25519(p[3],gf0);
1495 + for (i = 255;i >= 0;--i) {
1496 + u8 b = (s[i/8]>>(i&7))&1;
1497 + cswap(p,q,b);
1498 + add(q,p);
1499 + add(p,p);
1500 + cswap(p,q,b);
1501 + }
1502 +}
1503 +
1504 +sv scalarbase(gf p[4],const u8 *s)
1505 +{
1506 + gf q[4];
1507 + set25519(q[0],X);
1508 + set25519(q[1],Y);
1509 + set25519(q[2],gf1);
1510 + M(q[3],X,Y);
1511 + scalarmult(p,q,s);
1512 +}
1513 +
1514 +int dropbear_ed25519_make_key(u8 *pk,u8 *sk)
1515 +{
1516 + u8 d[64];
1517 + gf p[4];
1518 +
1519 + genrandom(sk, 32);
1520 +
1521 + crypto_hash(d, sk, 32);
1522 + d[0] &= 248;
1523 + d[31] &= 127;
1524 + d[31] |= 64;
1525 +
1526 + scalarbase(p,d);
1527 + pack(pk,p);
1528 +
1529 + return 0;
1530 +}
1531 +
1532 +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};
1533 +
1534 +sv modL(u8 *r,i64 x[64])
1535 +{
1536 + i64 carry,i,j;
1537 + for (i = 63;i >= 32;--i) {
1538 + carry = 0;
1539 + for (j = i - 32;j < i - 12;++j) {
1540 + x[j] += carry - 16 * x[i] * L[j - (i - 32)];
1541 + carry = (x[j] + 128) >> 8;
1542 + x[j] -= carry << 8;
1543 + }
1544 + x[j] += carry;
1545 + x[i] = 0;
1546 + }
1547 + carry = 0;
1548 + FOR(j,32) {
1549 + x[j] += carry - (x[31] >> 4) * L[j];
1550 + carry = x[j] >> 8;
1551 + x[j] &= 255;
1552 + }
1553 + FOR(j,32) x[j] -= carry * L[j];
1554 + FOR(i,32) {
1555 + x[i+1] += x[i] >> 8;
1556 + r[i] = x[i] & 255;
1557 + }
1558 +}
1559 +
1560 +sv reduce(u8 *r)
1561 +{
1562 + i64 x[64],i;
1563 + FOR(i,64) x[i] = (u64) r[i];
1564 + FOR(i,64) r[i] = 0;
1565 + modL(r,x);
1566 +}
1567 +
1568 +int dropbear_ed25519_sign(const u8 *m,u32 mlen,u8 *s,u32 *slen,const u8 *sk, const u8 *pk)
1569 +{
1570 + hash_state hs;
1571 + u8 d[64],h[64],r[64];
1572 + i64 x[64];
1573 + gf p[4];
1574 + u32 i,j;
1575 +
1576 + crypto_hash(d, sk, 32);
1577 + d[0] &= 248;
1578 + d[31] &= 127;
1579 + d[31] |= 64;
1580 +
1581 + *slen = 64;
1582 +
1583 + sha512_init(&hs);
1584 + sha512_process(&hs,d + 32,32);
1585 + sha512_process(&hs,m,mlen);
1586 + sha512_done(&hs,r);
1587 + reduce(r);
1588 + scalarbase(p,r);
1589 + pack(s,p);
1590 +
1591 + sha512_init(&hs);
1592 + sha512_process(&hs,s,32);
1593 + sha512_process(&hs,pk,32);
1594 + sha512_process(&hs,m,mlen);
1595 + sha512_done(&hs,h);
1596 + reduce(h);
1597 +
1598 + FOR(i,64) x[i] = 0;
1599 + FOR(i,32) x[i] = (u64) r[i];
1600 + FOR(i,32) FOR(j,32) x[i+j] += h[i] * (u64) d[j];
1601 + modL(s + 32,x);
1602 +
1603 + return 0;
1604 +}
1605 +
1606 +#if DROPBEAR_SIGNKEY_VERIFY
1607 +static int unpackneg(gf r[4],const u8 p[32])
1608 +{
1609 + gf t, chk, num, den, den2, den4, den6;
1610 + set25519(r[2],gf1);
1611 + unpack25519(r[1],p);
1612 + S(num,r[1]);
1613 + M(den,num,D);
1614 + Z(num,num,r[2]);
1615 + A(den,r[2],den);
1616 +
1617 + S(den2,den);
1618 + S(den4,den2);
1619 + M(den6,den4,den2);
1620 + M(t,den6,num);
1621 + M(t,t,den);
1622 +
1623 + pow2523(t,t);
1624 + M(t,t,num);
1625 + M(t,t,den);
1626 + M(t,t,den);
1627 + M(r[0],t,den);
1628 +
1629 + S(chk,r[0]);
1630 + M(chk,chk,den);
1631 + if (neq25519(chk, num)) M(r[0],r[0],I);
1632 +
1633 + S(chk,r[0]);
1634 + M(chk,chk,den);
1635 + if (neq25519(chk, num)) return -1;
1636 +
1637 + if (par25519(r[0]) == (p[31]>>7)) Z(r[0],gf0,r[0]);
1638 +
1639 + M(r[3],r[0],r[1]);
1640 + return 0;
1641 +}
1642 +
1643 +int dropbear_ed25519_verify(const u8 *m,u32 mlen,const u8 *s,u32 slen,const u8 *pk)
1644 +{
1645 + hash_state hs;
1646 + u8 t[32],h[64];
1647 + gf p[4],q[4];
1648 +
1649 + if (slen < 64) return -1;
1650 +
1651 + if (unpackneg(q,pk)) return -1;
1652 +
1653 + sha512_init(&hs);
1654 + sha512_process(&hs,s,32);
1655 + sha512_process(&hs,pk,32);
1656 + sha512_process(&hs,m,mlen);
1657 + sha512_done(&hs,h);
1658 +
1659 + reduce(h);
1660 + scalarmult(p,q,h);
1661 +
1662 + scalarbase(q,s + 32);
1663 + add(p,q);
1664 + pack(t,p);
1665 +
1666 + if (crypto_verify_32(s, t))
1667 + return -1;
1668 +
1669 + return 0;
1670 +}
1671 +#endif /* DROPBEAR_SIGNKEY_VERIFY */
1672 +
1673 +#endif /* DROPBEAR_ED25519 */
1674 +
1675 +#endif /* DROPBEAR_CURVE25519 || DROPBEAR_ED25519 */
1676 diff --git a/curve25519.h b/curve25519.h
1677 new file mode 100644
1678 index 0000000..7f75aed
1679 --- /dev/null
1680 +++ b/curve25519.h
1681 @@ -0,0 +1,37 @@
1682 +/*
1683 + * Dropbear - a SSH2 server
1684 + *
1685 + * Copyright (c) 2002,2003 Matt Johnston
1686 + * All rights reserved.
1687 + *
1688 + * Permission is hereby granted, free of charge, to any person obtaining a copy
1689 + * of this software and associated documentation files (the "Software"), to deal
1690 + * in the Software without restriction, including without limitation the rights
1691 + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
1692 + * copies of the Software, and to permit persons to whom the Software is
1693 + * furnished to do so, subject to the following conditions:
1694 + *
1695 + * The above copyright notice and this permission notice shall be included in
1696 + * all copies or substantial portions of the Software.
1697 + *
1698 + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
1699 + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
1700 + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
1701 + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
1702 + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
1703 + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
1704 + * SOFTWARE. */
1705 +
1706 +#ifndef DROPBEAR_CURVE25519_H
1707 +#define DROPBEAR_CURVE25519_H
1708 +
1709 +int dropbear_curve25519_scalarmult(unsigned char *q, const unsigned char *n, const unsigned char *p);
1710 +int dropbear_ed25519_make_key(unsigned char *pk, unsigned char *sk);
1711 +int dropbear_ed25519_sign(const unsigned char *m, unsigned long mlen,
1712 + unsigned char *s, unsigned long *slen,
1713 + const unsigned char *sk, const unsigned char *pk);
1714 +int dropbear_ed25519_verify(const unsigned char *m, unsigned long mlen,
1715 + const unsigned char *s, unsigned long slen,
1716 + const unsigned char *pk);
1717 +
1718 +#endif /* DROPBEAR_CURVE25519_H */
1719 diff --git a/default_options.h b/default_options.h
1720 index 9000fcc..5b232dd 100644
1721 --- a/default_options.h
1722 +++ b/default_options.h
1723 @@ -22,6 +22,7 @@ IMPORTANT: Some options will require "make clean" after changes */
1724 #define DSS_PRIV_FILENAME "/etc/dropbear/dropbear_dss_host_key"
1725 #define RSA_PRIV_FILENAME "/etc/dropbear/dropbear_rsa_host_key"
1726 #define ECDSA_PRIV_FILENAME "/etc/dropbear/dropbear_ecdsa_host_key"
1727 +#define ED25519_PRIV_FILENAME "/etc/dropbear/dropbear_ed25519_host_key"
1728
1729 /* Set NON_INETD_MODE if you require daemon functionality (ie Dropbear listens
1730 * on chosen ports and keeps accepting connections. This is the default.
1731 @@ -116,11 +117,15 @@ IMPORTANT: Some options will require "make clean" after changes */
1732 * code (either ECDSA or ECDH) increases binary size - around 30kB
1733 * on x86-64 */
1734 #define DROPBEAR_ECDSA 1
1735 +/* Ed25519 is faster than ECDSA. Compiling in Ed25519 code increases
1736 + binary size - around 7,5kB on x86-64 */
1737 +#define DROPBEAR_ED25519 1
1738
1739 /* RSA must be >=1024 */
1740 #define DROPBEAR_DEFAULT_RSA_SIZE 2048
1741 /* DSS is always 1024 */
1742 /* ECDSA defaults to largest size configured, usually 521 */
1743 +/* Ed25519 is always 256 */
1744
1745 /* Add runtime flag "-R" to generate hostkeys as-needed when the first
1746 connection using that key type occurs.
1747 @@ -143,7 +148,7 @@ IMPORTANT: Some options will require "make clean" after changes */
1748 * group14 is supported by most implementations.
1749 * group16 provides a greater strength level but is slower and increases binary size
1750 * curve25519 and ecdh algorithms are faster than non-elliptic curve methods
1751 - * curve25519 increases binary size by ~8kB on x86-64
1752 + * curve25519 increases binary size by ~2,5kB on x86-64
1753 * including either ECDH or ECDSA increases binary size by ~30kB on x86-64
1754
1755 * Small systems should generally include either curve25519 or ecdh for performance.
1756 diff --git a/dropbear.8 b/dropbear.8
1757 index 71c955a..345954f 100644
1758 --- a/dropbear.8
1759 +++ b/dropbear.8
1760 @@ -107,7 +107,7 @@ Print the version
1761 Authorized Keys
1762
1763 ~/.ssh/authorized_keys can be set up to allow remote login with a RSA,
1764 -ECDSA, or DSS
1765 +ECDSA, Ed25519 or DSS
1766 key. Each line is of the form
1767 .TP
1768 [restrictions] ssh-rsa AAAAB3NzaC1yc2EAAAABIwAAAIgAsp... [comment]
1769 @@ -146,8 +146,8 @@ key authentication.
1770 Host Key Files
1771
1772 Host key files are read at startup from a standard location, by default
1773 -/etc/dropbear/dropbear_dss_host_key, /etc/dropbear/dropbear_rsa_host_key, and
1774 -/etc/dropbear/dropbear_ecdsa_host_key
1775 +/etc/dropbear/dropbear_dss_host_key, /etc/dropbear/dropbear_rsa_host_key,
1776 +/etc/dropbear/dropbear_ecdsa_host_key and /etc/dropbear/dropbear_ed25519_host_key
1777
1778 If the -r command line option is specified the default files are not loaded.
1779 Host key files are of the form generated by dropbearkey.
1780 diff --git a/dropbearkey.c b/dropbearkey.c
1781 index dd0e697..f881855 100644
1782 --- a/dropbearkey.c
1783 +++ b/dropbearkey.c
1784 @@ -43,6 +43,10 @@
1785 * mp_int y
1786 * mp_int x
1787 *
1788 + * Ed25519:
1789 + * string "ssh-ed25519"
1790 + * string k (32 bytes) + A (32 bytes)
1791 + *
1792 */
1793 #include "includes.h"
1794 #include "signkey.h"
1795 @@ -51,6 +55,7 @@
1796
1797 #include "genrsa.h"
1798 #include "gendss.h"
1799 +#include "gened25519.h"
1800 #include "ecdsa.h"
1801 #include "crypto_desc.h"
1802 #include "dbrandom.h"
1803 @@ -75,6 +80,9 @@ static void printhelp(char * progname) {
1804 #endif
1805 #if DROPBEAR_ECDSA
1806 " ecdsa\n"
1807 +#endif
1808 +#if DROPBEAR_ED25519
1809 + " ed25519\n"
1810 #endif
1811 "-f filename Use filename for the secret key.\n"
1812 " ~/.ssh/id_dropbear is recommended for client keys.\n"
1813 @@ -94,6 +102,9 @@ static void printhelp(char * progname) {
1814 "521 "
1815 #endif
1816 "\n"
1817 +#endif
1818 +#if DROPBEAR_ED25519
1819 + " Ed25519 has a fixed size of 256 bits\n"
1820 #endif
1821 "-y Just print the publickey and fingerprint for the\n private key in <filename>.\n"
1822 #if DEBUG_TRACE
1823 @@ -106,6 +117,14 @@ static void printhelp(char * progname) {
1824 static void check_signkey_bits(enum signkey_type type, int bits)
1825 {
1826 switch (type) {
1827 +#if DROPBEAR_ED25519
1828 + case DROPBEAR_SIGNKEY_ED25519:
1829 + if (bits != 256) {
1830 + dropbear_exit("Ed25519 keys have a fixed size of 256 bits\n");
1831 + exit(EXIT_FAILURE);
1832 + }
1833 + break;
1834 +#endif
1835 #if DROPBEAR_RSA
1836 case DROPBEAR_SIGNKEY_RSA:
1837 if (bits < 512 || bits > 4096 || (bits % 8 != 0)) {
1838 @@ -224,6 +243,12 @@ int main(int argc, char ** argv) {
1839 keytype = DROPBEAR_SIGNKEY_ECDSA_KEYGEN;
1840 }
1841 #endif
1842 +#if DROPBEAR_ED25519
1843 + if (strcmp(typetext, "ed25519") == 0)
1844 + {
1845 + keytype = DROPBEAR_SIGNKEY_ED25519;
1846 + }
1847 +#endif
1848
1849 if (keytype == DROPBEAR_SIGNKEY_NONE) {
1850 fprintf(stderr, "Unknown key type '%s'\n", typetext);
1851 diff --git a/ed25519.c b/ed25519.c
1852 new file mode 100644
1853 index 0000000..3fb544c
1854 --- /dev/null
1855 +++ b/ed25519.c
1856 @@ -0,0 +1,184 @@
1857 +/*
1858 + * Dropbear - a SSH2 server
1859 + *
1860 + * Copyright (c) 2002,2003 Matt Johnston
1861 + * All rights reserved.
1862 + *
1863 + * Permission is hereby granted, free of charge, to any person obtaining a copy
1864 + * of this software and associated documentation files (the "Software"), to deal
1865 + * in the Software without restriction, including without limitation the rights
1866 + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
1867 + * copies of the Software, and to permit persons to whom the Software is
1868 + * furnished to do so, subject to the following conditions:
1869 + *
1870 + * The above copyright notice and this permission notice shall be included in
1871 + * all copies or substantial portions of the Software.
1872 + *
1873 + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
1874 + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
1875 + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
1876 + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
1877 + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
1878 + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
1879 + * SOFTWARE. */
1880 +
1881 +/* Perform Ed25519 operations on data, including reading keys, signing and
1882 + * verification. */
1883 +
1884 +#include "includes.h"
1885 +#include "dbutil.h"
1886 +#include "buffer.h"
1887 +#include "ssh.h"
1888 +#include "curve25519.h"
1889 +#include "ed25519.h"
1890 +
1891 +#if DROPBEAR_ED25519
1892 +
1893 +/* Load a public ed25519 key from a buffer, initialising the values.
1894 + * The key will have the same format as buf_put_ed25519_key.
1895 + * These should be freed with ed25519_key_free.
1896 + * Returns DROPBEAR_SUCCESS or DROPBEAR_FAILURE */
1897 +int buf_get_ed25519_pub_key(buffer *buf, dropbear_ed25519_key *key) {
1898 +
1899 + unsigned int len;
1900 +
1901 + TRACE(("enter buf_get_ed25519_pub_key"))
1902 + dropbear_assert(key != NULL);
1903 +
1904 + buf_incrpos(buf, 4+SSH_SIGNKEY_ED25519_LEN); /* int + "ssh-ed25519" */
1905 +
1906 + len = buf_getint(buf);
1907 + if (len != CURVE25519_LEN || buf->len - buf->pos < len) {
1908 + TRACE(("leave buf_get_ed25519_pub_key: failure"))
1909 + return DROPBEAR_FAILURE;
1910 + }
1911 +
1912 + m_burn(key->priv, CURVE25519_LEN);
1913 + memcpy(key->pub, buf_getptr(buf, CURVE25519_LEN), CURVE25519_LEN);
1914 + buf_incrpos(buf, CURVE25519_LEN);
1915 +
1916 + TRACE(("leave buf_get_ed25519_pub_key: success"))
1917 + return DROPBEAR_SUCCESS;
1918 +}
1919 +
1920 +/* Same as buf_get_ed25519_pub_key, but reads private key at the end.
1921 + * Loads a public and private ed25519 key from a buffer
1922 + * Returns DROPBEAR_SUCCESS or DROPBEAR_FAILURE */
1923 +int buf_get_ed25519_priv_key(buffer *buf, dropbear_ed25519_key *key) {
1924 +
1925 + unsigned int len;
1926 +
1927 + TRACE(("enter buf_get_ed25519_priv_key"))
1928 + dropbear_assert(key != NULL);
1929 +
1930 + buf_incrpos(buf, 4+SSH_SIGNKEY_ED25519_LEN); /* int + "ssh-ed25519" */
1931 +
1932 + len = buf_getint(buf);
1933 + if (len != CURVE25519_LEN*2 || buf->len - buf->pos < len) {
1934 + TRACE(("leave buf_get_ed25519_priv_key: failure"))
1935 + return DROPBEAR_FAILURE;
1936 + }
1937 +
1938 + memcpy(key->priv, buf_getptr(buf, CURVE25519_LEN), CURVE25519_LEN);
1939 + buf_incrpos(buf, CURVE25519_LEN);
1940 + memcpy(key->pub, buf_getptr(buf, CURVE25519_LEN), CURVE25519_LEN);
1941 + buf_incrpos(buf, CURVE25519_LEN);
1942 +
1943 + TRACE(("leave buf_get_ed25519_pub_key: success"))
1944 + return DROPBEAR_SUCCESS;
1945 +}
1946 +
1947 +/* Clear and free the memory used by a public or private key */
1948 +void ed25519_key_free(dropbear_ed25519_key *key) {
1949 +
1950 + TRACE2(("enter ed25519_key_free"))
1951 +
1952 + if (key == NULL) {
1953 + TRACE2(("leave ed25519_key_free: key == NULL"))
1954 + return;
1955 + }
1956 + m_burn(key->priv, CURVE25519_LEN);
1957 + m_free(key);
1958 +
1959 + TRACE2(("leave rsa_key_free"))
1960 +}
1961 +
1962 +/* Put the public ed25519 key into the buffer in the required format */
1963 +void buf_put_ed25519_pub_key(buffer *buf, const dropbear_ed25519_key *key) {
1964 +
1965 + TRACE(("enter buf_put_ed25519_pub_key"))
1966 + dropbear_assert(key != NULL);
1967 +
1968 + buf_putstring(buf, SSH_SIGNKEY_ED25519, SSH_SIGNKEY_ED25519_LEN);
1969 + buf_putstring(buf, key->pub, CURVE25519_LEN);
1970 +
1971 + TRACE(("leave buf_put_ed25519_pub_key"))
1972 +}
1973 +
1974 +/* Put the public and private ed25519 key into the buffer in the required format */
1975 +void buf_put_ed25519_priv_key(buffer *buf, const dropbear_ed25519_key *key) {
1976 +
1977 + TRACE(("enter buf_put_ed25519_priv_key"))
1978 + dropbear_assert(key != NULL);
1979 +
1980 + buf_putstring(buf, SSH_SIGNKEY_ED25519, SSH_SIGNKEY_ED25519_LEN);
1981 + buf_putint(buf, CURVE25519_LEN*2);
1982 + buf_putbytes(buf, key->priv, CURVE25519_LEN);
1983 + buf_putbytes(buf, key->pub, CURVE25519_LEN);
1984 +
1985 + TRACE(("leave buf_put_ed25519_priv_key"))
1986 +}
1987 +
1988 +/* Sign the data presented with key, writing the signature contents
1989 + * to the buffer */
1990 +void buf_put_ed25519_sign(buffer* buf, const dropbear_ed25519_key *key, const buffer *data_buf) {
1991 +
1992 + unsigned char s[64];
1993 + unsigned long slen = sizeof(s);
1994 +
1995 + TRACE(("enter buf_put_ed25519_sign"))
1996 + dropbear_assert(key != NULL);
1997 +
1998 + if (dropbear_ed25519_sign(data_buf->data, data_buf->len,
1999 + s, &slen, key->priv, key->pub) == 0) {
2000 + buf_putstring(buf, SSH_SIGNKEY_ED25519, SSH_SIGNKEY_ED25519_LEN);
2001 + buf_putstring(buf, s, slen);
2002 + }
2003 +
2004 + TRACE(("leave buf_put_ed25519_sign"))
2005 +}
2006 +
2007 +#if DROPBEAR_SIGNKEY_VERIFY
2008 +/* Verify a signature in buf, made on data by the key given.
2009 + * Returns DROPBEAR_SUCCESS or DROPBEAR_FAILURE */
2010 +int buf_ed25519_verify(buffer *buf, const dropbear_ed25519_key *key, const buffer *data_buf) {
2011 +
2012 + int ret = DROPBEAR_FAILURE;
2013 + unsigned char *s;
2014 + unsigned long slen;
2015 +
2016 + TRACE(("enter buf_ed25519_verify"))
2017 + dropbear_assert(key != NULL);
2018 +
2019 + slen = buf_getint(buf);
2020 + if (slen != 64 || buf->len - buf->pos < slen) {
2021 + TRACE(("bad size"))
2022 + goto out;
2023 + }
2024 + s = buf_getptr(buf, slen);
2025 +
2026 + if (dropbear_ed25519_verify(data_buf->data, data_buf->len,
2027 + s, slen, key->pub) == 0) {
2028 + /* signature is valid */
2029 + TRACE(("success!"))
2030 + ret = DROPBEAR_SUCCESS;
2031 + }
2032 +
2033 +out:
2034 + TRACE(("leave buf_ed25519_verify: ret %d", ret))
2035 + return ret;
2036 +}
2037 +
2038 +#endif /* DROPBEAR_SIGNKEY_VERIFY */
2039 +
2040 +#endif /* DROPBEAR_ED25519 */
2041 diff --git a/ed25519.h b/ed25519.h
2042 new file mode 100644
2043 index 0000000..16c0d7b
2044 --- /dev/null
2045 +++ b/ed25519.h
2046 @@ -0,0 +1,54 @@
2047 +/*
2048 + * Dropbear - a SSH2 server
2049 + *
2050 + * Copyright (c) 2002,2003 Matt Johnston
2051 + * All rights reserved.
2052 + *
2053 + * Permission is hereby granted, free of charge, to any person obtaining a copy
2054 + * of this software and associated documentation files (the "Software"), to deal
2055 + * in the Software without restriction, including without limitation the rights
2056 + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
2057 + * copies of the Software, and to permit persons to whom the Software is
2058 + * furnished to do so, subject to the following conditions:
2059 + *
2060 + * The above copyright notice and this permission notice shall be included in
2061 + * all copies or substantial portions of the Software.
2062 + *
2063 + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
2064 + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
2065 + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
2066 + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
2067 + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
2068 + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
2069 + * SOFTWARE. */
2070 +
2071 +#ifndef DROPBEAR_ED25519_H_
2072 +#define DROPBEAR_ED25519_H_
2073 +
2074 +#include "includes.h"
2075 +#include "buffer.h"
2076 +
2077 +#if DROPBEAR_ED25519
2078 +
2079 +#define CURVE25519_LEN 32
2080 +
2081 +typedef struct {
2082 +
2083 + unsigned char priv[CURVE25519_LEN];
2084 + unsigned char pub[CURVE25519_LEN];
2085 +
2086 +} dropbear_ed25519_key;
2087 +
2088 +void buf_put_ed25519_sign(buffer* buf, const dropbear_ed25519_key *key, const buffer *data_buf);
2089 +#if DROPBEAR_SIGNKEY_VERIFY
2090 +int buf_ed25519_verify(buffer * buf, const dropbear_ed25519_key *key, const buffer *data_buf);
2091 +#endif
2092 +int buf_get_ed25519_pub_key(buffer* buf, dropbear_ed25519_key *key);
2093 +int buf_get_ed25519_priv_key(buffer* buf, dropbear_ed25519_key *key);
2094 +void buf_put_ed25519_pub_key(buffer* buf, const dropbear_ed25519_key *key);
2095 +void buf_put_ed25519_priv_key(buffer* buf, const dropbear_ed25519_key *key);
2096 +void ed25519_key_free(dropbear_ed25519_key *key);
2097 +
2098 +#endif /* DROPBEAR_ED25519 */
2099 +
2100 +#endif /* DROPBEAR_ED25519_H_ */
2101 diff --git a/filelist.txt b/filelist.txt
2102 index 8281c14..3b9bb67 100644
2103 --- a/filelist.txt
2104 +++ b/filelist.txt
2105 @@ -99,6 +99,10 @@ rsa.c RSA asymmetric crypto routines
2106
2107 dss.c DSS asymmetric crypto routines
2108
2109 +ed25519.c Ed25519 asymmetric crypto routines
2110 +
2111 +gened25519.c Ed25519 key generation
2112 +
2113 gendss.c DSS key generation
2114
2115 genrsa.c RSA key generation
2116 diff --git a/fuzz-common.c b/fuzz-common.c
2117 index 5c90c45..b1b00f6 100644
2118 --- a/fuzz-common.c
2119 +++ b/fuzz-common.c
2120 @@ -112,6 +112,14 @@ static void load_fixed_hostkeys(void) {
2121 dropbear_exit("failed fixed ecdsa hostkey");
2122 }
2123
2124 + buf_setlen(b, 0);
2125 + buf_putbytes(b, keyed25519, keyed25519_len);
2126 + buf_setpos(b, 0);
2127 + type = DROPBEAR_SIGNKEY_ED25519;
2128 + if (buf_get_priv_key(b, svr_opts.hostkey, &type) == DROPBEAR_FAILURE) {
2129 + dropbear_exit("failed fixed ed25519 hostkey");
2130 + }
2131 +
2132 buf_free(b);
2133 }
2134
2135 diff --git a/fuzz-hostkeys.c b/fuzz-hostkeys.c
2136 index dc1615d..3fff5cb 100644
2137 --- a/fuzz-hostkeys.c
2138 +++ b/fuzz-hostkeys.c
2139 @@ -127,3 +127,13 @@ unsigned char keyd[] = {
2140 0xf9, 0x39
2141 };
2142 unsigned int keyd_len = 458;
2143 +unsigned char keyed25519[] = {
2144 + 0x00, 0x00, 0x00, 0x0b, 0x73, 0x73, 0x68, 0x2d, 0x65, 0x64, 0x32, 0x35,
2145 + 0x35, 0x31, 0x39, 0x00, 0x00, 0x00, 0x40, 0x10, 0xb3, 0x79, 0x06, 0xe5,
2146 + 0x9b, 0xe7, 0xe4, 0x6e, 0xec, 0xfe, 0xa5, 0x39, 0x21, 0x7c, 0xf6, 0x66,
2147 + 0x8c, 0x0b, 0x6a, 0x01, 0x09, 0x05, 0xc7, 0x4f, 0x64, 0xa8, 0x24, 0xd2,
2148 + 0x8d, 0xbd, 0xdd, 0xc6, 0x3c, 0x99, 0x1b, 0x2d, 0x3e, 0x33, 0x90, 0x19,
2149 + 0xa4, 0xd5, 0xe9, 0x23, 0xfe, 0x8e, 0xd6, 0xd4, 0xf9, 0xb1, 0x11, 0x69,
2150 + 0x7c, 0x57, 0x52, 0x0e, 0x41, 0xdb, 0x1b, 0x12, 0x87, 0xfa, 0xc9
2151 +};
2152 +unsigned int keyed25519_len = 83;
2153 diff --git a/fuzzer-kexcurve25519.c b/fuzzer-kexcurve25519.c
2154 new file mode 100644
2155 index 0000000..f2eab14
2156 --- /dev/null
2157 +++ b/fuzzer-kexcurve25519.c
2158 @@ -0,0 +1,72 @@
2159 +#include "fuzz.h"
2160 +#include "session.h"
2161 +#include "fuzz-wrapfd.h"
2162 +#include "debug.h"
2163 +#include "runopts.h"
2164 +#include "algo.h"
2165 +#include "bignum.h"
2166 +
2167 +int LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size) {
2168 + static int once = 0;
2169 + static struct key_context* keep_newkeys = NULL;
2170 + /* number of generated parameters is limited by the timeout for the first run.
2171 + TODO move this to the libfuzzer initialiser function instead if the timeout
2172 + doesn't apply there */
2173 + #define NUM_PARAMS 20
2174 + static struct kex_curve25519_param *curve25519_params[NUM_PARAMS];
2175 +
2176 + if (!once) {
2177 + fuzz_common_setup();
2178 + fuzz_svr_setup();
2179 +
2180 + keep_newkeys = (struct key_context*)m_malloc(sizeof(struct key_context));
2181 + keep_newkeys->algo_kex = fuzz_get_algo(sshkex, "curve25519-sha256");
2182 + keep_newkeys->algo_hostkey = DROPBEAR_SIGNKEY_ED25519;
2183 + ses.newkeys = keep_newkeys;
2184 +
2185 + /* Pre-generate parameters */
2186 + int i;
2187 + for (i = 0; i < NUM_PARAMS; i++) {
2188 + curve25519_params[i] = gen_kexcurve25519_param();
2189 + }
2190 +
2191 + once = 1;
2192 + }
2193 +
2194 + if (fuzz_set_input(Data, Size) == DROPBEAR_FAILURE) {
2195 + return 0;
2196 + }
2197 +
2198 + m_malloc_set_epoch(1);
2199 +
2200 + if (setjmp(fuzz.jmp) == 0) {
2201 + /* Based on recv_msg_kexdh_init()/send_msg_kexdh_reply()
2202 + with DROPBEAR_KEX_CURVE25519 */
2203 + ses.newkeys = keep_newkeys;
2204 +
2205 + /* Choose from the collection of curve25519 params */
2206 + unsigned int e = buf_getint(fuzz.input);
2207 + struct kex_curve25519_param *curve25519_param = curve25519_params[e % NUM_PARAMS];
2208 +
2209 + buffer * ecdh_qs = buf_getstringbuf(fuzz.input);
2210 +
2211 + ses.kexhashbuf = buf_new(KEXHASHBUF_MAX_INTS);
2212 + kexcurve25519_comb_key(curve25519_param, ecdh_qs, svr_opts.hostkey);
2213 +
2214 + mp_clear(ses.dh_K);
2215 + m_free(ses.dh_K);
2216 + buf_free(ecdh_qs);
2217 +
2218 + buf_free(ses.hash);
2219 + buf_free(ses.session_id);
2220 + /* kexhashbuf is freed in kexdh_comb_key */
2221 +
2222 + m_malloc_free_epoch(1, 0);
2223 + } else {
2224 + m_malloc_free_epoch(1, 1);
2225 + TRACE(("dropbear_exit longjmped"))
2226 + /* dropbear_exit jumped here */
2227 + }
2228 +
2229 + return 0;
2230 +}
2231 diff --git a/gened25519.c b/gened25519.c
2232 new file mode 100644
2233 index 0000000..a027914
2234 --- /dev/null
2235 +++ b/gened25519.c
2236 @@ -0,0 +1,47 @@
2237 +/*
2238 + * Dropbear - a SSH2 server
2239 + *
2240 + * Copyright (c) 2002,2003 Matt Johnston
2241 + * All rights reserved.
2242 + *
2243 + * Permission is hereby granted, free of charge, to any person obtaining a copy
2244 + * of this software and associated documentation files (the "Software"), to deal
2245 + * in the Software without restriction, including without limitation the rights
2246 + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
2247 + * copies of the Software, and to permit persons to whom the Software is
2248 + * furnished to do so, subject to the following conditions:
2249 + *
2250 + * The above copyright notice and this permission notice shall be included in
2251 + * all copies or substantial portions of the Software.
2252 + *
2253 + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
2254 + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
2255 + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
2256 + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
2257 + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
2258 + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
2259 + * SOFTWARE. */
2260 +
2261 +#include "includes.h"
2262 +#include "dbutil.h"
2263 +#include "dbrandom.h"
2264 +#include "curve25519.h"
2265 +#include "gened25519.h"
2266 +
2267 +#if DROPBEAR_ED25519
2268 +
2269 +dropbear_ed25519_key * gen_ed25519_priv_key(unsigned int size) {
2270 +
2271 + dropbear_ed25519_key *key;
2272 +
2273 + if (size != 256) {
2274 + dropbear_exit("Ed25519 keys have a fixed size of 256 bits");
2275 + }
2276 +
2277 + key = m_malloc(sizeof(*key));
2278 + dropbear_ed25519_make_key(key->pub, key->priv);
2279 +
2280 + return key;
2281 +}
2282 +
2283 +#endif /* DROPBEAR_ED25519 */
2284 diff --git a/gened25519.h b/gened25519.h
2285 new file mode 100644
2286 index 0000000..8058310
2287 --- /dev/null
2288 +++ b/gened25519.h
2289 @@ -0,0 +1,36 @@
2290 +/*
2291 + * Dropbear - a SSH2 server
2292 + *
2293 + * Copyright (c) 2002,2003 Matt Johnston
2294 + * All rights reserved.
2295 + *
2296 + * Permission is hereby granted, free of charge, to any person obtaining a copy
2297 + * of this software and associated documentation files (the "Software"), to deal
2298 + * in the Software without restriction, including without limitation the rights
2299 + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
2300 + * copies of the Software, and to permit persons to whom the Software is
2301 + * furnished to do so, subject to the following conditions:
2302 + *
2303 + * The above copyright notice and this permission notice shall be included in
2304 + * all copies or substantial portions of the Software.
2305 + *
2306 + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
2307 + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
2308 + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
2309 + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
2310 + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
2311 + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
2312 + * SOFTWARE. */
2313 +
2314 +#ifndef DROPBEAR_GENED25519_H_
2315 +#define DROPBEAR_GENED25519_H_
2316 +
2317 +#include "ed25519.h"
2318 +
2319 +#if DROPBEAR_ED25519
2320 +
2321 +dropbear_ed25519_key * gen_ed25519_priv_key(unsigned int size);
2322 +
2323 +#endif /* DROPBEAR_ED25519 */
2324 +
2325 +#endif /* DROPBEAR_GENED25519_H_ */
2326 diff --git a/gensignkey.c b/gensignkey.c
2327 index 34b6f5a..674d81f 100644
2328 --- a/gensignkey.c
2329 +++ b/gensignkey.c
2330 @@ -4,6 +4,7 @@
2331 #include "ecdsa.h"
2332 #include "genrsa.h"
2333 #include "gendss.h"
2334 +#include "gened25519.h"
2335 #include "signkey.h"
2336 #include "dbrandom.h"
2337
2338 @@ -68,6 +69,10 @@ static int get_default_bits(enum signkey_type keytype)
2339 return 384;
2340 case DROPBEAR_SIGNKEY_ECDSA_NISTP256:
2341 return 256;
2342 +#endif
2343 +#if DROPBEAR_ED25519
2344 + case DROPBEAR_SIGNKEY_ED25519:
2345 + return 256;
2346 #endif
2347 default:
2348 return 0;
2349 @@ -118,6 +123,11 @@ int signkey_generate(enum signkey_type keytype, int bits, const char* filename,
2350 *signkey_key_ptr(key, keytype) = ecckey;
2351 }
2352 break;
2353 +#endif
2354 +#if DROPBEAR_ED25519
2355 + case DROPBEAR_SIGNKEY_ED25519:
2356 + key->ed25519key = gen_ed25519_priv_key(bits);
2357 + break;
2358 #endif
2359 default:
2360 dropbear_exit("Internal error");
2361 diff --git a/keyimport.c b/keyimport.c
2362 index 7304e58..ad0c530 100644
2363 --- a/keyimport.c
2364 +++ b/keyimport.c
2365 @@ -35,6 +35,15 @@
2366 #include "buffer.h"
2367 #include "dbutil.h"
2368 #include "ecc.h"
2369 +#include "ssh.h"
2370 +
2371 +static const unsigned char OSSH_PKEY_BLOB[] =
2372 + "openssh-key-v1\0" /* AUTH_MAGIC */
2373 + "\0\0\0\4none" /* cipher name*/
2374 + "\0\0\0\4none" /* kdf name */
2375 + "\0\0\0\0" /* kdf */
2376 + "\0\0\0\1"; /* key num */
2377 +#define OSSH_PKEY_BLOBLEN (sizeof(OSSH_PKEY_BLOB) - 1)
2378
2379 #if DROPBEAR_ECDSA
2380 static const unsigned char OID_SEC256R1_BLOB[] = {0x2a, 0x86, 0x48, 0xce, 0x3d, 0x03, 0x01, 0x07};
2381 @@ -352,7 +361,7 @@ struct mpint_pos { void *start; int bytes; };
2382 * Code to read and write OpenSSH private keys.
2383 */
2384
2385 -enum { OSSH_DSA, OSSH_RSA, OSSH_EC };
2386 +enum { OSSH_DSA, OSSH_RSA, OSSH_EC, OSSH_PKEY };
2387 struct openssh_key {
2388 int type;
2389 int encrypted;
2390 @@ -364,11 +373,12 @@ struct openssh_key {
2391 static struct openssh_key *load_openssh_key(const char *filename)
2392 {
2393 struct openssh_key *ret;
2394 + buffer *buf = NULL;
2395 FILE *fp = NULL;
2396 char buffer[256];
2397 char *errmsg = NULL, *p = NULL;
2398 int headers_done;
2399 - unsigned long len, outlen;
2400 + unsigned long len;
2401
2402 ret = (struct openssh_key*)m_malloc(sizeof(struct openssh_key));
2403 ret->keyblob = NULL;
2404 @@ -397,12 +407,15 @@ static struct openssh_key *load_openssh_key(const char *filename)
2405 ret->type = OSSH_DSA;
2406 else if (!strcmp(buffer, "-----BEGIN EC PRIVATE KEY-----\n"))
2407 ret->type = OSSH_EC;
2408 + else if (!strcmp(buffer, "-----BEGIN OPENSSH PRIVATE KEY-----\n"))
2409 + ret->type = OSSH_PKEY;
2410 else {
2411 errmsg = "Unrecognised key type";
2412 goto error;
2413 }
2414
2415 headers_done = 0;
2416 + buf = buf_new(0);
2417 while (1) {
2418 if (!fgets(buffer, sizeof(buffer), fp)) {
2419 errmsg = "Unexpected end of file";
2420 @@ -448,20 +461,31 @@ static struct openssh_key *load_openssh_key(const char *filename)
2421 } else {
2422 headers_done = 1;
2423 len = strlen(buffer);
2424 - outlen = len*4/3;
2425 - if (ret->keyblob_len + outlen > ret->keyblob_size) {
2426 - ret->keyblob_size = ret->keyblob_len + outlen + 256;
2427 - ret->keyblob = (unsigned char*)m_realloc(ret->keyblob,
2428 - ret->keyblob_size);
2429 - }
2430 - outlen = ret->keyblob_size - ret->keyblob_len;
2431 - if (base64_decode((const unsigned char *)buffer, len,
2432 - ret->keyblob + ret->keyblob_len, &outlen) != CRYPT_OK){
2433 - errmsg = "Error decoding base64";
2434 - goto error;
2435 - }
2436 - ret->keyblob_len += outlen;
2437 + buf = buf_resize(buf, buf->size + len);
2438 + buf_putbytes(buf, buffer, len);
2439 + }
2440 + }
2441 +
2442 + if (buf && buf->len) {
2443 + ret->keyblob_size = ret->keyblob_len + buf->len*4/3 + 256;
2444 + ret->keyblob = (unsigned char*)m_realloc(ret->keyblob, ret->keyblob_size);
2445 + len = ret->keyblob_size;
2446 + if (base64_decode((const unsigned char *)buf->data, buf->len,
2447 + ret->keyblob, &len) != CRYPT_OK){
2448 + errmsg = "Error decoding base64";
2449 + goto error;
2450 + }
2451 + ret->keyblob_len = len;
2452 + }
2453 +
2454 + if (ret->type == OSSH_PKEY) {
2455 + if (ret->keyblob_len < OSSH_PKEY_BLOBLEN ||
2456 + memcmp(ret->keyblob, OSSH_PKEY_BLOB, OSSH_PKEY_BLOBLEN)) {
2457 + errmsg = "Error decoding OpenSSH key";
2458 + goto error;
2459 }
2460 + ret->keyblob_len -= OSSH_PKEY_BLOBLEN;
2461 + memmove(ret->keyblob, ret->keyblob + OSSH_PKEY_BLOBLEN, ret->keyblob_len);
2462 }
2463
2464 if (ret->keyblob_len == 0 || !ret->keyblob) {
2465 @@ -474,10 +498,18 @@ static struct openssh_key *load_openssh_key(const char *filename)
2466 goto error;
2467 }
2468
2469 + if (buf) {
2470 + buf_burn(buf);
2471 + buf_free(buf);
2472 + }
2473 m_burn(buffer, sizeof(buffer));
2474 return ret;
2475
2476 error:
2477 + if (buf) {
2478 + buf_burn(buf);
2479 + buf_free(buf);
2480 + }
2481 m_burn(buffer, sizeof(buffer));
2482 if (ret) {
2483 if (ret->keyblob) {
2484 @@ -569,6 +601,57 @@ static sign_key *openssh_read(const char *filename, const char * UNUSED(passphra
2485 #endif
2486 }
2487
2488 + /*
2489 + * Now we have a decrypted key blob, which contains OpenSSH
2490 + * encoded private key. We must now untangle the OpenSSH format.
2491 + */
2492 + if (key->type == OSSH_PKEY) {
2493 + blobbuf = buf_new(key->keyblob_len);
2494 + buf_putbytes(blobbuf, key->keyblob, key->keyblob_len);
2495 + buf_setpos(blobbuf, 0);
2496 +
2497 + /* limit length of private key blob */
2498 + len = buf_getint(blobbuf);
2499 + buf_setlen(blobbuf, blobbuf->pos + len);
2500 +
2501 + type = DROPBEAR_SIGNKEY_ANY;
2502 + if (buf_get_pub_key(blobbuf, retkey, &type)
2503 + != DROPBEAR_SUCCESS) {
2504 + errmsg = "Error parsing OpenSSH key";
2505 + goto ossh_error;
2506 + }
2507 +
2508 + /* restore full length */
2509 + buf_setlen(blobbuf, key->keyblob_len);
2510 +
2511 + if (type != DROPBEAR_SIGNKEY_NONE) {
2512 + retkey->type = type;
2513 + /* limit length of private key blob */
2514 + len = buf_getint(blobbuf);
2515 + buf_setlen(blobbuf, blobbuf->pos + len);
2516 +#if DROPBEAR_ED25519
2517 + if (type == DROPBEAR_SIGNKEY_ED25519) {
2518 + buf_incrpos(blobbuf, 8);
2519 + buf_eatstring(blobbuf);
2520 + buf_eatstring(blobbuf);
2521 + buf_incrpos(blobbuf, -SSH_SIGNKEY_ED25519_LEN-4);
2522 + if (buf_get_ed25519_priv_key(blobbuf, retkey->ed25519key)
2523 + == DROPBEAR_SUCCESS) {
2524 + errmsg = NULL;
2525 + retval = retkey;
2526 + goto error;
2527 + }
2528 + }
2529 +#endif
2530 + }
2531 +
2532 + errmsg = "Unsupported OpenSSH key type";
2533 + ossh_error:
2534 + sign_key_free(retkey);
2535 + retkey = NULL;
2536 + goto error;
2537 + }
2538 +
2539 /*
2540 * Now we have a decrypted key blob, which contains an ASN.1
2541 * encoded private key. We must now untangle the ASN.1.
2542 @@ -1129,6 +1212,51 @@ static int openssh_write(const char *filename, sign_key *key,
2543 }
2544 #endif
2545
2546 +#if DROPBEAR_ED25519
2547 + if (key->type == DROPBEAR_SIGNKEY_ED25519) {
2548 + buffer *buf = buf_new(300);
2549 + keyblob = buf_new(100);
2550 + extrablob = buf_new(200);
2551 +
2552 + /* private key blob w/o header */
2553 + buf_put_priv_key(keyblob, key, key->type);
2554 + buf_setpos(keyblob, 0);
2555 + buf_incrpos(keyblob, buf_getint(keyblob));
2556 + len = buf_getint(keyblob);
2557 +
2558 + /* header */
2559 + buf_putbytes(buf, OSSH_PKEY_BLOB, OSSH_PKEY_BLOBLEN);
2560 +
2561 + /* public key */
2562 + buf_put_pub_key(buf, key, key->type);
2563 +
2564 + /* private key */
2565 + buf_incrwritepos(extrablob, 4);
2566 + buf_put_pub_key(extrablob, key, key->type);
2567 + buf_putstring(extrablob, buf_getptr(keyblob, len), len);
2568 + /* comment */
2569 + buf_putstring(extrablob, "", 0);
2570 + /* padding to cipher block length */
2571 + len = (extrablob->len+8) & ~7;
2572 + for (i = 1; len - extrablob->len > 0; i++)
2573 + buf_putbyte(extrablob, i);
2574 + buf_setpos(extrablob, 0);
2575 + buf_putbytes(extrablob, "\0\0\0\0\0\0\0\0", 8);
2576 + buf_putbufstring(buf, extrablob);
2577 +
2578 + outlen = len = pos = buf->len;
2579 + outblob = (unsigned char*)m_malloc(outlen);
2580 + memcpy(outblob, buf->data, buf->len);
2581 +
2582 + buf_burn(buf);
2583 + buf_free(buf);
2584 + buf = NULL;
2585 +
2586 + header = "-----BEGIN OPENSSH PRIVATE KEY-----\n";
2587 + footer = "-----END OPENSSH PRIVATE KEY-----\n";
2588 + }
2589 +#endif
2590 +
2591 /*
2592 * Padding on OpenSSH keys is deterministic. The number of
2593 * padding bytes is always more than zero, and always at most
2594 diff --git a/signkey.c b/signkey.c
2595 index 88f06c7..a0af44a 100644
2596 --- a/signkey.c
2597 +++ b/signkey.c
2598 @@ -39,8 +39,11 @@ static const char * const signkey_names[DROPBEAR_SIGNKEY_NUM_NAMED] = {
2599 #if DROPBEAR_ECDSA
2600 "ecdsa-sha2-nistp256",
2601 "ecdsa-sha2-nistp384",
2602 - "ecdsa-sha2-nistp521"
2603 + "ecdsa-sha2-nistp521",
2604 #endif /* DROPBEAR_ECDSA */
2605 +#if DROPBEAR_ED25519
2606 + "ssh-ed25519",
2607 +#endif /* DROPBEAR_ED25519 */
2608 };
2609
2610 /* malloc a new sign_key and set the dss and rsa keys to NULL */
2611 @@ -107,6 +110,10 @@ Be sure to check both (ret != NULL) and (*ret != NULL) */
2612 void **
2613 signkey_key_ptr(sign_key *key, enum signkey_type type) {
2614 switch (type) {
2615 +#if DROPBEAR_ED25519
2616 + case DROPBEAR_SIGNKEY_ED25519:
2617 + return (void**)&key->ed25519key;
2618 +#endif
2619 #if DROPBEAR_ECDSA
2620 #if DROPBEAR_ECC_256
2621 case DROPBEAR_SIGNKEY_ECDSA_NISTP256:
2622 @@ -200,6 +207,17 @@ int buf_get_pub_key(buffer *buf, sign_key *key, enum signkey_type *type) {
2623 }
2624 }
2625 #endif
2626 +#if DROPBEAR_ED25519
2627 + if (keytype == DROPBEAR_SIGNKEY_ED25519) {
2628 + ed25519_key_free(key->ed25519key);
2629 + key->ed25519key = m_malloc(sizeof(*key->ed25519key));
2630 + ret = buf_get_ed25519_pub_key(buf, key->ed25519key);
2631 + if (ret == DROPBEAR_FAILURE) {
2632 + m_free(key->ed25519key);
2633 + key->ed25519key = NULL;
2634 + }
2635 + }
2636 +#endif
2637
2638 TRACE2(("leave buf_get_pub_key"))
2639
2640 @@ -270,6 +288,17 @@ int buf_get_priv_key(buffer *buf, sign_key *key, enum signkey_type *type) {
2641 }
2642 }
2643 #endif
2644 +#if DROPBEAR_ED25519
2645 + if (keytype == DROPBEAR_SIGNKEY_ED25519) {
2646 + ed25519_key_free(key->ed25519key);
2647 + key->ed25519key = m_malloc(sizeof(*key->ed25519key));
2648 + ret = buf_get_ed25519_priv_key(buf, key->ed25519key);
2649 + if (ret == DROPBEAR_FAILURE) {
2650 + m_free(key->ed25519key);
2651 + key->ed25519key = NULL;
2652 + }
2653 + }
2654 +#endif
2655
2656 TRACE2(("leave buf_get_priv_key"))
2657
2658 @@ -302,6 +331,11 @@ void buf_put_pub_key(buffer* buf, sign_key *key, enum signkey_type type) {
2659 buf_put_ecdsa_pub_key(pubkeys, *eck);
2660 }
2661 }
2662 +#endif
2663 +#if DROPBEAR_ED25519
2664 + if (type == DROPBEAR_SIGNKEY_ED25519) {
2665 + buf_put_ed25519_pub_key(pubkeys, key->ed25519key);
2666 + }
2667 #endif
2668 if (pubkeys->len == 0) {
2669 dropbear_exit("Bad key types in buf_put_pub_key");
2670 @@ -341,6 +375,13 @@ void buf_put_priv_key(buffer* buf, sign_key *key, enum signkey_type type) {
2671 return;
2672 }
2673 }
2674 +#endif
2675 +#if DROPBEAR_ED25519
2676 + if (type == DROPBEAR_SIGNKEY_ED25519) {
2677 + buf_put_ed25519_priv_key(buf, key->ed25519key);
2678 + TRACE(("leave buf_put_priv_key: ed25519 done"))
2679 + return;
2680 + }
2681 #endif
2682 dropbear_exit("Bad key types in put pub key");
2683 }
2684 @@ -379,6 +420,10 @@ void sign_key_free(sign_key *key) {
2685 key->ecckey521 = NULL;
2686 }
2687 #endif
2688 +#endif
2689 +#if DROPBEAR_ED25519
2690 + ed25519_key_free(key->ed25519key);
2691 + key->ed25519key = NULL;
2692 #endif
2693
2694 m_free(key->filename);
2695 @@ -503,6 +548,11 @@ void buf_put_sign(buffer* buf, sign_key *key, enum signkey_type type,
2696 buf_put_ecdsa_sign(sigblob, *eck, data_buf);
2697 }
2698 }
2699 +#endif
2700 +#if DROPBEAR_ED25519
2701 + if (type == DROPBEAR_SIGNKEY_ED25519) {
2702 + buf_put_ed25519_sign(sigblob, key->ed25519key, data_buf);
2703 + }
2704 #endif
2705 if (sigblob->len == 0) {
2706 dropbear_exit("Non-matching signing type");
2707 @@ -555,6 +605,14 @@ int buf_verify(buffer * buf, sign_key *key, const buffer *data_buf) {
2708 }
2709 }
2710 #endif
2711 +#if DROPBEAR_ED25519
2712 + if (type == DROPBEAR_SIGNKEY_ED25519) {
2713 + if (key->ed25519key == NULL) {
2714 + dropbear_exit("No Ed25519 key to verify signature");
2715 + }
2716 + return buf_ed25519_verify(buf, key->ed25519key, data_buf);
2717 + }
2718 +#endif
2719
2720 dropbear_exit("Non-matching signing type");
2721 return DROPBEAR_FAILURE;
2722 diff --git a/signkey.h b/signkey.h
2723 index 59df3ee..fa39a02 100644
2724 --- a/signkey.h
2725 +++ b/signkey.h
2726 @@ -28,6 +28,7 @@
2727 #include "buffer.h"
2728 #include "dss.h"
2729 #include "rsa.h"
2730 +#include "ed25519.h"
2731
2732 enum signkey_type {
2733 #if DROPBEAR_RSA
2734 @@ -41,6 +42,9 @@ enum signkey_type {
2735 DROPBEAR_SIGNKEY_ECDSA_NISTP384,
2736 DROPBEAR_SIGNKEY_ECDSA_NISTP521,
2737 #endif /* DROPBEAR_ECDSA */
2738 +#if DROPBEAR_ED25519
2739 + DROPBEAR_SIGNKEY_ED25519,
2740 +#endif
2741 DROPBEAR_SIGNKEY_NUM_NAMED,
2742 DROPBEAR_SIGNKEY_ECDSA_KEYGEN = 70, /* just "ecdsa" for keygen */
2743 DROPBEAR_SIGNKEY_ANY = 80,
2744 @@ -78,6 +82,9 @@ struct SIGN_key {
2745 ecc_key * ecckey521;
2746 #endif
2747 #endif
2748 +#if DROPBEAR_ED25519
2749 + dropbear_ed25519_key * ed25519key;
2750 +#endif
2751 };
2752
2753 typedef struct SIGN_key sign_key;
2754 diff --git a/ssh.h b/ssh.h
2755 index f40b65a..db723b8 100644
2756 --- a/ssh.h
2757 +++ b/ssh.h
2758 @@ -105,6 +105,8 @@
2759 #define SSH_SIGNKEY_DSS_LEN 7
2760 #define SSH_SIGNKEY_RSA "ssh-rsa"
2761 #define SSH_SIGNKEY_RSA_LEN 7
2762 +#define SSH_SIGNKEY_ED25519 "ssh-ed25519"
2763 +#define SSH_SIGNKEY_ED25519_LEN 11
2764
2765 /* Agent commands. These aren't part of the spec, and are defined
2766 * only on the openssh implementation. */
2767 diff --git a/svr-kex.c b/svr-kex.c
2768 index 406ad97..af16d2f 100644
2769 --- a/svr-kex.c
2770 +++ b/svr-kex.c
2771 @@ -122,6 +122,11 @@ static void svr_ensure_hostkey() {
2772 case DROPBEAR_SIGNKEY_ECDSA_NISTP521:
2773 fn = ECDSA_PRIV_FILENAME;
2774 break;
2775 +#endif
2776 +#if DROPBEAR_ED25519
2777 + case DROPBEAR_SIGNKEY_ED25519:
2778 + fn = ED25519_PRIV_FILENAME;
2779 + break;
2780 #endif
2781 default:
2782 dropbear_assert(0);
2783 @@ -219,7 +224,8 @@ static void send_msg_kexdh_reply(mp_int *dh_e, buffer *ecdh_qs) {
2784 {
2785 struct kex_curve25519_param *param = gen_kexcurve25519_param();
2786 kexcurve25519_comb_key(param, ecdh_qs, svr_opts.hostkey);
2787 - buf_putstring(ses.writepayload, (const char*)param->pub, CURVE25519_LEN);
2788 +
2789 + buf_putstring(ses.writepayload, param->pub, CURVE25519_LEN);
2790 free_kexcurve25519_param(param);
2791 }
2792 break;
2793 diff --git a/svr-runopts.c b/svr-runopts.c
2794 index d7a0d5a..d430825 100644
2795 --- a/svr-runopts.c
2796 +++ b/svr-runopts.c
2797 @@ -57,6 +57,9 @@ static void printhelp(const char * progname) {
2798 #if DROPBEAR_ECDSA
2799 " ecdsa %s\n"
2800 #endif
2801 +#if DROPBEAR_ED25519
2802 + " ed25519 %s\n"
2803 +#endif
2804 #if DROPBEAR_DELAY_HOSTKEY
2805 "-R Create hostkeys as required\n"
2806 #endif
2807 @@ -116,6 +119,9 @@ static void printhelp(const char * progname) {
2808 #endif
2809 #if DROPBEAR_ECDSA
2810 ECDSA_PRIV_FILENAME,
2811 +#endif
2812 +#if DROPBEAR_ED25519
2813 + ED25519_PRIV_FILENAME,
2814 #endif
2815 MAX_AUTH_TRIES,
2816 DROPBEAR_MAX_PORTS, DROPBEAR_DEFPORT, DROPBEAR_PIDFILE,
2817 @@ -538,6 +544,13 @@ static void loadhostkey(const char *keyfile, int fatal_duplicate) {
2818 }
2819 #endif
2820 #endif /* DROPBEAR_ECDSA */
2821 +
2822 +#if DROPBEAR_ED25519
2823 + if (type == DROPBEAR_SIGNKEY_ED25519) {
2824 + loadhostkey_helper("ed25519", (void**)&read_key->ed25519key, (void**)&svr_opts.hostkey->ed25519key, fatal_duplicate);
2825 + }
2826 +#endif
2827 +
2828 sign_key_free(read_key);
2829 TRACE(("leave loadhostkey"))
2830 }
2831 @@ -578,6 +591,9 @@ void load_all_hostkeys() {
2832
2833 #if DROPBEAR_ECDSA
2834 loadhostkey(ECDSA_PRIV_FILENAME, 0);
2835 +#endif
2836 +#if DROPBEAR_ED25519
2837 + loadhostkey(ED25519_PRIV_FILENAME, 0);
2838 #endif
2839 }
2840
2841 @@ -642,6 +658,14 @@ void load_all_hostkeys() {
2842 #endif
2843 #endif /* DROPBEAR_ECDSA */
2844
2845 +#if DROPBEAR_ED25519
2846 + if (!svr_opts.delay_hostkey && !svr_opts.hostkey->ed25519key) {
2847 + disablekey(DROPBEAR_SIGNKEY_ED25519);
2848 + } else {
2849 + any_keys = 1;
2850 + }
2851 +#endif
2852 +
2853 if (!any_keys) {
2854 dropbear_exit("No hostkeys available. 'dropbear -R' may be useful or run dropbearkey.");
2855 }
2856 diff --git a/sysoptions.h b/sysoptions.h
2857 index cfd5469..2c27caf 100644
2858 --- a/sysoptions.h
2859 +++ b/sysoptions.h
2860 @@ -145,7 +145,8 @@ If you test it please contact the Dropbear author */
2861 #define DROPBEAR_SHA384 (DROPBEAR_ECC_384)
2862 /* LTC SHA384 depends on SHA512 */
2863 #define DROPBEAR_SHA512 ((DROPBEAR_SHA2_512_HMAC) || (DROPBEAR_ECC_521) \
2864 - || (DROPBEAR_SHA384) || (DROPBEAR_DH_GROUP16))
2865 + || (DROPBEAR_SHA384) || (DROPBEAR_DH_GROUP16) \
2866 + || (DROPBEAR_ED25519))
2867 #define DROPBEAR_MD5 (DROPBEAR_MD5_HMAC)
2868
2869 #define DROPBEAR_DH_GROUP14 ((DROPBEAR_DH_GROUP14_SHA256) || (DROPBEAR_DH_GROUP14_SHA1))
2870 @@ -186,7 +187,7 @@ If you test it please contact the Dropbear author */
2871 /* For a 4096 bit DSS key, empirically determined */
2872 #define MAX_PRIVKEY_SIZE 1700
2873
2874 -#define MAX_HOSTKEYS 3
2875 +#define MAX_HOSTKEYS 4
2876
2877 /* The maximum size of the bignum portion of the kexhash buffer */
2878 /* Sect. 8 of the transport rfc 4253, K_S + e + f + K */
2879 @@ -252,7 +253,7 @@ If you test it please contact the Dropbear author */
2880 #error "At least one encryption algorithm must be enabled. AES128 is recommended."
2881 #endif
2882
2883 -#if !(DROPBEAR_RSA || DROPBEAR_DSS || DROPBEAR_ECDSA)
2884 +#if !(DROPBEAR_RSA || DROPBEAR_DSS || DROPBEAR_ECDSA || DROPBEAR_ED25519)
2885 #error "At least one hostkey or public-key algorithm must be enabled; RSA is recommended."
2886 #endif
2887
2888 --
2889 2.17.1
2890
Staging tree of dedeckeh