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