1 #include "inner.h"
2
3 /*
4 * Encoding/decoding of keys and signatures.
5 *
6 * ==========================(LICENSE BEGIN)============================
7 *
8 * Copyright (c) 2017-2019 Falcon Project
9 *
10 * Permission is hereby granted, free of charge, to any person obtaining
11 * a copy of this software and associated documentation files (the
12 * "Software"), to deal in the Software without restriction, including
13 * without limitation the rights to use, copy, modify, merge, publish,
14 * distribute, sublicense, and/or sell copies of the Software, and to
15 * permit persons to whom the Software is furnished to do so, subject to
16 * the following conditions:
17 *
18 * The above copyright notice and this permission notice shall be
19 * included in all copies or substantial portions of the Software.
20 *
21 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
22 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
23 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
24 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
25 * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
26 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
27 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
28 *
29 * ===========================(LICENSE END)=============================
30 *
31 * @author Thomas Pornin <thomas.pornin@nccgroup.com>
32 */
33
34
35 /* see inner.h */
36 size_t
PQCLEAN_FALCON1024_CLEAN_modq_encode(void * out,size_t max_out_len,const uint16_t * x,unsigned logn)37 PQCLEAN_FALCON1024_CLEAN_modq_encode(
38 void *out, size_t max_out_len,
39 const uint16_t *x, unsigned logn) {
40 size_t n, out_len, u;
41 uint8_t *buf;
42 uint32_t acc;
43 int acc_len;
44
45 n = (size_t)1 << logn;
46 for (u = 0; u < n; u ++) {
47 if (x[u] >= 12289) {
48 return 0;
49 }
50 }
51 out_len = ((n * 14) + 7) >> 3;
52 if (out == NULL) {
53 return out_len;
54 }
55 if (out_len > max_out_len) {
56 return 0;
57 }
58 buf = out;
59 acc = 0;
60 acc_len = 0;
61 for (u = 0; u < n; u ++) {
62 acc = (acc << 14) | x[u];
63 acc_len += 14;
64 while (acc_len >= 8) {
65 acc_len -= 8;
66 *buf ++ = (uint8_t)(acc >> acc_len);
67 }
68 }
69 if (acc_len > 0) {
70 *buf = (uint8_t)(acc << (8 - acc_len));
71 }
72 return out_len;
73 }
74
75 /* see inner.h */
76 size_t
PQCLEAN_FALCON1024_CLEAN_modq_decode(uint16_t * x,unsigned logn,const void * in,size_t max_in_len)77 PQCLEAN_FALCON1024_CLEAN_modq_decode(
78 uint16_t *x, unsigned logn,
79 const void *in, size_t max_in_len) {
80 size_t n, in_len, u;
81 const uint8_t *buf;
82 uint32_t acc;
83 int acc_len;
84
85 n = (size_t)1 << logn;
86 in_len = ((n * 14) + 7) >> 3;
87 if (in_len > max_in_len) {
88 return 0;
89 }
90 buf = in;
91 acc = 0;
92 acc_len = 0;
93 u = 0;
94 while (u < n) {
95 acc = (acc << 8) | (*buf ++);
96 acc_len += 8;
97 if (acc_len >= 14) {
98 unsigned w;
99
100 acc_len -= 14;
101 w = (acc >> acc_len) & 0x3FFF;
102 if (w >= 12289) {
103 return 0;
104 }
105 x[u ++] = (uint16_t)w;
106 }
107 }
108 if ((acc & (((uint32_t)1 << acc_len) - 1)) != 0) {
109 return 0;
110 }
111 return in_len;
112 }
113
114 /* see inner.h */
115 size_t
PQCLEAN_FALCON1024_CLEAN_trim_i16_encode(void * out,size_t max_out_len,const int16_t * x,unsigned logn,unsigned bits)116 PQCLEAN_FALCON1024_CLEAN_trim_i16_encode(
117 void *out, size_t max_out_len,
118 const int16_t *x, unsigned logn, unsigned bits) {
119 size_t n, u, out_len;
120 int minv, maxv;
121 uint8_t *buf;
122 uint32_t acc, mask;
123 unsigned acc_len;
124
125 n = (size_t)1 << logn;
126 maxv = (1 << (bits - 1)) - 1;
127 minv = -maxv;
128 for (u = 0; u < n; u ++) {
129 if (x[u] < minv || x[u] > maxv) {
130 return 0;
131 }
132 }
133 out_len = ((n * bits) + 7) >> 3;
134 if (out == NULL) {
135 return out_len;
136 }
137 if (out_len > max_out_len) {
138 return 0;
139 }
140 buf = out;
141 acc = 0;
142 acc_len = 0;
143 mask = ((uint32_t)1 << bits) - 1;
144 for (u = 0; u < n; u ++) {
145 acc = (acc << bits) | ((uint16_t)x[u] & mask);
146 acc_len += bits;
147 while (acc_len >= 8) {
148 acc_len -= 8;
149 *buf ++ = (uint8_t)(acc >> acc_len);
150 }
151 }
152 if (acc_len > 0) {
153 *buf ++ = (uint8_t)(acc << (8 - acc_len));
154 }
155 return out_len;
156 }
157
158 /* see inner.h */
159 size_t
PQCLEAN_FALCON1024_CLEAN_trim_i16_decode(int16_t * x,unsigned logn,unsigned bits,const void * in,size_t max_in_len)160 PQCLEAN_FALCON1024_CLEAN_trim_i16_decode(
161 int16_t *x, unsigned logn, unsigned bits,
162 const void *in, size_t max_in_len) {
163 size_t n, in_len;
164 const uint8_t *buf;
165 size_t u;
166 uint32_t acc, mask1, mask2;
167 unsigned acc_len;
168
169 n = (size_t)1 << logn;
170 in_len = ((n * bits) + 7) >> 3;
171 if (in_len > max_in_len) {
172 return 0;
173 }
174 buf = in;
175 u = 0;
176 acc = 0;
177 acc_len = 0;
178 mask1 = ((uint32_t)1 << bits) - 1;
179 mask2 = (uint32_t)1 << (bits - 1);
180 while (u < n) {
181 acc = (acc << 8) | *buf ++;
182 acc_len += 8;
183 while (acc_len >= bits && u < n) {
184 uint32_t w;
185
186 acc_len -= bits;
187 w = (acc >> acc_len) & mask1;
188 w |= -(w & mask2);
189 if (w == -mask2) {
190 /*
191 * The -2^(bits-1) value is forbidden.
192 */
193 return 0;
194 }
195 w |= -(w & mask2);
196 x[u ++] = (int16_t) * (int32_t *)&w;
197 }
198 }
199 if ((acc & (((uint32_t)1 << acc_len) - 1)) != 0) {
200 /*
201 * Extra bits in the last byte must be zero.
202 */
203 return 0;
204 }
205 return in_len;
206 }
207
208 /* see inner.h */
209 size_t
PQCLEAN_FALCON1024_CLEAN_trim_i8_encode(void * out,size_t max_out_len,const int8_t * x,unsigned logn,unsigned bits)210 PQCLEAN_FALCON1024_CLEAN_trim_i8_encode(
211 void *out, size_t max_out_len,
212 const int8_t *x, unsigned logn, unsigned bits) {
213 size_t n, u, out_len;
214 int minv, maxv;
215 uint8_t *buf;
216 uint32_t acc, mask;
217 unsigned acc_len;
218
219 n = (size_t)1 << logn;
220 maxv = (1 << (bits - 1)) - 1;
221 minv = -maxv;
222 for (u = 0; u < n; u ++) {
223 if (x[u] < minv || x[u] > maxv) {
224 return 0;
225 }
226 }
227 out_len = ((n * bits) + 7) >> 3;
228 if (out == NULL) {
229 return out_len;
230 }
231 if (out_len > max_out_len) {
232 return 0;
233 }
234 buf = out;
235 acc = 0;
236 acc_len = 0;
237 mask = ((uint32_t)1 << bits) - 1;
238 for (u = 0; u < n; u ++) {
239 acc = (acc << bits) | ((uint8_t)x[u] & mask);
240 acc_len += bits;
241 while (acc_len >= 8) {
242 acc_len -= 8;
243 *buf ++ = (uint8_t)(acc >> acc_len);
244 }
245 }
246 if (acc_len > 0) {
247 *buf ++ = (uint8_t)(acc << (8 - acc_len));
248 }
249 return out_len;
250 }
251
252 /* see inner.h */
253 size_t
PQCLEAN_FALCON1024_CLEAN_trim_i8_decode(int8_t * x,unsigned logn,unsigned bits,const void * in,size_t max_in_len)254 PQCLEAN_FALCON1024_CLEAN_trim_i8_decode(
255 int8_t *x, unsigned logn, unsigned bits,
256 const void *in, size_t max_in_len) {
257 size_t n, in_len;
258 const uint8_t *buf;
259 size_t u;
260 uint32_t acc, mask1, mask2;
261 unsigned acc_len;
262
263 n = (size_t)1 << logn;
264 in_len = ((n * bits) + 7) >> 3;
265 if (in_len > max_in_len) {
266 return 0;
267 }
268 buf = in;
269 u = 0;
270 acc = 0;
271 acc_len = 0;
272 mask1 = ((uint32_t)1 << bits) - 1;
273 mask2 = (uint32_t)1 << (bits - 1);
274 while (u < n) {
275 acc = (acc << 8) | *buf ++;
276 acc_len += 8;
277 while (acc_len >= bits && u < n) {
278 uint32_t w;
279
280 acc_len -= bits;
281 w = (acc >> acc_len) & mask1;
282 w |= -(w & mask2);
283 if (w == -mask2) {
284 /*
285 * The -2^(bits-1) value is forbidden.
286 */
287 return 0;
288 }
289 x[u ++] = (int8_t) * (int32_t *)&w;
290 }
291 }
292 if ((acc & (((uint32_t)1 << acc_len) - 1)) != 0) {
293 /*
294 * Extra bits in the last byte must be zero.
295 */
296 return 0;
297 }
298 return in_len;
299 }
300
301 /* see inner.h */
302 size_t
PQCLEAN_FALCON1024_CLEAN_comp_encode(void * out,size_t max_out_len,const int16_t * x,unsigned logn)303 PQCLEAN_FALCON1024_CLEAN_comp_encode(
304 void *out, size_t max_out_len,
305 const int16_t *x, unsigned logn) {
306 uint8_t *buf;
307 size_t n, u, v;
308 uint32_t acc;
309 unsigned acc_len;
310
311 n = (size_t)1 << logn;
312 buf = out;
313
314 /*
315 * Make sure that all values are within the -2047..+2047 range.
316 */
317 for (u = 0; u < n; u ++) {
318 if (x[u] < -2047 || x[u] > +2047) {
319 return 0;
320 }
321 }
322
323 acc = 0;
324 acc_len = 0;
325 v = 0;
326 for (u = 0; u < n; u ++) {
327 int t;
328 unsigned w;
329
330 /*
331 * Get sign and absolute value of next integer; push the
332 * sign bit.
333 */
334 acc <<= 1;
335 t = x[u];
336 if (t < 0) {
337 t = -t;
338 acc |= 1;
339 }
340 w = (unsigned)t;
341
342 /*
343 * Push the low 7 bits of the absolute value.
344 */
345 acc <<= 7;
346 acc |= w & 127u;
347 w >>= 7;
348
349 /*
350 * We pushed exactly 8 bits.
351 */
352 acc_len += 8;
353
354 /*
355 * Push as many zeros as necessary, then a one. Since the
356 * absolute value is at most 2047, w can only range up to
357 * 15 at this point, thus we will add at most 16 bits
358 * here. With the 8 bits above and possibly up to 7 bits
359 * from previous iterations, we may go up to 31 bits, which
360 * will fit in the accumulator, which is an uint32_t.
361 */
362 acc <<= (w + 1);
363 acc |= 1;
364 acc_len += w + 1;
365
366 /*
367 * Produce all full bytes.
368 */
369 while (acc_len >= 8) {
370 acc_len -= 8;
371 if (buf != NULL) {
372 if (v >= max_out_len) {
373 return 0;
374 }
375 buf[v] = (uint8_t)(acc >> acc_len);
376 }
377 v ++;
378 }
379 }
380
381 /*
382 * Flush remaining bits (if any).
383 */
384 if (acc_len > 0) {
385 if (buf != NULL) {
386 if (v >= max_out_len) {
387 return 0;
388 }
389 buf[v] = (uint8_t)(acc << (8 - acc_len));
390 }
391 v ++;
392 }
393
394 return v;
395 }
396
397 /* see inner.h */
398 size_t
PQCLEAN_FALCON1024_CLEAN_comp_decode(int16_t * x,unsigned logn,const void * in,size_t max_in_len)399 PQCLEAN_FALCON1024_CLEAN_comp_decode(
400 int16_t *x, unsigned logn,
401 const void *in, size_t max_in_len) {
402 const uint8_t *buf;
403 size_t n, u, v;
404 uint32_t acc;
405 unsigned acc_len;
406
407 n = (size_t)1 << logn;
408 buf = in;
409 acc = 0;
410 acc_len = 0;
411 v = 0;
412 for (u = 0; u < n; u ++) {
413 unsigned b, s, m;
414
415 /*
416 * Get next eight bits: sign and low seven bits of the
417 * absolute value.
418 */
419 if (v >= max_in_len) {
420 return 0;
421 }
422 acc = (acc << 8) | (uint32_t)buf[v ++];
423 b = acc >> acc_len;
424 s = b & 128;
425 m = b & 127;
426
427 /*
428 * Get next bits until a 1 is reached.
429 */
430 for (;;) {
431 if (acc_len == 0) {
432 if (v >= max_in_len) {
433 return 0;
434 }
435 acc = (acc << 8) | (uint32_t)buf[v ++];
436 acc_len = 8;
437 }
438 acc_len --;
439 if (((acc >> acc_len) & 1) != 0) {
440 break;
441 }
442 m += 128;
443 if (m > 2047) {
444 return 0;
445 }
446 }
447 x[u] = (int16_t) m;
448 if (s) {
449 x[u] = (int16_t) - x[u];
450 }
451 }
452 return v;
453 }
454
455 /*
456 * Key elements and signatures are polynomials with small integer
457 * coefficients. Here are some statistics gathered over many
458 * generated key pairs (10000 or more for each degree):
459 *
460 * log(n) n max(f,g) std(f,g) max(F,G) std(F,G)
461 * 1 2 129 56.31 143 60.02
462 * 2 4 123 40.93 160 46.52
463 * 3 8 97 28.97 159 38.01
464 * 4 16 100 21.48 154 32.50
465 * 5 32 71 15.41 151 29.36
466 * 6 64 59 11.07 138 27.77
467 * 7 128 39 7.91 144 27.00
468 * 8 256 32 5.63 148 26.61
469 * 9 512 22 4.00 137 26.46
470 * 10 1024 15 2.84 146 26.41
471 *
472 * We want a compact storage format for private key, and, as part of
473 * key generation, we are allowed to reject some keys which would
474 * otherwise be fine (this does not induce any noticeable vulnerability
475 * as long as we reject only a small proportion of possible keys).
476 * Hence, we enforce at key generation time maximum values for the
477 * elements of f, g, F and G, so that their encoding can be expressed
478 * in fixed-width values. Limits have been chosen so that generated
479 * keys are almost always within bounds, thus not impacting neither
480 * security or performance.
481 *
482 * IMPORTANT: the code assumes that all coefficients of f, g, F and G
483 * ultimately fit in the -127..+127 range. Thus, none of the elements
484 * of max_fg_bits[] and max_FG_bits[] shall be greater than 8.
485 */
486
487 const uint8_t PQCLEAN_FALCON1024_CLEAN_max_fg_bits[] = {
488 0, /* unused */
489 8,
490 8,
491 8,
492 8,
493 8,
494 7,
495 7,
496 6,
497 6,
498 5
499 };
500
501 const uint8_t PQCLEAN_FALCON1024_CLEAN_max_FG_bits[] = {
502 0, /* unused */
503 8,
504 8,
505 8,
506 8,
507 8,
508 8,
509 8,
510 8,
511 8,
512 8
513 };
514
515 /*
516 * When generating a new key pair, we can always reject keys which
517 * feature an abnormally large coefficient. This can also be done for
518 * signatures, albeit with some care: in case the signature process is
519 * used in a derandomized setup (explicitly seeded with the message and
520 * private key), we have to follow the specification faithfully, and the
521 * specification only enforces a limit on the L2 norm of the signature
522 * vector. The limit on the L2 norm implies that the absolute value of
523 * a coefficient of the signature cannot be more than the following:
524 *
525 * log(n) n max sig coeff (theoretical)
526 * 1 2 412
527 * 2 4 583
528 * 3 8 824
529 * 4 16 1166
530 * 5 32 1649
531 * 6 64 2332
532 * 7 128 3299
533 * 8 256 4665
534 * 9 512 6598
535 * 10 1024 9331
536 *
537 * However, the largest observed signature coefficients during our
538 * experiments was 1077 (in absolute value), hence we can assume that,
539 * with overwhelming probability, signature coefficients will fit
540 * in -2047..2047, i.e. 12 bits.
541 */
542
543 const uint8_t PQCLEAN_FALCON1024_CLEAN_max_sig_bits[] = {
544 0, /* unused */
545 10,
546 11,
547 11,
548 12,
549 12,
550 12,
551 12,
552 12,
553 12,
554 12
555 };
556