![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to bliss_private_key.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 / bliss|
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: