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 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 */ 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 */ 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 */ 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 */ 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 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 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 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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