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