Mercurial > dropbear

comparison curve25519.c @ 1659:d32bcb5c557d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add Ed25519 support (#91) * Add support for Ed25519 as a public key type Ed25519 is a elliptic curve signature scheme that offers better security than ECDSA and DSA and good performance. It may be used for both user and host keys. OpenSSH key import and fuzzer are not supported yet. Initially inspired by Peter Szabo. * Add curve25519 and ed25519 fuzzers * Add import and export of Ed25519 keys
author Vladislav Grishenko <themiron@users.noreply.github.com>
date Wed, 11 Mar 2020 21:09:45 +0500
parents
children 41a0ff8d5a89
comparison
equal deleted inserted replaced
1658:7402218141d4 1659:d32bcb5c557d
1 /*
2 * Dropbear - a SSH2 server
3 *
4 * Copyright (c) 2002,2003 Matt Johnston
5 * All rights reserved.
6 *
7 * Permission is hereby granted, free of charge, to any person obtaining a copy
8 * of this software and associated documentation files (the "Software"), to deal
9 * in the Software without restriction, including without limitation the rights
10 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
11 * copies of the Software, and to permit persons to whom the Software is
12 * furnished to do so, subject to the following conditions:
13 *
14 * The above copyright notice and this permission notice shall be included in
15 * all copies or substantial portions of the Software.
16 *
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
18 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
19 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
20 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
21 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
22 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
23 * SOFTWARE. */
24
25 #include "includes.h"
26 #include "dbrandom.h"
27 #include "curve25519.h"
28
29 #if DROPBEAR_CURVE25519 || DROPBEAR_ED25519
30
31 /* Modified TweetNaCl version 20140427, a self-contained public-domain C library.
32 * https://tweetnacl.cr.yp.to/ */
33
34 #define FOR(i,n) for (i = 0;i < n;++i)
35 #define sv static void
36
37 typedef unsigned char u8;
38 typedef unsigned long u32;
39 typedef unsigned long long u64;
40 typedef long long i64;
41 typedef i64 gf[16];
42
43 #if DROPBEAR_CURVE25519
44 static const gf
45 _121665 = {0xDB41,1};
46 #endif /* DROPBEAR_CURVE25519 */
47 #if DROPBEAR_ED25519
48 static const gf
49 gf0,
50 gf1 = {1},
51 D2 = {0xf159, 0x26b2, 0x9b94, 0xebd6, 0xb156, 0x8283, 0x149a, 0x00e0, 0xd130, 0xeef3, 0x80f2, 0x198e, 0xfce7, 0x56df, 0xd9dc, 0x2406},
52 X = {0xd51a, 0x8f25, 0x2d60, 0xc956, 0xa7b2, 0x9525, 0xc760, 0x692c, 0xdc5c, 0xfdd6, 0xe231, 0xc0a4, 0x53fe, 0xcd6e, 0x36d3, 0x2169},
53 Y = {0x6658, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666};
54 #if DROPBEAR_SIGNKEY_VERIFY
55 static const gf
56 D = {0x78a3, 0x1359, 0x4dca, 0x75eb, 0xd8ab, 0x4141, 0x0a4d, 0x0070, 0xe898, 0x7779, 0x4079, 0x8cc7, 0xfe73, 0x2b6f, 0x6cee, 0x5203},
57 I = {0xa0b0, 0x4a0e, 0x1b27, 0xc4ee, 0xe478, 0xad2f, 0x1806, 0x2f43, 0xd7a7, 0x3dfb, 0x0099, 0x2b4d, 0xdf0b, 0x4fc1, 0x2480, 0x2b83};
58 #endif /* DROPBEAR_SIGNKEY_VERIFY */
59 #endif /* DROPBEAR_ED25519 */
60
61 #if DROPBEAR_ED25519
62 #if DROPBEAR_SIGNKEY_VERIFY
63 static int vn(const u8 *x,const u8 *y,u32 n)
64 {
65 u32 i,d = 0;
66 FOR(i,n) d |= x[i]^y[i];
67 return (1 & ((d - 1) >> 8)) - 1;
68 }
69
70 static int crypto_verify_32(const u8 *x,const u8 *y)
71 {
72 return vn(x,y,32);
73 }
74 #endif /* DROPBEAR_SIGNKEY_VERIFY */
75
76 sv set25519(gf r, const gf a)
77 {
78 int i;
79 FOR(i,16) r[i]=a[i];
80 }
81 #endif /* DROPBEAR_ED25519 */
82
83 sv car25519(gf o)
84 {
85 int i;
86 i64 c;
87 FOR(i,16) {
88 o[i]+=(1LL<<16);
89 c=o[i]>>16;
90 o[(i+1)*(i<15)]+=c-1+37*(c-1)*(i==15);
91 o[i]-=c<<16;
92 }
93 }
94
95 sv sel25519(gf p,gf q,int b)
96 {
97 i64 t,i,c=~(b-1);
98 FOR(i,16) {
99 t= c&(p[i]^q[i]);
100 p[i]^=t;
101 q[i]^=t;
102 }
103 }
104
105 sv pack25519(u8 *o,const gf n)
106 {
107 int i,j,b;
108 gf m,t;
109 FOR(i,16) t[i]=n[i];
110 car25519(t);
111 car25519(t);
112 car25519(t);
113 FOR(j,2) {
114 m[0]=t[0]-0xffed;
115 for(i=1;i<15;i++) {
116 m[i]=t[i]-0xffff-((m[i-1]>>16)&1);
117 m[i-1]&=0xffff;
118 }
119 m[15]=t[15]-0x7fff-((m[14]>>16)&1);
120 b=(m[15]>>16)&1;
121 m[14]&=0xffff;
122 sel25519(t,m,1-b);
123 }
124 FOR(i,16) {
125 o[2*i]=t[i]&0xff;
126 o[2*i+1]=t[i]>>8;
127 }
128 }
129
130 #if DROPBEAR_ED25519
131 #if DROPBEAR_SIGNKEY_VERIFY
132 static int neq25519(const gf a, const gf b)
133 {
134 u8 c[32],d[32];
135 pack25519(c,a);
136 pack25519(d,b);
137 return crypto_verify_32(c,d);
138 }
139 #endif /* DROPBEAR_SIGNKEY_VERIFY */
140
141 static u8 par25519(const gf a)
142 {
143 u8 d[32];
144 pack25519(d,a);
145 return d[0]&1;
146 }
147 #endif /* DROPBEAR_ED25519 */
148
149 sv unpack25519(gf o, const u8 *n)
150 {
151 int i;
152 FOR(i,16) o[i]=n[2*i]+((i64)n[2*i+1]<<8);
153 o[15]&=0x7fff;
154 }
155
156 sv A(gf o,const gf a,const gf b)
157 {
158 int i;
159 FOR(i,16) o[i]=a[i]+b[i];
160 }
161
162 sv Z(gf o,const gf a,const gf b)
163 {
164 int i;
165 FOR(i,16) o[i]=a[i]-b[i];
166 }
167
168 sv M(gf o,const gf a,const gf b)
169 {
170 i64 i,j,t[31];
171 FOR(i,31) t[i]=0;
172 FOR(i,16) FOR(j,16) t[i+j]+=a[i]*b[j];
173 FOR(i,15) t[i]+=38*t[i+16];
174 FOR(i,16) o[i]=t[i];
175 car25519(o);
176 car25519(o);
177 }
178
179 sv S(gf o,const gf a)
180 {
181 M(o,a,a);
182 }
183
184 sv inv25519(gf o,const gf i)
185 {
186 gf c;
187 int a;
188 FOR(a,16) c[a]=i[a];
189 for(a=253;a>=0;a--) {
190 S(c,c);
191 if(a!=2&&a!=4) M(c,c,i);
192 }
193 FOR(a,16) o[a]=c[a];
194 }
195
196 #if DROPBEAR_ED25519 && DROPBEAR_SIGNKEY_VERIFY
197 sv pow2523(gf o,const gf i)
198 {
199 gf c;
200 int a;
201 FOR(a,16) c[a]=i[a];
202 for(a=250;a>=0;a--) {
203 S(c,c);
204 if(a!=1) M(c,c,i);
205 }
206 FOR(a,16) o[a]=c[a];
207 }
208 #endif /* DROPBEAR_ED25519 && DROPBEAR_SIGNKEY_VERIFY */
209
210 #if DROPBEAR_CURVE25519
211 int dropbear_curve25519_scalarmult(u8 *q,const u8 *n,const u8 *p)
212 {
213 u8 z[32];
214 i64 x[80],r,i;
215 gf a,b,c,d,e,f;
216 FOR(i,31) z[i]=n[i];
217 z[31]=(n[31]&127)|64;
218 z[0]&=248;
219 unpack25519(x,p);
220 FOR(i,16) {
221 b[i]=x[i];
222 d[i]=a[i]=c[i]=0;
223 }
224 a[0]=d[0]=1;
225 for(i=254;i>=0;--i) {
226 r=(z[i>>3]>>(i&7))&1;
227 sel25519(a,b,r);
228 sel25519(c,d,r);
229 A(e,a,c);
230 Z(a,a,c);
231 A(c,b,d);
232 Z(b,b,d);
233 S(d,e);
234 S(f,a);
235 M(a,c,a);
236 M(c,b,e);
237 A(e,a,c);
238 Z(a,a,c);
239 S(b,a);
240 Z(c,d,f);
241 M(a,c,_121665);
242 A(a,a,d);
243 M(c,c,a);
244 M(a,d,f);
245 M(d,b,x);
246 S(b,e);
247 sel25519(a,b,r);
248 sel25519(c,d,r);
249 }
250 FOR(i,16) {
251 x[i+16]=a[i];
252 x[i+32]=c[i];
253 x[i+48]=b[i];
254 x[i+64]=d[i];
255 }
256 inv25519(x+32,x+32);
257 M(x+16,x+16,x+32);
258 pack25519(q,x+16);
259 return 0;
260 }
261 #endif /* DROPBEAR_CURVE25519 */
262
263 #if DROPBEAR_ED25519
264 static int crypto_hash(u8 *out,const u8 *m,u64 n)
265 {
266 hash_state hs;
267
268 sha512_init(&hs);
269 sha512_process(&hs, m, n);
270 return sha512_done(&hs, out);
271 }
272
273 sv add(gf p[4],gf q[4])
274 {
275 gf a,b,c,d,t,e,f,g,h;
276
277 Z(a, p[1], p[0]);
278 Z(t, q[1], q[0]);
279 M(a, a, t);
280 A(b, p[0], p[1]);
281 A(t, q[0], q[1]);
282 M(b, b, t);
283 M(c, p[3], q[3]);
284 M(c, c, D2);
285 M(d, p[2], q[2]);
286 A(d, d, d);
287 Z(e, b, a);
288 Z(f, d, c);
289 A(g, d, c);
290 A(h, b, a);
291
292 M(p[0], e, f);
293 M(p[1], h, g);
294 M(p[2], g, f);
295 M(p[3], e, h);
296 }
297
298 sv cswap(gf p[4],gf q[4],u8 b)
299 {
300 int i;
301 FOR(i,4)
302 sel25519(p[i],q[i],b);
303 }
304
305 sv pack(u8 *r,gf p[4])
306 {
307 gf tx, ty, zi;
308 inv25519(zi, p[2]);
309 M(tx, p[0], zi);
310 M(ty, p[1], zi);
311 pack25519(r, ty);
312 r[31] ^= par25519(tx) << 7;
313 }
314
315 sv scalarmult(gf p[4],gf q[4],const u8 *s)
316 {
317 int i;
318 set25519(p[0],gf0);
319 set25519(p[1],gf1);
320 set25519(p[2],gf1);
321 set25519(p[3],gf0);
322 for (i = 255;i >= 0;--i) {
323 u8 b = (s[i/8]>>(i&7))&1;
324 cswap(p,q,b);
325 add(q,p);
326 add(p,p);
327 cswap(p,q,b);
328 }
329 }
330
331 sv scalarbase(gf p[4],const u8 *s)
332 {
333 gf q[4];
334 set25519(q[0],X);
335 set25519(q[1],Y);
336 set25519(q[2],gf1);
337 M(q[3],X,Y);
338 scalarmult(p,q,s);
339 }
340
341 int dropbear_ed25519_make_key(u8 *pk,u8 *sk)
342 {
343 u8 d[64];
344 gf p[4];
345
346 genrandom(sk, 32);
347
348 crypto_hash(d, sk, 32);
349 d[0] &= 248;
350 d[31] &= 127;
351 d[31] |= 64;
352
353 scalarbase(p,d);
354 pack(pk,p);
355
356 return 0;
357 }
358
359 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};
360
361 sv modL(u8 *r,i64 x[64])
362 {
363 i64 carry,i,j;
364 for (i = 63;i >= 32;--i) {
365 carry = 0;
366 for (j = i - 32;j < i - 12;++j) {
367 x[j] += carry - 16 * x[i] * L[j - (i - 32)];
368 carry = (x[j] + 128) >> 8;
369 x[j] -= carry << 8;
370 }
371 x[j] += carry;
372 x[i] = 0;
373 }
374 carry = 0;
375 FOR(j,32) {
376 x[j] += carry - (x[31] >> 4) * L[j];
377 carry = x[j] >> 8;
378 x[j] &= 255;
379 }
380 FOR(j,32) x[j] -= carry * L[j];
381 FOR(i,32) {
382 x[i+1] += x[i] >> 8;
383 r[i] = x[i] & 255;
384 }
385 }
386
387 sv reduce(u8 *r)
388 {
389 i64 x[64],i;
390 FOR(i,64) x[i] = (u64) r[i];
391 FOR(i,64) r[i] = 0;
392 modL(r,x);
393 }
394
395 int dropbear_ed25519_sign(const u8 *m,u32 mlen,u8 *s,u32 *slen,const u8 *sk, const u8 *pk)
396 {
397 hash_state hs;
398 u8 d[64],h[64],r[64];
399 i64 x[64];
400 gf p[4];
401 u32 i,j;
402
403 crypto_hash(d, sk, 32);
404 d[0] &= 248;
405 d[31] &= 127;
406 d[31] |= 64;
407
408 *slen = 64;
409
410 sha512_init(&hs);
411 sha512_process(&hs,d + 32,32);
412 sha512_process(&hs,m,mlen);
413 sha512_done(&hs,r);
414 reduce(r);
415 scalarbase(p,r);
416 pack(s,p);
417
418 sha512_init(&hs);
419 sha512_process(&hs,s,32);
420 sha512_process(&hs,pk,32);
421 sha512_process(&hs,m,mlen);
422 sha512_done(&hs,h);
423 reduce(h);
424
425 FOR(i,64) x[i] = 0;
426 FOR(i,32) x[i] = (u64) r[i];
427 FOR(i,32) FOR(j,32) x[i+j] += h[i] * (u64) d[j];
428 modL(s + 32,x);
429
430 return 0;
431 }
432
433 #if DROPBEAR_SIGNKEY_VERIFY
434 static int unpackneg(gf r[4],const u8 p[32])
435 {
436 gf t, chk, num, den, den2, den4, den6;
437 set25519(r[2],gf1);
438 unpack25519(r[1],p);
439 S(num,r[1]);
440 M(den,num,D);
441 Z(num,num,r[2]);
442 A(den,r[2],den);
443
444 S(den2,den);
445 S(den4,den2);
446 M(den6,den4,den2);
447 M(t,den6,num);
448 M(t,t,den);
449
450 pow2523(t,t);
451 M(t,t,num);
452 M(t,t,den);
453 M(t,t,den);
454 M(r[0],t,den);
455
456 S(chk,r[0]);
457 M(chk,chk,den);
458 if (neq25519(chk, num)) M(r[0],r[0],I);
459
460 S(chk,r[0]);
461 M(chk,chk,den);
462 if (neq25519(chk, num)) return -1;
463
464 if (par25519(r[0]) == (p[31]>>7)) Z(r[0],gf0,r[0]);
465
466 M(r[3],r[0],r[1]);
467 return 0;
468 }
469
470 int dropbear_ed25519_verify(const u8 *m,u32 mlen,const u8 *s,u32 slen,const u8 *pk)
471 {
472 hash_state hs;
473 u8 t[32],h[64];
474 gf p[4],q[4];
475
476 if (slen < 64) return -1;
477
478 if (unpackneg(q,pk)) return -1;
479
480 sha512_init(&hs);
481 sha512_process(&hs,s,32);
482 sha512_process(&hs,pk,32);
483 sha512_process(&hs,m,mlen);
484 sha512_done(&hs,h);
485
486 reduce(h);
487 scalarmult(p,q,h);
488
489 scalarbase(q,s + 32);
490 add(p,q);
491 pack(t,p);
492
493 if (crypto_verify_32(s, t))
494 return -1;
495
496 return 0;
497 }
498 #endif /* DROPBEAR_SIGNKEY_VERIFY */
499
500 #endif /* DROPBEAR_ED25519 */
501
502 #endif /* DROPBEAR_CURVE25519 || DROPBEAR_ED25519 */