1 /*
2 * Copyright (C) 2021 - This file is part of libecc project
3 *
4 * Authors:
5 * Ryad BENADJILA <ryadbenadjila@gmail.com>
6 * Arnaud EBALARD <arnaud.ebalard@ssi.gouv.fr>
7 *
8 * This software is licensed under a dual BSD and GPL v2 license.
9 * See LICENSE file at the root folder of the project.
10 */
11 #include <libecc/lib_ecc_config.h>
12 #if defined(WITH_SIG_EDDSA25519) || defined(WITH_SIG_EDDSA448)
13
14 /*
15 * XXX: EdDSA is incompatible with small stack devices for now ...
16 */
17 #if defined(USE_SMALL_STACK)
18 #error "Error: EDDSA25519 and EDDSA448 are incompatible with USE_SMALL_STACK (devices low on memory)"
19 #endif
20
21 /*
22 * Sanity checks on the hash functions and curves depending on the EdDSA variant.
23 */
24 /* EDDSA25519 used SHA-512 as a fixed hash function and WEI25519 as a fixed
25 * curve.
26 */
27 #if defined(WITH_SIG_EDDSA25519)
28 #if !defined(WITH_HASH_SHA512) || !defined(WITH_CURVE_WEI25519)
29 #error "Error: EDDSA25519 needs SHA-512 and WEI25519 to be defined! Please define them in libecc config file"
30 #endif
31 #endif
32 /* EDDSA448 used SHAKE256 as a fixed hash function and WEI448 as a fixed
33 * curve.
34 */
35 #if defined(WITH_SIG_EDDSA448)
36 #if !defined(WITH_HASH_SHAKE256) || !defined(WITH_CURVE_WEI448)
37 #error "Error: EDDSA25519 needs SHAKE256 and WEI448 to be defined! Please define them in libecc config file"
38 #endif
39 #endif
40
41 #include <libecc/nn/nn_rand.h>
42 #include <libecc/nn/nn_mul_public.h>
43 #include <libecc/nn/nn_logical.h>
44 #include <libecc/fp/fp.h>
45 #include <libecc/fp/fp_sqrt.h>
46 /* Include the "internal" header as we use non public API here */
47 #include "../nn/nn_div.h"
48
49
50 #include <libecc/sig/sig_algs_internal.h>
51 #include <libecc/sig/sig_algs.h>
52 #include <libecc/sig/ec_key.h>
53 #include <libecc/utils/utils.h>
54 #ifdef VERBOSE_INNER_VALUES
55 #define EC_SIG_ALG "EDDSA"
56 #endif
57 #include <libecc/utils/dbg_sig.h>
58
59
dom(u16 x,const u8 * y,u16 olen_y,const hash_mapping * h,hash_context * h_ctx,u8 dom_type)60 ATTRIBUTE_WARN_UNUSED_RET static inline int dom(u16 x, const u8 *y, u16 olen_y, const hash_mapping *h,
61 hash_context *h_ctx, u8 dom_type){
62 u8 tmp[2];
63 int ret;
64
65 MUST_HAVE((h != NULL) && (h_ctx != NULL), ret, err);
66 /* Sanity check on ancillary data len, its size must not exceed 255 bytes as per RFC8032 */
67 MUST_HAVE((x <= 255) && (olen_y <= 255), ret, err);
68
69 if(dom_type == 2){
70 ret = h->hfunc_update(h_ctx, (const u8*)"SigEd25519 no Ed25519 collisions", 32); EG(ret, err);
71 }
72 else if(dom_type == 4){
73 ret = h->hfunc_update(h_ctx, (const u8*)"SigEd448", 8); EG(ret, err);
74 }
75 else{
76 ret = -1;
77 goto err;
78 }
79 tmp[0] = (u8)x;
80 tmp[1] = (u8)olen_y;
81 ret = h->hfunc_update(h_ctx, tmp, 2); EG(ret, err);
82 if(y != NULL){
83 ret = h->hfunc_update(h_ctx, y, olen_y); EG(ret, err);
84 }
85
86 err:
87 return ret;
88 }
89
90 #if defined(WITH_SIG_EDDSA25519)
91 /* Helper for dom2(x, y).
92 *
93 * See RFC8032:
94 *
95 * dom2(x, y) The blank octet string when signing or verifying
96 * Ed25519. Otherwise, the octet string: "SigEd25519 no
97 * Ed25519 collisions" || octet(x) || octet(OLEN(y)) ||
98 * y, where x is in range 0-255 and y is an octet string
99 * of at most 255 octets. "SigEd25519 no Ed25519
100 * collisions" is in ASCII (32 octets).
101 */
dom2(u16 x,const u8 * y,u16 olen_y,const hash_mapping * h,hash_context * h_ctx)102 ATTRIBUTE_WARN_UNUSED_RET static inline int dom2(u16 x, const u8 *y, u16 olen_y, const hash_mapping *h,
103 hash_context *h_ctx){
104 return dom(x, y, olen_y, h, h_ctx, 2);
105 }
106 #endif /* defined(WITH_SIG_EDDSA25519) */
107
108 #if defined(WITH_SIG_EDDSA448)
109 /* Helper for dom4(x, y).
110 *
111 * See RFC8032:
112 *
113 * dom4(x, y) The octet string "SigEd448" || octet(x) ||
114 * octet(OLEN(y)) || y, where x is in range 0-255 and y
115 * is an octet string of at most 255 octets. "SigEd448"
116 * is in ASCII (8 octets).
117 */
dom4(u16 x,const u8 * y,u16 olen_y,const hash_mapping * h,hash_context * h_ctx)118 ATTRIBUTE_WARN_UNUSED_RET static inline int dom4(u16 x, const u8 *y, u16 olen_y, const hash_mapping *h,
119 hash_context *h_ctx){
120 return dom(x, y, olen_y, h, h_ctx, 4);
121 }
122 #endif /* defined(WITH_SIG_EDDSA448) */
123
124 /* EdDSA sanity check on keys.
125 * EDDSA25519 and variants only support WEI25519 as a curve, and SHA-512 as a hash function.
126 * EDDSA448 and variants only support WEI448 as a curve, and SHAKE256 as a "hash function".
127 */
get_eddsa_hash_type(ec_alg_type sig_type)128 ATTRIBUTE_WARN_UNUSED_RET static inline hash_alg_type get_eddsa_hash_type(ec_alg_type sig_type){
129 hash_alg_type hash_type = UNKNOWN_HASH_ALG;
130
131 switch (sig_type) {
132 #if defined(WITH_SIG_EDDSA25519)
133 case EDDSA25519:
134 case EDDSA25519PH:
135 case EDDSA25519CTX:{
136 hash_type = SHA512;
137 break;
138 }
139 #endif
140 #if defined(WITH_SIG_EDDSA448)
141 case EDDSA448:
142 case EDDSA448PH:{
143 hash_type = SHAKE256;
144 break;
145 }
146 #endif
147 default:{
148 hash_type = UNKNOWN_HASH_ALG;
149 break;
150 }
151 }
152 return hash_type;
153 }
154
155 /*
156 * Check given EdDSA key type does match given curve type. Returns 0 on success,
157 * and -1 on error.
158 */
eddsa_key_type_check_curve(ec_alg_type key_type,ec_curve_type curve_type)159 ATTRIBUTE_WARN_UNUSED_RET static int eddsa_key_type_check_curve(ec_alg_type key_type,
160 ec_curve_type curve_type)
161 {
162 int ret;
163
164 switch (key_type) {
165 #if defined(WITH_SIG_EDDSA25519)
166 case EDDSA25519:
167 case EDDSA25519PH:
168 case EDDSA25519CTX:{
169 /* Check curve */
170 ret = (curve_type == WEI25519) ? 0 : -1;
171 break;
172 }
173 #endif
174 #if defined(WITH_SIG_EDDSA448)
175 case EDDSA448:
176 case EDDSA448PH:{
177 /* Check curve */
178 ret = (curve_type == WEI448) ? 0 : -1;
179 break;
180 }
181 #endif
182 default:{
183 ret = -1;
184 break;
185 }
186 }
187
188 return ret;
189 }
190
eddsa_priv_key_sanity_check(const ec_priv_key * in_priv)191 ATTRIBUTE_WARN_UNUSED_RET static int eddsa_priv_key_sanity_check(const ec_priv_key *in_priv)
192 {
193 int ret;
194
195 ret = priv_key_check_initialized(in_priv); EG(ret, err);
196 ret = eddsa_key_type_check_curve(in_priv->key_type,
197 in_priv->params->curve_type);
198
199 err:
200 return ret;
201 }
202
eddsa_pub_key_sanity_check(const ec_pub_key * in_pub)203 ATTRIBUTE_WARN_UNUSED_RET static int eddsa_pub_key_sanity_check(const ec_pub_key *in_pub)
204 {
205 int ret;
206
207
208 ret = pub_key_check_initialized(in_pub); EG(ret, err);
209 ret = eddsa_key_type_check_curve(in_pub->key_type,
210 in_pub->params->curve_type);
211
212 err:
213 return ret;
214 }
215
eddsa_key_pair_sanity_check(const ec_key_pair * key_pair)216 ATTRIBUTE_WARN_UNUSED_RET static int eddsa_key_pair_sanity_check(const ec_key_pair *key_pair)
217 {
218 int ret;
219
220 MUST_HAVE((key_pair != NULL), ret, err);
221 ret = eddsa_priv_key_sanity_check(&(key_pair->priv_key)); EG(ret, err);
222 ret = eddsa_pub_key_sanity_check(&(key_pair->pub_key)); EG(ret, err);
223 MUST_HAVE((key_pair->priv_key.key_type == key_pair->pub_key.key_type), ret, err);
224
225 err:
226 return ret;
227 }
228
229 /*
230 * EdDSA decode an integer from a buffer using little endian format.
231 */
eddsa_decode_integer(nn_t nn_out,const u8 * buf,u16 buf_size)232 ATTRIBUTE_WARN_UNUSED_RET static int eddsa_decode_integer(nn_t nn_out, const u8 *buf, u16 buf_size)
233 {
234 u16 i;
235 u8 buf_little_endian[MAX_DIGEST_SIZE];
236 int ret;
237
238 MUST_HAVE((buf != NULL), ret, err);
239 MUST_HAVE((sizeof(buf_little_endian) >= buf_size), ret, err);
240
241 ret = nn_init(nn_out, 0); EG(ret, err);
242
243 ret = local_memset(buf_little_endian, 0, sizeof(buf_little_endian)); EG(ret, err);
244 if(buf_size > 1){
245 /* Inverse endianness of our input buffer */
246 for(i = 0; i < buf_size; i++){
247 buf_little_endian[i] = buf[buf_size - 1 - i];
248 }
249 }
250
251 /* Compute an integer from the buffer */
252 ret = nn_init_from_buf(nn_out, buf_little_endian, buf_size);
253
254 err:
255 return ret;
256 }
257
258 /*
259 * EdDSA encode an integer to a buffer using little endian format.
260 */
eddsa_encode_integer(nn_src_t nn_in,u8 * buf,u16 buf_size)261 ATTRIBUTE_WARN_UNUSED_RET static int eddsa_encode_integer(nn_src_t nn_in, u8 *buf, u16 buf_size)
262 {
263 u16 i;
264 u8 tmp;
265 int ret;
266 bitcnt_t blen;
267
268 MUST_HAVE((buf != NULL), ret, err);
269 ret = nn_check_initialized(nn_in); EG(ret, err);
270
271 /* Sanity check that we do not lose information */
272 ret = nn_bitlen(nn_in, &blen); EG(ret, err);
273 MUST_HAVE((((u32)blen) <= (8 * (u32)buf_size)), ret, err);
274
275 /* Export the number to our buffer */
276 ret = nn_export_to_buf(buf, buf_size, nn_in); EG(ret, err);
277
278 /* Now reverse endianness in place */
279 if(buf_size > 1){
280 for(i = 0; i < (buf_size / 2); i++){
281 tmp = buf[i];
282 buf[i] = buf[buf_size - 1 - i];
283 buf[buf_size - 1 - i] = tmp;
284 }
285 }
286
287 err:
288 return ret;
289 }
290
291 /*
292 * EdDSA encoding of scalar s.
293 */
eddsa_compute_s(nn_t s,const u8 * digest,u16 digest_size)294 ATTRIBUTE_WARN_UNUSED_RET static int eddsa_compute_s(nn_t s, const u8 *digest, u16 digest_size)
295 {
296 int ret;
297
298 MUST_HAVE((digest != NULL), ret, err);
299 MUST_HAVE(((digest_size % 2) == 0), ret, err);
300
301 /* s is half of the digest size encoded in little endian format */
302 ret = eddsa_decode_integer(s, digest, (digest_size / 2)); EG(ret, err);
303
304 err:
305 return ret;
306 }
307
308 /* Extract the digest from the encoded private key */
eddsa_get_digest_from_priv_key(u8 * digest,u8 * digest_size,const ec_priv_key * in_priv)309 ATTRIBUTE_WARN_UNUSED_RET static int eddsa_get_digest_from_priv_key(u8 *digest, u8 *digest_size, const ec_priv_key *in_priv)
310 {
311 int ret;
312 hash_alg_type hash_type;
313 const hash_mapping *hash;
314
315 MUST_HAVE(((digest != NULL) && (digest_size != NULL)), ret, err);
316 ret = eddsa_priv_key_sanity_check(in_priv); EG(ret, err);
317
318 MUST_HAVE(((hash_type = get_eddsa_hash_type(in_priv->key_type)) != UNKNOWN_HASH_ALG), ret, err);
319 ret = get_hash_by_type(hash_type, &hash); EG(ret, err);
320 MUST_HAVE((hash != NULL), ret, err);
321
322 /* Check real digest size */
323 MUST_HAVE(((*digest_size) >= hash->digest_size), ret, err);
324
325 (*digest_size) = hash->digest_size;
326 ret = nn_export_to_buf(digest, *digest_size, &(in_priv->x));
327
328 err:
329 return ret;
330 }
331
332 /* Encode an Edwards curve affine point in canonical form */
eddsa_encode_point(aff_pt_edwards_src_t in,fp_src_t alpha_edwards,u8 * buf,u16 buflen,ec_alg_type sig_alg)333 ATTRIBUTE_WARN_UNUSED_RET static int eddsa_encode_point(aff_pt_edwards_src_t in,
334 fp_src_t alpha_edwards,
335 u8 *buf, u16 buflen,
336 ec_alg_type sig_alg)
337 {
338 nn out_reduced;
339 u8 lsb = 0;
340 int ret;
341 out_reduced.magic = WORD(0);
342
343 /* Sanity checks */
344 MUST_HAVE((buf != NULL), ret, err);
345 ret = aff_pt_edwards_check_initialized(in); EG(ret, err);
346 ret = fp_check_initialized(alpha_edwards); EG(ret, err);
347
348 /* Zeroize the buffer */
349 ret = local_memset(buf, 0, buflen); EG(ret, err);
350 ret = nn_init(&out_reduced, 0); EG(ret, err);
351
352 /* Note: we should be reduced modulo Fp for canonical encoding here as
353 * coordinate elements are in Fp ...
354 */
355 #if defined(WITH_SIG_EDDSA448)
356 if((sig_alg == EDDSA448) || (sig_alg == EDDSA448PH)){
357 /*
358 * In case of EDDSA448, we apply the 4-isogeny to transfer from
359 * Ed448 to Edwards448.
360 * The isogeny maps (x, y) on Ed448 to (x1, y1) on Edwards448
361 * using:
362 * x1 = (4*x*y/c) / (y^2-x^2)
363 * y1 = (2-x^2-y^2) / (x^2+y^2) = (2 - (x^2+y^2)) / (x^2 + y^2)
364 * and (0, 1) as well as (0, -1) are mapped to (0, 1)
365 * We only need to encode our y1 here, but x1 computation is
366 * unfortunately needed to get its LSB that is necessary for
367 * the encoding.
368 */
369 fp tmp_x, tmp_y, y1;
370 tmp_x.magic = tmp_y.magic = y1.magic = WORD(0);
371 /* Compute x1 to get our LSB */
372 ret = fp_init(&y1, in->y.ctx); EG(ret, err1);
373 ret = fp_copy(&tmp_x, &(in->x)); EG(ret, err1);
374 ret = fp_sqr(&tmp_x, &tmp_x); EG(ret, err1);
375 ret = fp_copy(&tmp_y, &(in->y)); EG(ret, err1);
376 ret = fp_sqr(&tmp_y, &tmp_y); EG(ret, err1);
377 ret = fp_sub(&tmp_y, &tmp_y, &tmp_x); EG(ret, err1);
378 /* NOTE: inversion by zero should be caught by lower layers */
379 ret = fp_inv(&tmp_y, &tmp_y); EG(ret, err1);
380 ret = fp_set_word_value(&tmp_x, WORD(4)); EG(ret, err1);
381 ret = fp_mul(&tmp_x, &tmp_x, &(in->x)); EG(ret, err1);
382 ret = fp_mul(&tmp_x, &tmp_x, &(in->y)); EG(ret, err1);
383 ret = fp_mul(&tmp_x, &tmp_x, &tmp_y); EG(ret, err1);
384 ret = fp_inv(&tmp_y, alpha_edwards); EG(ret, err1);
385 ret = fp_mul(&tmp_x, &tmp_x, &tmp_y); EG(ret, err1);
386 ret = nn_getbit(&(tmp_x.fp_val), 0, &lsb); EG(ret, err1);
387 /* Compute y1 */
388 ret = fp_copy(&tmp_x, &(in->x)); EG(ret, err1);
389 ret = fp_sqr(&tmp_x, &tmp_x); EG(ret, err1);
390 ret = fp_copy(&tmp_y, &(in->y)); EG(ret, err1);
391 ret = fp_sqr(&tmp_y, &tmp_y); EG(ret, err1);
392 ret = fp_set_word_value(&y1, WORD(2)); EG(ret, err1);
393 ret = fp_sub(&y1, &y1, &tmp_x); EG(ret, err1);
394 ret = fp_sub(&y1, &y1, &tmp_y); EG(ret, err1);
395 ret = fp_add(&tmp_x, &tmp_x, &tmp_y); EG(ret, err1);
396 /* NOTE: inversion by zero should be caught by lower layers */
397 ret = fp_inv(&tmp_x, &tmp_x); EG(ret, err1);
398 ret = fp_mul(&y1, &y1, &tmp_x); EG(ret, err1);
399 ret = eddsa_encode_integer(&(y1.fp_val), buf, buflen);
400 err1:
401 fp_uninit(&tmp_x);
402 fp_uninit(&tmp_y);
403 fp_uninit(&y1);
404 EG(ret, err);
405 }
406 else
407 #endif /* !defined(WITH_SIG_EDDSA448) */
408 { /* EDDSA25519 and other cases */
409 FORCE_USED_VAR(sig_alg); /* To avoid unused variable error */
410 ret = nn_getbit(&(in->x.fp_val), 0, &lsb); EG(ret, err);
411 ret = eddsa_encode_integer(&(in->y.fp_val), buf, buflen); EG(ret, err);
412 }
413 /*
414 * Now deal with the sign for the last bit: copy the least significant
415 * bit of the x coordinate in the MSB of the last octet.
416 */
417 MUST_HAVE((buflen > 1), ret, err);
418 buf[buflen - 1] |= (u8)(lsb << 7);
419
420 err:
421 nn_uninit(&out_reduced);
422
423 return ret;
424 }
425
426 /* Decode an Edwards curve affine point from canonical form */
eddsa_decode_point(aff_pt_edwards_t out,ec_edwards_crv_src_t edwards_curve,fp_src_t alpha_edwards,const u8 * buf,u16 buflen,ec_alg_type sig_type)427 ATTRIBUTE_WARN_UNUSED_RET static int eddsa_decode_point(aff_pt_edwards_t out, ec_edwards_crv_src_t edwards_curve,
428 fp_src_t alpha_edwards, const u8 *buf, u16 buflen,
429 ec_alg_type sig_type)
430 {
431 fp x, y;
432 fp sqrt1, sqrt2;
433 u8 x_0, lsb;
434 u8 buf_little_endian[MAX_DIGEST_SIZE];
435 u16 i;
436 int ret, iszero;
437
438 #if defined(WITH_SIG_EDDSA448)
439 fp tmp;
440 tmp.magic = WORD(0);
441 #endif
442 x.magic = y.magic = sqrt1.magic = sqrt2.magic = WORD(0);
443
444 MUST_HAVE((buf != NULL), ret, err);
445
446 ret = ec_edwards_crv_check_initialized(edwards_curve); EG(ret, err);
447
448 ret = fp_check_initialized(alpha_edwards); EG(ret, err);
449
450 /* Extract the sign */
451 x_0 = ((buf[buflen - 1] & 0x80) >> 7);
452 /* Extract the value by reversing endianness */
453 MUST_HAVE((sizeof(buf_little_endian) >= buflen), ret, err);
454
455 /* Inverse endianness of our input buffer and mask the sign bit */
456 MUST_HAVE((buflen > 1), ret, err);
457
458 for(i = 0; i < buflen; i++){
459 buf_little_endian[i] = buf[buflen - 1 - i];
460 if(i == 0){
461 /* Mask the sign bit */
462 buf_little_endian[i] &= 0x7f;
463 }
464 }
465 /* Try to decode the y coordinate */
466 ret = fp_init_from_buf(&y, edwards_curve->a.ctx, buf_little_endian, buflen); EG(ret, err);
467 /*
468 * If we suceed, try to find our x coordinate that is the square root of
469 * (y^2 - 1) / (d y^2 + 1) or (y^2 - 1) / (d y^2 - 1) depending on the
470 * algorithm (EDDSA25519 our EDDSA448).
471 */
472 ret = fp_init(&sqrt1, edwards_curve->a.ctx); EG(ret, err);
473 ret = fp_init(&sqrt2, edwards_curve->a.ctx); EG(ret, err);
474 ret = fp_init(&x, edwards_curve->a.ctx); EG(ret, err);
475 #if defined(WITH_SIG_EDDSA448)
476 if((sig_type == EDDSA448) || (sig_type == EDDSA448PH)){
477 const u8 d_edwards448_buff[] = {
478 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
479 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
480 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
481 0xff, 0xff, 0xff, 0xfe, 0xff, 0xff, 0xff, 0xff,
482 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
483 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
484 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x67, 0x56
485 };
486 ec_edwards_crv edwards_curve_edwards448;
487
488 ret = fp_init(&tmp, edwards_curve->a.ctx); EG(ret, err);
489 /*
490 * If we deal with EDDSA448 we must handle the point on
491 * Edwards448 so we use the dedicated d.
492 */
493 ret = fp_init_from_buf(&tmp, edwards_curve->a.ctx,
494 (const u8*)d_edwards448_buff, sizeof(d_edwards448_buff)); EG(ret, err);
495 ret = ec_edwards_crv_init(&edwards_curve_edwards448, &(edwards_curve->a), &tmp, &(edwards_curve->order)); EG(ret, err);
496 /* Compute x from y using the dedicated primitive */
497 ret = aff_pt_edwards_x_from_y(&sqrt1, &sqrt2, &y, &edwards_curve_edwards448); EG(ret, err); /* Error or no square root found, this should not happen! */
498 ec_edwards_crv_uninit(&edwards_curve_edwards448);
499 }
500 else
501 #endif
502 {
503 /* Compute x from y using the dedicated primitive */
504 ret = aff_pt_edwards_x_from_y(&sqrt1, &sqrt2, &y, edwards_curve); EG(ret, err); /* Error or no square root found, this should not happen! */
505 }
506 /* Now select the square root of the proper sign */
507 ret = nn_getbit(&(sqrt1.fp_val), 0, &lsb); EG(ret, err);
508 if(lsb == x_0){
509 ret = fp_copy(&x, &sqrt1); EG(ret, err);
510 }
511 else{
512 ret = fp_copy(&x, &sqrt2); EG(ret, err);
513 }
514 /* If x = 0 and the sign bit is 1, this is an error */
515 ret = fp_iszero(&x, &iszero); EG(ret, err);
516 MUST_HAVE(!(iszero && (x_0 == 1)), ret, err);
517 /*
518 * In case of EDDSA448, we apply the 4-isogeny to transfer from
519 * Edwards448 to Ed448.
520 * The isogeny maps (x1, y1) on Edwards448 to (x, y) on Ed448 using:
521 * x = alpha_edwards * (x1*y1) / (2-x1^2-y1^2)
522 * y = (x1^2+y1^2) / (y1^2-x1^2)
523 */
524 #if defined(WITH_SIG_EDDSA448)
525 if((sig_type == EDDSA448) || (sig_type == EDDSA448PH)){
526 /*
527 * Use sqrt1 and sqrt2 as temporary buffers for x and y, and
528 * tmp as scratch pad buffer
529 */
530 ret = fp_copy(&sqrt1, &x); EG(ret, err);
531 ret = fp_copy(&sqrt2, &y); EG(ret, err);
532
533 ret = fp_set_word_value(&x, WORD(2)); EG(ret, err);
534 ret = fp_sqr(&tmp, &sqrt1); EG(ret, err);
535 ret = fp_sub(&x, &x, &tmp); EG(ret, err);
536 ret = fp_sqr(&tmp, &sqrt2); EG(ret, err);
537 ret = fp_sub(&x, &x, &tmp); EG(ret, err);
538 /* NOTE: inversion by zero should be caught by lower layers */
539 ret = fp_inv(&x, &x); EG(ret, err);
540 ret = fp_mul(&x, &x, &sqrt1); EG(ret, err);
541 ret = fp_mul(&x, &x, &sqrt2); EG(ret, err);
542 ret = fp_mul(&x, &x, alpha_edwards); EG(ret, err);
543
544 ret = fp_sqr(&sqrt1, &sqrt1); EG(ret, err);
545 ret = fp_sqr(&sqrt2, &sqrt2); EG(ret, err);
546 ret = fp_sub(&y, &sqrt2, &sqrt1); EG(ret, err);
547 /* NOTE: inversion by zero should be caught by lower layers */
548 ret = fp_inv(&y, &y); EG(ret, err);
549 ret = fp_add(&sqrt1, &sqrt1, &sqrt2); EG(ret, err);
550 ret = fp_mul(&y, &y, &sqrt1); EG(ret, err);
551 }
552 #endif /* !defined(WITH_SIG_EDDSA448) */
553
554 /* Initialize our point */
555 ret = aff_pt_edwards_init_from_coords(out, edwards_curve, &x, &y);
556
557 err:
558 fp_uninit(&sqrt1);
559 fp_uninit(&sqrt2);
560 fp_uninit(&x);
561 fp_uninit(&y);
562 #if defined(WITH_SIG_EDDSA448)
563 fp_uninit(&tmp);
564 #endif
565
566 return ret;
567 }
568
569
570 /*
571 * Derive hash from private key.
572 */
eddsa_derive_priv_key_hash(const ec_priv_key * in_priv,u8 * buf,u16 buflen)573 ATTRIBUTE_WARN_UNUSED_RET static int eddsa_derive_priv_key_hash(const ec_priv_key *in_priv,
574 u8 *buf, u16 buflen)
575 {
576 hash_alg_type hash_type = UNKNOWN_HASH_ALG;
577 const hash_mapping *hash;
578 u8 x_buf[EC_PRIV_KEY_MAX_SIZE];
579 int ret;
580 const u8 *in[2];
581 u32 in_len[2];
582
583 MUST_HAVE((buf != NULL), ret, err);
584 ret = eddsa_priv_key_sanity_check(in_priv); EG(ret, err);
585
586 MUST_HAVE(((hash_type = get_eddsa_hash_type(in_priv->key_type)) != UNKNOWN_HASH_ALG), ret, err);
587 ret = get_hash_by_type(hash_type, &hash); EG(ret, err);
588 MUST_HAVE((hash != NULL), ret, err);
589
590 /* Get the private key as a buffer and hash it */
591 ret = local_memset(x_buf, 0, sizeof(x_buf)); EG(ret, err);
592 MUST_HAVE((sizeof(x_buf) >= (hash->digest_size / 2)), ret, err);
593
594 ret = ec_priv_key_export_to_buf(in_priv, x_buf, (hash->digest_size / 2)); EG(ret, err);
595
596 ret = hash_mapping_callbacks_sanity_check(hash); EG(ret, err);
597
598 MUST_HAVE((buflen >= hash->digest_size), ret, err);
599
600 in[0] = x_buf; in[1] = NULL;
601 in_len[0] = (hash->digest_size / 2); in_len[1] = 0;
602 ret = hash->hfunc_scattered(in, in_len, buf);
603
604 err:
605 PTR_NULLIFY(hash);
606
607 return ret;
608 }
609
610 /*
611 * Derive an EdDSA private key.
612 *
613 */
eddsa_derive_priv_key(ec_priv_key * priv_key)614 int eddsa_derive_priv_key(ec_priv_key *priv_key)
615 {
616 int ret, cmp;
617 u8 digest_size;
618 u8 digest[MAX_DIGEST_SIZE];
619 hash_alg_type hash_type = UNKNOWN_HASH_ALG;
620 word_t cofactor = WORD(0);
621
622 /* Check if private key is initialized. */
623 ret = eddsa_priv_key_sanity_check(priv_key); EG(ret, err);
624
625 /* Check hash function compatibility:
626 * We must have 2**(b-1) > p with (2*b) the size of the hash function.
627 */
628 MUST_HAVE(((hash_type = get_eddsa_hash_type(priv_key->key_type)) != UNKNOWN_HASH_ALG), ret, err);
629
630 digest_size = 0;
631 ret = get_hash_sizes(hash_type, &digest_size, NULL); EG(ret, err);
632
633 MUST_HAVE(((2 * priv_key->params->ec_fp.p_bitlen) < (8 * (bitcnt_t)digest_size)), ret, err);
634 MUST_HAVE(((digest_size % 2) == 0), ret, err);
635 MUST_HAVE((digest_size <= sizeof(digest)), ret, err);
636
637 /*
638 * Now that we have our private scalar, derive the hash value of secret
639 * key
640 */
641 /* Hash the private key */
642 ret = eddsa_derive_priv_key_hash(priv_key, digest, digest_size); EG(ret, err);
643
644 /* Get the cofactor as an integer */
645 cofactor = priv_key->params->ec_gen_cofactor.val[0];
646 ret = nn_cmp_word(&(priv_key->params->ec_gen_cofactor), cofactor, &cmp); EG(ret, err);
647 MUST_HAVE((cmp == 0), ret, err);
648 /* Cofactor must be 2**2 or 2**3 as per RFC8032 standard */
649 MUST_HAVE((cofactor == (0x1 << 2)) || (cofactor == (0x1 << 3)), ret, err);
650
651 /* Now clear the low bits related to cofactor */
652 digest[0] &= (u8)(~(cofactor - 1));
653 #if defined(WITH_SIG_EDDSA25519)
654 if ((priv_key->key_type == EDDSA25519) ||
655 (priv_key->key_type == EDDSA25519CTX) ||
656 (priv_key->key_type == EDDSA25519PH)){
657 /*
658 * MSB of highest octet of half must be cleared, second MSB must
659 * be set
660 */
661 digest[(digest_size / 2) - 1] &= 0x7f;
662 digest[(digest_size / 2) - 1] |= 0x40;
663 }
664 #endif
665 #if defined(WITH_SIG_EDDSA448)
666 if ((priv_key->key_type == EDDSA448) || (priv_key->key_type == EDDSA448PH)) {
667 MUST_HAVE((digest_size / 2) >= 2, ret, err);
668 /*
669 * All eight bits of the last octet are cleared, highest bit
670 * of the second to last octet is set.
671 */
672 digest[(digest_size / 2) - 1] = 0;
673 digest[(digest_size / 2) - 2] |= 0x80;
674 }
675 #endif
676 #if !defined(WITH_SIG_EDDSA25519) && !defined(WITH_SIG_EDDSA448)
677 ret = -1;
678 goto err;
679 #endif
680 /*
681 * Now that we have derived our hash, store it in place of our secret
682 * value NOTE: we do not need the secret value anymore since only the
683 * hash is needed.
684 */
685 ret = nn_init_from_buf(&(priv_key->x), digest, digest_size);
686
687 err:
688 VAR_ZEROIFY(digest_size);
689
690 return ret;
691 }
692
693 /*
694 * Generate an EdDSA private key.
695 *
696 */
eddsa_gen_priv_key(ec_priv_key * priv_key)697 int eddsa_gen_priv_key(ec_priv_key *priv_key)
698 {
699 int ret;
700 u8 digest_size;
701 hash_alg_type hash_type = UNKNOWN_HASH_ALG;
702
703 /* Check if private key is initialized. */
704 ret = eddsa_priv_key_sanity_check(priv_key); EG(ret, err);
705
706 /* Check hash function compatibility:
707 * We must have 2**(b-1) > p with (2*b) the size of the hash function.
708 */
709 MUST_HAVE(((hash_type = get_eddsa_hash_type(priv_key->key_type)) != UNKNOWN_HASH_ALG), ret, err);
710
711 digest_size = 0;
712 ret = get_hash_sizes(hash_type, &digest_size, NULL); EG(ret, err);
713
714 MUST_HAVE(((2 * priv_key->params->ec_fp.p_bitlen) < (8 * (bitcnt_t)digest_size)), ret, err);
715 MUST_HAVE(((digest_size % 2) == 0), ret, err);
716
717 /* Generate a random private key
718 * An EdDSA secret scalar is a b bit string with (2*b) the size of the hash function
719 */
720 ret = nn_get_random_len(&(priv_key->x), (digest_size / 2)); EG(ret, err);
721
722 /* Derive the private key */
723 ret = eddsa_derive_priv_key(priv_key);
724
725 err:
726 VAR_ZEROIFY(digest_size);
727
728 return ret;
729 }
730
731
732 /* Import an EdDSA private key from a raw buffer.
733 * NOTE: the private key must be a big number associated to the curve that
734 * depends on the flavor of EdDSA (Ed25519 or Ed448), and the result is a
735 * derived private key that can be used by the internal EdDSA functions.
736 * The derived key is a hash of the private key: we mainly perform this
737 * derivation early to prevent side-channel attacks and other leaks on the
738 * "root" private key.
739 */
eddsa_import_priv_key(ec_priv_key * priv_key,const u8 * buf,u16 buflen,const ec_params * shortw_curve_params,ec_alg_type sig_type)740 int eddsa_import_priv_key(ec_priv_key *priv_key, const u8 *buf, u16 buflen,
741 const ec_params *shortw_curve_params,
742 ec_alg_type sig_type)
743 {
744 int ret;
745 hash_alg_type hash_type = UNKNOWN_HASH_ALG;
746 u8 digest_size;
747 bitcnt_t blen;
748
749 /* Some sanity checks */
750 MUST_HAVE((priv_key != NULL) && (buf != NULL) && (shortw_curve_params != NULL), ret, err);
751
752 /* Import the big number from our buffer */
753 ret = nn_init_from_buf(&(priv_key->x), buf, buflen); EG(ret, err);
754 /* The bit length of our big number must be <= b, half the digest size */
755 hash_type = get_eddsa_hash_type(sig_type);
756 MUST_HAVE((hash_type != UNKNOWN_HASH_ALG), ret, err);
757
758 digest_size = 0;
759 ret = get_hash_sizes(hash_type, &digest_size, NULL); EG(ret, err);
760
761 ret = nn_bitlen(&(priv_key->x), &blen); EG(ret, err);
762 MUST_HAVE((blen <= (8 * ((bitcnt_t)digest_size / 2))), ret, err);
763
764 /* Initialize stuff */
765 priv_key->key_type = sig_type;
766 priv_key->params = shortw_curve_params;
767 priv_key->magic = PRIV_KEY_MAGIC;
768
769 /* Now derive the private key.
770 * NOTE: sanity check on the private key is performed during derivation.
771 */
772 ret = eddsa_derive_priv_key(priv_key);
773
774 err:
775 if((priv_key != NULL) && ret){
776 IGNORE_RET_VAL(local_memset(priv_key, 0, sizeof(ec_priv_key)));
777 }
778 VAR_ZEROIFY(digest_size);
779 VAR_ZEROIFY(blen);
780
781 return ret;
782 }
783
784 /* NOTE: we perform EDDSA public key computation on the short Weierstrass
785 * form of the curve thanks to the birational equivalence of curve
786 * models (the isomorphism allows to perform the scalar multiplication
787 * on the equivalent curve).
788 */
eddsa_init_pub_key(ec_pub_key * out_pub,const ec_priv_key * in_priv)789 int eddsa_init_pub_key(ec_pub_key *out_pub, const ec_priv_key *in_priv)
790 {
791 prj_pt_src_t G;
792 u8 digest_size;
793 u8 digest[MAX_DIGEST_SIZE];
794 /* Secret scalar used for public generation */
795 nn s;
796 hash_alg_type hash_type;
797 u8 digest_size_;
798 int ret;
799 s.magic = WORD(0);
800
801 MUST_HAVE(out_pub != NULL, ret, err);
802 ret = eddsa_priv_key_sanity_check(in_priv); EG(ret, err);
803
804 ret = nn_init(&s, 0); EG(ret, err);
805
806 /* Zero init public key to be generated */
807 ret = local_memset(out_pub, 0, sizeof(ec_pub_key)); EG(ret, err);
808
809 /* Get the generator G */
810 G = &(in_priv->params->ec_gen);
811
812 /* Get the digest in proper format */
813 MUST_HAVE(((hash_type = get_eddsa_hash_type(in_priv->key_type)) != UNKNOWN_HASH_ALG), ret, err);
814
815 digest_size_ = 0;
816 ret = get_hash_sizes(hash_type, &digest_size_, NULL); EG(ret, err);
817
818 /* Extract the digest */
819 digest_size = sizeof(digest);
820 ret = eddsa_get_digest_from_priv_key(digest, &digest_size, in_priv); EG(ret, err);
821
822 /* Sanity check */
823 MUST_HAVE((digest_size == digest_size_), ret, err);
824
825 /* Encode the scalar s from the digest */
826 ret = eddsa_compute_s(&s, digest, digest_size); EG(ret, err);
827
828 /* Compute s x G where G is the base point */
829 /*
830 * Use blinding when computing point scalar multiplication as we
831 * manipulate a fixed secret.
832 */
833 #if defined(WITH_SIG_EDDSA448)
834 if((in_priv->key_type == EDDSA448) || (in_priv->key_type == EDDSA448PH)){
835 /*
836 * NOTE: because of the 4-isogeny between Ed448 and Edwards448,
837 * we actually multiply by (s/4) since the base point of
838 * Edwards448 is four times the one of Ed448.
839 * Here, s/4 can be simply computed by right shifting by 2 as
840 * we are ensured that our scalar is a multiple of 4 by
841 * construction.
842 */
843 ret = nn_rshift(&s, &s, 2); EG(ret, err);
844 }
845 #endif
846 ret = prj_pt_mul_blind(&(out_pub->y), &s, G); EG(ret, err);
847
848 out_pub->key_type = in_priv->key_type;
849 out_pub->params = in_priv->params;
850 out_pub->magic = PUB_KEY_MAGIC;
851
852 err:
853 PTR_NULLIFY(G);
854 VAR_ZEROIFY(digest_size);
855 nn_uninit(&s);
856
857 return ret;
858 }
859
860 /*
861 * Import a public key in canonical form.
862 * (imports a public key from a buffer and checks its canonical form.)
863 *
864 */
eddsa_import_pub_key(ec_pub_key * pub_key,const u8 * buf,u16 buflen,const ec_params * shortw_curve_params,ec_alg_type sig_type)865 int eddsa_import_pub_key(ec_pub_key *pub_key, const u8 *buf, u16 buflen,
866 const ec_params *shortw_curve_params,
867 ec_alg_type sig_type)
868 {
869 aff_pt_edwards _Tmp;
870 ec_edwards_crv edwards_curve;
871 int ret;
872 ec_shortw_crv_src_t shortw_curve;
873 fp_src_t alpha_montgomery;
874 fp_src_t gamma_montgomery;
875 fp_src_t alpha_edwards;
876 prj_pt_t pub_key_y;
877 _Tmp.magic = edwards_curve.magic = WORD(0);
878
879 #if defined(WITH_SIG_EDDSA25519) && defined(WITH_SIG_EDDSA448)
880 if((sig_type != EDDSA25519) && (sig_type != EDDSA25519CTX) && (sig_type != EDDSA25519PH) && \
881 (sig_type != EDDSA448) && (sig_type != EDDSA448PH)){
882 #endif
883 #if defined(WITH_SIG_EDDSA25519) && !defined(WITH_SIG_EDDSA448)
884 if((sig_type != EDDSA25519) && (sig_type != EDDSA25519CTX) && (sig_type != EDDSA25519PH)){
885 #endif
886 #if !defined(WITH_SIG_EDDSA25519) && defined(WITH_SIG_EDDSA448)
887 if((sig_type != EDDSA448) && (sig_type != EDDSA448PH)){
888 #endif
889 ret = -1;
890 goto err;
891 }
892
893 MUST_HAVE((pub_key != NULL) && (shortw_curve_params != NULL) && (buf != NULL), ret, err);
894
895 /* Check for sizes on the buffer for strict size depending on EdDSA types */
896 #if defined(WITH_SIG_EDDSA25519)
897 if((sig_type == EDDSA25519) || (sig_type == EDDSA25519CTX) || (sig_type == EDDSA25519PH)){
898 MUST_HAVE((buflen == EDDSA25519_PUB_KEY_ENCODED_LEN), ret, err);
899 }
900 #endif
901 #if defined(WITH_SIG_EDDSA448)
902 if((sig_type == EDDSA448) || (sig_type == EDDSA448PH)){
903 MUST_HAVE((buflen == EDDSA448_PUB_KEY_ENCODED_LEN), ret, err);
904 }
905 #endif
906
907 /* Make things more readable */
908 shortw_curve = &(shortw_curve_params->ec_curve);
909 alpha_montgomery = &(shortw_curve_params->ec_alpha_montgomery);
910 gamma_montgomery = &(shortw_curve_params->ec_gamma_montgomery);
911 alpha_edwards = &(shortw_curve_params->ec_alpha_edwards);
912 pub_key_y = &(pub_key->y);
913
914 /* Get the isogenic Edwards curve */
915 ret = curve_shortw_to_edwards(shortw_curve, &edwards_curve, alpha_montgomery,
916 gamma_montgomery, alpha_edwards); EG(ret, err);
917
918 /* Decode the point in Edwards */
919 ret = eddsa_decode_point(&_Tmp, &edwards_curve, alpha_edwards, buf, buflen,
920 sig_type); EG(ret, err);
921 /* Then transfer to short Weierstrass in our public key */
922 ret = aff_pt_edwards_to_prj_pt_shortw(&_Tmp, shortw_curve, pub_key_y,
923 alpha_edwards); EG(ret, err);
924 #if defined(WITH_SIG_EDDSA448)
925 if((sig_type == EDDSA448) || (sig_type == EDDSA448PH)){
926 nn_src_t gen_order = &(shortw_curve_params->ec_gen_order);
927 nn tmp;
928 tmp.magic = WORD(0);
929
930 /*
931 * NOTE: because of the 4-isogeny between Ed448 and Edwards448,
932 * we actually multiply by (s/4) since the base point of
933 * Edwards448 is four times the one of Ed448.
934 * Here, s/4 is computed by multiplying s by the modular
935 * inverse of 4.
936 */
937 ret = nn_init(&tmp, 0); EG(ret, err1);
938 ret = nn_modinv_word(&tmp, WORD(4), gen_order); EG(ret, err1);
939 ret = prj_pt_mul(&(pub_key->y), &tmp, pub_key_y); EG(ret, err1);
940 err1:
941 nn_uninit(&tmp);
942 PTR_NULLIFY(gen_order);
943 EG(ret, err);
944 }
945 #endif
946 /* Mark the public key as initialized */
947 pub_key->key_type = sig_type;
948 pub_key->params = shortw_curve_params;
949 pub_key->magic = PUB_KEY_MAGIC;
950
951 /* Now sanity check our public key before validating the import */
952 ret = eddsa_pub_key_sanity_check(pub_key);
953
954 err:
955 if((pub_key != NULL) && ret){
956 IGNORE_RET_VAL(local_memset(pub_key, 0, sizeof(ec_pub_key)));
957 }
958 PTR_NULLIFY(shortw_curve);
959 PTR_NULLIFY(alpha_montgomery);
960 PTR_NULLIFY(gamma_montgomery);
961 PTR_NULLIFY(alpha_edwards);
962 PTR_NULLIFY(pub_key_y);
963 aff_pt_edwards_uninit(&_Tmp);
964 ec_edwards_crv_uninit(&edwards_curve);
965
966 return ret;
967 }
968
969 /*
970 * Export a public key in canonical form.
971 * (exports a public key to a buffer in canonical form.)
972 */
973 int eddsa_export_pub_key(const ec_pub_key *in_pub, u8 *buf, u16 buflen)
974 {
975 aff_pt_edwards _Tmp;
976 ec_edwards_crv edwards_curve;
977 ec_alg_type sig_type;
978 int ret;
979 ec_shortw_crv_src_t shortw_curve;
980 fp_src_t alpha_montgomery;
981 fp_src_t gamma_montgomery;
982 fp_src_t alpha_edwards;
983 prj_pt_src_t pub_key_y;
984 _Tmp.magic = edwards_curve.magic = WORD(0);
985
986 ret = pub_key_check_initialized(in_pub); EG(ret, err);
987 MUST_HAVE((buf != NULL), ret, err);
988
989 /* Make things more readable */
990 shortw_curve = &(in_pub->params->ec_curve);
991 alpha_montgomery = &(in_pub->params->ec_alpha_montgomery);
992 gamma_montgomery = &(in_pub->params->ec_gamma_montgomery);
993 alpha_edwards = &(in_pub->params->ec_alpha_edwards);
994 pub_key_y = &(in_pub->y);
995 sig_type = in_pub->key_type;
996
997 /* Check for sizes on the buffer for strict size depending on EdDSA types */
998 #if defined(WITH_SIG_EDDSA25519)
999 if((sig_type == EDDSA25519) || (sig_type == EDDSA25519CTX) || (sig_type == EDDSA25519PH)){
1000 MUST_HAVE((buflen == EDDSA25519_PUB_KEY_ENCODED_LEN), ret, err);
1001 }
1002 #endif
1003 #if defined(WITH_SIG_EDDSA448)
1004 if((sig_type == EDDSA448) || (sig_type == EDDSA448PH)){
1005 MUST_HAVE((buflen == EDDSA448_PUB_KEY_ENCODED_LEN), ret, err);
1006 }
1007 #endif
1008
1009 /* Transfer our short Weierstrass to Edwards representation */
1010 ret = curve_shortw_to_edwards(shortw_curve, &edwards_curve, alpha_montgomery,
1011 gamma_montgomery, alpha_edwards); EG(ret, err);
1012 ret = prj_pt_shortw_to_aff_pt_edwards(pub_key_y, &edwards_curve, &_Tmp,
1013 alpha_edwards); EG(ret, err);
1014 /* Export to buffer canonical form */
1015 ret = eddsa_encode_point(&_Tmp, alpha_edwards, buf,
1016 buflen, in_pub->key_type);
1017
1018 err:
1019 PTR_NULLIFY(shortw_curve);
1020 PTR_NULLIFY(alpha_montgomery);
1021 PTR_NULLIFY(gamma_montgomery);
1022 PTR_NULLIFY(alpha_edwards);
1023 PTR_NULLIFY(pub_key_y);
1024 aff_pt_edwards_uninit(&_Tmp);
1025 ec_edwards_crv_uninit(&edwards_curve);
1026
1027 return ret;
1028 }
1029
1030 /* Import an EdDSA key pair from a private key buffer */
1031 int eddsa_import_key_pair_from_priv_key_buf(ec_key_pair *kp,
1032 const u8 *buf, u16 buflen,
1033 const ec_params *shortw_curve_params,
1034 ec_alg_type sig_type)
1035 {
1036 int ret;
1037
1038 MUST_HAVE((kp != NULL), ret, err);
1039
1040 /* Try to import the private key */
1041 ret = eddsa_import_priv_key(&(kp->priv_key), buf, buflen,
1042 shortw_curve_params, sig_type); EG(ret, err);
1043
1044 /* Now derive the public key */
1045 ret = eddsa_init_pub_key(&(kp->pub_key), &(kp->priv_key));
1046
1047 err:
1048 return ret;
1049 }
1050
1051 /* Compute PH(M) with PH being the hash depending on the key type */
1052 ATTRIBUTE_WARN_UNUSED_RET static int eddsa_compute_pre_hash(const u8 *message, u32 message_size,
1053 u8 *digest, u8 *digest_size,
1054 ec_alg_type sig_type)
1055 {
1056 hash_alg_type hash_type;
1057 const hash_mapping *hash;
1058 hash_context hash_ctx;
1059 int ret;
1060
1061 MUST_HAVE((message != NULL) && (digest != NULL) && (digest_size != NULL), ret, err);
1062
1063 MUST_HAVE(((hash_type = get_eddsa_hash_type(sig_type)) != UNKNOWN_HASH_ALG), ret, err);
1064
1065 ret = get_hash_by_type(hash_type, &hash); EG(ret, err);
1066 MUST_HAVE((hash != NULL), ret, err);
1067
1068 /* Sanity check on the size */
1069 MUST_HAVE(((*digest_size) >= hash->digest_size), ret, err);
1070
1071 (*digest_size) = hash->digest_size;
1072 /* Hash the message */
1073 ret = hash_mapping_callbacks_sanity_check(hash); EG(ret, err);
1074 ret = hash->hfunc_init(&hash_ctx); EG(ret, err);
1075 ret = hash->hfunc_update(&hash_ctx, message, message_size); EG(ret, err);
1076 ret = hash->hfunc_finalize(&hash_ctx, digest); EG(ret, err);
1077
1078 err:
1079 return ret;
1080 }
1081
1082 /*****************/
1083
1084 /* EdDSA signature length */
1085 int eddsa_siglen(u16 p_bit_len, u16 q_bit_len, u8 hsize, u8 blocksize, u8 *siglen)
1086 {
1087 int ret;
1088
1089 MUST_HAVE((siglen != NULL), ret, err);
1090 MUST_HAVE((p_bit_len <= CURVES_MAX_P_BIT_LEN) &&
1091 (q_bit_len <= CURVES_MAX_Q_BIT_LEN) &&
1092 (hsize <= MAX_DIGEST_SIZE) && (blocksize <= MAX_BLOCK_SIZE), ret, err);
1093
1094 (*siglen) = (u8)EDDSA_SIGLEN(hsize);
1095 ret = 0;
1096 err:
1097 return ret;
1098 }
1099
1100 /*
1101 * Generic *internal* EdDSA signature functions (init, update and finalize).
1102 *
1103 * Global EdDSA signature process is as follows (I,U,F provides
1104 * information in which function(s) (init(), update() or finalize())
1105 * a specific step is performed):
1106 *
1107 */
1108
1109 #define EDDSA_SIGN_MAGIC ((word_t)(0x7632542bf630972bULL))
1110 #define EDDSA_SIGN_CHECK_INITIALIZED(A, ret, err) \
1111 MUST_HAVE((((void *)(A)) != NULL) && ((A)->magic == EDDSA_SIGN_MAGIC), ret, err)
1112
1113 int _eddsa_sign_init_pre_hash(struct ec_sign_context *ctx)
1114 {
1115 int ret;
1116 bitcnt_t blen;
1117 u8 use_message_pre_hash = 0;
1118 ec_alg_type key_type = UNKNOWN_ALG;
1119 const ec_key_pair *key_pair;
1120 const hash_mapping *h;
1121
1122 /* First, verify context has been initialized */
1123 ret = sig_sign_check_initialized(ctx); EG(ret, err);
1124
1125 /* Make things more readable */
1126 key_pair = ctx->key_pair;
1127 h = ctx->h;
1128 key_type = ctx->key_pair->priv_key.key_type;
1129
1130 /* Sanity check: this function is only supported in PH mode */
1131 #if defined(WITH_SIG_EDDSA25519)
1132 if(key_type == EDDSA25519PH){
1133 use_message_pre_hash = 1;
1134 }
1135 #endif
1136 #if defined(WITH_SIG_EDDSA448)
1137 if(key_type == EDDSA448PH){
1138 use_message_pre_hash = 1;
1139 }
1140 #endif
1141 MUST_HAVE((use_message_pre_hash == 1), ret, err);
1142
1143 /* Additional sanity checks on input params from context */
1144 ret = eddsa_key_pair_sanity_check(key_pair); EG(ret, err);
1145
1146 MUST_HAVE((h != NULL) && (h->digest_size <= MAX_DIGEST_SIZE) && (h->block_size <= MAX_BLOCK_SIZE), ret, err);
1147
1148 /* Sanity check on hash types */
1149 MUST_HAVE((key_type == key_pair->pub_key.key_type) && (h->type == get_eddsa_hash_type(key_type)), ret, err);
1150
1151 /*
1152 * Sanity check on hash size versus private key size
1153 */
1154 ret = nn_bitlen(&(key_pair->priv_key.x), &blen); EG(ret, err);
1155 MUST_HAVE(blen <= (8 * h->digest_size), ret, err);
1156
1157 /*
1158 * Initialize hash context stored in our private part of context
1159 * and record data init has been done
1160 */
1161 /* Since we call a callback, sanity check our mapping */
1162 ret = hash_mapping_callbacks_sanity_check(h); EG(ret, err);
1163 ret = h->hfunc_init(&(ctx->sign_data.eddsa.h_ctx)); EG(ret, err);
1164
1165 /* Initialize other elements in the context */
1166 ctx->sign_data.eddsa.magic = EDDSA_SIGN_MAGIC;
1167
1168 err:
1169 PTR_NULLIFY(key_pair);
1170 PTR_NULLIFY(h);
1171 VAR_ZEROIFY(use_message_pre_hash);
1172
1173 return ret;
1174 }
1175
1176 int _eddsa_sign_update_pre_hash(struct ec_sign_context *ctx,
1177 const u8 *chunk, u32 chunklen)
1178 {
1179 int ret;
1180 ec_alg_type key_type = UNKNOWN_ALG;
1181 u8 use_message_pre_hash = 0;
1182
1183 /*
1184 * First, verify context has been initialized and public
1185 * part too. This guarantees the context is an EDDSA
1186 * verification one and we do not update() or finalize()
1187 * before init().
1188 */
1189 ret = sig_sign_check_initialized(ctx); EG(ret, err);
1190 EDDSA_SIGN_CHECK_INITIALIZED(&(ctx->sign_data.eddsa), ret, err);
1191 MUST_HAVE((chunk != NULL), ret, err);
1192
1193 key_type = ctx->key_pair->priv_key.key_type;
1194
1195 /* Sanity check: this function is only supported in PH mode */
1196 #if defined(WITH_SIG_EDDSA25519)
1197 if(key_type == EDDSA25519PH){
1198 use_message_pre_hash = 1;
1199 }
1200 #endif
1201 #if defined(WITH_SIG_EDDSA448)
1202 if(key_type == EDDSA448PH){
1203 use_message_pre_hash = 1;
1204 }
1205 #endif
1206 MUST_HAVE(use_message_pre_hash == 1, ret, err);
1207
1208 /* Sanity check on hash types */
1209 MUST_HAVE((ctx->h->type == get_eddsa_hash_type(key_type)), ret, err);
1210
1211 /* 2. Compute h = H(m) */
1212 /* Since we call a callback, sanity check our mapping */
1213 ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err);
1214
1215 ret = ctx->h->hfunc_update(&(ctx->sign_data.eddsa.h_ctx), chunk, chunklen);
1216
1217 err:
1218 VAR_ZEROIFY(use_message_pre_hash);
1219
1220 return ret;
1221
1222 }
1223
1224 int _eddsa_sign_finalize_pre_hash(struct ec_sign_context *ctx, u8 *sig, u8 siglen)
1225 {
1226 const ec_priv_key *priv_key;
1227 const ec_pub_key *pub_key;
1228 prj_pt_src_t G;
1229 u8 hash[MAX_DIGEST_SIZE];
1230 u8 ph_hash[MAX_DIGEST_SIZE];
1231 prj_pt R;
1232 ec_edwards_crv crv_edwards;
1233 aff_pt_edwards Tmp_edwards;
1234 nn_src_t q;
1235 u8 hsize, hash_size;
1236 int ret;
1237 ec_shortw_crv_src_t shortw_curve;
1238 fp_src_t alpha_montgomery;
1239 fp_src_t gamma_montgomery;
1240 fp_src_t alpha_edwards;
1241 prj_pt_src_t pub_key_y;
1242 u8 use_message_pre_hash = 0;
1243 u16 use_message_pre_hash_hsize = 0;
1244 ec_alg_type key_type = UNKNOWN_ALG;
1245 u8 r_len, s_len;
1246 const hash_mapping *h;
1247
1248 nn r, s, S;
1249 #ifdef USE_SIG_BLINDING
1250 /* b is the blinding mask */
1251 nn b, binv;
1252 b.magic = binv.magic = WORD(0);
1253 #endif /* !USE_SIG_BLINDING */
1254 r.magic = s.magic = S.magic = WORD(0);
1255 R.magic = crv_edwards.magic = Tmp_edwards.magic = WORD(0);
1256
1257 /*
1258 * First, verify context has been initialized and private
1259 * part too. This guarantees the context is an EDDSA
1260 * signature one and we do not update() or finalize()
1261 * before init().
1262 */
1263 ret = sig_sign_check_initialized(ctx); EG(ret, err);
1264 EDDSA_SIGN_CHECK_INITIALIZED(&(ctx->sign_data.eddsa), ret, err);
1265 MUST_HAVE((sig != NULL), ret, err);
1266
1267 /* Zero init out points and data */
1268 ret = local_memset(&R, 0, sizeof(prj_pt)); EG(ret, err);
1269 ret = local_memset(&Tmp_edwards, 0, sizeof(aff_pt_edwards)); EG(ret, err);
1270 ret = local_memset(&crv_edwards, 0, sizeof(ec_edwards_crv)); EG(ret, err);
1271 ret = local_memset(hash, 0, sizeof(hash)); EG(ret, err);
1272 ret = local_memset(ph_hash, 0, sizeof(ph_hash)); EG(ret, err);
1273
1274 /* Key type */
1275 key_type = ctx->key_pair->priv_key.key_type;
1276 /* Sanity check on hash types */
1277 MUST_HAVE((key_type == ctx->key_pair->pub_key.key_type) && (ctx->h->type == get_eddsa_hash_type(key_type)), ret, err);
1278
1279 /* Make things more readable */
1280 priv_key = &(ctx->key_pair->priv_key);
1281 pub_key = &(ctx->key_pair->pub_key);
1282 q = &(priv_key->params->ec_gen_order);
1283 G = &(priv_key->params->ec_gen);
1284 h = ctx->h;
1285 hsize = h->digest_size;
1286 r_len = EDDSA_R_LEN(hsize);
1287 s_len = EDDSA_S_LEN(hsize);
1288
1289 shortw_curve = &(priv_key->params->ec_curve);
1290 alpha_montgomery = &(priv_key->params->ec_alpha_montgomery);
1291 gamma_montgomery = &(priv_key->params->ec_gamma_montgomery);
1292 alpha_edwards = &(priv_key->params->ec_alpha_edwards);
1293 pub_key_y = &(pub_key->y);
1294
1295 dbg_nn_print("p", &(priv_key->params->ec_fp.p));
1296 dbg_nn_print("q", &(priv_key->params->ec_gen_order));
1297 dbg_priv_key_print("x", priv_key);
1298 dbg_ec_point_print("G", &(priv_key->params->ec_gen));
1299 dbg_pub_key_print("Y", &(ctx->key_pair->pub_key));
1300
1301 /* Check provided signature length */
1302 MUST_HAVE((siglen == EDDSA_SIGLEN(hsize)) && (siglen == (r_len + s_len)), ret, err);
1303
1304 /* Is it indeed a PH version of the algorithm? */
1305 #if defined(WITH_SIG_EDDSA25519)
1306 if(key_type == EDDSA25519PH){
1307 use_message_pre_hash = 1;
1308 use_message_pre_hash_hsize = hsize;
1309 }
1310 #endif
1311 #if defined(WITH_SIG_EDDSA448)
1312 if(key_type == EDDSA448PH){
1313 use_message_pre_hash = 1;
1314 /* NOTE: as per RFC8032, EDDSA448PH uses
1315 * SHAKE256 with 64 bytes output.
1316 */
1317 use_message_pre_hash_hsize = 64;
1318 }
1319 #endif
1320 /* Sanity check: this function is only supported in PH mode */
1321 MUST_HAVE((use_message_pre_hash == 1), ret, err);
1322
1323 /* Finish the message hash session */
1324 /* Since we call a callback, sanity check our mapping */
1325 ret = hash_mapping_callbacks_sanity_check(h); EG(ret, err);
1326
1327 ret = h->hfunc_finalize(&(ctx->sign_data.eddsa.h_ctx), ph_hash); EG(ret, err);
1328
1329 /* 1. Finish computing the nonce r = H(h256 || ... || h511 || m) */
1330 /* Update our hash context with half of the secret key */
1331 hash_size = sizeof(hash);
1332 ret = eddsa_get_digest_from_priv_key(hash, &hash_size, priv_key); EG(ret, err);
1333
1334 /* Sanity check */
1335 MUST_HAVE((hash_size == hsize), ret, err);
1336
1337 /* Hash half the digest */
1338 ret = h->hfunc_init(&(ctx->sign_data.eddsa.h_ctx)); EG(ret, err);
1339
1340 /* At this point, we are ensured that we have PH versions of the algorithms */
1341 #if defined(WITH_SIG_EDDSA25519)
1342 if(key_type == EDDSA25519PH){
1343 ret = dom2(1, ctx->adata, ctx->adata_len, h,
1344 &(ctx->sign_data.eddsa.h_ctx)); EG(ret, err);
1345 }
1346 #endif
1347 #if defined(WITH_SIG_EDDSA448)
1348 if(key_type == EDDSA448PH){
1349 ret = dom4(1, ctx->adata, ctx->adata_len, h,
1350 &(ctx->sign_data.eddsa.h_ctx)); EG(ret, err);
1351 }
1352 #endif
1353 ret = h->hfunc_update(&(ctx->sign_data.eddsa.h_ctx), &hash[hsize / 2], hsize / 2); EG(ret, err);
1354
1355 /* Update hash h with message hash PH(m) */
1356 MUST_HAVE((use_message_pre_hash_hsize <= hsize), ret, err);
1357
1358 ret = h->hfunc_update(&(ctx->sign_data.eddsa.h_ctx), ph_hash,
1359 use_message_pre_hash_hsize); EG(ret, err);
1360
1361 /* 1. Finish computing the nonce r = H(h256 || ... || h511 || PH(m)) */
1362 ret = h->hfunc_finalize(&(ctx->sign_data.eddsa.h_ctx), hash); EG(ret, err);
1363 dbg_buf_print("h(h || m)", hash, hsize);
1364
1365 /* Import r as the hash scalar */
1366 ret = eddsa_decode_integer(&r, hash, hsize); EG(ret, err);
1367
1368 #ifdef USE_SIG_BLINDING
1369 /* Get a random b for blinding the r modular operations before the
1370 * scalar multiplication as we do not want it to leak.
1371 */
1372 ret = nn_get_random_mod(&b, q); EG(ret, err);
1373 dbg_nn_print("b", &b);
1374 /* NOTE: we use Fermat's little theorem inversion for
1375 * constant time here. This is possible since q is prime.
1376 */
1377 ret = nn_modinv_fermat(&binv, &b, q); EG(ret, err);
1378
1379 /* Blind r */
1380 ret = nn_mul(&r, &r, &b); EG(ret, err);
1381 #endif /* USE_SIG_BLINDING */
1382
1383 /* Reduce r modulo q for the next computation.
1384 * (this is a blind reduction if USE_SIG_BLINDING).
1385 */
1386 ret = nn_mod_notrim(&r, &r, q); EG(ret, err);
1387
1388 /* Now perform our scalar multiplication.
1389 */
1390 #if defined(WITH_SIG_EDDSA448)
1391 if(key_type == EDDSA448PH){
1392 /*
1393 * NOTE: in case of EDDSA448, because of the 4-isogeny we must
1394 * divide our scalar by 4.
1395 */
1396 nn r_tmp;
1397 r_tmp.magic = WORD(0);
1398
1399 ret = nn_init(&r_tmp, 0); EG(ret, err1);
1400 ret = nn_modinv_word(&r_tmp, WORD(4), q); EG(ret, err1);
1401 ret = nn_mod_mul(&r_tmp, &r_tmp, &r, q); EG(ret, err1);
1402
1403 #ifdef USE_SIG_BLINDING
1404 /* Unblind r_tmp */
1405 ret = nn_mod_mul(&r_tmp, &r_tmp, &binv, q); EG(ret, err1);
1406 ret = prj_pt_mul_blind(&R, &r_tmp, G);
1407 #else
1408 ret = prj_pt_mul(&R, &r_tmp, G);
1409 #endif /* !USE_SIG_BLINDING */
1410 err1:
1411 nn_uninit(&r_tmp);
1412 EG(ret, err);
1413 }
1414 else
1415 #endif /* !defined(WITH_SIG_EDDSA448) */
1416 {
1417 #ifdef USE_SIG_BLINDING
1418 nn r_tmp;
1419 r_tmp.magic = WORD(0);
1420
1421 ret = nn_init(&r_tmp, 0); EG(ret, err2);
1422 ret = nn_copy(&r_tmp, &r); EG(ret, err2);
1423
1424 /* Unblind r_tmp */
1425 ret = nn_mod_mul(&r_tmp, &r_tmp, &binv, q); EG(ret, err2);
1426 ret = prj_pt_mul_blind(&R, &r_tmp, G); EG(ret, err2);
1427 err2:
1428 nn_uninit(&r_tmp);
1429 EG(ret, err);
1430 #else
1431 ret = prj_pt_mul(&R, &r, G); EG(ret, err);
1432 #endif /* !USE_SIG_BLINDING */
1433 }
1434
1435 /* Now compute S = (r + H(R || PubKey || PH(m)) * secret) mod q */
1436 ret = h->hfunc_init(&(ctx->sign_data.eddsa.h_ctx)); EG(ret, err);
1437 /* Transfer R to Edwards */
1438 ret = curve_shortw_to_edwards(shortw_curve, &crv_edwards, alpha_montgomery,
1439 gamma_montgomery, alpha_edwards); EG(ret, err);
1440 ret = prj_pt_shortw_to_aff_pt_edwards(&R, &crv_edwards, &Tmp_edwards,
1441 alpha_edwards); EG(ret, err);
1442 dbg_ec_edwards_point_print("R", &Tmp_edwards);
1443
1444 MUST_HAVE((r_len <= siglen), ret, err);
1445 /* Encode R and update */
1446 ret = eddsa_encode_point(&Tmp_edwards, alpha_edwards, &sig[0],
1447 r_len, key_type); EG(ret, err);
1448 /* At this point, we are ensured that we have PH versions of the algorithms */
1449 #if defined(WITH_SIG_EDDSA25519)
1450 if(key_type == EDDSA25519PH){
1451 ret = dom2(1, ctx->adata, ctx->adata_len, h,
1452 &(ctx->sign_data.eddsa.h_ctx)); EG(ret, err);
1453 }
1454 #endif
1455 #if defined(WITH_SIG_EDDSA448)
1456 if(key_type == EDDSA448PH){
1457 ret = dom4(1, ctx->adata, ctx->adata_len, h,
1458 &(ctx->sign_data.eddsa.h_ctx)); EG(ret, err);
1459 }
1460 #endif
1461 /* Update the hash with the encoded R point */
1462 ret = h->hfunc_update(&(ctx->sign_data.eddsa.h_ctx), &sig[0], r_len); EG(ret, err);
1463 /* Encode the public key */
1464 /* Transfer the public key to Edwards */
1465 ret = prj_pt_shortw_to_aff_pt_edwards(pub_key_y, &crv_edwards,
1466 &Tmp_edwards, alpha_edwards); EG(ret, err);
1467 dbg_ec_edwards_point_print("A", &Tmp_edwards);
1468 MUST_HAVE(r_len <= sizeof(hash), ret, err);
1469
1470 /* NOTE: we use the hash buffer as a temporary buffer */
1471 ret = eddsa_encode_point(&Tmp_edwards, alpha_edwards, hash,
1472 r_len, key_type); EG(ret, err);
1473
1474 /* Update the hash with the encoded public key point */
1475 ret = h->hfunc_update(&(ctx->sign_data.eddsa.h_ctx), hash, r_len); EG(ret, err);
1476 /* Update the hash with PH(m) */
1477 ret = h->hfunc_update(&(ctx->sign_data.eddsa.h_ctx), ph_hash,
1478 use_message_pre_hash_hsize); EG(ret, err);
1479 /* Finalize the hash */
1480 ret = h->hfunc_finalize(&(ctx->sign_data.eddsa.h_ctx), hash); EG(ret, err);
1481 dbg_buf_print("h(R || PubKey || PH(m))", hash, hsize);
1482 /* Import our resulting hash as an integer in S */
1483 ret = eddsa_decode_integer(&S, hash, hsize); EG(ret, err);
1484 ret = nn_mod(&S, &S, q); EG(ret, err);
1485 /* Extract the digest */
1486 hsize = sizeof(hash);
1487 ret = eddsa_get_digest_from_priv_key(hash, &hsize, priv_key); EG(ret, err);
1488 /* Encode the scalar s from the digest */
1489 ret = eddsa_compute_s(&s, hash, hsize); EG(ret, err);
1490 ret = nn_mod(&s, &s, q); EG(ret, err);
1491
1492 #ifdef USE_SIG_BLINDING
1493 /* If we use blinding, multiply by b */
1494 ret = nn_mod_mul(&S, &S, &b, q); EG(ret, err);
1495 #endif /* !USE_SIG_BLINDING */
1496 /* Multiply by the secret */
1497 ret = nn_mod_mul(&S, &S, &s, q); EG(ret, err);
1498 /* The secret is not needed anymore */
1499 nn_uninit(&s);
1500 /* Add to r */
1501 ret = nn_mod_add(&S, &S, &r, q); EG(ret, err);
1502 #ifdef USE_SIG_BLINDING
1503 /* Unblind the result */
1504 ret = nn_mod_mul(&S, &S, &binv, q); EG(ret, err);
1505 #endif /* !USE_SIG_BLINDING */
1506 /* Store our S in the context as an encoded buffer */
1507 MUST_HAVE((s_len <= (siglen - r_len)), ret, err);
1508 ret = eddsa_encode_integer(&S, &sig[r_len], s_len);
1509
1510 err:
1511 /* Clean what remains on the stack */
1512 PTR_NULLIFY(h);
1513 PTR_NULLIFY(priv_key);
1514 PTR_NULLIFY(pub_key);
1515 PTR_NULLIFY(G);
1516 PTR_NULLIFY(q);
1517 PTR_NULLIFY(shortw_curve);
1518 PTR_NULLIFY(alpha_montgomery);
1519 PTR_NULLIFY(gamma_montgomery);
1520 PTR_NULLIFY(alpha_edwards);
1521 PTR_NULLIFY(pub_key_y);
1522 VAR_ZEROIFY(hsize);
1523 VAR_ZEROIFY(hash_size);
1524 VAR_ZEROIFY(use_message_pre_hash);
1525 VAR_ZEROIFY(use_message_pre_hash_hsize);
1526 VAR_ZEROIFY(r_len);
1527 VAR_ZEROIFY(s_len);
1528
1529 prj_pt_uninit(&R);
1530 ec_edwards_crv_uninit(&crv_edwards);
1531 aff_pt_edwards_uninit(&Tmp_edwards);
1532 nn_uninit(&s);
1533 nn_uninit(&r);
1534 nn_uninit(&S);
1535
1536 #ifdef USE_SIG_BLINDING
1537 nn_uninit(&b);
1538 nn_uninit(&binv);
1539 #endif /* !USE_SIG_BLINDING */
1540
1541 /*
1542 * We can now clear data part of the context. This will clear
1543 * magic and avoid further reuse of the whole context.
1544 */
1545 if(ctx != NULL){
1546 IGNORE_RET_VAL(local_memset(&(ctx->sign_data.eddsa), 0, sizeof(eddsa_sign_data)));
1547 }
1548 IGNORE_RET_VAL(local_memset(ph_hash, 0, sizeof(ph_hash)));
1549
1550 return ret;
1551 }
1552
1553
1554 /******** Signature function specific to pure EdDSA where the message
1555 ********* streaming mode via init/update/finalize is not supported.
1556 */
1557 int _eddsa_sign(u8 *sig, u8 siglen, const ec_key_pair *key_pair,
1558 const u8 *m, u32 mlen, int (*rand) (nn_t out, nn_src_t q),
1559 ec_alg_type sig_type, hash_alg_type hash_type,
1560 const u8 *adata, u16 adata_len)
1561 {
1562 int ret;
1563 ec_alg_type key_type = UNKNOWN_ALG;
1564 ec_shortw_crv_src_t shortw_curve;
1565 fp_src_t alpha_montgomery;
1566 fp_src_t gamma_montgomery;
1567 fp_src_t alpha_edwards;
1568 prj_pt_src_t pub_key_y;
1569 u8 use_message_pre_hash = 0;
1570 u16 use_message_pre_hash_hsize = 0;
1571 prj_pt_src_t G;
1572 prj_pt R;
1573 aff_pt_edwards Tmp_edwards;
1574 ec_edwards_crv crv_edwards;
1575 u8 hash[MAX_DIGEST_SIZE];
1576 u8 ph_hash[MAX_DIGEST_SIZE];
1577 const ec_priv_key *priv_key;
1578 const ec_pub_key *pub_key;
1579 nn_src_t q;
1580 u8 hsize, hash_size;
1581 hash_context h_ctx;
1582 u8 r_len, s_len;
1583 bitcnt_t blen;
1584 const hash_mapping *h;
1585
1586 nn r, s, S;
1587 #ifdef USE_SIG_BLINDING
1588 /* b is the blinding mask */
1589 nn b, binv;
1590 b.magic = binv.magic = WORD(0);
1591 #endif
1592
1593 r.magic = s.magic = S.magic = WORD(0);
1594 R.magic = Tmp_edwards.magic = crv_edwards.magic = WORD(0);
1595
1596 /*
1597 * NOTE: EdDSA does not use any notion of random Nonce, so no need
1598 * to use 'rand' here: we strictly check that NULL is provided.
1599 */
1600 MUST_HAVE((rand == NULL), ret, err);
1601
1602 /* Zero init out points and data */
1603 ret = local_memset(&R, 0, sizeof(prj_pt)); EG(ret, err);
1604 ret = local_memset(&Tmp_edwards, 0, sizeof(aff_pt_edwards)); EG(ret, err);
1605 ret = local_memset(&crv_edwards, 0, sizeof(ec_edwards_crv)); EG(ret, err);
1606 ret = local_memset(hash, 0, sizeof(hash)); EG(ret, err);
1607 ret = local_memset(ph_hash, 0, sizeof(ph_hash)); EG(ret, err);
1608
1609 /* Sanity check on the key pair */
1610 ret = eddsa_key_pair_sanity_check(key_pair); EG(ret, err);
1611
1612 /* Make things more readable */
1613 ret = get_hash_by_type(hash_type, &h); EG(ret, err);
1614 key_type = key_pair->priv_key.key_type;
1615
1616 /* Sanity check on the hash type */
1617 MUST_HAVE((h != NULL), ret, err);
1618 MUST_HAVE((get_eddsa_hash_type(sig_type) == hash_type), ret, err);
1619 /* Sanity check on the key type */
1620 MUST_HAVE(key_type == sig_type, ret, err);
1621 MUST_HAVE((h != NULL) && (h->digest_size <= MAX_DIGEST_SIZE) && (h->block_size <= MAX_BLOCK_SIZE), ret, err);
1622 /*
1623 * Sanity check on hash size versus private key size
1624 */
1625 ret = nn_bitlen(&(key_pair->priv_key.x), &blen); EG(ret, err);
1626 MUST_HAVE((blen <= (8 * h->digest_size)), ret, err);
1627
1628 /* Make things more readable */
1629 priv_key = &(key_pair->priv_key);
1630 pub_key = &(key_pair->pub_key);
1631 q = &(priv_key->params->ec_gen_order);
1632 G = &(priv_key->params->ec_gen);
1633 hsize = h->digest_size;
1634 r_len = EDDSA_R_LEN(hsize);
1635 s_len = EDDSA_S_LEN(hsize);
1636
1637 shortw_curve = &(priv_key->params->ec_curve);
1638 alpha_montgomery = &(priv_key->params->ec_alpha_montgomery);
1639 gamma_montgomery = &(priv_key->params->ec_gamma_montgomery);
1640 alpha_edwards = &(priv_key->params->ec_alpha_edwards);
1641 pub_key_y = &(pub_key->y);
1642
1643 dbg_nn_print("p", &(priv_key->params->ec_fp.p));
1644 dbg_nn_print("q", &(priv_key->params->ec_gen_order));
1645 dbg_priv_key_print("x", priv_key);
1646 dbg_ec_point_print("G", &(priv_key->params->ec_gen));
1647 dbg_pub_key_print("Y", pub_key);
1648
1649 /* Check provided signature length */
1650 MUST_HAVE((siglen == EDDSA_SIGLEN(hsize)) && (siglen == (r_len + s_len)), ret, err);
1651
1652 /* Do we use the raw message or its PH(M) hashed version? */
1653 #if defined(WITH_SIG_EDDSA25519)
1654 if(key_type == EDDSA25519PH){
1655 use_message_pre_hash = 1;
1656 use_message_pre_hash_hsize = hsize;
1657 }
1658 #endif
1659 #if defined(WITH_SIG_EDDSA448)
1660 if(key_type == EDDSA448PH){
1661 use_message_pre_hash = 1;
1662 /* NOTE: as per RFC8032, EDDSA448PH uses
1663 * SHAKE256 with 64 bytes output.
1664 */
1665 use_message_pre_hash_hsize = 64;
1666 }
1667 #endif
1668 /* First of all, compute the message hash if necessary */
1669 if(use_message_pre_hash){
1670 hash_size = sizeof(ph_hash);
1671 ret = eddsa_compute_pre_hash(m, mlen, ph_hash, &hash_size, sig_type); EG(ret, err);
1672 MUST_HAVE(use_message_pre_hash_hsize <= hash_size, ret, err);
1673 }
1674 /* Initialize our hash context */
1675 /* Compute half of the secret key */
1676 hash_size = sizeof(hash);
1677 ret = eddsa_get_digest_from_priv_key(hash, &hash_size, &(key_pair->priv_key)); EG(ret, err);
1678 /* Sanity check */
1679 MUST_HAVE((hash_size == hsize), ret, err);
1680 /* Since we call a callback, sanity check our mapping */
1681 ret = hash_mapping_callbacks_sanity_check(h); EG(ret, err);
1682 ret = h->hfunc_init(&h_ctx); EG(ret, err);
1683 #if defined(WITH_SIG_EDDSA25519)
1684 if(key_type == EDDSA25519CTX){
1685 /* As per RFC8032, for EDDSA25519CTX the context SHOULD NOT be empty */
1686 MUST_HAVE(adata != NULL, ret, err);
1687 ret = dom2(0, adata, adata_len, h, &h_ctx); EG(ret, err);
1688 }
1689 if(key_type == EDDSA25519PH){
1690 ret = dom2(1, adata, adata_len, h, &h_ctx); EG(ret, err);
1691 }
1692 #endif
1693 #if defined(WITH_SIG_EDDSA448)
1694 if(key_type == EDDSA448){
1695 ret = dom4(0, adata, adata_len, h, &h_ctx); EG(ret, err);
1696 }
1697 if(key_type == EDDSA448PH){
1698 ret = dom4(1, adata, adata_len, h, &h_ctx); EG(ret, err);
1699 }
1700 #endif
1701 ret = h->hfunc_update(&h_ctx, &hash[hsize / 2], hsize / 2); EG(ret, err);
1702
1703 /* Now finish computing the scalar r */
1704 if(use_message_pre_hash){
1705 ret = h->hfunc_update(&h_ctx, ph_hash, use_message_pre_hash_hsize); EG(ret, err);
1706 }
1707 else{
1708 ret = h->hfunc_update(&h_ctx, m, mlen); EG(ret, err);
1709 }
1710 ret = h->hfunc_finalize(&h_ctx, hash); EG(ret, err);
1711 dbg_buf_print("h(h || PH(m))", hash, hsize);
1712
1713 /* Import r as the hash scalar */
1714 ret = eddsa_decode_integer(&r, hash, hsize); EG(ret, err);
1715
1716 #ifdef USE_SIG_BLINDING
1717 /* Get a random b for blinding the r modular operations before the
1718 * scalar multiplication as we do not want it to leak.
1719 */
1720 ret = nn_get_random_mod(&b, q); EG(ret, err);
1721 dbg_nn_print("b", &b);
1722 /* NOTE: we use Fermat's little theorem inversion for
1723 * constant time here. This is possible since q is prime.
1724 */
1725 ret = nn_modinv_fermat(&binv, &b, q); EG(ret, err);
1726
1727 /* Blind r */
1728 ret = nn_mul(&r, &r, &b); EG(ret, err);
1729 #endif /* !USE_SIG_BLINDING */
1730
1731 /* Reduce r modulo q for the next computation.
1732 * (this is a blind reduction if USE_SIG_BLINDING).
1733 */
1734 ret = nn_mod_notrim(&r, &r, q); EG(ret, err);
1735
1736 /* Now perform our scalar multiplication.
1737 */
1738 #if defined(WITH_SIG_EDDSA448)
1739 if((key_type == EDDSA448) || (key_type == EDDSA448PH)){
1740 /*
1741 * NOTE: in case of EDDSA448, because of the 4-isogeny we must
1742 * divide our scalar by 4.
1743 */
1744 nn r_tmp;
1745 r_tmp.magic = WORD(0);
1746
1747 ret = nn_init(&r_tmp, 0); EG(ret, err1);
1748 ret = nn_modinv_word(&r_tmp, WORD(4), q); EG(ret, err1);
1749 ret = nn_mod_mul(&r_tmp, &r_tmp, &r, q); EG(ret, err1);
1750
1751 #ifdef USE_SIG_BLINDING
1752 /* Unblind r_tmp */
1753 ret = nn_mod_mul(&r_tmp, &r_tmp, &binv, q); EG(ret, err1);
1754 ret = prj_pt_mul_blind(&R, &r_tmp, G);
1755 #else
1756 ret = prj_pt_mul(&R, &r_tmp, G);
1757 #endif /* !USE_SIG_BLINDING */
1758 err1:
1759 nn_uninit(&r_tmp);
1760 EG(ret, err);
1761 }
1762 else
1763 #endif /* !defined(WITH_SIG_EDDSA448) */
1764 {
1765 #ifdef USE_SIG_BLINDING
1766 nn r_tmp;
1767 r_tmp.magic = WORD(0);
1768
1769 ret = nn_init(&r_tmp, 0); EG(ret, err2);
1770 ret = nn_copy(&r_tmp, &r); EG(ret, err2);
1771
1772 /* Unblind r_tmp */
1773 ret = nn_mod_mul(&r_tmp, &r_tmp, &binv, q); EG(ret, err2);
1774 ret = prj_pt_mul_blind(&R, &r_tmp, G); EG(ret, err2);
1775 err2:
1776 nn_uninit(&r_tmp);
1777 EG(ret, err);
1778 #else
1779 ret = prj_pt_mul(&R, &r, G); EG(ret, err);
1780 #endif /* !USE_SIG_BLINDING */
1781 }
1782
1783 /* Now compute S = (r + H(R || PubKey || PH(m)) * secret) mod q */
1784 ret = hash_mapping_callbacks_sanity_check(h); EG(ret, err);
1785 ret = h->hfunc_init(&h_ctx); EG(ret, err);
1786 /* Transfer R to Edwards */
1787 ret = curve_shortw_to_edwards(shortw_curve, &crv_edwards, alpha_montgomery,
1788 gamma_montgomery, alpha_edwards); EG(ret, err);
1789 ret = prj_pt_shortw_to_aff_pt_edwards(&R, &crv_edwards, &Tmp_edwards,
1790 alpha_edwards); EG(ret, err);
1791 dbg_ec_edwards_point_print("R", &Tmp_edwards);
1792 MUST_HAVE((r_len <= siglen), ret, err);
1793 /* Encode R and update */
1794 ret = eddsa_encode_point(&Tmp_edwards, alpha_edwards, &sig[0],
1795 r_len, key_type); EG(ret, err);
1796 #if defined(WITH_SIG_EDDSA25519)
1797 if(key_type == EDDSA25519CTX){
1798 /*
1799 * As per RFC8032, for EDDSA25519CTX the context
1800 * SHOULD NOT be empty
1801 */
1802 MUST_HAVE((adata != NULL), ret, err);
1803 ret = dom2(0, adata, adata_len, h, &h_ctx); EG(ret, err);
1804 }
1805 if(key_type == EDDSA25519PH){
1806 ret = dom2(1, adata, adata_len, h, &h_ctx); EG(ret, err);
1807 }
1808 #endif
1809 #if defined(WITH_SIG_EDDSA448)
1810 if(key_type == EDDSA448){
1811 ret = dom4(0, adata, adata_len, h, &h_ctx); EG(ret, err);
1812 }
1813 if(key_type == EDDSA448PH){
1814 ret = dom4(1, adata, adata_len, h, &h_ctx); EG(ret, err);
1815 }
1816 #endif
1817 /* Update the hash with the encoded R point */
1818 ret = h->hfunc_update(&h_ctx, &sig[0], r_len); EG(ret, err);
1819 /* Transfer the public key to Edwards */
1820 ret = prj_pt_shortw_to_aff_pt_edwards(pub_key_y, &crv_edwards, &Tmp_edwards,
1821 alpha_edwards); EG(ret, err);
1822 dbg_ec_edwards_point_print("A", &Tmp_edwards);
1823 MUST_HAVE((r_len <= sizeof(hash)), ret, err);
1824 /* Encode the public key */
1825 /* NOTE: we use the hash buffer as a temporary buffer */
1826 ret = eddsa_encode_point(&Tmp_edwards, alpha_edwards,
1827 hash, r_len, key_type); EG(ret, err);
1828 /* Update the hash with the encoded public key point */
1829 ret = h->hfunc_update(&h_ctx, hash, r_len); EG(ret, err);
1830 /* Update the hash with the message or its hash for the PH versions */
1831 if(use_message_pre_hash){
1832 ret = h->hfunc_update(&h_ctx, ph_hash, use_message_pre_hash_hsize); EG(ret, err);
1833 }
1834 else{
1835 ret = h->hfunc_update(&h_ctx, m, mlen); EG(ret, err);
1836 }
1837 /* Finalize the hash */
1838 ret = h->hfunc_finalize(&h_ctx, hash); EG(ret, err);
1839 dbg_buf_print("h(R || PubKey || PH(m))", hash, hsize);
1840 /* Import our resulting hash as an integer in S */
1841 ret = eddsa_decode_integer(&S, hash, hsize); EG(ret, err);
1842 ret = nn_mod(&S, &S, q); EG(ret, err);
1843 /* Extract the digest */
1844 hsize = sizeof(hash);
1845 ret = eddsa_get_digest_from_priv_key(hash, &hsize, priv_key); EG(ret, err);
1846 ret = eddsa_compute_s(&s, hash, hsize); EG(ret, err);
1847 ret = nn_mod(&s, &s, q); EG(ret, err);
1848 #ifdef USE_SIG_BLINDING
1849 /* If we use blinding, multiply by b */
1850 ret = nn_mod_mul(&S, &S, &b, q); EG(ret, err);
1851 #endif /* !USE_SIG_BLINDING */
1852 /* Multiply by the secret */
1853 ret = nn_mod_mul(&S, &S, &s, q); EG(ret, err);
1854 /* The secret is not needed anymore */
1855 nn_uninit(&s);
1856 /* Add to r */
1857 ret = nn_mod_add(&S, &S, &r, q); EG(ret, err);
1858 #ifdef USE_SIG_BLINDING
1859 /* Unblind the result */
1860 ret = nn_mod_mul(&S, &S, &binv, q); EG(ret, err);
1861 #endif /* !USE_SIG_BLINDING */
1862 /* Store our S in the context as an encoded buffer */
1863 MUST_HAVE((s_len <= (siglen - r_len)), ret, err);
1864 /* Encode the scalar s from the digest */
1865 ret = eddsa_encode_integer(&S, &sig[r_len], s_len);
1866
1867 err:
1868 /* Clean what remains on the stack */
1869 PTR_NULLIFY(priv_key);
1870 PTR_NULLIFY(pub_key);
1871 PTR_NULLIFY(G);
1872 PTR_NULLIFY(q);
1873 PTR_NULLIFY(shortw_curve);
1874 PTR_NULLIFY(alpha_montgomery);
1875 PTR_NULLIFY(gamma_montgomery);
1876 PTR_NULLIFY(alpha_edwards);
1877 PTR_NULLIFY(pub_key_y);
1878 PTR_NULLIFY(h);
1879 VAR_ZEROIFY(hsize);
1880 VAR_ZEROIFY(hash_size);
1881 VAR_ZEROIFY(use_message_pre_hash);
1882 VAR_ZEROIFY(use_message_pre_hash_hsize);
1883 VAR_ZEROIFY(r_len);
1884 VAR_ZEROIFY(s_len);
1885 VAR_ZEROIFY(blen);
1886 IGNORE_RET_VAL(local_memset(&h_ctx, 0, sizeof(h_ctx)));
1887 IGNORE_RET_VAL(local_memset(hash, 0, sizeof(hash)));
1888 IGNORE_RET_VAL(local_memset(ph_hash, 0, sizeof(ph_hash)));
1889
1890 prj_pt_uninit(&R);
1891 ec_edwards_crv_uninit(&crv_edwards);
1892 aff_pt_edwards_uninit(&Tmp_edwards);
1893 nn_uninit(&s);
1894 nn_uninit(&r);
1895 nn_uninit(&S);
1896
1897 #ifdef USE_SIG_BLINDING
1898 nn_uninit(&b);
1899 nn_uninit(&binv);
1900 #endif /* USE_SIG_BLINDING */
1901
1902 return ret;
1903 }
1904
1905 /******************************************************************************/
1906 /*
1907 * Generic *internal* EDDSA verification functions (init, update and finalize).
1908 *
1909 */
1910
1911 #define EDDSA_VERIFY_MAGIC ((word_t)(0x3298fe87e77151beULL))
1912 #define EDDSA_VERIFY_CHECK_INITIALIZED(A, ret, err) \
1913 MUST_HAVE((((void *)(A)) != NULL) && ((A)->magic == EDDSA_VERIFY_MAGIC), ret, err)
1914
1915 int _eddsa_verify_init(struct ec_verify_context *ctx, const u8 *sig, u8 siglen)
1916 {
1917 nn_src_t q;
1918 ec_edwards_crv crv_edwards;
1919 aff_pt_edwards R;
1920 prj_pt _Tmp;
1921 prj_pt_t _R;
1922 aff_pt_edwards A;
1923 nn *S;
1924 u8 buff[MAX_DIGEST_SIZE];
1925 int ret, iszero, cmp;
1926 u16 hsize;
1927 const ec_pub_key *pub_key;
1928 ec_shortw_crv_src_t shortw_curve;
1929 fp_src_t alpha_montgomery;
1930 fp_src_t gamma_montgomery;
1931 fp_src_t alpha_edwards;
1932 nn_src_t gen_cofactor;
1933 prj_pt_src_t pub_key_y;
1934 hash_context *h_ctx;
1935 hash_context *h_ctx_pre_hash;
1936 ec_alg_type key_type = UNKNOWN_ALG;
1937
1938 R.magic = crv_edwards.magic = _Tmp.magic = A.magic = WORD(0);
1939
1940 /* First, verify context has been initialized */
1941 ret = sig_verify_check_initialized(ctx); EG(ret, err);
1942 MUST_HAVE((sig != NULL), ret, err);
1943
1944 /* Zero init our local data */
1945 ret = local_memset(&A, 0, sizeof(aff_pt_edwards)); EG(ret, err);
1946 ret = local_memset(&crv_edwards, 0, sizeof(ec_edwards_crv)); EG(ret, err);
1947 ret = local_memset(buff, 0, sizeof(buff)); EG(ret, err);
1948 ret = local_memset(&R, 0, sizeof(R)); EG(ret, err);
1949 ret = local_memset(&_Tmp, 0, sizeof(_Tmp)); EG(ret, err);
1950
1951 /* Do some sanity checks on input params */
1952 ret = eddsa_pub_key_sanity_check(ctx->pub_key); EG(ret, err);
1953 MUST_HAVE((ctx->h != NULL) && (ctx->h->digest_size <= MAX_DIGEST_SIZE) && (ctx->h->block_size <= MAX_BLOCK_SIZE), ret, err);
1954
1955 /* Make things more readable */
1956 q = &(ctx->pub_key->params->ec_gen_order);
1957 _R = &(ctx->verify_data.eddsa._R);
1958 S = &(ctx->verify_data.eddsa.S);
1959 hsize = ctx->h->digest_size;
1960
1961 pub_key = ctx->pub_key;
1962 shortw_curve = &(pub_key->params->ec_curve);
1963 alpha_montgomery = &(pub_key->params->ec_alpha_montgomery);
1964 gamma_montgomery = &(pub_key->params->ec_gamma_montgomery);
1965 alpha_edwards = &(pub_key->params->ec_alpha_edwards);
1966 gen_cofactor = &(pub_key->params->ec_gen_cofactor);
1967 pub_key_y = &(pub_key->y);
1968 key_type = pub_key->key_type;
1969 h_ctx = &(ctx->verify_data.eddsa.h_ctx);
1970 h_ctx_pre_hash = &(ctx->verify_data.eddsa.h_ctx_pre_hash);
1971
1972 /* Sanity check on hash types */
1973 MUST_HAVE((ctx->h->type == get_eddsa_hash_type(key_type)), ret, err);
1974
1975 /* Check given signature length is the expected one */
1976 MUST_HAVE((siglen == EDDSA_SIGLEN(hsize)), ret, err);
1977 MUST_HAVE((siglen == (EDDSA_R_LEN(hsize) + EDDSA_S_LEN(hsize))), ret, err);
1978
1979 /* Initialize the hash context */
1980 /* Since we call a callback, sanity check our mapping */
1981 ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err);
1982 ret = ctx->h->hfunc_init(h_ctx); EG(ret, err);
1983 ret = ctx->h->hfunc_init(h_ctx_pre_hash); EG(ret, err);
1984 #if defined(WITH_SIG_EDDSA25519)
1985 if(key_type == EDDSA25519CTX){
1986 /* As per RFC8032, for EDDSA25519CTX the context SHOULD NOT be empty */
1987 MUST_HAVE((ctx->adata != NULL), ret, err);
1988 ret = dom2(0, ctx->adata, ctx->adata_len, ctx->h, h_ctx); EG(ret, err);
1989 }
1990 if(key_type == EDDSA25519PH){
1991 ret = dom2(1, ctx->adata, ctx->adata_len, ctx->h, h_ctx); EG(ret, err);
1992 }
1993 #endif
1994 #if defined(WITH_SIG_EDDSA448)
1995 if(key_type == EDDSA448){
1996 ret = dom4(0, ctx->adata, ctx->adata_len, ctx->h, h_ctx); EG(ret, err);
1997 }
1998 if(key_type == EDDSA448PH){
1999 ret = dom4(1, ctx->adata, ctx->adata_len, ctx->h, h_ctx); EG(ret, err);
2000 }
2001 #endif
2002 /* Import R and S values from signature buffer */
2003 /*******************************/
2004 /* Import R as an Edwards point */
2005 ret = curve_shortw_to_edwards(shortw_curve, &crv_edwards, alpha_montgomery,
2006 gamma_montgomery, alpha_edwards); EG(ret, err);
2007 /* NOTE: non canonical R are checked and rejected here */
2008 ret = eddsa_decode_point(&R, &crv_edwards, alpha_edwards, &sig[0],
2009 EDDSA_R_LEN(hsize), key_type); EG(ret, err);
2010 dbg_ec_edwards_point_print("R", &R);
2011 /* Transfer our public point R to Weierstrass */
2012 ret = aff_pt_edwards_to_prj_pt_shortw(&R, shortw_curve, _R, alpha_edwards); EG(ret, err);
2013 /* Update the hash with the encoded R */
2014 ret = ctx->h->hfunc_update(h_ctx, &sig[0], EDDSA_R_LEN(hsize)); EG(ret, err);
2015
2016 /*******************************/
2017 /* Import S as an integer */
2018 ret = eddsa_decode_integer(S, &sig[EDDSA_R_LEN(hsize)], EDDSA_S_LEN(hsize)); EG(ret, err);
2019 /* Reject S if it is not reduced modulo q */
2020 ret = nn_cmp(S, q, &cmp); EG(ret, err);
2021 MUST_HAVE((cmp < 0), ret, err);
2022 dbg_nn_print("S", S);
2023
2024 /*******************************/
2025 /* Encode the public key
2026 * NOTE: since we deal with a public key transfered to Weierstrass,
2027 * encoding checking has been handled elsewhere.
2028 */
2029 /* Reject the signature if the public key is one of small order points.
2030 * We multiply by the cofactor: since this is a public verification,
2031 * we use a basic double and add algorithm.
2032 */
2033 ret = _prj_pt_unprotected_mult(&_Tmp, gen_cofactor, pub_key_y); EG(ret, err);
2034 /* Reject the signature if we have point at infinity here as this means
2035 * that the public key is of small order.
2036 */
2037 ret = prj_pt_iszero(&_Tmp, &iszero); EG(ret, err);
2038 MUST_HAVE((!iszero), ret, err);
2039
2040 /* Transfer the public key to Edwards */
2041 ret = prj_pt_shortw_to_aff_pt_edwards(pub_key_y, &crv_edwards, &A, alpha_edwards); EG(ret, err);
2042 dbg_ec_edwards_point_print("A", &A);
2043 MUST_HAVE((EDDSA_R_LEN(hsize) <= sizeof(buff)), ret, err);
2044 /* NOTE: we use the hash buffer as a temporary buffer */
2045 ret = eddsa_encode_point(&A, alpha_edwards, buff, EDDSA_R_LEN(hsize), key_type); EG(ret, err);
2046
2047 /* Update the hash with the encoded public key */
2048 ret = ctx->h->hfunc_update(h_ctx, buff, EDDSA_R_LEN(hsize)); EG(ret, err);
2049
2050 /* Context magic set */
2051 ctx->verify_data.eddsa.magic = EDDSA_VERIFY_MAGIC;
2052
2053 err:
2054 PTR_NULLIFY(q);
2055 PTR_NULLIFY(_R);
2056 PTR_NULLIFY(S);
2057 PTR_NULLIFY(pub_key);
2058 PTR_NULLIFY(shortw_curve);
2059 PTR_NULLIFY(alpha_montgomery);
2060 PTR_NULLIFY(gamma_montgomery);
2061 PTR_NULLIFY(alpha_edwards);
2062 PTR_NULLIFY(gen_cofactor);
2063 PTR_NULLIFY(pub_key_y);
2064
2065 ec_edwards_crv_uninit(&crv_edwards);
2066 aff_pt_edwards_uninit(&A);
2067 aff_pt_edwards_uninit(&R);
2068 prj_pt_uninit(&_Tmp);
2069
2070 return ret;
2071 }
2072
2073 int _eddsa_verify_update(struct ec_verify_context *ctx,
2074 const u8 *chunk, u32 chunklen)
2075 {
2076 int ret;
2077 ec_alg_type key_type = UNKNOWN_ALG;
2078 u8 use_message_pre_hash = 0;
2079 hash_context *h_ctx;
2080 hash_context *h_ctx_pre_hash;
2081
2082 /*
2083 * First, verify context has been initialized and public
2084 * part too. This guarantees the context is an EDDSA
2085 * verification one and we do not update() or finalize()
2086 * before init().
2087 */
2088 ret = sig_verify_check_initialized(ctx); EG(ret, err);
2089 EDDSA_VERIFY_CHECK_INITIALIZED(&(ctx->verify_data.eddsa), ret, err);
2090
2091 key_type = ctx->pub_key->key_type;
2092 h_ctx = &(ctx->verify_data.eddsa.h_ctx);
2093 h_ctx_pre_hash = &(ctx->verify_data.eddsa.h_ctx_pre_hash);
2094
2095 /* Sanity check on hash types */
2096 MUST_HAVE(ctx->h->type == get_eddsa_hash_type(key_type), ret, err);
2097
2098 /* Do we use the raw message or its PH(M) hashed version? */
2099 #if defined(WITH_SIG_EDDSA25519)
2100 if(key_type == EDDSA25519PH){
2101 use_message_pre_hash = 1;
2102 }
2103 #endif
2104 #if defined(WITH_SIG_EDDSA448)
2105 if(key_type == EDDSA448PH){
2106 use_message_pre_hash = 1;
2107 }
2108 #endif
2109 /* 2. Compute h = H(m) */
2110 /* Since we call a callback, sanity check our mapping */
2111 ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err);
2112 if(use_message_pre_hash == 1){
2113 /* In PH mode, update the dedicated hash context */
2114 ret = ctx->h->hfunc_update(h_ctx_pre_hash,
2115 chunk, chunklen); EG(ret, err);
2116 }
2117 else{
2118 /* In normal mode, update the nominal hash context */
2119 ret = ctx->h->hfunc_update(h_ctx, chunk, chunklen); EG(ret, err);
2120 }
2121
2122 err:
2123 VAR_ZEROIFY(use_message_pre_hash);
2124
2125 return ret;
2126 }
2127
2128 int _eddsa_verify_finalize(struct ec_verify_context *ctx)
2129 {
2130 prj_pt_src_t G, _R, A;
2131 prj_pt _Tmp1, _Tmp2;
2132 nn_src_t q, S;
2133 nn h;
2134 u16 hsize;
2135 u8 hash[MAX_DIGEST_SIZE];
2136 nn_src_t gen_cofactor;
2137 int ret, iszero, cmp;
2138 ec_alg_type key_type = UNKNOWN_ALG;
2139 u8 use_message_pre_hash = 0;
2140 u16 use_message_pre_hash_hsize = 0;
2141 hash_context *h_ctx;
2142 hash_context *h_ctx_pre_hash;
2143
2144 _Tmp1.magic = _Tmp2.magic = h.magic = WORD(0);
2145
2146 /*
2147 * First, verify context has been initialized and public
2148 * part too. This guarantees the context is an EDDSA
2149 * verification one and we do not finalize() before init().
2150 */
2151 ret = sig_verify_check_initialized(ctx); EG(ret, err);
2152 EDDSA_VERIFY_CHECK_INITIALIZED(&(ctx->verify_data.eddsa), ret, err);
2153
2154 /* Zero init points */
2155 ret = local_memset(&_Tmp1, 0, sizeof(prj_pt)); EG(ret, err);
2156 ret = local_memset(&_Tmp2, 0, sizeof(prj_pt)); EG(ret, err);
2157 ret = local_memset(hash, 0, sizeof(hash)); EG(ret, err);
2158
2159 /* Make things more readable */
2160 G = &(ctx->pub_key->params->ec_gen);
2161 A = &(ctx->pub_key->y);
2162 q = &(ctx->pub_key->params->ec_gen_order);
2163 hsize = ctx->h->digest_size;
2164 S = &(ctx->verify_data.eddsa.S);
2165 _R = &(ctx->verify_data.eddsa._R);
2166 gen_cofactor = &(ctx->pub_key->params->ec_gen_cofactor);
2167 key_type = ctx->pub_key->key_type;
2168 h_ctx = &(ctx->verify_data.eddsa.h_ctx);
2169 h_ctx_pre_hash = &(ctx->verify_data.eddsa.h_ctx_pre_hash);
2170
2171 /* Sanity check on hash types */
2172 MUST_HAVE((ctx->h->type == get_eddsa_hash_type(key_type)), ret, err);
2173
2174 /* Do we use the raw message or its PH(M) hashed version? */
2175 #if defined(WITH_SIG_EDDSA25519)
2176 if(key_type == EDDSA25519PH){
2177 use_message_pre_hash = 1;
2178 use_message_pre_hash_hsize = hsize;
2179 }
2180 #endif
2181 #if defined(WITH_SIG_EDDSA448)
2182 if(key_type == EDDSA448PH){
2183 use_message_pre_hash = 1;
2184 /* NOTE: as per RFC8032, EDDSA448PH uses
2185 * SHAKE256 with 64 bytes output.
2186 */
2187 use_message_pre_hash_hsize = 64;
2188 }
2189 #endif
2190
2191 /* Reject S if it is not reduced modulo q */
2192 ret = nn_cmp(S, q, &cmp); EG(ret, err);
2193 MUST_HAVE((cmp < 0), ret, err);
2194
2195 MUST_HAVE((hsize <= sizeof(hash)), ret, err);
2196
2197 /* 2. Finish our computation of h = H(R || A || M) */
2198 /* Since we call a callback, sanity check our mapping */
2199 ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err);
2200 /* Update the hash with the message or its hash for the PH versions */
2201 if(use_message_pre_hash == 1){
2202 ret = ctx->h->hfunc_finalize(h_ctx_pre_hash, hash); EG(ret, err);
2203 MUST_HAVE((use_message_pre_hash_hsize <= hsize), ret, err);
2204 ret = ctx->h->hfunc_update(h_ctx, hash, use_message_pre_hash_hsize); EG(ret, err);
2205 }
2206 ret = ctx->h->hfunc_finalize(h_ctx, hash); EG(ret, err);
2207 dbg_buf_print("hash = H(R || A || PH(M))", hash, hsize);
2208
2209 /* 3. Import our hash as a NN and reduce it modulo q */
2210 ret = eddsa_decode_integer(&h, hash, hsize); EG(ret, err);
2211 ret = nn_mod(&h, &h, q); EG(ret, err);
2212 dbg_nn_print("h = ", &h);
2213
2214 #if defined(WITH_SIG_EDDSA448)
2215 if((key_type == EDDSA448) || (key_type == EDDSA448PH)){
2216 /* When dealing with EDDSA448, because of our 4-isogeny between Edwars448 and Ed448
2217 * mapping base point to four times base point, we actually multiply our public key by 4 here
2218 * to be inline with the other computations (the public key stored in Weierstrass )
2219 */
2220 ret = nn_lshift(&h, &h, 2); EG(ret, err);
2221 ret = nn_mod(&h, &h, q); EG(ret, err);
2222 }
2223 #endif
2224 /* 4. Compute (S * G) - R - (h * A) */
2225 ret = prj_pt_mul(&_Tmp1, S, G); EG(ret, err);
2226 ret = prj_pt_neg(&_Tmp2, _R); EG(ret, err);
2227 ret = prj_pt_add(&_Tmp1, &_Tmp1, &_Tmp2); EG(ret, err);
2228 ret = prj_pt_mul(&_Tmp2, &h, A); EG(ret, err);
2229 ret = prj_pt_neg(&_Tmp2, &_Tmp2); EG(ret, err);
2230 ret = prj_pt_add(&_Tmp1, &_Tmp1, &_Tmp2); EG(ret, err);
2231
2232 /* 5. We use cofactored multiplication, so multiply by the cofactor:
2233 * since this is a public verification, we use a basic double and add
2234 * algorithm.
2235 */
2236 ret = _prj_pt_unprotected_mult(&_Tmp2, gen_cofactor, &_Tmp1); EG(ret, err);
2237
2238 /* Reject the signature if we do not have point at infinity here */
2239 ret = prj_pt_iszero(&_Tmp2, &iszero); EG(ret, err);
2240 ret = iszero ? 0 : -1;
2241
2242 err:
2243 /*
2244 * We can now clear data part of the context. This will clear
2245 * magic and avoid further reuse of the whole context.
2246 */
2247 if(ctx != NULL){
2248 IGNORE_RET_VAL(local_memset(&(ctx->verify_data.eddsa), 0, sizeof(eddsa_verify_data)));
2249 }
2250
2251 /* Clean what remains on the stack */
2252 PTR_NULLIFY(G);
2253 PTR_NULLIFY(A);
2254 PTR_NULLIFY(q);
2255 PTR_NULLIFY(S);
2256 PTR_NULLIFY(_R);
2257 PTR_NULLIFY(gen_cofactor);
2258 VAR_ZEROIFY(hsize);
2259 VAR_ZEROIFY(use_message_pre_hash);
2260 VAR_ZEROIFY(use_message_pre_hash_hsize);
2261
2262 nn_uninit(&h);
2263 prj_pt_uninit(&_Tmp1);
2264 prj_pt_uninit(&_Tmp2);
2265
2266 return ret;
2267 }
2268
2269 /* Batch verification function:
2270 * This function takes multiple signatures/messages/public keys, and
2271 * checks all the signatures.
2272 *
2273 * This returns 0 if *all* the signatures are correct, and -1 if at least
2274 * one signature is not correct.
2275 *
2276 * NOTE: the "no_memory" version is not optimized and straightforwardly
2277 * checks for the signature using naive sums. See below for an optimized
2278 * Bos-Coster version (but requiring additional memory to work).
2279 *
2280 */
2281 ATTRIBUTE_WARN_UNUSED_RET static int _eddsa_verify_batch_no_memory(const u8 **s, const u8 *s_len, const ec_pub_key **pub_keys,
2282 const u8 **m, const u32 *m_len, u32 num, ec_alg_type sig_type,
2283 hash_alg_type hash_type, const u8 **adata, const u16 *adata_len)
2284 {
2285 nn_src_t q = NULL;
2286 ec_edwards_crv crv_edwards;
2287 aff_pt_edwards R, A;
2288 prj_pt_src_t G = NULL;
2289 prj_pt _Tmp, _R_sum, _A_sum;
2290 nn S, S_sum, z, h;
2291 u8 hash[MAX_DIGEST_SIZE];
2292 int ret, iszero, cmp;
2293 u16 hsize;
2294 const ec_pub_key *pub_key, *pub_key0;
2295 ec_shortw_crv_src_t shortw_curve;
2296 fp_src_t alpha_montgomery;
2297 fp_src_t gamma_montgomery;
2298 fp_src_t alpha_edwards;
2299 nn_src_t gen_cofactor = NULL;
2300 prj_pt_src_t pub_key_y;
2301 hash_context h_ctx;
2302 hash_context h_ctx_pre_hash;
2303 u8 use_message_pre_hash = 0;
2304 u16 use_message_pre_hash_hsize = 0;
2305 const hash_mapping *hm;
2306 ec_alg_type key_type = UNKNOWN_ALG;
2307 u32 i;
2308
2309 R.magic = S.magic = S_sum.magic = crv_edwards.magic = WORD(0);
2310 _Tmp.magic = _R_sum.magic = _A_sum.magic = WORD(0);
2311 z.magic = h.magic = WORD(0);
2312
2313 /* First, some sanity checks */
2314 MUST_HAVE((s != NULL) && (pub_keys != NULL) && (m != NULL) && (adata != NULL), ret, err);
2315 /* We need at least one element in our batch data bags */
2316 MUST_HAVE((num > 0), ret, err);
2317
2318
2319 /* Zero init our local data */
2320 ret = local_memset(&crv_edwards, 0, sizeof(ec_edwards_crv)); EG(ret, err);
2321 ret = local_memset(hash, 0, sizeof(hash)); EG(ret, err);
2322 ret = local_memset(&A, 0, sizeof(aff_pt_edwards)); EG(ret, err);
2323 ret = local_memset(&R, 0, sizeof(aff_pt_edwards)); EG(ret, err);
2324 ret = local_memset(&_R_sum, 0, sizeof(prj_pt)); EG(ret, err);
2325 ret = local_memset(&_A_sum, 0, sizeof(prj_pt)); EG(ret, err);
2326 ret = local_memset(&_Tmp, 0, sizeof(prj_pt)); EG(ret, err);
2327
2328 pub_key0 = pub_keys[0];
2329 MUST_HAVE((pub_key0 != NULL), ret, err);
2330
2331 /* Get our hash mapping */
2332 ret = get_hash_by_type(hash_type, &hm); EG(ret, err);
2333 hsize = hm->digest_size;
2334 MUST_HAVE((hm != NULL), ret, err);
2335
2336 /* Do we use the raw message or its PH(M) hashed version? */
2337 #if defined(WITH_SIG_EDDSA25519)
2338 if(sig_type == EDDSA25519PH){
2339 use_message_pre_hash = 1;
2340 use_message_pre_hash_hsize = hsize;
2341 }
2342 #endif
2343 #if defined(WITH_SIG_EDDSA448)
2344 if(sig_type == EDDSA448PH){
2345 use_message_pre_hash = 1;
2346 /* NOTE: as per RFC8032, EDDSA448PH uses
2347 * SHAKE256 with 64 bytes output.
2348 */
2349 use_message_pre_hash_hsize = 64;
2350 }
2351 #endif
2352
2353 for(i = 0; i < num; i++){
2354 u8 siglen;
2355 const u8 *sig = NULL;
2356
2357 ret = eddsa_pub_key_sanity_check(pub_keys[i]); EG(ret, err);
2358
2359 /* Make things more readable */
2360 pub_key = pub_keys[i];
2361
2362 /* Sanity check that all our public keys have the same parameters */
2363 MUST_HAVE((pub_key->params) == (pub_key0->params), ret, err);
2364
2365 q = &(pub_key->params->ec_gen_order);
2366 shortw_curve = &(pub_key->params->ec_curve);
2367 alpha_montgomery = &(pub_key->params->ec_alpha_montgomery);
2368 gamma_montgomery = &(pub_key->params->ec_gamma_montgomery);
2369 alpha_edwards = &(pub_key->params->ec_alpha_edwards);
2370 gen_cofactor = &(pub_key->params->ec_gen_cofactor);
2371 pub_key_y = &(pub_key->y);
2372 key_type = pub_key->key_type;
2373 G = &(pub_key->params->ec_gen);
2374
2375 /* Check the key type versus the algorithm */
2376 MUST_HAVE((key_type == sig_type), ret, err);
2377
2378 if(i == 0){
2379 /* Initialize our sums to zero/point at infinity */
2380 ret = nn_init(&S_sum, 0); EG(ret, err);
2381 ret = prj_pt_init(&_R_sum, shortw_curve); EG(ret, err);
2382 ret = prj_pt_zero(&_R_sum); EG(ret, err);
2383 ret = prj_pt_init(&_A_sum, shortw_curve); EG(ret, err);
2384 ret = prj_pt_zero(&_A_sum); EG(ret, err);
2385 ret = nn_init(&z, 0); EG(ret, err);
2386 ret = nn_init(&h, 0); EG(ret, err);
2387 }
2388
2389 gen_z_again:
2390 /* Get a random z for randomizing the linear combination */
2391 ret = nn_get_random_len(&z, (hsize / 4)); EG(ret, err);
2392 ret = nn_iszero(&z, &iszero); EG(ret, err);
2393 if(iszero){
2394 goto gen_z_again;
2395 }
2396
2397 /* Sanity check on hash types */
2398 MUST_HAVE((hash_type == get_eddsa_hash_type(key_type)), ret, err);
2399
2400 /* Check given signature length is the expected one */
2401 siglen = s_len[i];
2402 sig = s[i];
2403 MUST_HAVE((siglen == EDDSA_SIGLEN(hsize)), ret, err);
2404 MUST_HAVE((siglen == (EDDSA_R_LEN(hsize) + EDDSA_S_LEN(hsize))), ret, err);
2405
2406 /* Initialize the hash context */
2407 /* Since we call a callback, sanity check our mapping */
2408 ret = hash_mapping_callbacks_sanity_check(hm); EG(ret, err);
2409 ret = hm->hfunc_init(&h_ctx); EG(ret, err);
2410 ret = hm->hfunc_init(&h_ctx_pre_hash); EG(ret, err);
2411 #if defined(WITH_SIG_EDDSA25519)
2412 if(key_type == EDDSA25519CTX){
2413 /* As per RFC8032, for EDDSA25519CTX the context SHOULD NOT be empty */
2414 MUST_HAVE((adata[i] != NULL), ret, err);
2415 ret = dom2(0, adata[i], adata_len[i], hm, &h_ctx); EG(ret, err);
2416 }
2417 if(key_type == EDDSA25519PH){
2418 ret = dom2(1, adata[i], adata_len[i], hm, &h_ctx); EG(ret, err);
2419 }
2420 #endif
2421 #if defined(WITH_SIG_EDDSA448)
2422 if(key_type == EDDSA448){
2423 ret = dom4(0, adata[i], adata_len[i], hm, &h_ctx); EG(ret, err);
2424 }
2425 if(key_type == EDDSA448PH){
2426 ret = dom4(1, adata[i], adata_len[i], hm, &h_ctx); EG(ret, err);
2427 }
2428 #endif
2429 /* Import R and S values from signature buffer */
2430 /*******************************/
2431 /* Import R as an Edwards point */
2432 ret = curve_shortw_to_edwards(shortw_curve, &crv_edwards, alpha_montgomery,
2433 gamma_montgomery, alpha_edwards); EG(ret, err);
2434 /* NOTE: non canonical R are checked and rejected here */
2435 ret = eddsa_decode_point(&R, &crv_edwards, alpha_edwards, &sig[0],
2436 EDDSA_R_LEN(hsize), key_type); EG(ret, err);
2437 dbg_ec_edwards_point_print("R", &R);
2438 /* Transfer our public point R to Weierstrass */
2439 ret = aff_pt_edwards_to_prj_pt_shortw(&R, shortw_curve, &_Tmp, alpha_edwards); EG(ret, err);
2440 /* Update the hash with the encoded R */
2441 ret = hm->hfunc_update(&h_ctx, &sig[0], EDDSA_R_LEN(hsize)); EG(ret, err);
2442 /* Multiply by z.
2443 */
2444 ret = _prj_pt_unprotected_mult(&_Tmp, &z, &_Tmp); EG(ret, err);
2445 /* Add to the sum */
2446 ret = prj_pt_add(&_R_sum, &_R_sum, &_Tmp); EG(ret, err);
2447
2448 /*******************************/
2449 /* Import S as an integer */
2450 ret = eddsa_decode_integer(&S, &sig[EDDSA_R_LEN(hsize)], EDDSA_S_LEN(hsize)); EG(ret, err);
2451 /* Reject S if it is not reduced modulo q */
2452 ret = nn_cmp(&S, q, &cmp); EG(ret, err);
2453 MUST_HAVE((cmp < 0), ret, err);
2454 dbg_nn_print("S", &S);
2455
2456 /* Add z S to the sum */
2457 ret = nn_mul(&S, &S, &z); EG(ret, err);
2458 ret = nn_mod(&S, &S, q); EG(ret, err);
2459 ret = nn_mod_add(&S_sum, &S_sum, &S, q); EG(ret, err);
2460
2461 /*******************************/
2462 /* Encode the public key
2463 * NOTE: since we deal with a public key transfered to Weierstrass,
2464 * encoding checking has been handled elsewhere.
2465 */
2466 /* Reject the signature if the public key is one of small order points.
2467 * We multiply by the cofactor: since this is a public verification,
2468 * we use a basic double and add algorithm.
2469 */
2470 ret = _prj_pt_unprotected_mult(&_Tmp, gen_cofactor, pub_key_y); EG(ret, err);
2471 /* Reject the signature if we have point at infinity here as this means
2472 * that the public key is of small order.
2473 */
2474 ret = prj_pt_iszero(&_Tmp, &iszero); EG(ret, err);
2475 MUST_HAVE((!iszero), ret, err);
2476
2477 /* Transfer the public key to Edwards */
2478 ret = prj_pt_shortw_to_aff_pt_edwards(pub_key_y, &crv_edwards, &A, alpha_edwards); EG(ret, err);
2479 dbg_ec_edwards_point_print("A", &A);
2480 MUST_HAVE((EDDSA_R_LEN(hsize) <= sizeof(hash)), ret, err);
2481 /* NOTE: we use the hash buffer as a temporary buffer */
2482 ret = eddsa_encode_point(&A, alpha_edwards, hash, EDDSA_R_LEN(hsize), key_type); EG(ret, err);
2483
2484 /* Update the hash with the encoded public key */
2485 ret = hm->hfunc_update(&h_ctx, hash, EDDSA_R_LEN(hsize)); EG(ret, err);
2486 /* Finish our computation of h = H(R || A || M) */
2487 /* Update the hash with the message or its hash for the PH versions */
2488 if(use_message_pre_hash == 1){
2489 ret = hm->hfunc_update(&h_ctx_pre_hash, m[i], m_len[i]); EG(ret, err);
2490 ret = hm->hfunc_finalize(&h_ctx_pre_hash, hash); EG(ret, err);
2491 MUST_HAVE((use_message_pre_hash_hsize <= hsize), ret, err);
2492 ret = hm->hfunc_update(&h_ctx, hash, use_message_pre_hash_hsize); EG(ret, err);
2493 }
2494 else{
2495 ret = hm->hfunc_update(&h_ctx, m[i], m_len[i]); EG(ret, err);
2496 }
2497 ret = hm->hfunc_finalize(&h_ctx, hash); EG(ret, err);
2498 dbg_buf_print("hash = H(R || A || PH(M))", hash, hsize);
2499
2500 /* Import our hash as a NN and reduce it modulo q */
2501 ret = eddsa_decode_integer(&h, hash, hsize); EG(ret, err);
2502 ret = nn_mod(&h, &h, q); EG(ret, err);
2503 dbg_nn_print("h = ", &h);
2504 #if defined(WITH_SIG_EDDSA448)
2505 if((key_type == EDDSA448) || (key_type == EDDSA448PH)){
2506 /* When dealing with EDDSA448, because of our 4-isogeny between Edwars448 and Ed448
2507 * mapping base point to four times base point, we actually multiply our public key by 4 here
2508 * to be inline with the other computations (the public key stored in Weierstrass )
2509 */
2510 ret = nn_lshift(&h, &h, 2); EG(ret, err);
2511 ret = nn_mod(&h, &h, q); EG(ret, err);
2512 }
2513 #endif
2514
2515 /* Multiply by (z * h) mod q.
2516 * NOTE: we use unprotected scalar multiplication since this is a
2517 * public operation.
2518 */
2519 ret = nn_mul(&z, &z, &h); EG(ret, err);
2520 ret = nn_mod(&z, &z, q); EG(ret, err);
2521 ret = _prj_pt_unprotected_mult(&_Tmp, &z, &_Tmp); EG(ret, err);
2522 /* Add to the sum */
2523 ret = prj_pt_add(&_A_sum, &_A_sum, &_Tmp); EG(ret, err);
2524 }
2525
2526 /* Sanity check */
2527 MUST_HAVE((gen_cofactor != NULL) && (q != NULL) && (G != NULL), ret, err);
2528
2529 /* Multiply the S sum by the cofactor */
2530 ret = nn_mul(&S_sum, &S_sum, gen_cofactor); EG(ret, err);
2531 ret = nn_mod(&S_sum, &S_sum, q); EG(ret, err);
2532 /* Negate it. NOTE: -x mod q is (q - x) mod q, i.e. (q - x) when x is reduced */
2533 ret = nn_mod_neg(&S_sum, &S_sum, q); EG(ret, err);
2534 /* Multiply this by the generator */
2535 ret = _prj_pt_unprotected_mult(&_Tmp, &S_sum, G); EG(ret, err);
2536
2537 /* Multiply the R sum by the cofactor */
2538 ret = _prj_pt_unprotected_mult(&_R_sum, gen_cofactor, &_R_sum); EG(ret, err);
2539
2540 /* Now add the three sums */
2541 ret = prj_pt_add(&_Tmp, &_Tmp, &_A_sum);
2542 ret = prj_pt_add(&_Tmp, &_Tmp, &_R_sum);
2543
2544 /* Reject the signature if we do not have point at infinity here */
2545 ret = prj_pt_iszero(&_Tmp, &iszero); EG(ret, err);
2546 ret = iszero ? 0 : -1;
2547
2548 err:
2549 PTR_NULLIFY(q);
2550 PTR_NULLIFY(pub_key);
2551 PTR_NULLIFY(pub_key0);
2552 PTR_NULLIFY(shortw_curve);
2553 PTR_NULLIFY(alpha_montgomery);
2554 PTR_NULLIFY(gamma_montgomery);
2555 PTR_NULLIFY(alpha_edwards);
2556 PTR_NULLIFY(gen_cofactor);
2557 PTR_NULLIFY(pub_key_y);
2558 PTR_NULLIFY(G);
2559
2560 ec_edwards_crv_uninit(&crv_edwards);
2561 aff_pt_edwards_uninit(&A);
2562 aff_pt_edwards_uninit(&R);
2563 prj_pt_uninit(&_R_sum);
2564 prj_pt_uninit(&_A_sum);
2565 prj_pt_uninit(&_Tmp);
2566 nn_uninit(&S);
2567 nn_uninit(&S_sum);
2568 nn_uninit(&z);
2569 nn_uninit(&h);
2570
2571 return ret;
2572
2573 }
2574
2575 /*
2576 * The following batch verification uses the Bos-Coster algorithm, presented e.g. in
2577 * https://ed25519.cr.yp.to/ed25519-20110705.pdf
2578 *
2579 * The Bos-Coster algorithm allows to optimize a sum of scalar multiplications using
2580 * addition chains.
2581 *
2582 */
2583 ATTRIBUTE_WARN_UNUSED_RET static int _eddsa_verify_batch(const u8 **s, const u8 *s_len, const ec_pub_key **pub_keys,
2584 const u8 **m, const u32 *m_len, u32 num, ec_alg_type sig_type,
2585 hash_alg_type hash_type, const u8 **adata, const u16 *adata_len,
2586 verify_batch_scratch_pad *scratch_pad_area, u32 *scratch_pad_area_len)
2587 {
2588 nn_src_t q = NULL;
2589 ec_edwards_crv crv_edwards;
2590 aff_pt_edwards R, A;
2591 prj_pt_src_t G = NULL;
2592 nn S, z;
2593 u8 hash[MAX_DIGEST_SIZE];
2594 int ret, iszero, cmp;
2595 u16 hsize;
2596 const ec_pub_key *pub_key, *pub_key0;
2597 ec_shortw_crv_src_t shortw_curve;
2598 fp_src_t alpha_montgomery;
2599 fp_src_t gamma_montgomery;
2600 fp_src_t alpha_edwards;
2601 nn_src_t gen_cofactor = NULL;
2602 prj_pt_src_t pub_key_y;
2603 hash_context h_ctx;
2604 hash_context h_ctx_pre_hash;
2605 u8 use_message_pre_hash = 0;
2606 u16 use_message_pre_hash_hsize = 0;
2607 const hash_mapping *hm;
2608 ec_alg_type key_type = UNKNOWN_ALG;
2609 /* NN numbers and points pointers */
2610 verify_batch_scratch_pad *elements = scratch_pad_area;
2611 u32 i;
2612 u64 expected_len;
2613 bitcnt_t q_bit_len = 0;
2614
2615 S.magic = z.magic = crv_edwards.magic = WORD(0);
2616
2617 /* First, some sanity checks */
2618 MUST_HAVE((s != NULL) && (pub_keys != NULL) && (m != NULL) && (adata != NULL), ret, err);
2619 MUST_HAVE((scratch_pad_area_len != NULL), ret, err);
2620 MUST_HAVE(((2 * num) >= num), ret, err);
2621 MUST_HAVE(((2 * num) + 1) >= num, ret, err);
2622
2623 /* In oder to apply the algorithm, we must have at least two
2624 * elements to verify. If this is not the case, we fallback to
2625 * the regular "no memory" version.
2626 */
2627 if(num <= 1){
2628 if(scratch_pad_area == NULL){
2629 /* We do not require any memory in this case */
2630 (*scratch_pad_area_len) = 0;
2631 ret = 0;
2632 goto err;
2633 }
2634 else{
2635 ret = _eddsa_verify_batch_no_memory(s, s_len, pub_keys, m, m_len, num, sig_type,
2636 hash_type, adata, adata_len);
2637 goto err;
2638 }
2639 }
2640
2641 expected_len = ((2 * num) + 1) * sizeof(verify_batch_scratch_pad);
2642 MUST_HAVE((expected_len < 0xffffffff), ret, err);
2643
2644 if(scratch_pad_area == NULL){
2645 /* Return the needed size: we need to keep track of (2 * num) + 1 NN numbers
2646 * and (2 * num) + 1 projective points, plus (2 * num) + 1 indices
2647 */
2648 (*scratch_pad_area_len) = (u32)expected_len;
2649 ret = 0;
2650 goto err;
2651 }
2652 else{
2653 MUST_HAVE((*scratch_pad_area_len) >= expected_len, ret, err);
2654 }
2655
2656 /********************************************/
2657 /****** Initialize elements *****************/
2658 /* Zero init our local data */
2659 ret = local_memset(&crv_edwards, 0, sizeof(ec_edwards_crv)); EG(ret, err);
2660 ret = local_memset(hash, 0, sizeof(hash)); EG(ret, err);
2661 ret = local_memset(&A, 0, sizeof(aff_pt_edwards)); EG(ret, err);
2662 ret = local_memset(&R, 0, sizeof(aff_pt_edwards)); EG(ret, err);
2663
2664 pub_key0 = pub_keys[0];
2665 MUST_HAVE((pub_key0 != NULL), ret, err);
2666
2667 /* Get our hash mapping */
2668 ret = get_hash_by_type(hash_type, &hm); EG(ret, err);
2669 hsize = hm->digest_size;
2670 MUST_HAVE((hm != NULL), ret, err);
2671
2672 /* Do we use the raw message or its PH(M) hashed version? */
2673 #if defined(WITH_SIG_EDDSA25519)
2674 if(sig_type == EDDSA25519PH){
2675 use_message_pre_hash = 1;
2676 use_message_pre_hash_hsize = hsize;
2677 }
2678 #endif
2679 #if defined(WITH_SIG_EDDSA448)
2680 if(sig_type == EDDSA448PH){
2681 use_message_pre_hash = 1;
2682 /* NOTE: as per RFC8032, EDDSA448PH uses
2683 * SHAKE256 with 64 bytes output.
2684 */
2685 use_message_pre_hash_hsize = 64;
2686 }
2687 #endif
2688
2689 /* Compute our original numbers and points */
2690 MUST_HAVE((num >= 1), ret, err);
2691 for(i = 0; i < num; i++){
2692 u8 siglen;
2693 const u8 *sig = NULL;
2694
2695 ret = eddsa_pub_key_sanity_check(pub_keys[i]); EG(ret, err);
2696
2697 /* Make things more readable */
2698 pub_key = pub_keys[i];
2699
2700 /* Sanity check that all our public keys have the same parameters */
2701 MUST_HAVE((pub_key->params) == (pub_key0->params), ret, err);
2702
2703 q = &(pub_key->params->ec_gen_order);
2704 shortw_curve = &(pub_key->params->ec_curve);
2705 alpha_montgomery = &(pub_key->params->ec_alpha_montgomery);
2706 gamma_montgomery = &(pub_key->params->ec_gamma_montgomery);
2707 alpha_edwards = &(pub_key->params->ec_alpha_edwards);
2708 gen_cofactor = &(pub_key->params->ec_gen_cofactor);
2709 pub_key_y = &(pub_key->y);
2710 key_type = pub_key->key_type;
2711 G = &(pub_key->params->ec_gen);
2712 q_bit_len = pub_key->params->ec_gen_order_bitlen;
2713
2714 /* Check the key type versus the algorithm */
2715 MUST_HAVE((key_type == sig_type), ret, err);
2716
2717 if(i == 0){
2718 /* Initialize our numbers */
2719 ret = nn_init(&z, 0); EG(ret, err);
2720 ret = nn_init(&S, 0); EG(ret, err);
2721 ret = nn_init(&elements[(2 * num)].number, 0); EG(ret, err);
2722 ret = _prj_pt_unprotected_mult(&elements[(2 * num)].point, gen_cofactor, G); EG(ret, err);
2723 }
2724
2725 gen_z_again:
2726 /* Get a random z for randomizing the linear combination */
2727 ret = nn_get_random_len(&z, (hsize / 4)); EG(ret, err);
2728 ret = nn_iszero(&z, &iszero); EG(ret, err);
2729 if(iszero){
2730 goto gen_z_again;
2731 }
2732
2733 /* Sanity check on hash types */
2734 MUST_HAVE((hash_type == get_eddsa_hash_type(key_type)), ret, err);
2735
2736 /* Check given signature length is the expected one */
2737 siglen = s_len[i];
2738 sig = s[i];
2739 MUST_HAVE((siglen == EDDSA_SIGLEN(hsize)), ret, err);
2740 MUST_HAVE((siglen == (EDDSA_R_LEN(hsize) + EDDSA_S_LEN(hsize))), ret, err);
2741
2742 /* Initialize the hash context */
2743 /* Since we call a callback, sanity check our mapping */
2744 ret = hash_mapping_callbacks_sanity_check(hm); EG(ret, err);
2745 ret = hm->hfunc_init(&h_ctx); EG(ret, err);
2746 ret = hm->hfunc_init(&h_ctx_pre_hash); EG(ret, err);
2747 #if defined(WITH_SIG_EDDSA25519)
2748 if(key_type == EDDSA25519CTX){
2749 /* As per RFC8032, for EDDSA25519CTX the context SHOULD NOT be empty */
2750 MUST_HAVE((adata[i] != NULL), ret, err);
2751 ret = dom2(0, adata[i], adata_len[i], hm, &h_ctx); EG(ret, err);
2752 }
2753 if(key_type == EDDSA25519PH){
2754 ret = dom2(1, adata[i], adata_len[i], hm, &h_ctx); EG(ret, err);
2755 }
2756 #endif
2757 #if defined(WITH_SIG_EDDSA448)
2758 if(key_type == EDDSA448){
2759 ret = dom4(0, adata[i], adata_len[i], hm, &h_ctx); EG(ret, err);
2760 }
2761 if(key_type == EDDSA448PH){
2762 ret = dom4(1, adata[i], adata_len[i], hm, &h_ctx); EG(ret, err);
2763 }
2764 #endif
2765 /* Import R and S values from signature buffer */
2766 /*******************************/
2767 /* Import R as an Edwards point */
2768 ret = curve_shortw_to_edwards(shortw_curve, &crv_edwards, alpha_montgomery,
2769 gamma_montgomery, alpha_edwards); EG(ret, err);
2770 /* NOTE: non canonical R are checked and rejected here */
2771 ret = eddsa_decode_point(&R, &crv_edwards, alpha_edwards, &sig[0],
2772 EDDSA_R_LEN(hsize), key_type); EG(ret, err);
2773 dbg_ec_edwards_point_print("R", &R);
2774 /* Transfer our public point R to Weierstrass */
2775 ret = aff_pt_edwards_to_prj_pt_shortw(&R, shortw_curve, &elements[i].point, alpha_edwards); EG(ret, err);
2776 /* Update the hash with the encoded R */
2777 ret = hm->hfunc_update(&h_ctx, &sig[0], EDDSA_R_LEN(hsize)); EG(ret, err);
2778 /* Store 8 * z in our number to be multiplied with R */
2779 ret = nn_init(&elements[i].number, 0); EG(ret, err);
2780 ret = nn_mul(&elements[i].number, gen_cofactor, &z); EG(ret, err);
2781 ret = nn_mod(&elements[i].number, &elements[i].number, q); EG(ret, err);
2782
2783 /*******************************/
2784 /* Import S as an integer */
2785 ret = eddsa_decode_integer(&S, &sig[EDDSA_R_LEN(hsize)], EDDSA_S_LEN(hsize)); EG(ret, err);
2786 /* Reject S if it is not reduced modulo q */
2787 ret = nn_cmp(&S, q, &cmp); EG(ret, err);
2788 MUST_HAVE((cmp < 0), ret, err);
2789 dbg_nn_print("S", &S);
2790
2791 /* Add (- z S) to the sum */
2792 ret = nn_mul(&S, &S, &z); EG(ret, err);
2793 ret = nn_mod(&S, &S, q); EG(ret, err);
2794 ret = nn_mod_neg(&S, &S, q); EG(ret, err); /* Negate S */
2795 ret = nn_mod_add(&elements[(2 * num)].number, &elements[(2 * num)].number, &S, q); EG(ret, err);
2796
2797 /*******************************/
2798 /* Encode the public key
2799 * NOTE: since we deal with a public key transfered to Weierstrass,
2800 * encoding checking has been handled elsewhere.
2801 */
2802 /* Reject the signature if the public key is one of small order points.
2803 * We multiply by the cofactor: since this is a public verification,
2804 * we use a basic double and add algorithm.
2805 */
2806 ret = _prj_pt_unprotected_mult(&elements[num + i].point, gen_cofactor, pub_key_y); EG(ret, err);
2807 /* Reject the signature if we have point at infinity here as this means
2808 * that the public key is of small order.
2809 */
2810 ret = prj_pt_iszero(&elements[num + i].point, &iszero); EG(ret, err);
2811 MUST_HAVE((!iszero), ret, err);
2812
2813 /* Transfer the public key to Edwards */
2814 ret = prj_pt_shortw_to_aff_pt_edwards(pub_key_y, &crv_edwards, &A, alpha_edwards); EG(ret, err);
2815 dbg_ec_edwards_point_print("A", &A);
2816 MUST_HAVE((EDDSA_R_LEN(hsize) <= sizeof(hash)), ret, err);
2817 /* NOTE: we use the hash buffer as a temporary buffer */
2818 ret = eddsa_encode_point(&A, alpha_edwards, hash, EDDSA_R_LEN(hsize), key_type); EG(ret, err);
2819
2820 /* Update the hash with the encoded public key */
2821 ret = hm->hfunc_update(&h_ctx, hash, EDDSA_R_LEN(hsize)); EG(ret, err);
2822 /* Finish our computation of h = H(R || A || M) */
2823 /* Update the hash with the message or its hash for the PH versions */
2824 if(use_message_pre_hash == 1){
2825 ret = hm->hfunc_update(&h_ctx_pre_hash, m[i], m_len[i]); EG(ret, err);
2826 ret = hm->hfunc_finalize(&h_ctx_pre_hash, hash); EG(ret, err);
2827 MUST_HAVE((use_message_pre_hash_hsize <= hsize), ret, err);
2828 ret = hm->hfunc_update(&h_ctx, hash, use_message_pre_hash_hsize); EG(ret, err);
2829 }
2830 else{
2831 ret = hm->hfunc_update(&h_ctx, m[i], m_len[i]); EG(ret, err);
2832 }
2833 ret = hm->hfunc_finalize(&h_ctx, hash); EG(ret, err);
2834 dbg_buf_print("hash = H(R || A || PH(M))", hash, hsize);
2835
2836 /* Import our hash as a NN and reduce it modulo q */
2837 ret = eddsa_decode_integer(&elements[num + i].number, hash, hsize); EG(ret, err);
2838 ret = nn_mod(&elements[num + i].number, &elements[num + i].number, q); EG(ret, err);
2839 dbg_nn_print("h = ", &elements[num + i].number);
2840 #if defined(WITH_SIG_EDDSA448)
2841 if((key_type == EDDSA448) || (key_type == EDDSA448PH)){
2842 /* When dealing with EDDSA448, because of our 4-isogeny between Edwars448 and Ed448
2843 * mapping base point to four times base point, we actually multiply our public key by 4 here
2844 * to be inline with the other computations (the public key stored in Weierstrass )
2845 */
2846 ret = nn_lshift(&elements[num + i].number, &elements[num + i].number, 2); EG(ret, err);
2847 ret = nn_mod(&elements[num + i].number, &elements[num + i].number, q); EG(ret, err);
2848 }
2849 #endif
2850 /* Compute by (z * h) mod q.
2851 */
2852 ret = nn_mul(&elements[num + i].number, &elements[num + i].number, &z); EG(ret, err);
2853 ret = nn_mod(&elements[num + i].number, &elements[num + i].number, q); EG(ret, err);
2854 }
2855
2856 /* Sanity check */
2857 MUST_HAVE((gen_cofactor != NULL) && (q != NULL) && (G != NULL) && (q_bit_len != 0), ret, err);
2858
2859 /********************************************/
2860 /****** Bos-Coster algorithm ****************/
2861 ret = ec_verify_bos_coster(elements, (2 * num) + 1, q_bit_len);
2862 if(ret){
2863 if(ret == -2){
2864 /* In case of Bos-Coster time out, we fall back to the
2865 * slower regular batch verification.
2866 */
2867 ret = _eddsa_verify_batch_no_memory(s, s_len, pub_keys, m, m_len, num, sig_type,
2868 hash_type, adata, adata_len); EG(ret, err);
2869 }
2870 goto err;
2871 }
2872
2873 /* The first element should contain the sum: it should
2874 * be equal to zero. Reject the signature if this is not
2875 * the case.
2876 */
2877 ret = prj_pt_iszero(&elements[elements[0].index].point, &iszero); EG(ret, err);
2878 ret = iszero ? 0 : -1;
2879
2880 err:
2881 PTR_NULLIFY(q);
2882 PTR_NULLIFY(pub_key);
2883 PTR_NULLIFY(pub_key0);
2884 PTR_NULLIFY(shortw_curve);
2885 PTR_NULLIFY(alpha_montgomery);
2886 PTR_NULLIFY(gamma_montgomery);
2887 PTR_NULLIFY(alpha_edwards);
2888 PTR_NULLIFY(gen_cofactor);
2889 PTR_NULLIFY(pub_key_y);
2890 PTR_NULLIFY(G);
2891 PTR_NULLIFY(elements);
2892
2893 /* Unitialize all our scratch_pad_area */
2894 if((scratch_pad_area != NULL) && (scratch_pad_area_len != NULL)){
2895 IGNORE_RET_VAL(local_memset((u8*)scratch_pad_area, 0, (*scratch_pad_area_len)));
2896 }
2897
2898 ec_edwards_crv_uninit(&crv_edwards);
2899 aff_pt_edwards_uninit(&A);
2900 aff_pt_edwards_uninit(&R);
2901 nn_uninit(&S);
2902 nn_uninit(&z);
2903
2904 return ret;
2905 }
2906
2907 int eddsa_verify_batch(const u8 **s, const u8 *s_len, const ec_pub_key **pub_keys,
2908 const u8 **m, const u32 *m_len, u32 num, ec_alg_type sig_type,
2909 hash_alg_type hash_type, const u8 **adata, const u16 *adata_len,
2910 verify_batch_scratch_pad *scratch_pad_area, u32 *scratch_pad_area_len)
2911 {
2912 int ret;
2913
2914 if(scratch_pad_area != NULL){
2915 MUST_HAVE((scratch_pad_area_len != NULL), ret, err);
2916 ret = _eddsa_verify_batch(s, s_len, pub_keys, m, m_len, num, sig_type,
2917 hash_type, adata, adata_len,
2918 scratch_pad_area, scratch_pad_area_len); EG(ret, err);
2919 }
2920 else{
2921 ret = _eddsa_verify_batch_no_memory(s, s_len, pub_keys, m, m_len, num, sig_type,
2922 hash_type, adata, adata_len); EG(ret, err);
2923 }
2924
2925 err:
2926 return ret;
2927 }
2928
2929 #else /* !(defined(WITH_SIG_EDDSA25519) || defined(WITH_SIG_EDDSA448)) */
2930
2931 /*
2932 * Dummy definition to avoid the empty translation unit ISO C warning
2933 */
2934 typedef int dummy;
2935 #endif /* defined(WITH_SIG_EDDSA25519) || defined(WITH_SIG_EDDSA448) */
2936