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