Mercurial > dropbear

comparison curve25519.c @ 1733:d529a52b2f7c coverity coverity

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
merge coverity from main
author Matt Johnston <matt@ucc.asn.au>
date Fri, 26 Jun 2020 21:07:34 +0800
parents 41a0ff8d5a89
children
comparison
equal deleted inserted replaced
1643:b59623a64678 1733:d529a52b2f7c
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 void 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 }
260 #endif /* DROPBEAR_CURVE25519 */
261
262 #if DROPBEAR_ED25519
263 static int crypto_hash(u8 *out,const u8 *m,u64 n)
264 {
265 hash_state hs;
266
267 sha512_init(&hs);
268 sha512_process(&hs, m, n);
269 return sha512_done(&hs, out);
270 }
271
272 sv add(gf p[4],gf q[4])
273 {
274 gf a,b,c,d,t,e,f,g,h;
275
276 Z(a, p[1], p[0]);
277 Z(t, q[1], q[0]);
278 M(a, a, t);
279 A(b, p[0], p[1]);
280 A(t, q[0], q[1]);
281 M(b, b, t);
282 M(c, p[3], q[3]);
283 M(c, c, D2);
284 M(d, p[2], q[2]);
285 A(d, d, d);
286 Z(e, b, a);
287 Z(f, d, c);
288 A(g, d, c);
289 A(h, b, a);
290
291 M(p[0], e, f);
292 M(p[1], h, g);
293 M(p[2], g, f);
294 M(p[3], e, h);
295 }
296
297 sv cswap(gf p[4],gf q[4],u8 b)
298 {
299 int i;
300 FOR(i,4)
301 sel25519(p[i],q[i],b);
302 }
303
304 sv pack(u8 *r,gf p[4])
305 {
306 gf tx, ty, zi;
307 inv25519(zi, p[2]);
308 M(tx, p[0], zi);
309 M(ty, p[1], zi);
310 pack25519(r, ty);
311 r[31] ^= par25519(tx) << 7;
312 }
313
314 sv scalarmult(gf p[4],gf q[4],const u8 *s)
315 {
316 int i;
317 set25519(p[0],gf0);
318 set25519(p[1],gf1);
319 set25519(p[2],gf1);
320 set25519(p[3],gf0);
321 for (i = 255;i >= 0;--i) {
322 u8 b = (s[i/8]>>(i&7))&1;
323 cswap(p,q,b);
324 add(q,p);
325 add(p,p);
326 cswap(p,q,b);
327 }
328 }
329
330 sv scalarbase(gf p[4],const u8 *s)
331 {
332 gf q[4];
333 set25519(q[0],X);
334 set25519(q[1],Y);
335 set25519(q[2],gf1);
336 M(q[3],X,Y);
337 scalarmult(p,q,s);
338 }
339
340 void dropbear_ed25519_make_key(u8 *pk,u8 *sk)
341 {
342 u8 d[64];
343 gf p[4];
344
345 genrandom(sk, 32);
346
347 crypto_hash(d, sk, 32);
348 d[0] &= 248;
349 d[31] &= 127;
350 d[31] |= 64;
351
352 scalarbase(p,d);
353 pack(pk,p);
354 }
355
356 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};
357
358 sv modL(u8 *r,i64 x[64])
359 {
360 i64 carry,i,j;
361 for (i = 63;i >= 32;--i) {
362 carry = 0;
363 for (j = i - 32;j < i - 12;++j) {
364 x[j] += carry - 16 * x[i] * L[j - (i - 32)];
365 carry = (x[j] + 128) >> 8;
366 x[j] -= carry << 8;
367 }
368 x[j] += carry;
369 x[i] = 0;
370 }
371 carry = 0;
372 FOR(j,32) {
373 x[j] += carry - (x[31] >> 4) * L[j];
374 carry = x[j] >> 8;
375 x[j] &= 255;
376 }
377 FOR(j,32) x[j] -= carry * L[j];
378 FOR(i,32) {
379 x[i+1] += x[i] >> 8;
380 r[i] = x[i] & 255;
381 }
382 }
383
384 sv reduce(u8 *r)
385 {
386 i64 x[64],i;
387 FOR(i,64) x[i] = (u64) r[i];
388 FOR(i,64) r[i] = 0;
389 modL(r,x);
390 }
391
392 void dropbear_ed25519_sign(const u8 *m,u32 mlen,u8 *s,u32 *slen,const u8 *sk, const u8 *pk)
393 {
394 hash_state hs;
395 u8 d[64],h[64],r[64];
396 i64 x[64];
397 gf p[4];
398 u32 i,j;
399
400 crypto_hash(d, sk, 32);
401 d[0] &= 248;
402 d[31] &= 127;
403 d[31] |= 64;
404
405 *slen = 64;
406
407 sha512_init(&hs);
408 sha512_process(&hs,d + 32,32);
409 sha512_process(&hs,m,mlen);
410 sha512_done(&hs,r);
411 reduce(r);
412 scalarbase(p,r);
413 pack(s,p);
414
415 sha512_init(&hs);
416 sha512_process(&hs,s,32);
417 sha512_process(&hs,pk,32);
418 sha512_process(&hs,m,mlen);
419 sha512_done(&hs,h);
420 reduce(h);
421
422 FOR(i,64) x[i] = 0;
423 FOR(i,32) x[i] = (u64) r[i];
424 FOR(i,32) FOR(j,32) x[i+j] += h[i] * (u64) d[j];
425 modL(s + 32,x);
426 }
427
428 #if DROPBEAR_SIGNKEY_VERIFY
429 static int unpackneg(gf r[4],const u8 p[32])
430 {
431 gf t, chk, num, den, den2, den4, den6;
432 set25519(r[2],gf1);
433 unpack25519(r[1],p);
434 S(num,r[1]);
435 M(den,num,D);
436 Z(num,num,r[2]);
437 A(den,r[2],den);
438
439 S(den2,den);
440 S(den4,den2);
441 M(den6,den4,den2);
442 M(t,den6,num);
443 M(t,t,den);
444
445 pow2523(t,t);
446 M(t,t,num);
447 M(t,t,den);
448 M(t,t,den);
449 M(r[0],t,den);
450
451 S(chk,r[0]);
452 M(chk,chk,den);
453 if (neq25519(chk, num)) M(r[0],r[0],I);
454
455 S(chk,r[0]);
456 M(chk,chk,den);
457 if (neq25519(chk, num)) return -1;
458
459 if (par25519(r[0]) == (p[31]>>7)) Z(r[0],gf0,r[0]);
460
461 M(r[3],r[0],r[1]);
462 return 0;
463 }
464
465 int dropbear_ed25519_verify(const u8 *m,u32 mlen,const u8 *s,u32 slen,const u8 *pk)
466 {
467 hash_state hs;
468 u8 t[32],h[64];
469 gf p[4],q[4];
470
471 if (slen < 64) return -1;
472
473 if (unpackneg(q,pk)) return -1;
474
475 sha512_init(&hs);
476 sha512_process(&hs,s,32);
477 sha512_process(&hs,pk,32);
478 sha512_process(&hs,m,mlen);
479 sha512_done(&hs,h);
480
481 reduce(h);
482 scalarmult(p,q,h);
483
484 scalarbase(q,s + 32);
485 add(p,q);
486 pack(t,p);
487
488 if (crypto_verify_32(s, t))
489 return -1;
490
491 return 0;
492 }
493 #endif /* DROPBEAR_SIGNKEY_VERIFY */
494
495 #endif /* DROPBEAR_ED25519 */
496
497 #endif /* DROPBEAR_CURVE25519 || DROPBEAR_ED25519 */