Annotation of embedaddon/strongswan/src/libstrongswan/plugins/newhope/newhope_ke.c, revision 1.1
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: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[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