falcon.c
1 /*
2 * Implementation of the external Falcon API.
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 "falcon.h"
33 #include "inner.h"
34
35 /* see falcon.h */
36 void
37 shake256_init(shake256_context *sc)
38 {
39 inner_shake256_init((inner_shake256_context *)sc);
40 }
41
42 /* see falcon.h */
43 void
44 shake256_inject(shake256_context *sc, const void *data, size_t len)
45 {
46 inner_shake256_inject((inner_shake256_context *)sc, data, len);
47 }
48
49 /* see falcon.h */
50 void
51 shake256_flip(shake256_context *sc)
52 {
53 inner_shake256_flip((inner_shake256_context *)sc);
54 }
55
56 /* see falcon.h */
57 void
58 shake256_extract(shake256_context *sc, void *out, size_t len)
59 {
60 inner_shake256_extract((inner_shake256_context *)sc, out, len);
61 }
62
63 /* see falcon.h */
64 void
65 shake256_init_prng_from_seed(shake256_context *sc,
66 const void *seed, size_t seed_len)
67 {
68 shake256_init(sc);
69 shake256_inject(sc, seed, seed_len);
70 shake256_flip(sc);
71 }
72
73 /* see falcon.h */
74 int
75 shake256_init_prng_from_system(shake256_context *sc)
76 {
77 uint8_t seed[48];
78
79 if (!Zf(get_seed)(seed, sizeof seed)) {
80 return FALCON_ERR_RANDOM;
81 }
82 shake256_init(sc);
83 shake256_inject(sc, seed, sizeof seed);
84 shake256_flip(sc);
85 return 0;
86 }
87
88 static inline uint8_t *
89 align_u64(void *tmp)
90 {
91 uint8_t *atmp;
92 unsigned off;
93
94 atmp = tmp;
95 off = (uintptr_t)atmp & 7u;
96 if (off != 0) {
97 atmp += 8u - off;
98 }
99 return atmp;
100 }
101
102 static inline uint8_t *
103 align_u16(void *tmp)
104 {
105 uint8_t *atmp;
106
107 atmp = tmp;
108 if (((uintptr_t)atmp & 1u) != 0) {
109 atmp ++;
110 }
111 return atmp;
112 }
113
114 static inline fpr *
115 align_fpr(void *tmp)
116 {
117 uint8_t *atmp;
118 unsigned off;
119
120 atmp = tmp;
121 off = (uintptr_t)atmp & 7u;
122 if (off != 0) {
123 atmp += 8u - off;
124 }
125 return (fpr *)atmp;
126 }
127
128 /* see falcon.h */
129 int
130 falcon_keygen_make(
131 shake256_context *rng,
132 unsigned logn,
133 void *privkey, size_t privkey_len,
134 void *pubkey, size_t pubkey_len,
135 void *tmp, size_t tmp_len)
136 {
137 int8_t *f, *g, *F;
138 uint16_t *h;
139 uint8_t *atmp;
140 size_t n, u, v, sk_len, pk_len;
141 uint8_t *sk, *pk;
142 unsigned oldcw;
143
144 /*
145 * Check parameters.
146 */
147 if (logn < 1 || logn > 10) {
148 return FALCON_ERR_BADARG;
149 }
150 if (privkey_len < FALCON_PRIVKEY_SIZE(logn)
151 || (pubkey != NULL && pubkey_len < FALCON_PUBKEY_SIZE(logn))
152 || tmp_len < FALCON_TMPSIZE_KEYGEN(logn))
153 {
154 return FALCON_ERR_SIZE;
155 }
156
157 /*
158 * Prepare buffers and generate private key.
159 */
160 n = (size_t)1 << logn;
161 f = tmp;
162 g = f + n;
163 F = g + n;
164 atmp = align_u64(F + n);
165 oldcw = set_fpu_cw(2);
166 Zf(keygen)((inner_shake256_context *)rng,
167 f, g, F, NULL, NULL, logn, atmp);
168 set_fpu_cw(oldcw);
169
170 /*
171 * Encode private key.
172 */
173 sk = privkey;
174 sk_len = FALCON_PRIVKEY_SIZE(logn);
175 sk[0] = 0x50 + logn;
176 u = 1;
177 v = Zf(trim_i8_encode)(sk + u, sk_len - u,
178 f, logn, Zf(max_fg_bits)[logn]);
179 if (v == 0) {
180 return FALCON_ERR_INTERNAL;
181 }
182 u += v;
183 v = Zf(trim_i8_encode)(sk + u, sk_len - u,
184 g, logn, Zf(max_fg_bits)[logn]);
185 if (v == 0) {
186 return FALCON_ERR_INTERNAL;
187 }
188 u += v;
189 v = Zf(trim_i8_encode)(sk + u, sk_len - u,
190 F, logn, Zf(max_FG_bits)[logn]);
191 if (v == 0) {
192 return FALCON_ERR_INTERNAL;
193 }
194 u += v;
195 if (u != sk_len) {
196 return FALCON_ERR_INTERNAL;
197 }
198
199 /*
200 * Recompute public key and encode it.
201 */
202 if (pubkey != NULL) {
203 h = (uint16_t *)align_u16(g + n);
204 atmp = (uint8_t *)(h + n);
205 if (!Zf(compute_public)(h, f, g, logn, atmp)) {
206 return FALCON_ERR_INTERNAL;
207 }
208 pk = pubkey;
209 pk_len = FALCON_PUBKEY_SIZE(logn);
210 pk[0] = 0x00 + logn;
211 v = Zf(modq_encode)(pk + 1, pk_len - 1, h, logn);
212 if (v != pk_len - 1) {
213 return FALCON_ERR_INTERNAL;
214 }
215 }
216
217 return 0;
218 }
219
220 /* see falcon.h */
221 int
222 falcon_make_public(
223 void *pubkey, size_t pubkey_len,
224 const void *privkey, size_t privkey_len,
225 void *tmp, size_t tmp_len)
226 {
227 uint8_t *pk, *atmp;
228 const uint8_t *sk;
229 unsigned logn;
230 size_t u, v, n, pk_len;
231 int8_t *f, *g;
232 uint16_t *h;
233
234 /*
235 * Get degree from private key header byte, and check
236 * parameters.
237 */
238 if (privkey_len == 0) {
239 return FALCON_ERR_FORMAT;
240 }
241 sk = privkey;
242 if ((sk[0] & 0xF0) != 0x50) {
243 return FALCON_ERR_FORMAT;
244 }
245 logn = sk[0] & 0x0F;
246 if (logn < 1 || logn > 10) {
247 return FALCON_ERR_FORMAT;
248 }
249 if (privkey_len != FALCON_PRIVKEY_SIZE(logn)) {
250 return FALCON_ERR_FORMAT;
251 }
252 if (pubkey_len < FALCON_PUBKEY_SIZE(logn)
253 || tmp_len < FALCON_TMPSIZE_MAKEPUB(logn))
254 {
255 return FALCON_ERR_SIZE;
256 }
257
258 /*
259 * Decode private key (f and g).
260 */
261 n = (size_t)1 << logn;
262 f = (int8_t *)tmp;
263 g = f + n;
264 u = 1;
265 v = Zf(trim_i8_decode)(f, logn, Zf(max_fg_bits)[logn],
266 sk + u, privkey_len - u);
267 if (v == 0) {
268 return FALCON_ERR_FORMAT;
269 }
270 u += v;
271 v = Zf(trim_i8_decode)(g, logn, Zf(max_fg_bits)[logn],
272 sk + u, privkey_len - u);
273 if (v == 0) {
274 return FALCON_ERR_FORMAT;
275 }
276
277 /*
278 * Compute public key.
279 */
280 h = (uint16_t *)align_u16(g + n);
281 atmp = (uint8_t *)(h + n);
282 if (!Zf(compute_public)(h, f, g, logn, atmp)) {
283 return FALCON_ERR_FORMAT;
284 }
285
286 /*
287 * Encode public key.
288 */
289 pk = pubkey;
290 pk_len = FALCON_PUBKEY_SIZE(logn);
291 pk[0] = 0x00 + logn;
292 v = Zf(modq_encode)(pk + 1, pk_len - 1, h, logn);
293 if (v != pk_len - 1) {
294 return FALCON_ERR_INTERNAL;
295 }
296 return 0;
297 }
298
299 /* see falcon.h */
300 int
301 falcon_get_logn(void *obj, size_t len)
302 {
303 int logn;
304
305 if (len == 0) {
306 return FALCON_ERR_FORMAT;
307 }
308 logn = *(uint8_t *)obj & 0x0F;
309 if (logn < 1 || logn > 10) {
310 return FALCON_ERR_FORMAT;
311 }
312 return logn;
313 }
314
315 /* see falcon.h */
316 int
317 falcon_sign_start(shake256_context *rng,
318 void *nonce,
319 shake256_context *hash_data)
320 {
321 shake256_extract(rng, nonce, 40);
322 shake256_init(hash_data);
323 shake256_inject(hash_data, nonce, 40);
324 return 0;
325 }
326
327 /* see falcon.h */
328 int
329 falcon_sign_dyn_finish(shake256_context *rng,
330 void *sig, size_t *sig_len, int sig_type,
331 const void *privkey, size_t privkey_len,
332 shake256_context *hash_data, const void *nonce,
333 void *tmp, size_t tmp_len)
334 {
335 unsigned logn;
336 const uint8_t *sk;
337 uint8_t *es;
338 int8_t *f, *g, *F, *G;
339 uint16_t *hm;
340 int16_t *sv;
341 uint8_t *atmp;
342 size_t u, v, n, es_len;
343 unsigned oldcw;
344 inner_shake256_context sav_hash_data;
345
346 /*
347 * Get degree from private key header byte, and check
348 * parameters.
349 */
350 if (privkey_len == 0) {
351 return FALCON_ERR_FORMAT;
352 }
353 sk = privkey;
354 if ((sk[0] & 0xF0) != 0x50) {
355 return FALCON_ERR_FORMAT;
356 }
357 logn = sk[0] & 0x0F;
358 if (logn < 1 || logn > 10) {
359 return FALCON_ERR_FORMAT;
360 }
361 if (privkey_len != FALCON_PRIVKEY_SIZE(logn)) {
362 return FALCON_ERR_FORMAT;
363 }
364 if (tmp_len < FALCON_TMPSIZE_SIGNDYN(logn)) {
365 return FALCON_ERR_SIZE;
366 }
367 es_len = *sig_len;
368 if (es_len < 41) {
369 return FALCON_ERR_SIZE;
370 }
371 switch (sig_type) {
372 case FALCON_SIG_COMPRESSED:
373 break;
374 case FALCON_SIG_PADDED:
375 if (*sig_len < FALCON_SIG_PADDED_SIZE(logn)) {
376 return FALCON_ERR_SIZE;
377 }
378 break;
379 case FALCON_SIG_CT:
380 if (*sig_len < FALCON_SIG_CT_SIZE(logn)) {
381 return FALCON_ERR_SIZE;
382 }
383 break;
384 default:
385 return FALCON_ERR_BADARG;
386 }
387
388 /*
389 * Decode private key elements, and complete private key.
390 */
391 n = (size_t)1 << logn;
392 f = (int8_t *)tmp;
393 g = f + n;
394 F = g + n;
395 G = F + n;
396 hm = (uint16_t *)(G + n);
397 sv = (int16_t *)hm;
398 atmp = align_u64(hm + n);
399 u = 1;
400 v = Zf(trim_i8_decode)(f, logn, Zf(max_fg_bits)[logn],
401 sk + u, privkey_len - u);
402 if (v == 0) {
403 return FALCON_ERR_FORMAT;
404 }
405 u += v;
406 v = Zf(trim_i8_decode)(g, logn, Zf(max_fg_bits)[logn],
407 sk + u, privkey_len - u);
408 if (v == 0) {
409 return FALCON_ERR_FORMAT;
410 }
411 u += v;
412 v = Zf(trim_i8_decode)(F, logn, Zf(max_FG_bits)[logn],
413 sk + u, privkey_len - u);
414 if (v == 0) {
415 return FALCON_ERR_FORMAT;
416 }
417 u += v;
418 if (u != privkey_len) {
419 return FALCON_ERR_FORMAT;
420 }
421 if (!Zf(complete_private)(G, f, g, F, logn, atmp)) {
422 return FALCON_ERR_FORMAT;
423 }
424
425 /*
426 * Hash message to a point.
427 */
428 shake256_flip(hash_data);
429 sav_hash_data = *(inner_shake256_context *)hash_data;
430
431 /*
432 * Compute and encode signature.
433 */
434 for (;;) {
435 /*
436 * Hash message to a point. We must redo it when looping
437 * (in case of a padded signature format and a failed
438 * attempt due to an oversized compressed signature), because
439 * we overwrite the hash output with the signature (in order
440 * to save some RAM).
441 */
442 *(inner_shake256_context *)hash_data = sav_hash_data;
443 if (sig_type == FALCON_SIG_CT) {
444 Zf(hash_to_point_ct)(
445 (inner_shake256_context *)hash_data,
446 hm, logn, atmp);
447 } else {
448 Zf(hash_to_point_vartime)(
449 (inner_shake256_context *)hash_data,
450 hm, logn);
451 }
452 oldcw = set_fpu_cw(2);
453 Zf(sign_dyn)(sv, (inner_shake256_context *)rng,
454 f, g, F, G, hm, logn, atmp);
455 set_fpu_cw(oldcw);
456 es = sig;
457 es_len = *sig_len;
458 memcpy(es + 1, nonce, 40);
459 u = 41;
460 switch (sig_type) {
461 size_t tu;
462
463 case FALCON_SIG_COMPRESSED:
464 es[0] = 0x30 + logn;
465 v = Zf(comp_encode)(es + u, es_len - u, sv, logn);
466 if (v == 0) {
467 return FALCON_ERR_SIZE;
468 }
469 break;
470 case FALCON_SIG_PADDED:
471 es[0] = 0x30 + logn;
472 tu = FALCON_SIG_PADDED_SIZE(logn);
473 v = Zf(comp_encode)(es + u, tu - u, sv, logn);
474 if (v == 0) {
475 /*
476 * Signature does not fit, loop.
477 */
478 continue;
479 }
480 if (u + v < tu) {
481 memset(es + u + v, 0, tu - (u + v));
482 v = tu - u;
483 }
484 break;
485 case FALCON_SIG_CT:
486 es[0] = 0x50 + logn;
487 v = Zf(trim_i16_encode)(es + u, es_len - u,
488 sv, logn, Zf(max_sig_bits)[logn]);
489 if (v == 0) {
490 return FALCON_ERR_SIZE;
491 }
492 break;
493 }
494 *sig_len = u + v;
495 return 0;
496 }
497 }
498
499 /* see falcon.h */
500 int
501 falcon_expand_privkey(void *expanded_key, size_t expanded_key_len,
502 const void *privkey, size_t privkey_len,
503 void *tmp, size_t tmp_len)
504 {
505 unsigned logn;
506 const uint8_t *sk;
507 int8_t *f, *g, *F, *G;
508 uint8_t *atmp;
509 size_t u, v, n;
510 fpr *expkey;
511 unsigned oldcw;
512
513 /*
514 * Get degree from private key header byte, and check
515 * parameters.
516 */
517 if (privkey_len == 0) {
518 return FALCON_ERR_FORMAT;
519 }
520 sk = privkey;
521 if ((sk[0] & 0xF0) != 0x50) {
522 return FALCON_ERR_FORMAT;
523 }
524 logn = sk[0] & 0x0F;
525 if (logn < 1 || logn > 10) {
526 return FALCON_ERR_FORMAT;
527 }
528 if (privkey_len != FALCON_PRIVKEY_SIZE(logn)) {
529 return FALCON_ERR_FORMAT;
530 }
531 if (expanded_key_len < FALCON_EXPANDEDKEY_SIZE(logn)
532 || tmp_len < FALCON_TMPSIZE_EXPANDPRIV(logn))
533 {
534 return FALCON_ERR_SIZE;
535 }
536
537 /*
538 * Decode private key elements, and complete private key.
539 */
540 n = (size_t)1 << logn;
541 f = (int8_t *)tmp;
542 g = f + n;
543 F = g + n;
544 G = F + n;
545 atmp = align_u64(G + n);
546 u = 1;
547 v = Zf(trim_i8_decode)(f, logn, Zf(max_fg_bits)[logn],
548 sk + u, privkey_len - u);
549 if (v == 0) {
550 return FALCON_ERR_FORMAT;
551 }
552 u += v;
553 v = Zf(trim_i8_decode)(g, logn, Zf(max_fg_bits)[logn],
554 sk + u, privkey_len - u);
555 if (v == 0) {
556 return FALCON_ERR_FORMAT;
557 }
558 u += v;
559 v = Zf(trim_i8_decode)(F, logn, Zf(max_FG_bits)[logn],
560 sk + u, privkey_len - u);
561 if (v == 0) {
562 return FALCON_ERR_FORMAT;
563 }
564 u += v;
565 if (u != privkey_len) {
566 return FALCON_ERR_FORMAT;
567 }
568 if (!Zf(complete_private)(G, f, g, F, logn, atmp)) {
569 return FALCON_ERR_FORMAT;
570 }
571
572 /*
573 * Expand private key.
574 */
575 *(uint8_t *)expanded_key = logn;
576 expkey = align_fpr((uint8_t *)expanded_key + 1);
577 oldcw = set_fpu_cw(2);
578 Zf(expand_privkey)(expkey, f, g, F, G, logn, atmp);
579 set_fpu_cw(oldcw);
580 return 0;
581 }
582
583 /* see falcon.h */
584 int
585 falcon_sign_tree_finish(shake256_context *rng,
586 void *sig, size_t *sig_len, int sig_type,
587 const void *expanded_key,
588 shake256_context *hash_data, const void *nonce,
589 void *tmp, size_t tmp_len)
590 {
591 unsigned logn;
592 uint8_t *es;
593 const fpr *expkey;
594 uint16_t *hm;
595 int16_t *sv;
596 uint8_t *atmp;
597 size_t u, v, n, es_len;
598 unsigned oldcw;
599 inner_shake256_context sav_hash_data;
600
601 /*
602 * Get degree from private key header byte, and check
603 * parameters.
604 */
605 logn = *(const uint8_t *)expanded_key;
606 if (logn < 1 || logn > 10) {
607 return FALCON_ERR_FORMAT;
608 }
609 if (tmp_len < FALCON_TMPSIZE_SIGNTREE(logn)) {
610 return FALCON_ERR_SIZE;
611 }
612 es_len = *sig_len;
613 if (es_len < 41) {
614 return FALCON_ERR_SIZE;
615 }
616 expkey = (const fpr *)align_fpr((uint8_t *)expanded_key + 1);
617 switch (sig_type) {
618 case FALCON_SIG_COMPRESSED:
619 break;
620 case FALCON_SIG_PADDED:
621 if (*sig_len < FALCON_SIG_PADDED_SIZE(logn)) {
622 return FALCON_ERR_SIZE;
623 }
624 break;
625 case FALCON_SIG_CT:
626 if (*sig_len < FALCON_SIG_CT_SIZE(logn)) {
627 return FALCON_ERR_SIZE;
628 }
629 break;
630 default:
631 return FALCON_ERR_BADARG;
632 }
633
634 n = (size_t)1 << logn;
635 hm = (uint16_t *)align_u16(tmp);
636 sv = (int16_t *)hm;
637 atmp = align_u64(sv + n);
638
639 /*
640 * Hash message to a point.
641 */
642 shake256_flip(hash_data);
643 sav_hash_data = *(inner_shake256_context *)hash_data;
644
645 /*
646 * Compute and encode signature.
647 */
648 for (;;) {
649 /*
650 * Hash message to a point. We must redo it when looping
651 * (in case of a padded signature format and a failed
652 * attempt due to an oversized compressed signature), because
653 * we overwrite the hash output with the signature (in order
654 * to save some RAM).
655 */
656 *(inner_shake256_context *)hash_data = sav_hash_data;
657 if (sig_type == FALCON_SIG_CT) {
658 Zf(hash_to_point_ct)(
659 (inner_shake256_context *)hash_data,
660 hm, logn, atmp);
661 } else {
662 Zf(hash_to_point_vartime)(
663 (inner_shake256_context *)hash_data,
664 hm, logn);
665 }
666 oldcw = set_fpu_cw(2);
667 Zf(sign_tree)(sv, (inner_shake256_context *)rng,
668 expkey, hm, logn, atmp);
669 set_fpu_cw(oldcw);
670 es = sig;
671 es_len = *sig_len;
672 memcpy(es + 1, nonce, 40);
673 u = 41;
674 switch (sig_type) {
675 size_t tu;
676
677 case FALCON_SIG_COMPRESSED:
678 es[0] = 0x30 + logn;
679 v = Zf(comp_encode)(es + u, es_len - u, sv, logn);
680 if (v == 0) {
681 return FALCON_ERR_SIZE;
682 }
683 break;
684 case FALCON_SIG_PADDED:
685 es[0] = 0x30 + logn;
686 tu = FALCON_SIG_PADDED_SIZE(logn);
687 v = Zf(comp_encode)(es + u, tu - u, sv, logn);
688 if (v == 0) {
689 /*
690 * Signature does not fit, loop.
691 */
692 continue;
693 }
694 if (u + v < tu) {
695 memset(es + u + v, 0, tu - (u + v));
696 v = tu - u;
697 }
698 break;
699 case FALCON_SIG_CT:
700 es[0] = 0x50 + logn;
701 v = Zf(trim_i16_encode)(es + u, es_len - u,
702 sv, logn, Zf(max_sig_bits)[logn]);
703 if (v == 0) {
704 return FALCON_ERR_SIZE;
705 }
706 break;
707 }
708 *sig_len = u + v;
709 return 0;
710 }
711 }
712
713 /* see falcon.h */
714 int
715 falcon_sign_dyn(shake256_context *rng,
716 void *sig, size_t *sig_len, int sig_type,
717 const void *privkey, size_t privkey_len,
718 const void *data, size_t data_len,
719 void *tmp, size_t tmp_len)
720 {
721 shake256_context hd;
722 uint8_t nonce[40];
723 int r;
724
725 r = falcon_sign_start(rng, nonce, &hd);
726 if (r != 0) {
727 return r;
728 }
729 shake256_inject(&hd, data, data_len);
730 return falcon_sign_dyn_finish(rng, sig, sig_len, sig_type,
731 privkey, privkey_len, &hd, nonce, tmp, tmp_len);
732 }
733
734 /* see falcon.h */
735 int
736 falcon_sign_tree(shake256_context *rng,
737 void *sig, size_t *sig_len, int sig_type,
738 const void *expanded_key,
739 const void *data, size_t data_len,
740 void *tmp, size_t tmp_len)
741 {
742 shake256_context hd;
743 uint8_t nonce[40];
744 int r;
745
746 r = falcon_sign_start(rng, nonce, &hd);
747 if (r != 0) {
748 return r;
749 }
750 shake256_inject(&hd, data, data_len);
751 return falcon_sign_tree_finish(rng, sig, sig_len, sig_type,
752 expanded_key, &hd, nonce, tmp, tmp_len);
753 }
754
755 /* see falcon.h */
756 int
757 falcon_verify_start(shake256_context *hash_data,
758 const void *sig, size_t sig_len)
759 {
760 if (sig_len < 41) {
761 return FALCON_ERR_FORMAT;
762 }
763 shake256_init(hash_data);
764 shake256_inject(hash_data, (const uint8_t *)sig + 1, 40);
765 return 0;
766 }
767
768 /* see falcon.h */
769 int
770 falcon_verify_finish(const void *sig, size_t sig_len, int sig_type,
771 const void *pubkey, size_t pubkey_len,
772 shake256_context *hash_data,
773 void *tmp, size_t tmp_len)
774 {
775 unsigned logn;
776 uint8_t *atmp;
777 const uint8_t *pk, *es;
778 size_t u, v, n;
779 uint16_t *h, *hm;
780 int16_t *sv;
781 int ct;
782
783 /*
784 * Get Falcon degree from public key; verify consistency with
785 * signature value, and check parameters.
786 */
787 if (sig_len < 41 || pubkey_len == 0) {
788 return FALCON_ERR_FORMAT;
789 }
790 es = sig;
791 pk = pubkey;
792 if ((pk[0] & 0xF0) != 0x00) {
793 return FALCON_ERR_FORMAT;
794 }
795 logn = pk[0] & 0x0F;
796 if (logn < 1 || logn > 10) {
797 return FALCON_ERR_FORMAT;
798 }
799 if ((es[0] & 0x0F) != logn) {
800 return FALCON_ERR_BADSIG;
801 }
802 ct = 0;
803 switch (sig_type) {
804 case 0:
805 switch (es[0] & 0xF0) {
806 case 0x30:
807 break;
808 case 0x50:
809 if (sig_len != FALCON_SIG_CT_SIZE(logn)) {
810 return FALCON_ERR_FORMAT;
811 }
812 ct = 1;
813 break;
814 default:
815 return FALCON_ERR_BADSIG;
816 }
817 break;
818 case FALCON_SIG_COMPRESSED:
819 if ((es[0] & 0xF0) != 0x30) {
820 return FALCON_ERR_FORMAT;
821 }
822 break;
823 case FALCON_SIG_PADDED:
824 if ((es[0] & 0xF0) != 0x30) {
825 return FALCON_ERR_FORMAT;
826 }
827 if (sig_len != FALCON_SIG_PADDED_SIZE(logn)) {
828 return FALCON_ERR_FORMAT;
829 }
830 break;
831 case FALCON_SIG_CT:
832 if ((es[0] & 0xF0) != 0x50) {
833 return FALCON_ERR_FORMAT;
834 }
835 if (sig_len != FALCON_SIG_CT_SIZE(logn)) {
836 return FALCON_ERR_FORMAT;
837 }
838 ct = 1;
839 break;
840 default:
841 return FALCON_ERR_BADARG;
842 }
843 if (pubkey_len != FALCON_PUBKEY_SIZE(logn)) {
844 return FALCON_ERR_FORMAT;
845 }
846 if (tmp_len < FALCON_TMPSIZE_VERIFY(logn)) {
847 return FALCON_ERR_SIZE;
848 }
849
850 n = (size_t)1 << logn;
851 h = (uint16_t *)align_u16(tmp);
852 hm = h + n;
853 sv = (int16_t *)(hm + n);
854 atmp = (uint8_t *)(sv + n);
855
856 /*
857 * Decode public key.
858 */
859 if (Zf(modq_decode)(h, logn, pk + 1, pubkey_len - 1)
860 != pubkey_len - 1)
861 {
862 return FALCON_ERR_FORMAT;
863 }
864
865 /*
866 * Decode signature value.
867 */
868 u = 41;
869 if (ct) {
870 v = Zf(trim_i16_decode)(sv, logn,
871 Zf(max_sig_bits)[logn], es + u, sig_len - u);
872 } else {
873 v = Zf(comp_decode)(sv, logn, es + u, sig_len - u);
874 }
875 if (v == 0) {
876 return FALCON_ERR_FORMAT;
877 }
878 if ((u + v) != sig_len) {
879 /*
880 * Extra bytes of value 0 are tolerated only for the
881 * "padded" format.
882 */
883 if ((sig_type == 0 && sig_len == FALCON_SIG_PADDED_SIZE(logn))
884 || sig_type == FALCON_SIG_PADDED)
885 {
886 while (u + v < sig_len) {
887 if (es[u + v] != 0) {
888 return FALCON_ERR_FORMAT;
889 }
890 v ++;
891 }
892 } else {
893 return FALCON_ERR_FORMAT;
894 }
895 }
896
897 /*
898 * Hash message to point.
899 */
900 shake256_flip(hash_data);
901 if (ct) {
902 Zf(hash_to_point_ct)(
903 (inner_shake256_context *)hash_data, hm, logn, atmp);
904 } else {
905 Zf(hash_to_point_vartime)(
906 (inner_shake256_context *)hash_data, hm, logn);
907 }
908
909 /*
910 * Verify signature.
911 */
912 Zf(to_ntt_monty)(h, logn);
913 if (!Zf(verify_raw)(hm, sv, h, logn, atmp)) {
914 return FALCON_ERR_BADSIG;
915 }
916 return 0;
917 }
918
919 /* see falcon.h */
920 int
921 falcon_verify(const void *sig, size_t sig_len, int sig_type,
922 const void *pubkey, size_t pubkey_len,
923 const void *data, size_t data_len,
924 void *tmp, size_t tmp_len)
925 {
926 shake256_context hd;
927 int r;
928
929 r = falcon_verify_start(&hd, sig, sig_len);
930 if (r < 0) {
931 return r;
932 }
933 shake256_inject(&hd, data, data_len);
934 return falcon_verify_finish(sig, sig_len, sig_type,
935 pubkey, pubkey_len, &hd, tmp, tmp_len);
936 }