Return to bliss_private_key.c CVS log | Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / strongswan / src / libstrongswan / plugins / bliss |
1.1 misho 1: /* 2: * Copyright (C) 2014-2016 Andreas Steffen 3: * HSR Hochschule fuer Technik Rapperswil 4: * 5: * This program is free software; you can redistribute it and/or modify it 6: * under the terms of the GNU General Public License as published by the 7: * Free Software Foundation; either version 2 of the License, or (at your 8: * option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>. 9: * 10: * This program is distributed in the hope that it will be useful, but 11: * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 12: * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 13: * for more details. 14: */ 15: 16: #include "bliss_private_key.h" 17: #include "bliss_public_key.h" 18: #include "bliss_param_set.h" 19: #include "bliss_utils.h" 20: #include "bliss_sampler.h" 21: #include "bliss_signature.h" 22: #include "bliss_bitpacker.h" 23: #include "ntt_fft.h" 24: #include "ntt_fft_reduce.h" 25: 26: #include <crypto/xofs/xof_bitspender.h> 27: #include <asn1/asn1.h> 28: #include <asn1/asn1_parser.h> 29: #include <asn1/oid.h> 30: 31: #define _GNU_SOURCE 32: #include <stdlib.h> 33: 34: typedef struct private_bliss_private_key_t private_bliss_private_key_t; 35: 36: #define SECRET_KEY_TRIALS_MAX 50 37: 38: /** 39: * Private data of a bliss_private_key_t object. 40: */ 41: struct private_bliss_private_key_t { 42: /** 43: * Public interface for this signer. 44: */ 45: bliss_private_key_t public; 46: 47: /** 48: * BLISS signature parameter set 49: */ 50: const bliss_param_set_t *set; 51: 52: /** 53: * BLISS secret key S1 (coefficients of polynomial f) 54: */ 55: int8_t *s1; 56: 57: /** 58: * BLISS secret key S2 (coefficients of polynomial 2g + 1) 59: */ 60: int8_t *s2; 61: 62: /** 63: * NTT of BLISS public key a (coefficients of polynomial (2g + 1)/f) 64: */ 65: uint32_t *A; 66: 67: /** 68: * NTT of BLISS public key in Montgomery representation Ar = rA mod 69: */ 70: uint32_t *Ar; 71: 72: /** 73: * reference count 74: */ 75: refcount_t ref; 76: }; 77: 78: METHOD(private_key_t, get_type, key_type_t, 79: private_bliss_private_key_t *this) 80: { 81: return KEY_BLISS; 82: } 83: 84: /** 85: * Multiply secret vector s with binary challenge vector c 86: */ 87: static void multiply_by_c(int8_t *s, int n, uint16_t *c_indices, 88: uint16_t kappa, int32_t *product) 89: { 90: int i, j, index; 91: 92: for (i = 0; i < n; i++) 93: { 94: product[i] = 0; 95: 96: for (j = 0; j < kappa; j++) 97: { 98: index = c_indices[j]; 99: if (i - index < 0) 100: { 101: product[i] -= s[i - index + n]; 102: } 103: else 104: { 105: product[i] += s[i - index]; 106: } 107: } 108: } 109: } 110: 111: /** 112: * BLISS-B GreedySC algorithm 113: */ 114: static void greedy_sc(int8_t *s1, int8_t *s2, int n, uint16_t *c_indices, 115: uint16_t kappa, int32_t *v1, int32_t *v2) 116: { 117: int i, j, index; 118: int32_t sign; 119: 120: for (i = 0; i < n; i++) 121: { 122: v1[i] = v2[i] = 0; 123: } 124: for (j = 0; j < kappa; j++) 125: { 126: index = c_indices[j]; 127: sign = 0; 128: 129: for (i = 0; i < index; i++) 130: { 131: sign -= (v1[i] * s1[i - index + n] + v2[i] * s2[i - index + n]); 132: } 133: for (i = index; i < n; i++) 134: { 135: sign += (v1[i] * s1[i - index] + v2[i] * s2[i - index]); 136: } 137: for (i = 0; i < index; i++) 138: { 139: if (sign > 0) 140: { 141: v1[i] += s1[i - index + n]; 142: v2[i] += s2[i - index + n]; 143: } 144: else 145: { 146: v1[i] -= s1[i - index + n]; 147: v2[i] -= s2[i - index + n]; 148: } 149: } 150: for (i = index; i < n; i++) 151: { 152: if (sign > 0) 153: { 154: v1[i] -= s1[i - index]; 155: v2[i] -= s2[i - index]; 156: } 157: else 158: { 159: v1[i] += s1[i - index]; 160: v2[i] += s2[i - index]; 161: } 162: } 163: } 164: } 165: 166: /** 167: * Compute a BLISS signature 168: */ 169: static bool sign_bliss(private_bliss_private_key_t *this, hash_algorithm_t alg, 170: chunk_t data, chunk_t *signature) 171: { 172: ntt_fft_t *fft; 173: bliss_signature_t *sig; 174: bliss_sampler_t *sampler = NULL; 175: rng_t *rng; 176: hasher_t *hasher; 177: ext_out_function_t mgf1_alg, oracle_alg; 178: size_t mgf1_seed_len; 179: uint8_t mgf1_seed_buf[HASH_SIZE_SHA512], data_hash_buf[HASH_SIZE_SHA512]; 180: chunk_t mgf1_seed, data_hash; 181: uint16_t q, q2, p, p2, *c_indices, tests = 0; 182: uint32_t *ay; 183: int32_t *y1, *y2, *z1, *z2, *u, *s1c, *s2c; 184: int32_t y1_min = 0, y1i, y1_max = 0, y2_min = 0, y2i, y2_max = 0; 185: int32_t scalar, norm, ui; 186: int16_t *ud, *uz2d, *z2d, value; 187: int i, n; 188: double mean1 = 0, mean2 = 0, sigma1 = 0, sigma2 = 0; 189: bool accepted, positive, success = FALSE, use_bliss_b; 190: 191: /* Initialize signature */ 192: *signature = chunk_empty; 193: 194: /* Create data hash using configurable hash algorithm */ 195: hasher = lib->crypto->create_hasher(lib->crypto, alg); 196: if (!hasher) 197: { 198: return FALSE; 199: } 200: data_hash = chunk_create(data_hash_buf, hasher->get_hash_size(hasher)); 201: 202: if (!hasher->get_hash(hasher, data, data_hash_buf)) 203: { 204: hasher->destroy(hasher); 205: return FALSE; 206: } 207: hasher->destroy(hasher); 208: 209: /* Set MGF1 hash algorithm and seed length based on security strength */ 210: if (this->set->strength > 160) 211: { 212: mgf1_alg = XOF_MGF1_SHA256; 213: mgf1_seed_len = HASH_SIZE_SHA256; 214: } 215: else 216: { 217: mgf1_alg = XOF_MGF1_SHA1; 218: mgf1_seed_len = HASH_SIZE_SHA1; 219: } 220: mgf1_seed = chunk_create(mgf1_seed_buf, mgf1_seed_len); 221: 222: rng = lib->crypto->create_rng(lib->crypto, RNG_STRONG); 223: if (!rng) 224: { 225: return FALSE; 226: } 227: 228: /* MGF1 hash algorithm to be used for random oracle */ 229: oracle_alg = XOF_MGF1_SHA512; 230: 231: /* Initialize a couple of needed variables */ 232: n = this->set->n; 233: q = this->set->q; 234: p = this->set->p; 235: q2 = 2 * q; 236: p2 = p / 2; 237: ay = malloc(n * sizeof(uint32_t)); 238: z2 = malloc(n * sizeof(int32_t)); 239: s1c = malloc(n * sizeof(int32_t)); 240: s2c = malloc(n * sizeof(int32_t)); 241: u = malloc(n * sizeof(int32_t)); 242: uz2d = malloc(n * sizeof(int16_t)); 243: 244: sig = bliss_signature_create(this->set); 245: sig->get_parameters(sig, &z1, &z2d, &c_indices); 246: y1 = z1; 247: y2 = z2; 248: ud = z2d; 249: 250: fft = ntt_fft_create(this->set->fft_params); 251: 252: /* Use of the enhanced BLISS-B signature algorithm? */ 253: switch (this->set->id) 254: { 255: default: 256: case BLISS_I: 257: case BLISS_II: 258: case BLISS_III: 259: case BLISS_IV: 260: use_bliss_b = FALSE; 261: break; 262: case BLISS_B_I: 263: case BLISS_B_II: 264: case BLISS_B_III: 265: case BLISS_B_IV: 266: use_bliss_b = TRUE; 267: break; 268: } 269: 270: while (true) 271: { 272: tests++; 273: 274: if (!rng->get_bytes(rng, mgf1_seed_len, mgf1_seed_buf)) 275: { 276: goto end; 277: } 278: DESTROY_IF(sampler); 279: 280: sampler = bliss_sampler_create(mgf1_alg, mgf1_seed, this->set); 281: if (!sampler) 282: { 283: goto end; 284: } 285: 286: /* Gaussian sampling for vectors y1 and y2 */ 287: for (i = 0; i < n; i++) 288: { 289: if (!sampler->gaussian(sampler, &y1i) || 290: !sampler->gaussian(sampler, &y2i)) 291: { 292: goto end; 293: } 294: y1[i] = y1i; 295: y2[i] = y2i; 296: 297: /* Collect statistical data on rejection sampling */ 298: if (i == 0) 299: { 300: y1_min = y1_max = y1i; 301: y2_min = y2_max = y2i; 302: } 303: else 304: { 305: if (y1i < y1_min) 306: { 307: y1_min = y1i; 308: } 309: else if (y1i > y1_max) 310: { 311: y1_max = y1i; 312: } 313: if (y2i < y2_min) 314: { 315: y2_min = y2i; 316: } 317: else if (y2i > y2_max) 318: { 319: y2_max = y2i; 320: } 321: } 322: mean1 += y1i; 323: mean2 += y2i; 324: sigma1 += y1i * y1i; 325: sigma2 += y2i * y2i; 326: 327: ay[i] = y1i < 0 ? q + y1i : y1i; 328: } 329: 330: /* Compute statistics on vectors y1 and y2 */ 331: mean1 /= n; 332: mean2 /= n; 333: sigma1 /= n; 334: sigma2 /= n; 335: sigma2 -= mean1 * mean1; 336: sigma2 -= mean2 * mean2; 337: DBG2(DBG_LIB, "y1 = %d..%d (sigma2 = %5.0f, mean = %4.1f)", 338: y1_min, y1_max, sigma1, mean1); 339: DBG2(DBG_LIB, "y2 = %d..%d (sigma2 = %5.0f, mean = %4.1f)", 340: y2_min, y2_max, sigma2, mean2); 341: 342: fft->transform(fft, ay, ay, FALSE); 343: 344: for (i = 0; i < n; i++) 345: { 346: ay[i] = ntt_fft_mreduce(this->Ar[i] * ay[i], this->set->fft_params); 347: } 348: fft->transform(fft, ay, ay, TRUE); 349: 350: for (i = 0; i < n; i++) 351: { 352: ui = 2 * this->set->q2_inv * (int32_t)ay[i] + y2[i]; 353: u[i] = ((ui < 0) ? q2 + ui : ui) % q2; 354: } 355: bliss_utils_round_and_drop(this->set, u, ud); 356: 357: /* Detailed debugging information */ 358: DBG3(DBG_LIB, " i u[i] ud[i]"); 359: for (i = 0; i < n; i++) 360: { 361: DBG3(DBG_LIB, "%3d %6d %4d", i, u[i], ud[i]); 362: } 363: 364: if (!bliss_utils_generate_c(oracle_alg, data_hash, ud, this->set, 365: c_indices)) 366: { 367: goto end; 368: } 369: 370: if (use_bliss_b) 371: { 372: /* Compute v = (s1c, s2c) with the GreedySC algorithm */ 373: greedy_sc(this->s1, this->s2, n, c_indices, this->set->kappa, 374: s1c, s2c); 375: 376: /* Compute norm = ||v||^2 = ||Sc'||^2 */ 377: norm = bliss_utils_scalar_product(s1c, s1c, n) + 378: bliss_utils_scalar_product(s2c, s2c, n); 379: 380: /* Just in case. ||v||^2 <= P_max should always be fulfilled */ 381: if (norm > this->set->p_max) 382: { 383: goto end; 384: } 385: } 386: else 387: { 388: /* Compute s*c */ 389: multiply_by_c(this->s1, n, c_indices, this->set->kappa, s1c); 390: multiply_by_c(this->s2, n, c_indices, this->set->kappa, s2c); 391: 392: /* Compute norm = |Sc||^2 */ 393: norm = bliss_utils_scalar_product(s1c, s1c, n) + 394: bliss_utils_scalar_product(s2c, s2c, n); 395: } 396: 397: if (!sampler->bernoulli_exp(sampler, this->set->M - norm, &accepted)) 398: { 399: goto end; 400: } 401: if (use_bliss_b) 402: { 403: DBG2(DBG_LIB, "norm2(s1*c') + norm2(s2*c') = %u (%u max), %s", 404: norm, this->set->p_max, accepted ? "accepted" : "rejected"); 405: 406: } 407: else 408: { 409: DBG2(DBG_LIB, "norm2(s1*c) + norm2(s2*c) = %u, %s", 410: norm, accepted ? "accepted" : "rejected"); 411: } 412: if (!accepted) 413: { 414: continue; 415: } 416: 417: /* Compute z */ 418: if (!sampler->sign(sampler, &positive)) 419: { 420: goto end; 421: } 422: for (i = 0; i < n; i++) 423: { 424: if (positive) 425: { 426: z1[i] = y1[i] + s1c[i]; 427: z2[i] = y2[i] + s2c[i]; 428: } 429: else 430: { 431: z1[i] = y1[i] - s1c[i]; 432: z2[i] = y2[i] - s2c[i]; 433: } 434: } 435: /* Reject with probability 1/cosh(scalar/sigma^2) */ 436: scalar = bliss_utils_scalar_product(z1, s1c, n) + 437: bliss_utils_scalar_product(z2, s2c, n); 438: 439: if (!sampler->bernoulli_cosh(sampler, scalar, &accepted)) 440: { 441: goto end; 442: } 443: DBG2(DBG_LIB, "scalar(z1,s1*c) + scalar(z2,s2*c) = %d, %s", 444: scalar, accepted ? "accepted" : "rejected"); 445: if (!accepted) 446: { 447: continue; 448: } 449: 450: /* Compute z2 with dropped bits */ 451: for (i = 0; i < n; i++) 452: { 453: u[i] -= z2[i]; 454: if (u[i] < 0) 455: { 456: u[i] += q2; 457: } 458: else if (u[i] >= q2) 459: { 460: u[i] -= q2; 461: } 462: } 463: bliss_utils_round_and_drop(this->set, u, uz2d); 464: 465: for (i = 0; i < n; i++) 466: { 467: value = ud[i] - uz2d[i]; 468: if (value <= -p2) 469: { 470: value += p; 471: } 472: else if (value > p2) 473: { 474: value -= p; 475: } 476: z2d[i] = value; 477: } 478: 479: if (!bliss_utils_check_norms(this->set, z1, z2d)) 480: { 481: continue; 482: } 483: 484: *signature = sig->get_encoding(sig); 485: if (signature->len == 0) 486: { 487: DBG1(DBG_LIB, "inefficient Huffman coding of signature"); 488: continue; 489: } 490: DBG2(DBG_LIB, "signature generation needed %u round%s", tests, 491: (tests == 1) ? "" : "s"); 492: break; 493: } 494: success = TRUE; 495: 496: end: 497: /* cleanup */ 498: DESTROY_IF(sampler); 499: sig->destroy(sig); 500: fft->destroy(fft); 501: rng->destroy(rng); 502: memwipe(s1c, n * sizeof(int32_t)); 503: memwipe(s2c, n * sizeof(int32_t)); 504: free(s1c); 505: free(s2c); 506: free(ay); 507: free(z2); 508: free(u); 509: free(uz2d); 510: 511: return success; 512: } 513: 514: METHOD(private_key_t, sign, bool, 515: private_bliss_private_key_t *this, signature_scheme_t scheme, void *params, 516: chunk_t data, chunk_t *signature) 517: { 518: switch (scheme) 519: { 520: case SIGN_BLISS_WITH_SHA2_256: 521: return sign_bliss(this, HASH_SHA256, data, signature); 522: case SIGN_BLISS_WITH_SHA2_384: 523: return sign_bliss(this, HASH_SHA384, data, signature); 524: case SIGN_BLISS_WITH_SHA2_512: 525: return sign_bliss(this, HASH_SHA512, data, signature); 526: case SIGN_BLISS_WITH_SHA3_256: 527: return sign_bliss(this, HASH_SHA3_256, data, signature); 528: case SIGN_BLISS_WITH_SHA3_384: 529: return sign_bliss(this, HASH_SHA3_384, data, signature); 530: case SIGN_BLISS_WITH_SHA3_512: 531: return sign_bliss(this, HASH_SHA3_512, data, signature); 532: default: 533: DBG1(DBG_LIB, "signature scheme %N not supported with BLISS", 534: signature_scheme_names, scheme); 535: return FALSE; 536: } 537: } 538: 539: METHOD(private_key_t, decrypt, bool, 540: private_bliss_private_key_t *this, encryption_scheme_t scheme, 541: chunk_t crypto, chunk_t *plain) 542: { 543: DBG1(DBG_LIB, "encryption scheme %N not supported", 544: encryption_scheme_names, scheme); 545: return FALSE; 546: } 547: 548: METHOD(private_key_t, get_keysize, int, 549: private_bliss_private_key_t *this) 550: { 551: return this->set->strength; 552: } 553: 554: METHOD(private_key_t, get_public_key, public_key_t*, 555: private_bliss_private_key_t *this) 556: { 557: public_key_t *public; 558: chunk_t pubkey; 559: 560: pubkey = bliss_public_key_info_encode(this->set->oid, this->A, this->set); 561: public = lib->creds->create(lib->creds, CRED_PUBLIC_KEY, KEY_BLISS, 562: BUILD_BLOB_ASN1_DER, pubkey, BUILD_END); 563: free(pubkey.ptr); 564: 565: return public; 566: } 567: 568: METHOD(private_key_t, get_encoding, bool, 569: private_bliss_private_key_t *this, cred_encoding_type_t type, 570: chunk_t *encoding) 571: { 572: switch (type) 573: { 574: case PRIVKEY_ASN1_DER: 575: case PRIVKEY_PEM: 576: { 577: chunk_t s1, s2, pubkey; 578: bliss_bitpacker_t *packer; 579: size_t s_bits; 580: int8_t value; 581: bool success = TRUE; 582: int i; 583: 584: pubkey = bliss_public_key_encode(this->A, this->set); 585: 586: /* Use either 2 or 3 bits per array element */ 587: s_bits = 2 + (this->set->non_zero2 > 0); 588: 589: /* Encode secret s1 */ 590: packer = bliss_bitpacker_create(s_bits * this->set->n); 591: for (i = 0; i < this->set->n; i++) 592: { 593: packer->write_bits(packer, this->s1[i], s_bits); 594: } 595: s1 = packer->extract_buf(packer); 596: packer->destroy(packer); 597: 598: /* Encode secret s2 */ 599: packer = bliss_bitpacker_create(s_bits * this->set->n); 600: for (i = 0; i < this->set->n; i++) 601: { 602: value = this->s2[i]; 603: if (i == 0) 604: { 605: value -= 1; 606: } 607: value /= 2; 608: packer->write_bits(packer, value, s_bits); 609: } 610: s2 = packer->extract_buf(packer); 611: packer->destroy(packer); 612: 613: *encoding = asn1_wrap(ASN1_SEQUENCE, "mmss", 614: asn1_build_known_oid(this->set->oid), 615: asn1_bitstring("m", pubkey), 616: asn1_bitstring("m", s1), 617: asn1_bitstring("m", s2) 618: ); 619: if (type == PRIVKEY_PEM) 620: { 621: chunk_t asn1_encoding = *encoding; 622: 623: success = lib->encoding->encode(lib->encoding, PRIVKEY_PEM, 624: NULL, encoding, CRED_PART_BLISS_PRIV_ASN1_DER, 625: asn1_encoding, CRED_PART_END); 626: chunk_clear(&asn1_encoding); 627: } 628: return success; 629: } 630: default: 631: return FALSE; 632: } 633: } 634: 635: METHOD(private_key_t, get_fingerprint, bool, 636: private_bliss_private_key_t *this, cred_encoding_type_t type, chunk_t *fp) 637: { 638: bool success; 639: 640: if (lib->encoding->get_cache(lib->encoding, type, this, fp)) 641: { 642: return TRUE; 643: } 644: success = bliss_public_key_fingerprint(this->set->oid, this->A, 645: this->set, type, fp); 646: if (success) 647: { 648: lib->encoding->cache(lib->encoding, type, this, *fp); 649: } 650: return success; 651: } 652: 653: METHOD(private_key_t, get_ref, private_key_t*, 654: private_bliss_private_key_t *this) 655: { 656: ref_get(&this->ref); 657: return &this->public.key; 658: } 659: 660: METHOD(private_key_t, destroy, void, 661: private_bliss_private_key_t *this) 662: { 663: if (ref_put(&this->ref)) 664: { 665: lib->encoding->clear_cache(lib->encoding, this); 666: if (this->s1) 667: { 668: memwipe(this->s1, this->set->n * sizeof(int8_t)); 669: free(this->s1); 670: } 671: if (this->s2) 672: { 673: memwipe(this->s2, this->set->n * sizeof(int8_t)); 674: free(this->s2); 675: } 676: free(this->A); 677: free(this->Ar); 678: free(this); 679: } 680: } 681: 682: /** 683: * Internal generic constructor 684: */ 685: static private_bliss_private_key_t *bliss_private_key_create_empty(void) 686: { 687: private_bliss_private_key_t *this; 688: 689: INIT(this, 690: .public = { 691: .key = { 692: .get_type = _get_type, 693: .sign = _sign, 694: .decrypt = _decrypt, 695: .get_keysize = _get_keysize, 696: .get_public_key = _get_public_key, 697: .equals = private_key_equals, 698: .belongs_to = private_key_belongs_to, 699: .get_fingerprint = _get_fingerprint, 700: .has_fingerprint = private_key_has_fingerprint, 701: .get_encoding = _get_encoding, 702: .get_ref = _get_ref, 703: .destroy = _destroy, 704: }, 705: }, 706: .ref = 1, 707: ); 708: return this; 709: } 710: 711: /** 712: * Compute the scalar product of a vector x with a negative wrapped vector y 713: */ 714: static int16_t wrapped_product(int8_t *x, int8_t *y, int n, int shift) 715: { 716: int16_t product = 0; 717: int i; 718: 719: for (i = 0; i < n - shift; i++) 720: { 721: product += x[i] * y[i + shift]; 722: } 723: for (i = n - shift; i < n; i++) 724: { 725: product -= x[i] * y[i + shift - n]; 726: } 727: return product; 728: } 729: 730: /** 731: * Apply a negative wrapped rotation to a vector x 732: */ 733: static void wrap(int16_t *x, int n, int shift, int16_t *x_wrapped) 734: { 735: int i; 736: 737: for (i = 0; i < n - shift; i++) 738: { 739: x_wrapped[i + shift] = x[i]; 740: } 741: for (i = n - shift; i < n; i++) 742: { 743: x_wrapped[i + shift - n] = -x[i]; 744: } 745: } 746: 747: /** 748: * int16_t compare function needed for qsort() 749: */ 750: static int compare(const int16_t *a, const int16_t *b) 751: { 752: int16_t temp = *a - *b; 753: 754: if (temp > 0) 755: { 756: return 1; 757: } 758: else if (temp < 0) 759: { 760: return -1; 761: } 762: else 763: { 764: return 0; 765: } 766: } 767: 768: /** 769: * Compute the Nk(S) norm of S = (s1, s2) 770: */ 771: static uint32_t nks_norm(int8_t *s1, int8_t *s2, int n, uint16_t kappa) 772: { 773: int16_t t[n], t_wrapped[n], max_kappa[n]; 774: uint32_t nks = 0; 775: int i, j; 776: 777: for (i = 0; i < n; i++) 778: { 779: t[i] = wrapped_product(s1, s1, n, i) + wrapped_product(s2, s2, n, i); 780: } 781: 782: for (i = 0; i < n; i++) 783: { 784: wrap(t, n, i, t_wrapped); 785: qsort(t_wrapped, n, sizeof(int16_t), (void*)compare); 786: max_kappa[i] = 0; 787: 788: for (j = 1; j <= kappa; j++) 789: { 790: max_kappa[i] += t_wrapped[n - j]; 791: } 792: } 793: qsort(max_kappa, n, sizeof(int16_t), (void*)compare); 794: 795: for (i = 1; i <= kappa; i++) 796: { 797: nks += max_kappa[n - i]; 798: } 799: return nks; 800: } 801: 802: /** 803: * Compute the inverse x1 of x modulo q as x^(-1) = x^(q-2) mod q 804: */ 805: static uint32_t invert(private_bliss_private_key_t *this, uint32_t x) 806: { 807: uint32_t x1, x2; 808: uint16_t q2; 809: int i, i_max; 810: 811: q2 = this->set->q - 2; 812: x1 = (q2 & 1) ? x : 1; 813: x2 = x; 814: i_max = 15; 815: 816: while ((q2 & (1 << i_max)) == 0) 817: { 818: i_max--; 819: } 820: for (i = 1; i <= i_max; i++) 821: { 822: x2 = ntt_fft_mreduce(x2 * x2, this->set->fft_params); 823: 824: if (q2 & (1 << i)) 825: { 826: x1 = ntt_fft_mreduce(x1 * x2, this->set->fft_params); 827: } 828: } 829: 830: return x1; 831: } 832: 833: /** 834: * Create a vector with sparse and small coefficients from seed 835: */ 836: static int8_t* create_vector_from_seed(private_bliss_private_key_t *this, 837: ext_out_function_t alg, chunk_t seed) 838: { 839: xof_bitspender_t *bitspender; 840: uint32_t index, sign; 841: int8_t *vector; 842: int non_zero; 843: 844: bitspender = xof_bitspender_create(alg, seed, FALSE); 845: if (!bitspender) 846: { 847: return NULL; 848: } 849: 850: vector = malloc(sizeof(int8_t) * this->set->n); 851: memset(vector, 0x00, this->set->n); 852: 853: non_zero = this->set->non_zero1; 854: while (non_zero) 855: { 856: if (!bitspender->get_bits(bitspender, this->set->n_bits, &index)) 857: { 858: free(vector); 859: return NULL; 860: } 861: if (vector[index] != 0) 862: { 863: continue; 864: } 865: 866: if (!bitspender->get_bits(bitspender, 1, &sign)) 867: { 868: free(vector); 869: return NULL; 870: } 871: vector[index] = sign ? 1 : -1; 872: non_zero--; 873: } 874: 875: non_zero = this->set->non_zero2; 876: while (non_zero) 877: { 878: if (!bitspender->get_bits(bitspender, this->set->n_bits, &index)) 879: { 880: free(vector); 881: return NULL; 882: } 883: if (vector[index] != 0) 884: { 885: continue; 886: } 887: 888: if (!bitspender->get_bits(bitspender, 1, &sign)) 889: { 890: free(vector); 891: return NULL; 892: } 893: vector[index] = sign ? 2 : -2; 894: non_zero--; 895: } 896: bitspender->destroy(bitspender); 897: 898: return vector; 899: } 900: 901: /** 902: * Generate the secret key S = (s1, s2) fulfilling the Nk(S) norm 903: */ 904: static bool create_secret(private_bliss_private_key_t *this, rng_t *rng, 905: int8_t **s1, int8_t **s2, int *trials) 906: { 907: uint8_t seed_buf[32]; 908: uint8_t *f, *g; 909: uint32_t l2_norm, nks; 910: int i, n; 911: chunk_t seed; 912: size_t seed_len; 913: ext_out_function_t alg; 914: 915: n = this->set->n; 916: *s1 = NULL; 917: *s2 = NULL; 918: 919: /* Set MGF1 hash algorithm and seed length based on security strength */ 920: if (this->set->strength > 160) 921: { 922: alg = XOF_MGF1_SHA256; 923: seed_len = HASH_SIZE_SHA256; 924: } 925: else 926: { 927: alg = XOF_MGF1_SHA1; 928: seed_len = HASH_SIZE_SHA1; 929: } 930: seed = chunk_create(seed_buf, seed_len); 931: 932: while (*trials < SECRET_KEY_TRIALS_MAX) 933: { 934: (*trials)++; 935: 936: if (!rng->get_bytes(rng, seed_len, seed_buf)) 937: { 938: return FALSE; 939: } 940: f = create_vector_from_seed(this, alg, seed); 941: if (f == NULL) 942: { 943: return FALSE; 944: } 945: if (!rng->get_bytes(rng, seed_len, seed_buf)) 946: { 947: free(f); 948: return FALSE; 949: } 950: g = create_vector_from_seed(this, alg, seed); 951: if (g == NULL) 952: { 953: free(f); 954: return FALSE; 955: } 956: 957: /* Compute 2g + 1 */ 958: for (i = 0; i < n; i++) 959: { 960: g[i] *= 2; 961: } 962: g[0] += 1; 963: 964: l2_norm = wrapped_product(f, f, n, 0) + wrapped_product(g, g, n, 0); 965: nks = nks_norm(f, g, n, this->set->kappa); 966: 967: switch (this->set->id) 968: { 969: case BLISS_I: 970: case BLISS_II: 971: case BLISS_III: 972: case BLISS_IV: 973: DBG2(DBG_LIB, "l2 norm of s1||s2: %d, Nk(S): %u (%u max)", 974: l2_norm, nks, this->set->nks_max); 975: if (nks < this->set->nks_max) 976: { 977: *s1 = f; 978: *s2 = g; 979: return TRUE; 980: } 981: free(f); 982: free(g); 983: break; 984: case BLISS_B_I: 985: case BLISS_B_II: 986: case BLISS_B_III: 987: case BLISS_B_IV: 988: DBG2(DBG_LIB, "l2 norm of s1||s2: %d, Nk(S): %u", 989: l2_norm, nks); 990: *s1 = f; 991: *s2 = g; 992: return TRUE; 993: } 994: } 995: 996: return FALSE; 997: } 998: 999: /** 1000: * See header. 1001: */ 1002: bliss_private_key_t *bliss_private_key_gen(key_type_t type, va_list args) 1003: { 1004: private_bliss_private_key_t *this; 1005: u_int key_size = BLISS_B_I; 1006: int i, n, trials = 0; 1007: uint32_t *S1, *S2, *a; 1008: uint16_t q; 1009: bool success = FALSE; 1010: const bliss_param_set_t *set; 1011: ntt_fft_t *fft; 1012: rng_t *rng; 1013: 1014: while (TRUE) 1015: { 1016: switch (va_arg(args, builder_part_t)) 1017: { 1018: case BUILD_KEY_SIZE: 1019: key_size = va_arg(args, u_int); 1020: continue; 1021: case BUILD_END: 1022: break; 1023: default: 1024: return NULL; 1025: } 1026: break; 1027: } 1028: 1029: if (lib->settings->get_bool(lib->settings, "%s.plugins.bliss.use_bliss_b", 1030: TRUE, lib->ns)) 1031: { 1032: switch (key_size) 1033: { 1034: case BLISS_I: 1035: key_size = BLISS_B_I; 1036: break; 1037: case BLISS_II: 1038: key_size = BLISS_B_II; 1039: break; 1040: case BLISS_III: 1041: key_size = BLISS_B_III; 1042: break; 1043: case BLISS_IV: 1044: key_size = BLISS_B_IV; 1045: break; 1046: default: 1047: break; 1048: } 1049: } 1050: 1051: /* Only BLISS or BLISS-B types I, III, or IV are currently supported */ 1052: set = bliss_param_set_get_by_id(key_size); 1053: if (!set) 1054: { 1055: DBG1(DBG_LIB, "BLISS parameter set %u not supported", key_size); 1056: return NULL; 1057: } 1058: 1059: /* Some shortcuts for often used variables */ 1060: n = set->n; 1061: q = set->q; 1062: 1063: if (set->fft_params->n != n || set->fft_params->q != q) 1064: { 1065: DBG1(DBG_LIB, "FFT parameters do not match BLISS parameters"); 1066: return NULL; 1067: } 1068: this = bliss_private_key_create_empty(); 1069: this->set = set; 1070: 1071: /* We derive the public key from the private key using the FFT */ 1072: fft = ntt_fft_create(set->fft_params); 1073: 1074: /* Some vectors needed to derive the public key */ 1075: S1 = malloc(n * sizeof(uint32_t)); 1076: S2 = malloc(n * sizeof(uint32_t)); 1077: a = malloc(n * sizeof(uint32_t)); 1078: this->A = malloc(n * sizeof(uint32_t)); 1079: this->Ar = malloc(n * sizeof(uint32_t)); 1080: 1081: /* Instantiate a true random generator */ 1082: rng = lib->crypto->create_rng(lib->crypto, RNG_TRUE); 1083: 1084: /* Loop until we have an invertible polynomial s1 */ 1085: do 1086: { 1087: if (!create_secret(this, rng, &this->s1, &this->s2, &trials)) 1088: { 1089: break; 1090: } 1091: 1092: /* Convert signed arrays to unsigned arrays before FFT */ 1093: for (i = 0; i < n; i++) 1094: { 1095: S1[i] = (this->s1[i] < 0) ? this->s1[i] + q : this->s1[i]; 1096: S2[i] = (this->s2[i] > 0) ? q - this->s2[i] : -this->s2[i]; 1097: } 1098: fft->transform(fft, S1, S1, FALSE); 1099: fft->transform(fft, S2, S2, FALSE); 1100: 1101: success = TRUE; 1102: 1103: for (i = 0; i < n; i++) 1104: { 1105: if (S1[i] == 0) 1106: { 1107: DBG1(DBG_LIB, "S1[%d] is zero - s1 is not invertible", i); 1108: free(this->s1); 1109: free(this->s2); 1110: this->s1 = NULL; 1111: this->s2 = NULL; 1112: success = FALSE; 1113: break; 1114: } 1115: this->Ar[i] = invert(this, S1[i]); 1116: this->Ar[i] = ntt_fft_mreduce(S2[i] * this->Ar[i], set->fft_params); 1117: this->A[i] = ntt_fft_mreduce(this->Ar[i], set->fft_params); 1118: } 1119: } 1120: while (!success && trials < SECRET_KEY_TRIALS_MAX); 1121: 1122: DBG1(DBG_LIB, "secret key generation %s after %d trial%s", 1123: success ? "succeeded" : "failed", trials, (trials == 1) ? "" : "s"); 1124: 1125: if (success) 1126: { 1127: fft->transform(fft, this->Ar, a, TRUE); 1128: 1129: DBG4(DBG_LIB, " i f g a F G A"); 1130: for (i = 0; i < n; i++) 1131: { 1132: DBG4(DBG_LIB, "%4d %3d %3d %5u %5u %5u %5u", 1133: i, this->s1[i], this->s2[i], 1134: ntt_fft_mreduce(a[i], set->fft_params), 1135: S1[i], S2[i], this->A[i]); 1136: } 1137: } 1138: else 1139: { 1140: destroy(this); 1141: } 1142: 1143: /* Cleanup */ 1144: fft->destroy(fft); 1145: rng->destroy(rng); 1146: memwipe(S1, n * sizeof(uint32_t)); 1147: memwipe(S2, n * sizeof(uint32_t)); 1148: free(S1); 1149: free(S2); 1150: free(a); 1151: 1152: return success ? &this->public : NULL; 1153: } 1154: 1155: /** 1156: * ASN.1 definition of a BLISS private key 1157: */ 1158: static const asn1Object_t privkeyObjects[] = { 1159: { 0, "BLISSPrivateKey", ASN1_SEQUENCE, ASN1_NONE }, /* 0 */ 1160: { 1, "keyType", ASN1_OID, ASN1_BODY }, /* 1 */ 1161: { 1, "public", ASN1_BIT_STRING, ASN1_BODY }, /* 2 */ 1162: { 1, "secret1", ASN1_BIT_STRING, ASN1_BODY }, /* 3 */ 1163: { 1, "secret2", ASN1_BIT_STRING, ASN1_BODY }, /* 4 */ 1164: { 0, "exit", ASN1_EOC, ASN1_EXIT } 1165: }; 1166: #define PRIV_KEY_TYPE 1 1167: #define PRIV_KEY_PUBLIC 2 1168: #define PRIV_KEY_SECRET1 3 1169: #define PRIV_KEY_SECRET2 4 1170: 1171: /** 1172: * See header. 1173: */ 1174: bliss_private_key_t *bliss_private_key_load(key_type_t type, va_list args) 1175: { 1176: private_bliss_private_key_t *this; 1177: chunk_t key = chunk_empty, object; 1178: bliss_bitpacker_t *packer; 1179: asn1_parser_t *parser; 1180: size_t s_bits = 0; 1181: int8_t s, s_min = 0, s_max = 0; 1182: uint32_t s_sign = 0x02, s_mask = 0xfffffffc, value, r2; 1183: bool success = FALSE; 1184: int objectID, oid, i; 1185: 1186: while (TRUE) 1187: { 1188: switch (va_arg(args, builder_part_t)) 1189: { 1190: case BUILD_BLOB_ASN1_DER: 1191: key = va_arg(args, chunk_t); 1192: continue; 1193: case BUILD_END: 1194: break; 1195: default: 1196: return NULL; 1197: } 1198: break; 1199: } 1200: 1201: if (key.len == 0) 1202: { 1203: return NULL; 1204: } 1205: this = bliss_private_key_create_empty(); 1206: 1207: parser = asn1_parser_create(privkeyObjects, key); 1208: parser->set_flags(parser, FALSE, TRUE); 1209: 1210: while (parser->iterate(parser, &objectID, &object)) 1211: { 1212: switch (objectID) 1213: { 1214: case PRIV_KEY_TYPE: 1215: oid = asn1_known_oid(object); 1216: if (oid == OID_UNKNOWN) 1217: { 1218: goto end; 1219: } 1220: this->set = bliss_param_set_get_by_oid(oid); 1221: if (this->set == NULL) 1222: { 1223: goto end; 1224: } 1225: if (lib->settings->get_bool(lib->settings, 1226: "%s.plugins.bliss.use_bliss_b",TRUE, lib->ns)) 1227: { 1228: switch (this->set->id) 1229: { 1230: case BLISS_I: 1231: this->set = bliss_param_set_get_by_id(BLISS_B_I); 1232: break; 1233: case BLISS_III: 1234: this->set = bliss_param_set_get_by_id(BLISS_B_III); 1235: break; 1236: case BLISS_IV: 1237: this->set = bliss_param_set_get_by_id(BLISS_B_IV); 1238: break; 1239: default: 1240: break; 1241: } 1242: } 1243: if (this->set->non_zero2) 1244: { 1245: s_min = -2; 1246: s_max = 2; 1247: s_bits = 3; 1248: } 1249: else 1250: { 1251: s_min = -1; 1252: s_max = 1; 1253: s_bits = 2; 1254: } 1255: s_sign = 1 << (s_bits - 1); 1256: s_mask = ((1 << (32 - s_bits)) - 1) << s_bits; 1257: break; 1258: case PRIV_KEY_PUBLIC: 1259: if (!bliss_public_key_from_asn1(object, this->set, &this->A)) 1260: { 1261: goto end; 1262: } 1263: this->Ar = malloc(this->set->n * sizeof(uint32_t)); 1264: r2 = this->set->fft_params->r2; 1265: 1266: for (i = 0; i < this->set->n; i++) 1267: { 1268: this->Ar[i] = ntt_fft_mreduce(this->A[i] * r2, 1269: this->set->fft_params); 1270: } 1271: break; 1272: case PRIV_KEY_SECRET1: 1273: if (object.len != 1 + (s_bits * this->set->n + 7)/8) 1274: { 1275: goto end; 1276: } 1277: this->s1 = malloc(this->set->n); 1278: 1279: /* Skip unused bits octet */ 1280: object = chunk_skip(object, 1); 1281: packer = bliss_bitpacker_create_from_data(object); 1282: for (i = 0; i < this->set->n; i++) 1283: { 1284: packer->read_bits(packer, &value, s_bits); 1285: s = (value & s_sign) ? value | s_mask : value; 1286: if (s < s_min || s > s_max) 1287: { 1288: packer->destroy(packer); 1289: goto end; 1290: } 1291: this->s1[i] = s; 1292: } 1293: packer->destroy(packer); 1294: break; 1295: case PRIV_KEY_SECRET2: 1296: if (object.len != 1 + (s_bits * this->set->n + 7)/8) 1297: { 1298: goto end; 1299: } 1300: this->s2 = malloc(this->set->n); 1301: 1302: /* Skip unused bits octet */ 1303: object = chunk_skip(object, 1); 1304: packer = bliss_bitpacker_create_from_data(object); 1305: for (i = 0; i < this->set->n; i++) 1306: { 1307: packer->read_bits(packer, &value, s_bits); 1308: s = (value & s_sign) ? value | s_mask : value; 1309: if (s < s_min || s > s_max) 1310: { 1311: packer->destroy(packer); 1312: goto end; 1313: } 1314: this->s2[i] = 2 * s; 1315: if (i == 0) 1316: { 1317: this->s2[0] += 1; 1318: } 1319: } 1320: packer->destroy(packer); 1321: break; 1322: } 1323: } 1324: success = parser->success(parser); 1325: 1326: end: 1327: parser->destroy(parser); 1328: if (!success) 1329: { 1330: destroy(this); 1331: return NULL; 1332: } 1333: 1334: return &this->public; 1335: } 1336: