![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to newhope_ke.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / strongswan / src / libstrongswan / plugins / newhope|
Return to newhope_ke.c CVS log | Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / strongswan / src / libstrongswan / plugins / newhope |
1.1 misho 1: /*
2: * Copyright (C) 2016 Andreas Steffen
3: * HSR Hochschule fuer Technik Rapperswil
4: *
5: * Based on public domain code by Erdem Alkim, Léo Ducas, Thomas Pöppelmann,
6: * and Peter Schwabe.
7: *
8: * This program is free software; you can redistribute it and/or modify it
9: * under the terms of the GNU General Public License as published by the
10: * Free Software Foundation; either version 2 of the License, or (at your
11: * option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>.
12: *
13: * This program is distributed in the hope that it will be useful, but
14: * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
15: * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16: * for more details.
17: */
18:
19: #include "newhope_ke.h"
20: #include "newhope_noise.h"
21: #include "newhope_reconciliation.h"
22:
23: #include <ntt_fft.h>
24: #include <ntt_fft_reduce.h>
25: #include <crypto/diffie_hellman.h>
26: #include <utils/debug.h>
27:
28: static const int seed_len = 32; /* 256 bits */
29: static const int poly_len = 1792; /* size of 1024 packed 14-bit coefficients */
30: static const int rec_len = 256; /* size of 1024 packed 2-bit coefficients */
31:
32: typedef struct private_newhope_ke_t private_newhope_ke_t;
33:
34: /**
35: * Private data of an newhope_ke_t object.
36: */
37: struct private_newhope_ke_t {
38:
39: /**
40: * Public newhope_ke_t interface.
41: */
42: newhope_ke_t public;
43:
44: /**
45: * FFT parameter set
46: */
47: const ntt_fft_params_t *params;
48:
49: /**
50: * Secret noise polynomial s
51: */
52: uint32_t *s;
53:
54: /**
55: * Output polynomial u = a * NTT(s') + NTT(e')
56: */
57: uint32_t *u;
58:
59: /**
60: * Error reconciliation help bits
61: */
62: uint8_t *r;
63:
64: /**
65: * Shared secret
66: */
67: chunk_t shared_secret;
68:
69: };
70:
71: /**
72: * Derive 14-bit coefficients of polynomial a from 256 bit random seed
73: * using the SHAKE128 extended output function
74: */
75: static uint32_t* derive_a_poly(private_newhope_ke_t *this, chunk_t seed)
76: {
77: uint32_t *a;
78: uint8_t x[2];
79: int i = 0;
80: xof_t *xof;
81:
82: xof = lib->crypto->create_xof(lib->crypto, XOF_SHAKE_128);
83: if (!xof)
84: {
85: DBG1(DBG_LIB, "could not instantiate SHAKE128 XOF");
86: return NULL;
87: }
88:
89: if (!xof->set_seed(xof, seed))
90: {
91: DBG1(DBG_LIB, "could not set seed of SHAKE128 XOF");
92: xof->destroy(xof);
93: return NULL;
94: }
95:
96: /* allocate dynamic memory for polynomial a */
97: a = (uint32_t*)malloc(this->params->n * sizeof(uint32_t));
98:
99: while (i < this->params->n)
100: {
101: if (!xof->get_bytes(xof, sizeof(x), x))
102: {
103: DBG1(DBG_LIB, "could not get bytes from SHAKE128 XOF");
104: xof->destroy(xof);
105: free(a);
106: return NULL;
107: }
108:
109: /*
110: * Treat x as a 16 bit unsigned little endian integer
111: * and truncate to 14 bits
112: */
113: a[i] = uletoh16(x) & 0x3fff;
114:
115: if (a[i] < this->params->q)
116: {
117: i++;
118: }
119: }
120: xof->destroy(xof);
121:
122: return a;
123: }
124:
125: /**
126: * Pack four 14-bit coefficients into seven consecutive bytes
127: *
128: * 1 2 3
129: * 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
130: * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
131: * |L 0 0 0 0 0 0 0|L 1 H 0 0 0 0 0|M 1 1 1 1 1 1 1|L 2 2 2 H 1 1 1|
132: * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
133: * |M 2 2 2 2 2 2 2|L 3 3 3 3 3 H 2|H 3 3 3 3 3 3 3|L 0 0 0 0 0 0 0|
134: * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
135: */
136: static void pack_poly(private_newhope_ke_t *this, uint8_t *x, uint32_t *p)
137: {
138: int i;
139:
140: for (i = 0; i < this->params->n; i += 4)
141: {
142: *x++ = (p[i] & 0xff );
143: *x++ = (p[i] >> 8) | (p[i+1] << 6);
144: *x++ = (p[i+1] >> 2);
145: *x++ = (p[i+1] >> 10) | (p[i+2] << 4);
146: *x++ = (p[i+2] >> 4);
147: *x++ = (p[i+2] >> 12) | (p[i+3] << 2);
148: *x++ = (p[i+3] >> 6);
149: }
150: }
151:
152: /**
153: * Unpack seven consecutive bytes into four 14-bit coefficients
154: */
155: static uint32_t* unpack_poly(private_newhope_ke_t * this, uint8_t *x)
156: {
157: uint32_t *p;
158: int i;
159:
160: p = (uint32_t*)malloc(this->params->n * sizeof(uint32_t));
161:
162: for (i = 0; i < this->params->n; i += 4)
163: {
164: p[i] = x[0] | (((uint32_t)x[1] & 0x3f) << 8);
165: p[i+1] = (x[1] >> 6) | (((uint32_t)x[2]) << 2)
166: | (((uint32_t)x[3] & 0x0f) << 10);
167: p[i+2] = (x[3] >> 4) | (((uint32_t)x[4]) << 4)
168: | (((uint32_t)x[5] & 0x03) << 12);
169: p[i+3] = (x[5] >> 2) | (((uint32_t)x[6]) << 6);
170: x += 7;
171: }
172: for (i = 0; i < this->params->n; i++)
173: {
174: if (p[i] >= this->params->q)
175: {
176: DBG1(DBG_LIB, "polynomial coefficient must be smaller than %u",
177: this->params->q);
178: free(p);
179: return NULL;
180: }
181: }
182: return p;
183: }
184:
185: /**
186: * Multiply and add polynomials in the frequency domain
187: */
188: static uint32_t* multiply_add_poly(private_newhope_ke_t *this,
189: uint32_t *a, uint32_t *e)
190: {
191: ntt_fft_t *fft;
192: uint32_t *b, t;
193: int i;
194:
195: /* transform s and h to frequency domain */
196: fft = ntt_fft_create(this->params);
197: fft->transform(fft, this->s, this->s, FALSE);
198: fft->transform(fft, e, e, FALSE);
199: fft->destroy(fft);
200:
201: b = (uint32_t*)malloc(this->params->n * sizeof(uint32_t));
202:
203: /* compute b = a * s + e in the frequency domain */
204: for (i = 0; i < this->params->n; i++)
205: {
206: /* convert a[i] to Montgomery domain */
207: t = ntt_fft_mreduce(a[i] * this->params->r2, this->params);
208:
209: /* compute b[i] = a[i] * s[i] + e[i] in Montgomery domain */
210: t = ntt_fft_mreduce(t * this->s[i], this->params) + e[i];
211:
212: /* exit Montgomery domain before transmitting polynomial b */
213: b[i] = ntt_fft_mreduce(t, this->params);
214: }
215: memwipe(e, this->params->n * sizeof(uint32_t));
216:
217: return b;
218: }
219:
220: /**
221: * Multiply polynomials in the frequency domain and return to time domain
222: */
223: static uint32_t* multiply_ntt_inv_poly(private_newhope_ke_t *this, uint32_t *b)
224: {
225: ntt_fft_t *fft;
226: uint32_t *v, t;
227: int i;
228:
229: v = (uint32_t*)malloc(this->params->n * sizeof(uint32_t));
230:
231: for (i = 0; i < this->params->n; i++)
232: {
233: /* convert b[i] to Montgomery domain */
234: t = ntt_fft_mreduce(b[i] * this->params->r2, this->params);
235:
236: /* compute v[i] = b[i] * s[i] in Montgomery domain */
237: v[i] = ntt_fft_mreduce(t * this->s[i], this->params);
238: }
239:
240: /* transform v back to time domain */
241: fft = ntt_fft_create(this->params);
242: fft->transform(fft, v, v, TRUE);
243: fft->destroy(fft);
244:
245: return v;
246: }
247:
248: /**
249: * Pack four 2-bit coefficients into one byte
250: */
251: static void pack_rec(private_newhope_ke_t *this, uint8_t *x, uint8_t *r)
252: {
253: int i;
254:
255: for (i = 0; i < this->params->n; i += 4)
256: {
257: *x++ = r[i] | r[i+1] << 2 | r[i+2] << 4 | r[i+3] << 6;
258: }
259: }
260:
261: static uint8_t* unpack_rec(private_newhope_ke_t *this, uint8_t *x)
262: {
263: uint8_t *r;
264: int i;
265:
266: r = (uint8_t*)malloc(this->params->n);
267:
268: for (i = 0; i < this->params->n; i += 4)
269: {
270: r[i] = (*x) & 0x03;
271: r[i+1] = (*x >> 2) & 0x03;
272: r[i+2] = (*x >> 4) & 0x03;
273: r[i+3] = (*x >> 6) & 0x03;
274: x++;
275: }
276:
277: return r;
278: }
279:
280: METHOD(diffie_hellman_t, get_my_public_value, bool,
281: private_newhope_ke_t *this, chunk_t *value)
282: {
283: uint16_t n, q;
284: int i;
285:
286: /* Define some often-used constants */
287: n = this->params->n;
288: q = this->params->q;
289:
290: /* are we the initiator? */
291: if (this->u == NULL)
292: {
293: rng_t *rng;
294: uint32_t *a = NULL, *b = NULL, *e = NULL;
295: uint8_t noise_seed_buf[seed_len];
296: chunk_t noise_seed = { noise_seed_buf, seed_len};
297: chunk_t a_seed;
298: newhope_noise_t *noise = NULL;
299: bool success = FALSE;
300:
301: /* allocate space for public output value */
302: *value = chunk_alloc(poly_len + seed_len);
303: a_seed = chunk_create(value->ptr + poly_len, seed_len);
304:
305: /* create polynomial a from 256 bit random seed */
306: rng = lib->crypto->create_rng(lib->crypto, RNG_STRONG);
307: if (!rng)
308: {
309: DBG1(DBG_LIB, "could not instantiate random source");
310: return FALSE;
311: }
312: if (!rng->get_bytes(rng, seed_len, a_seed.ptr))
313: {
314: DBG1(DBG_LIB, "could not generate seed for polynomial a");
315: goto end;
316: }
317:
318: a = derive_a_poly(this, a_seed);
319: if (a == NULL)
320: {
321: goto end;
322: }
323:
324: /* generate random seed for the derivation of noise polynomials */
325: if (!rng->get_bytes(rng, seed_len, noise_seed.ptr))
326: {
327: DBG1(DBG_LIB, "could not generate seed for noise polynomials");
328: goto end;
329: }
330:
331: /* create noise polynomial generator */
332: noise = newhope_noise_create(noise_seed);
333: if (!noise)
334: {
335: goto end;
336: }
337:
338: /* create noise polynomial s from seed with nonce = 0x00 */
339: this->s = noise->get_binomial_words(noise, 0x00, n, q);
340: if (this->s == NULL)
341: {
342: goto end;
343: }
344:
345: /* create noise polynomial e from seed with nonce = 0x01 */
346: e = noise->get_binomial_words(noise, 0x01, n, q);
347: if (e == NULL)
348: {
349: goto end;
350: }
351:
352: /* compute b = a * NTT(s) + NTT(e) */
353: b = multiply_add_poly(this, a, e);
354:
355: DBG3(DBG_LIB, " i a[i] b[i]");
356: for (i = 0; i < n; i++)
357: {
358: DBG3(DBG_LIB, "%4d %5u %5u", i, a[i], b[i]);
359: }
360:
361: /* pack coefficients of polynomial b */
362: pack_poly(this, value->ptr, b);
363: success = TRUE;
364:
365: end:
366: rng->destroy(rng);
367: DESTROY_IF(noise);
368: free(a);
369: free(b);
370: free(e);
371:
372: if (!success)
373: {
374: chunk_free(value);
375: }
376: return success;
377: }
378: else
379: {
380: DBG3(DBG_LIB, " i u[i] r[i]");
381: for (i = 0; i < n; i++)
382: {
383: DBG3(DBG_LIB, "%4d %5u %5u", i, this->u[i], this->r[i]);
384: }
385:
386: /* allocate space for public output value */
387: *value = chunk_alloc(poly_len + rec_len);
388:
389: /* pack coefficients of polynomial u */
390: pack_poly(this, value->ptr, this->u);
391:
392: /* pack coefficients of polynomial r */
393: pack_rec(this, value->ptr + poly_len, this->r);
394:
395: return TRUE;
396: }
397: }
398:
399: METHOD(diffie_hellman_t, get_shared_secret, bool,
400: private_newhope_ke_t *this, chunk_t *secret)
401: {
402: if (this->shared_secret.len == 0)
403: {
404: *secret = chunk_empty;
405: return FALSE;
406: }
407: *secret = chunk_clone(this->shared_secret);
408:
409: return TRUE;
410: }
411:
412: METHOD(diffie_hellman_t, set_other_public_value, bool,
413: private_newhope_ke_t *this, chunk_t value)
414: {
415: newhope_reconciliation_t * rec;
416: uint16_t n, q;
417: int i;
418:
419: /* Define some often-used constants */
420: n = this->params->n;
421: q = this->params->q;
422:
423: /* are we the responder? */
424: if (this->s == NULL)
425: {
426: uint32_t *a = NULL, *b = NULL, *e1 = NULL, *e2 = NULL, *v = NULL, t;
427: uint8_t *rbits = NULL;
428: uint8_t noise_seed_buf[seed_len];
429: chunk_t noise_seed = { noise_seed_buf, seed_len };
430: chunk_t a_seed;
431: newhope_noise_t *noise = NULL;
432: rng_t *rng = NULL;
433: bool success = FALSE;
434:
435: if (value.len != poly_len + seed_len)
436: {
437: DBG1(DBG_LIB, "received %N KE payload of incorrect size",
438: diffie_hellman_group_names, NH_128_BIT);
439: return FALSE;
440: }
441: a_seed = chunk_create(value.ptr + poly_len, seed_len);
442:
443: a = derive_a_poly(this, a_seed);
444: if (a == NULL)
445: {
446: return FALSE;
447: }
448:
449: b = unpack_poly(this, value.ptr);
450: if (b == NULL)
451: {
452: goto end;
453: }
454:
455: /* debug output of polynomials a and b */
456: DBG3(DBG_LIB, " i a[i] b[i]");
457: for (i = 0; i < n; i++)
458: {
459: DBG3(DBG_LIB, "%4d %5u %5u", i, a[i], b[i]);
460: }
461:
462: /* generate random seed for the derivation of noise polynomials */
463: rng = lib->crypto->create_rng(lib->crypto, RNG_STRONG);
464: if (!rng)
465: {
466: DBG1(DBG_LIB, "could not instantiate random source");
467: goto end;
468: }
469: if (!rng->get_bytes(rng, seed_len, noise_seed.ptr))
470: {
471: DBG1(DBG_LIB, "could not generate seed for noise polynomials");
472: goto end;
473: }
474:
475: /* create noise polynomial generator */
476: noise = newhope_noise_create(noise_seed);
477: if (!noise)
478: {
479: goto end;
480: }
481:
482: /* create noise polynomial s' from seed with nonce = 0x00 */
483: this->s = noise->get_binomial_words(noise, 0x00, n, q);
484: if (this->s == NULL)
485: {
486: goto end;
487: }
488:
489: /* create noise polynomial e' from seed with nonce = 0x01 */
490: e1 = noise->get_binomial_words(noise, 0x01, n, q);
491: if (e1 == NULL)
492: {
493: goto end;
494: }
495:
496: /* create noise polynomial e'' from seed with nonce = 0x02 */
497: e2 = noise->get_binomial_words(noise, 0x02, n, q);
498: if (e2 == NULL)
499: {
500: goto end;
501: }
502:
503: /* compute u = a * NTT(s') + NTT(e') */
504: this->u = multiply_add_poly(this, a, e1);
505:
506: /* compute v = NTT_inv( b * NTT(s') ) */
507: v = multiply_ntt_inv_poly(this, b);
508:
509: /* compute v = v + e'' */
510: for (i = 0; i < n; i++)
511: {
512: t = v[i] + e2[i];
513: v[i] = (t < q) ? t : t - q;
514: }
515: memwipe(e2, n * sizeof(uint32_t));
516:
517: /* create uniform noise bytes from seed with nonce = 0x02 */
518: rbits = noise->get_uniform_bytes(noise, 0x03, n/(4*8));
519:
520: rec = newhope_reconciliation_create(n, q);
521: this->r = rec->help_reconcile(rec, v, rbits);
522: free(rbits);
523: this->shared_secret = rec->reconcile(rec, v, this->r);
524: rec->destroy(rec);
525:
526: DBG4(DBG_LIB, "key: %B", &this->shared_secret);
527: success = TRUE;
528:
529: end:
530: DESTROY_IF(rng);
531: DESTROY_IF(noise);
532: free(a);
533: free(b);
534: free(e1);
535: free(e2);
536: free(v);
537:
538: return success;
539: }
540: else
541: {
542: uint32_t *v;
543:
544: if (value.len != poly_len + rec_len)
545: {
546: DBG1(DBG_LIB, "received %N KE payload of incorrect size",
547: diffie_hellman_group_names, NH_128_BIT);
548: return FALSE;
549: }
550:
551: this->u = unpack_poly(this, value.ptr);
552: if (this->u == NULL)
553: {
554: return FALSE;
555: }
556:
557: this->r = unpack_rec(this, value.ptr + poly_len);
558: if (this->r == NULL)
559: {
560: return FALSE;
561: }
562:
563: DBG3(DBG_LIB, " i u[i] r[i]");
564: for (i = 0; i < n; i++)
565: {
566: DBG3(DBG_LIB, "%4d %5u %5u", i, this->u[i], this->r[i]);
567: }
568:
569: /* compute v' = NTT_inv( u * NTT(s) ) */
570: v = multiply_ntt_inv_poly(this, this->u);
571:
572: rec = newhope_reconciliation_create(n, q);
573: this->shared_secret = rec->reconcile(rec, v, this->r);
574: free(v);
575: rec->destroy(rec);
576:
577: DBG4(DBG_LIB, "key: %B", &this->shared_secret);
578:
579: return TRUE;
580: }
581: }
582:
583: METHOD(diffie_hellman_t, get_dh_group, diffie_hellman_group_t,
584: private_newhope_ke_t *this)
585: {
586: return NH_128_BIT;
587: }
588:
589: METHOD(diffie_hellman_t, destroy, void,
590: private_newhope_ke_t *this)
591: {
592: chunk_clear(&this->shared_secret);
593: memwipe(this->s, this->params->n * sizeof(uint32_t));
594: free(this->s);
595: free(this->u);
596: free(this->r);
597: free(this);
598: }
599:
600: /*
601: * Described in header.
602: */
603: newhope_ke_t *newhope_ke_create(diffie_hellman_group_t group, chunk_t g, chunk_t p)
604: {
605: private_newhope_ke_t *this;
606:
607: INIT(this,
608: .public = {
609: .dh = {
610: .get_shared_secret = _get_shared_secret,
611: .set_other_public_value = _set_other_public_value,
612: .get_my_public_value = _get_my_public_value,
613: .get_dh_group = _get_dh_group,
614: .destroy = _destroy,
615: },
616: },
617: .params = &ntt_fft_12289_1024,
618:
619: );
620:
621: return &this->public;
622: }