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