1 /* 2 * Copyright (C) 2022 - 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_BIP0340) 13 14 /* BIP0340 needs SHA-256: check it */ 15 #if !defined(WITH_HASH_SHA256) 16 #error "Error: BIP0340 needs SHA-256 to be defined! Please define it in libecc config file" 17 #endif 18 19 #include <libecc/nn/nn_rand.h> 20 #include <libecc/nn/nn_mul_public.h> 21 #include <libecc/nn/nn_logical.h> 22 23 #include <libecc/sig/sig_algs_internal.h> 24 #include <libecc/sig/sig_algs.h> 25 #include <libecc/sig/ec_key.h> 26 #ifdef VERBOSE_INNER_VALUES 27 #define EC_SIG_ALG "BIP0340" 28 #endif 29 #include <libecc/utils/dbg_sig.h> 30 31 /* 32 * The current implementation is for the BIP0340 signature as described 33 * in https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki 34 * 35 * The BIP0340 signature is only compatible with SHA-256 and secp256k1, 36 * but we extend it to any hash function or curve. 37 * 38 */ 39 40 /* The "hash" function static prefixes */ 41 #define BIP0340_AUX "BIP0340/aux" 42 #define BIP0340_NONCE "BIP0340/nonce" 43 #define BIP0340_CHALLENGE "BIP0340/challenge" 44 45 ATTRIBUTE_WARN_UNUSED_RET static int _bip0340_hash(const u8 *tag, u32 tag_len, 46 const u8 *m, u32 m_len, 47 const hash_mapping *hm, hash_context *h_ctx) 48 { 49 int ret; 50 u8 hash[MAX_DIGEST_SIZE]; 51 52 MUST_HAVE((h_ctx != NULL), ret, err); 53 54 ret = hash_mapping_callbacks_sanity_check(hm); EG(ret, err); 55 56 ret = hm->hfunc_init(h_ctx); EG(ret, err); 57 ret = hm->hfunc_update(h_ctx, tag, tag_len); EG(ret, err); 58 ret = hm->hfunc_finalize(h_ctx, hash); EG(ret, err); 59 60 /* Now compute hash(hash(tag) || hash(tag) || m) */ 61 ret = hm->hfunc_init(h_ctx); EG(ret, err); 62 ret = hm->hfunc_update(h_ctx, hash, hm->digest_size); EG(ret, err); 63 ret = hm->hfunc_update(h_ctx, hash, hm->digest_size); EG(ret, err); 64 ret = hm->hfunc_update(h_ctx, m, m_len); EG(ret, err); 65 66 ret = 0; 67 err: 68 return ret; 69 } 70 71 /* Set the scalar value depending on the parity bit of the input 72 * point y coordinate. 73 */ 74 ATTRIBUTE_WARN_UNUSED_RET static int _bip0340_set_scalar(nn_t scalar, 75 nn_src_t q, 76 prj_pt_src_t P) 77 { 78 int ret, isodd, isone; 79 80 /* Sanity check */ 81 ret = prj_pt_check_initialized(P); EG(ret, err); 82 83 /* This operation is only meaningful on the "affine" representative. 84 * Check it. 85 */ 86 ret = nn_isone(&(P->Z.fp_val), &isone); EG(ret, err); 87 MUST_HAVE((isone), ret, err); 88 89 /* Check if Py is odd or even */ 90 ret = nn_isodd(&(P->Y.fp_val), &isodd); EG(ret, err); 91 92 if(isodd){ 93 /* Replace the input scalar by (q - scalar) 94 * (its opposite modulo q) 95 */ 96 ret = nn_mod_neg(scalar, scalar, q); EG(ret, err); 97 } 98 99 err: 100 return ret; 101 } 102 103 /* 104 * Generic *internal* helper for BIP340 public key initialization 105 * functions. The function returns 0 on success, -1 on error. 106 */ 107 int bip0340_init_pub_key(ec_pub_key *out_pub, const ec_priv_key *in_priv) 108 { 109 prj_pt_src_t G; 110 int ret; 111 112 MUST_HAVE((out_pub != NULL), ret, err); 113 114 /* Zero init public key to be generated */ 115 ret = local_memset(out_pub, 0, sizeof(ec_pub_key)); EG(ret, err); 116 117 ret = priv_key_check_initialized_and_type(in_priv, BIP0340); EG(ret, err); 118 119 /* Y = xG */ 120 G = &(in_priv->params->ec_gen); 121 /* Use blinding when computing point scalar multiplication */ 122 ret = prj_pt_mul_blind(&(out_pub->y), &(in_priv->x), G); EG(ret, err); 123 124 out_pub->key_type = BIP0340; 125 out_pub->params = in_priv->params; 126 out_pub->magic = PUB_KEY_MAGIC; 127 128 err: 129 return ret; 130 } 131 132 /* 133 * Generic *internal* helper for BIP0340 signature length functions. 134 */ 135 int bip0340_siglen(u16 p_bit_len, u16 q_bit_len, u8 hsize, u8 blocksize, 136 u8 *siglen) 137 { 138 int ret; 139 140 MUST_HAVE((siglen != NULL), ret, err); 141 MUST_HAVE(((p_bit_len <= CURVES_MAX_P_BIT_LEN) && 142 (q_bit_len <= CURVES_MAX_Q_BIT_LEN) && 143 (hsize <= MAX_DIGEST_SIZE) && (blocksize <= MAX_BLOCK_SIZE)), 144 ret, err); 145 146 (*siglen) = (u8)BIP0340_SIGLEN(p_bit_len, q_bit_len); 147 ret = 0; 148 149 err: 150 return ret; 151 } 152 153 /* 154 * Generic *internal* helper for BIP0340 signature. 155 * NOTE: because of the semi-deterministinc nonce generation 156 * process, streaming mode is NOT supported for signing. 157 * Hence the following all-in-one signature function. 158 * 159 * The function returns 0 on success, -1 on error. 160 */ 161 int _bip0340_sign(u8 *sig, u8 siglen, const ec_key_pair *key_pair, 162 const u8 *m, u32 mlen, int (*rand) (nn_t out, nn_src_t q), 163 ec_alg_type sig_type, hash_alg_type hash_type, 164 const u8 *adata, u16 adata_len) 165 { 166 prj_pt_src_t G; 167 prj_pt Y; 168 nn_src_t q; 169 nn k, d, e; 170 prj_pt kG; 171 const ec_priv_key *priv_key; 172 const ec_pub_key *pub_key; 173 bitcnt_t p_bit_len, q_bit_len; 174 u8 i, p_len, q_len; 175 int ret, cmp, iszero; 176 hash_context h_ctx; 177 const hash_mapping *hm; 178 u8 buff[MAX_DIGEST_SIZE]; 179 #ifdef USE_SIG_BLINDING 180 /* b is the blinding mask */ 181 nn b, binv; 182 b.magic = binv.magic = WORD(0); 183 #endif /* USE_SIG_BLINDING */ 184 185 k.magic = d.magic = e.magic = kG.magic = Y.magic = WORD(0); 186 187 FORCE_USED_VAR(adata_len); 188 189 /* No ancillary data is expected with BIP0340 */ 190 MUST_HAVE((key_pair != NULL) && (sig != NULL) && (adata == NULL), ret, err); 191 192 /* Check our algorithm type */ 193 MUST_HAVE((sig_type == BIP0340), ret, err); 194 195 /* Check that keypair is initialized */ 196 ret = key_pair_check_initialized_and_type(key_pair, BIP0340); EG(ret, err); 197 198 /* Get the hash mapping */ 199 ret = get_hash_by_type(hash_type, &hm); EG(ret, err); 200 MUST_HAVE((hm != NULL), ret, err); 201 ret = hash_mapping_callbacks_sanity_check(hm); EG(ret, err); 202 203 /* Make things more readable */ 204 priv_key = &(key_pair->priv_key); 205 pub_key = &(key_pair->pub_key); 206 G = &(priv_key->params->ec_gen); 207 q = &(priv_key->params->ec_gen_order); 208 p_bit_len = priv_key->params->ec_fp.p_bitlen; 209 q_bit_len = priv_key->params->ec_gen_order_bitlen; 210 q_len = (u8)BYTECEIL(q_bit_len); 211 p_len = (u8)BYTECEIL(p_bit_len); 212 213 /* Copy the public key point to work on the unique 214 * affine representative. 215 */ 216 ret = prj_pt_copy(&Y, &(pub_key->y)); EG(ret, err); 217 ret = prj_pt_unique(&Y, &Y); EG(ret, err); 218 219 ret = nn_init(&d, 0); EG(ret, err); 220 ret = nn_copy(&d, &(priv_key->x)); EG(ret, err); 221 222 dbg_nn_print("d", &d); 223 224 /* Check signature size */ 225 MUST_HAVE((siglen == BIP0340_SIGLEN(p_bit_len, q_bit_len)), ret, err); 226 MUST_HAVE((p_len == BIP0340_R_LEN(p_bit_len)), ret, err); 227 MUST_HAVE((q_len == BIP0340_S_LEN(q_bit_len)), ret, err); 228 229 /* Fail if d = 0 or d >= q */ 230 ret = nn_iszero(&d, &iszero); EG(ret, err); 231 ret = nn_cmp(&d, q, &cmp); EG(ret, err); 232 MUST_HAVE((!iszero) && (cmp < 0), ret, err); 233 234 /* Adjust d depending on public key y */ 235 ret = _bip0340_set_scalar(&d, q, &Y); EG(ret, err); 236 237 /* Compute the nonce in a deterministic way. 238 * First, we get the random auxilary data. 239 */ 240 #ifdef NO_KNOWN_VECTORS 241 /* NOTE: when we do not need self tests for known vectors, 242 * we can be strict about random function handler! 243 * This allows us to avoid the corruption of such a pointer. 244 */ 245 /* Sanity check on the handler before calling it */ 246 MUST_HAVE((rand == nn_get_random_mod), ret, err); 247 #endif 248 ret = nn_init(&e, 0); EG(ret, err); 249 ret = nn_one(&e); EG(ret, err); 250 ret = nn_lshift(&e, &e, (bitcnt_t)(8 * q_len)); EG(ret, err); 251 if(rand == NULL){ 252 rand = nn_get_random_mod; 253 } 254 ret = rand(&k, &e); EG(ret, err); 255 dbg_nn_print("a", &k); 256 257 MUST_HAVE((siglen >= q_len), ret, err); 258 ret = nn_export_to_buf(&sig[0], q_len, &k); EG(ret, err); 259 260 /* Compute the seed for the nonce computation */ 261 ret = _bip0340_hash((const u8*)BIP0340_AUX, sizeof(BIP0340_AUX) - 1, 262 &sig[0], q_len, hm, &h_ctx); EG(ret, err); 263 ret = hm->hfunc_finalize(&h_ctx, buff); EG(ret, err); 264 265 ret = nn_export_to_buf(&sig[0], q_len, &d); EG(ret, err); 266 267 if(q_len > hm->digest_size){ 268 for(i = 0; i < hm->digest_size; i++){ 269 sig[i] ^= buff[i]; 270 } 271 ret = _bip0340_hash((const u8*)BIP0340_NONCE, sizeof(BIP0340_NONCE) - 1, 272 &sig[0], q_len, hm, &h_ctx); EG(ret, err); 273 } 274 else{ 275 for(i = 0; i < q_len; i++){ 276 buff[i] ^= sig[i]; 277 } 278 ret = _bip0340_hash((const u8*)BIP0340_NONCE, sizeof(BIP0340_NONCE) - 1, 279 &buff[0], hm->digest_size, hm, &h_ctx); EG(ret, err); 280 } 281 ret = fp_export_to_buf(&sig[0], p_len, &(Y.X)); EG(ret, err); 282 ret = hm->hfunc_update(&h_ctx, &sig[0], p_len); EG(ret, err); 283 ret = hm->hfunc_update(&h_ctx, m, mlen); EG(ret, err); 284 ret = hm->hfunc_finalize(&h_ctx, buff); EG(ret, err); 285 286 /* Now import the semi-deterministic nonce modulo q */ 287 ret = nn_init_from_buf(&k, buff, hm->digest_size); EG(ret, err); 288 ret = nn_mod(&k, &k, q); EG(ret, err); 289 290 dbg_nn_print("k", &k); 291 292 /* Fail if the nonce is zero */ 293 ret = nn_iszero(&k, &iszero); EG(ret, err); 294 MUST_HAVE((!iszero), ret, err); 295 296 /* Proceed with the modulation exponentiation kG */ 297 #ifdef USE_SIG_BLINDING 298 /* We use blinding for the scalar multiplication */ 299 ret = prj_pt_mul_blind(&kG, &k, G); EG(ret, err); 300 #else 301 ret = prj_pt_mul(&kG, &k, G); EG(ret, err); 302 #endif 303 ret = prj_pt_unique(&kG, &kG); EG(ret, err); 304 305 dbg_ec_point_print("(k G)", &kG); 306 307 /* Update k depending on the kG y coordinate */ 308 ret = _bip0340_set_scalar(&k, q, &kG); EG(ret, err); 309 310 /* Compute e */ 311 /* We export our r here */ 312 ret = fp_export_to_buf(&sig[0], p_len, &(kG.X)); EG(ret, err); 313 ret = _bip0340_hash((const u8*)BIP0340_CHALLENGE, sizeof(BIP0340_CHALLENGE) - 1, 314 &sig[0], p_len, hm, &h_ctx); EG(ret, err); 315 /* Export our public key */ 316 ret = fp_export_to_buf(&sig[0], p_len, &(Y.X)); EG(ret, err); 317 ret = hm->hfunc_update(&h_ctx, &sig[0], p_len); EG(ret, err); 318 /* Update with the message */ 319 ret = hm->hfunc_update(&h_ctx, m, mlen); EG(ret, err); 320 ret = hm->hfunc_finalize(&h_ctx, buff); EG(ret, err); 321 ret = nn_init_from_buf(&e, buff, hm->digest_size); EG(ret, err); 322 ret = nn_mod(&e, &e, q); EG(ret, err); 323 dbg_nn_print("e", &e); 324 325 /* Export our r in the signature */ 326 dbg_nn_print("r", &(kG.X.fp_val)); 327 ret = fp_export_to_buf(&sig[0], p_len, &(kG.X)); EG(ret, err); 328 329 /* Compute (k + ed) mod n */ 330 #ifdef USE_SIG_BLINDING 331 ret = nn_get_random_mod(&b, q); EG(ret, err); 332 dbg_nn_print("b", &b); 333 #endif /* USE_SIG_BLINDING */ 334 335 #ifdef USE_SIG_BLINDING 336 /* Blind e with b */ 337 ret = nn_mod_mul(&e, &e, &b, q); EG(ret, err); 338 /* Blind k with b */ 339 ret = nn_mod_mul(&k, &k, &b, q); EG(ret, err); 340 #endif /* USE_SIG_BLINDING */ 341 342 ret = nn_mod_mul(&e, &e, &d, q); EG(ret, err); 343 ret = nn_mod_add(&e, &k, &e, q); EG(ret, err); 344 345 #ifdef USE_SIG_BLINDING 346 /* Unblind */ 347 /* NOTE: we use Fermat's little theorem inversion for 348 * constant time here. This is possible since q is prime. 349 */ 350 ret = nn_modinv_fermat(&binv, &b, q); EG(ret, err); 351 ret = nn_mod_mul(&e, &e, &binv, q); EG(ret, err); 352 #endif /* USE_SIG_BLINDING */ 353 354 /* Export our s in the signature */ 355 dbg_nn_print("s", &e); 356 ret = nn_export_to_buf(&sig[p_len], q_len, &e); EG(ret, err); 357 358 err: 359 PTR_NULLIFY(G); 360 PTR_NULLIFY(q); 361 PTR_NULLIFY(priv_key); 362 PTR_NULLIFY(pub_key); 363 PTR_NULLIFY(hm); 364 365 prj_pt_uninit(&Y); 366 nn_uninit(&k); 367 nn_uninit(&e); 368 nn_uninit(&d); 369 370 return ret; 371 } 372 373 /* local helper for context sanity checks. Returns 0 on success, -1 on error. */ 374 #define BIP0340_VERIFY_MAGIC ((word_t)(0x340175910abafcddULL)) 375 #define BIP0340_VERIFY_CHECK_INITIALIZED(A, ret, err) \ 376 MUST_HAVE((((const void *)(A)) != NULL) && \ 377 ((A)->magic == BIP0340_VERIFY_MAGIC), ret, err) 378 379 /* 380 * Generic *internal* helper for BIP0340 verification initialization functions. 381 * The function returns 0 on success, -1 on error. 382 */ 383 int _bip0340_verify_init(struct ec_verify_context *ctx, 384 const u8 *sig, u8 siglen) 385 { 386 bitcnt_t p_bit_len, q_bit_len; 387 u8 p_len, q_len; 388 int ret, cmp; 389 nn_src_t q; 390 prj_pt Y; 391 fp *rx; 392 nn *s; 393 u8 Pubx[NN_MAX_BYTE_LEN]; 394 395 /* First, verify context has been initialized */ 396 ret = sig_verify_check_initialized(ctx); EG(ret, err); 397 398 /* Do some sanity checks on input params */ 399 ret = pub_key_check_initialized_and_type(ctx->pub_key, BIP0340); EG(ret, err); 400 MUST_HAVE((ctx->h != NULL) && (ctx->h->digest_size <= MAX_DIGEST_SIZE) && 401 (ctx->h->block_size <= MAX_BLOCK_SIZE), ret, err); 402 MUST_HAVE((sig != NULL), ret, err); 403 404 /* Since we call a callback, sanity check our mapping */ 405 ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err); 406 407 /* Make things more readable */ 408 q = &(ctx->pub_key->params->ec_gen_order); 409 p_bit_len = ctx->pub_key->params->ec_fp.p_bitlen; 410 q_bit_len = ctx->pub_key->params->ec_gen_order_bitlen; 411 p_len = (u8)BYTECEIL(p_bit_len); 412 q_len = (u8)BYTECEIL(q_bit_len); 413 s = &(ctx->verify_data.bip0340.s); 414 rx = &(ctx->verify_data.bip0340.r); 415 416 MUST_HAVE((siglen == BIP0340_SIGLEN(p_bit_len, q_bit_len)), ret, err); 417 MUST_HAVE((p_len == BIP0340_R_LEN(p_bit_len)), ret, err); 418 MUST_HAVE((q_len == BIP0340_S_LEN(q_bit_len)), ret, err); 419 420 /* Copy the public key point to work on the unique 421 * affine representative. 422 */ 423 ret = prj_pt_copy(&Y, &(ctx->pub_key->y)); EG(ret, err); 424 ret = prj_pt_unique(&Y, &Y); EG(ret, err); 425 426 /* Extract r and s */ 427 ret = fp_init(rx, ctx->pub_key->params->ec_curve.a.ctx); EG(ret, err); 428 ret = fp_import_from_buf(rx, &sig[0], p_len); EG(ret, err); 429 ret = nn_init_from_buf(s, &sig[p_len], q_len); EG(ret, err); 430 ret = nn_cmp(s, q, &cmp); EG(ret, err); 431 MUST_HAVE((cmp < 0), ret, err); 432 433 dbg_nn_print("r", &(rx->fp_val)); 434 dbg_nn_print("s", s); 435 436 /* Initialize our hash context */ 437 ret = _bip0340_hash((const u8*)BIP0340_CHALLENGE, sizeof(BIP0340_CHALLENGE) - 1, 438 &sig[0], p_len, ctx->h, 439 &(ctx->verify_data.bip0340.h_ctx)); EG(ret, err); 440 ret = fp_export_to_buf(&Pubx[0], p_len, &(Y.X)); EG(ret, err); 441 ret = ctx->h->hfunc_update(&(ctx->verify_data.bip0340.h_ctx), &Pubx[0], p_len); EG(ret, err); 442 ret = local_memset(Pubx, 0, sizeof(Pubx)); EG(ret, err); 443 444 ctx->verify_data.bip0340.magic = BIP0340_VERIFY_MAGIC; 445 446 err: 447 PTR_NULLIFY(q); 448 PTR_NULLIFY(rx); 449 PTR_NULLIFY(s); 450 451 prj_pt_uninit(&Y); 452 453 if (ret && (ctx != NULL)) { 454 /* 455 * Signature is invalid. Clear data part of the context. 456 * This will clear magic and avoid further reuse of the 457 * whole context. 458 */ 459 IGNORE_RET_VAL(local_memset(&(ctx->verify_data.bip0340), 0, 460 sizeof(bip0340_verify_data))); 461 } 462 463 return ret; 464 } 465 466 /* 467 * Generic *internal* helper for BIP0340 verification update functions. 468 * The function returns 0 on success, -1 on error. 469 */ 470 int _bip0340_verify_update(struct ec_verify_context *ctx, 471 const u8 *chunk, u32 chunklen) 472 { 473 int ret; 474 475 /* 476 * First, verify context has been initialized and public 477 * part too. This guarantees the context is an BIP0340 478 * verification one and we do not update() or finalize() 479 * before init(). 480 */ 481 ret = sig_verify_check_initialized(ctx); EG(ret, err); 482 BIP0340_VERIFY_CHECK_INITIALIZED(&(ctx->verify_data.bip0340), ret, err); 483 484 /* Since we call a callback, sanity check our mapping */ 485 ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err); 486 ret = ctx->h->hfunc_update(&(ctx->verify_data.bip0340.h_ctx), chunk, 487 chunklen); 488 489 err: 490 return ret; 491 } 492 493 /* 494 * Generic *internal* helper for BIP0340 verification finalization 495 * functions. The function returns 0 on success, -1 on error. 496 */ 497 int _bip0340_verify_finalize(struct ec_verify_context *ctx) 498 { 499 prj_pt_src_t G; 500 nn_src_t s, q; 501 fp_src_t r; 502 nn e; 503 prj_pt sG, eY, Y; 504 u8 e_buf[MAX_DIGEST_SIZE]; 505 u8 hsize; 506 int ret, iszero, isodd, cmp; 507 508 ret = sig_verify_check_initialized(ctx); EG(ret, err); 509 BIP0340_VERIFY_CHECK_INITIALIZED(&(ctx->verify_data.bip0340), ret, err); 510 511 /* Since we call a callback, sanity check our mapping */ 512 ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err); 513 514 /* Zero init points */ 515 ret = local_memset(&sG, 0, sizeof(prj_pt)); EG(ret, err); 516 ret = local_memset(&eY, 0, sizeof(prj_pt)); EG(ret, err); 517 518 /* Make things more readable */ 519 G = &(ctx->pub_key->params->ec_gen); 520 hsize = ctx->h->digest_size; 521 q = &(ctx->pub_key->params->ec_gen_order); 522 s = &(ctx->verify_data.bip0340.s); 523 r = &(ctx->verify_data.bip0340.r); 524 525 /* Copy the public key point to work on the unique 526 * affine representative. 527 */ 528 ret = prj_pt_copy(&Y, &(ctx->pub_key->y)); EG(ret, err); 529 ret = prj_pt_unique(&Y, &Y); EG(ret, err); 530 531 /* Compute e */ 532 ret = ctx->h->hfunc_finalize(&(ctx->verify_data.bip0340.h_ctx), 533 &e_buf[0]); EG(ret, err); 534 ret = nn_init_from_buf(&e, e_buf, hsize); EG(ret, err); 535 ret = nn_mod(&e, &e, q); EG(ret, err); 536 537 dbg_nn_print("e", &e); 538 539 /* Compute s G - e Y */ 540 ret = prj_pt_mul(&sG, s, G); EG(ret, err); 541 ret = nn_mod_neg(&e, &e, q); EG(ret, err); /* compute -e = (q - e) mod q */ 542 /* Do we have to "lift" Y the public key ? */ 543 ret = nn_isodd(&(Y.Y.fp_val), &isodd); EG(ret, err); 544 if(isodd){ 545 /* If yes, negate the y coordinate */ 546 ret = fp_neg(&(Y.Y), &(Y.Y)); EG(ret, err); 547 } 548 ret = prj_pt_mul(&eY, &e, &Y); EG(ret, err); 549 ret = prj_pt_add(&sG, &sG, &eY); EG(ret, err); 550 ret = prj_pt_unique(&sG, &sG); EG(ret, err); 551 552 dbg_ec_point_print("(s G - e Y)", &sG); 553 554 /* Reject point at infinity */ 555 ret = prj_pt_iszero(&sG, &iszero); EG(ret, err); 556 MUST_HAVE((!iszero), ret, err); 557 558 /* Reject non even Y coordinate */ 559 ret = nn_isodd(&(sG.Y.fp_val), &isodd); EG(ret, err); 560 MUST_HAVE((!isodd), ret, err); 561 562 /* Check the x coordinate against r */ 563 ret = nn_cmp(&(r->fp_val), &(sG.X.fp_val), &cmp); EG(ret, err); 564 ret = (cmp == 0) ? 0 : -1; 565 566 err: 567 PTR_NULLIFY(G); 568 PTR_NULLIFY(s); 569 PTR_NULLIFY(q); 570 PTR_NULLIFY(r); 571 572 nn_uninit(&e); 573 prj_pt_uninit(&sG); 574 prj_pt_uninit(&eY); 575 prj_pt_uninit(&Y); 576 577 /* 578 * We can now clear data part of the context. This will clear 579 * magic and avoid further reuse of the whole context. 580 */ 581 if(ctx != NULL){ 582 IGNORE_RET_VAL(local_memset(&(ctx->verify_data.bip0340), 0, 583 sizeof(bip0340_verify_data))); 584 } 585 586 return ret; 587 } 588 589 /* 590 * Helper to compute the seed to generate batch verification randomizing scalars. 591 * 592 */ 593 /****************************************************/ 594 /* 595 * 32-bit integer manipulation macros (big endian) 596 */ 597 #ifndef GET_UINT32_LE 598 #define GET_UINT32_LE(n, b, i) \ 599 do { \ 600 (n) = ( ((u32) (b)[(i) + 3]) << 24 ) \ 601 | ( ((u32) (b)[(i) + 2]) << 16 ) \ 602 | ( ((u32) (b)[(i) + 1]) << 8 ) \ 603 | ( ((u32) (b)[(i) ]) ); \ 604 } while( 0 ) 605 #endif 606 607 #ifndef PUT_UINT32_LE 608 #define PUT_UINT32_LE(n, b, i) \ 609 do { \ 610 (b)[(i) + 3] = (u8) ( (n) >> 24 ); \ 611 (b)[(i) + 2] = (u8) ( (n) >> 16 ); \ 612 (b)[(i) + 1] = (u8) ( (n) >> 8 ); \ 613 (b)[(i) ] = (u8) ( (n) ); \ 614 } while( 0 ) 615 #endif 616 617 #ifndef PUT_UINT32_BE 618 #define PUT_UINT32_BE(n, b, i) \ 619 do { \ 620 (b)[(i) ] = (u8) ( (n) >> 24 ); \ 621 (b)[(i) + 1] = (u8) ( (n) >> 16 ); \ 622 (b)[(i) + 2] = (u8) ( (n) >> 8 ); \ 623 (b)[(i) + 3] = (u8) ( (n) ); \ 624 } while( 0 ) 625 #endif 626 627 #define _CHACHA20_ROTL_(x, y) (((x) << (y)) | ((x) >> ((sizeof(u32) * 8) - (y)))) 628 #define CHACA20_ROTL(x, y) ((((y) < (sizeof(u32) * 8)) && ((y) > 0)) ? (_CHACHA20_ROTL_(x, y)) : (x)) 629 630 #define CHACHA20_QROUND(a, b, c, d) do { \ 631 (a) += (b); \ 632 (d) ^= (a); \ 633 (d) = CHACA20_ROTL((d), 16); \ 634 (c) += (d); \ 635 (b) ^= (c); \ 636 (b) = CHACA20_ROTL((b), 12); \ 637 (a) += (b); \ 638 (d) ^= (a); \ 639 (d) = CHACA20_ROTL((d), 8); \ 640 (c) += (d); \ 641 (b) ^= (c); \ 642 (b) = CHACA20_ROTL((b), 7); \ 643 } while(0) 644 645 #define CHACHA20_INNER_BLOCK(s) do { \ 646 CHACHA20_QROUND(s[0], s[4], s[ 8], s[12]); \ 647 CHACHA20_QROUND(s[1], s[5], s[ 9], s[13]); \ 648 CHACHA20_QROUND(s[2], s[6], s[10], s[14]); \ 649 CHACHA20_QROUND(s[3], s[7], s[11], s[15]); \ 650 CHACHA20_QROUND(s[0], s[5], s[10], s[15]); \ 651 CHACHA20_QROUND(s[1], s[6], s[11], s[12]); \ 652 CHACHA20_QROUND(s[2], s[7], s[ 8], s[13]); \ 653 CHACHA20_QROUND(s[3], s[4], s[ 9], s[14]); \ 654 } while(0) 655 656 #define CHACHA20_MAX_ASKED_LEN 64 657 658 ATTRIBUTE_WARN_UNUSED_RET static int _bip0340_chacha20_block(const u8 key[32], const u8 nonce[12], u32 block_counter, u8 *stream, u32 stream_len){ 659 int ret; 660 u32 state[16]; 661 u32 initial_state[16]; 662 unsigned int i; 663 664 MUST_HAVE((stream != NULL), ret, err); 665 MUST_HAVE((stream_len <= CHACHA20_MAX_ASKED_LEN), ret, err); 666 667 /* Initial state */ 668 state[0] = 0x61707865; 669 state[1] = 0x3320646e; 670 state[2] = 0x79622d32; 671 state[3] = 0x6b206574; 672 673 for(i = 4; i < 12; i++){ 674 GET_UINT32_LE(state[i], key, (4 * (i - 4))); 675 } 676 state[12] = block_counter; 677 for(i = 13; i < 16; i++){ 678 GET_UINT32_LE(state[i], nonce, (4 * (i - 13))); 679 } 680 681 /* Core loop */ 682 ret = local_memcpy(initial_state, state, sizeof(state)); EG(ret, err); 683 for(i = 0; i < 10; i++){ 684 CHACHA20_INNER_BLOCK(state); 685 } 686 /* Serialize and output the block */ 687 for(i = 0; i < 16; i++){ 688 u32 tmp = (u32)(state[i] + initial_state[i]); 689 PUT_UINT32_LE(tmp, (u8*)(&state[i]), 0); 690 } 691 ret = local_memcpy(stream, &state[0], stream_len); 692 693 err: 694 return ret; 695 } 696 697 ATTRIBUTE_WARN_UNUSED_RET static int _bip0340_compute_batch_csprng_one_scalar(const u8 *seed, u32 seedlen, 698 u8 *scalar, u32 scalar_len, u32 num) 699 { 700 int ret; 701 u8 nonce[12]; 702 703 /* Sanity check for ChaCha20 */ 704 MUST_HAVE((seedlen == SHA256_DIGEST_SIZE) && (scalar_len <= CHACHA20_MAX_ASKED_LEN), ret, err); 705 706 /* NOTE: nothing in the BIP340 specification fixes the nonce for 707 * ChaCha20. We simply use 0 here for the nonce. */ 708 ret = local_memset(nonce, 0, sizeof(nonce)); EG(ret, err); 709 710 /* Use our CSPRNG based on ChaCha20 to generate the scalars */ 711 ret = _bip0340_chacha20_block(seed, nonce, num, scalar, scalar_len); 712 713 err: 714 return ret; 715 } 716 717 ATTRIBUTE_WARN_UNUSED_RET static int _bip0340_compute_batch_csprng_scalars(const u8 *seed, u32 seedlen, 718 u8 *scalar, u32 scalar_len, 719 u32 *num, nn_src_t q, 720 bitcnt_t q_bit_len, u8 q_len, 721 nn_t a) 722 { 723 int ret, iszero, cmp; 724 u32 size, remain; 725 726 MUST_HAVE((seed != NULL) && (scalar != NULL) && (num != NULL) && (a != NULL), ret, err); 727 MUST_HAVE((scalar_len >= q_len), ret, err); 728 729 gen_scalar_again: 730 size = remain = 0; 731 while(size < q_len){ 732 MUST_HAVE((*num) < 0xffffffff, ret, err); 733 remain = ((q_len - size) < CHACHA20_MAX_ASKED_LEN) ? (q_len - size): CHACHA20_MAX_ASKED_LEN; 734 ret = _bip0340_compute_batch_csprng_one_scalar(seed, seedlen, 735 &scalar[size], remain, 736 (*num)); EG(ret, err); 737 (*num)++; 738 size += remain; 739 } 740 if((q_bit_len % 8) != 0){ 741 /* Handle the cutoff when q_bit_len is not a byte multiple */ 742 scalar[0] &= (u8)((0x1 << (q_bit_len % 8)) - 1); 743 } 744 /* Import the scalar */ 745 ret = nn_init_from_buf(a, scalar, q_len); EG(ret, err); 746 /* Check if the scalar is between 1 and q-1 */ 747 ret = nn_iszero(a, &iszero); EG(ret, err); 748 ret = nn_cmp(a, q, &cmp); EG(ret, err); 749 if((iszero) || (cmp >= 0)){ 750 goto gen_scalar_again; 751 } 752 753 ret = 0; 754 err: 755 return ret; 756 } 757 758 ATTRIBUTE_WARN_UNUSED_RET static int _bip0340_compute_batch_csprng_seed(const u8 **s, const u8 *s_len, 759 const ec_pub_key **pub_keys, 760 const u8 **m, const u32 *m_len, u32 num, 761 u8 p_len, u8 *seed, u32 seedlen) 762 { 763 int ret; 764 u32 i; 765 hash_context h_ctx; 766 u8 Pubx[NN_MAX_BYTE_LEN]; 767 const hash_mapping *hm; 768 769 /* NOTE: sanity checks on inputs are performed by the upper layer */ 770 771 ret = local_memset(Pubx, 0, sizeof(Pubx)); EG(ret, err); 772 773 /* Get our hash mapping for SHA-256 as we need a fixed 256-bit key 774 * for keying our ChaCha20 CSPRNG 775 */ 776 ret = get_hash_by_type(SHA256, &hm); EG(ret, err); 777 MUST_HAVE((hm != NULL), ret, err); 778 779 MUST_HAVE((seedlen == hm->digest_size), ret, err); 780 781 /* As per specification, seed = seed_hash(pk1..pku || m1..mu || sig1..sigu), instantiated 782 * with SHA-256 */ 783 ret = hm->hfunc_init(&h_ctx); EG(ret, err); 784 for(i = 0; i < num; i++){ 785 ret = fp_export_to_buf(&Pubx[0], p_len, &(pub_keys[i]->y.X)); EG(ret, err); 786 ret = hm->hfunc_update(&h_ctx, &Pubx[0], p_len); EG(ret, err); 787 } 788 for(i = 0; i < num; i++){ 789 ret = hm->hfunc_update(&h_ctx, m[i], m_len[i]); EG(ret, err); 790 } 791 for(i = 0; i < num; i++){ 792 ret = hm->hfunc_update(&h_ctx, s[i], s_len[i]); EG(ret, err); 793 } 794 ret = hm->hfunc_finalize(&h_ctx, seed); 795 796 err: 797 return ret; 798 } 799 800 /* Batch verification function: 801 * This function takes multiple signatures/messages/public keys, and 802 * checks in an optimized way all the signatures. 803 * 804 * This returns 0 if *all* the signatures are correct, and -1 if at least 805 * one signature is not correct. 806 * 807 */ 808 static int _bip0340_verify_batch_no_memory(const u8 **s, const u8 *s_len, const ec_pub_key **pub_keys, 809 const u8 **m, const u32 *m_len, u32 num, ec_alg_type sig_type, 810 hash_alg_type hash_type, const u8 **adata, const u16 *adata_len) 811 { 812 nn_src_t q = NULL; 813 prj_pt_src_t G = NULL; 814 prj_pt_t R = NULL, Y = NULL; 815 prj_pt Tmp, R_sum, P_sum; 816 nn S, S_sum, e, a; 817 fp rx; 818 u8 hash[MAX_DIGEST_SIZE]; 819 u8 Pubx[NN_MAX_BYTE_LEN]; 820 const ec_pub_key *pub_key, *pub_key0; 821 int ret, iszero, isodd, cmp; 822 prj_pt_src_t pub_key_y; 823 hash_context h_ctx; 824 const hash_mapping *hm; 825 ec_shortw_crv_src_t shortw_curve; 826 ec_alg_type key_type = UNKNOWN_ALG; 827 bitcnt_t p_bit_len, q_bit_len; 828 u8 p_len, q_len; 829 u16 hsize; 830 u32 i; 831 u8 chacha20_seed[SHA256_DIGEST_SIZE]; 832 u8 chacha20_scalar[BYTECEIL(CURVES_MAX_Q_BIT_LEN)]; 833 u32 chacha20_scalar_counter = 1; 834 835 Tmp.magic = R_sum.magic = P_sum.magic = WORD(0); 836 S.magic = S_sum.magic = e.magic = a.magic = WORD(0); 837 rx.magic = WORD(0); 838 839 FORCE_USED_VAR(adata_len); 840 FORCE_USED_VAR(adata); 841 842 /* First, some sanity checks */ 843 MUST_HAVE((s != NULL) && (pub_keys != NULL) && (m != NULL), ret, err); 844 /* We need at least one element in our batch data bags */ 845 MUST_HAVE((num > 0), ret, err); 846 847 /* Zeroize buffers */ 848 ret = local_memset(hash, 0, sizeof(hash)); EG(ret, err); 849 ret = local_memset(Pubx, 0, sizeof(Pubx)); EG(ret, err); 850 ret = local_memset(chacha20_seed, 0,sizeof(chacha20_seed)); EG(ret, err); 851 ret = local_memset(chacha20_scalar, 0,sizeof(chacha20_scalar)); EG(ret, err); 852 853 pub_key0 = pub_keys[0]; 854 MUST_HAVE((pub_key0 != NULL), ret, err); 855 856 /* Get our hash mapping */ 857 ret = get_hash_by_type(hash_type, &hm); EG(ret, err); 858 hsize = hm->digest_size; 859 MUST_HAVE((hm != NULL), ret, err); 860 861 for(i = 0; i < num; i++){ 862 u8 siglen; 863 const u8 *sig = NULL; 864 865 ret = pub_key_check_initialized_and_type(pub_keys[i], BIP0340); EG(ret, err); 866 867 /* Make things more readable */ 868 pub_key = pub_keys[i]; 869 870 /* Sanity check that all our public keys have the same parameters */ 871 MUST_HAVE((pub_key->params) == (pub_key0->params), ret, err); 872 873 q = &(pub_key->params->ec_gen_order); 874 shortw_curve = &(pub_key->params->ec_curve); 875 pub_key_y = &(pub_key->y); 876 key_type = pub_key->key_type; 877 G = &(pub_key->params->ec_gen); 878 p_bit_len = pub_key->params->ec_fp.p_bitlen; 879 q_bit_len = pub_key->params->ec_gen_order_bitlen; 880 p_len = (u8)BYTECEIL(p_bit_len); 881 q_len = (u8)BYTECEIL(q_bit_len); 882 883 /* Check given signature length is the expected one */ 884 siglen = s_len[i]; 885 sig = s[i]; 886 MUST_HAVE((siglen == BIP0340_SIGLEN(p_bit_len, q_bit_len)), ret, err); 887 MUST_HAVE((siglen == (BIP0340_R_LEN(p_bit_len) + BIP0340_S_LEN(q_bit_len))), ret, err); 888 889 /* Check the key type versus the algorithm */ 890 MUST_HAVE((key_type == sig_type), ret, err); 891 892 if(i == 0){ 893 /* Initialize our sums to zero/point at infinity */ 894 ret = nn_init(&S_sum, 0); EG(ret, err); 895 ret = prj_pt_init(&R_sum, shortw_curve); EG(ret, err); 896 ret = prj_pt_zero(&R_sum); EG(ret, err); 897 ret = prj_pt_init(&P_sum, shortw_curve); EG(ret, err); 898 ret = prj_pt_zero(&P_sum); EG(ret, err); 899 ret = prj_pt_init(&Tmp, shortw_curve); EG(ret, err); 900 ret = nn_init(&e, 0); EG(ret, err); 901 ret = nn_init(&a, 0); EG(ret, err); 902 /* Compute the ChaCha20 seed */ 903 ret = _bip0340_compute_batch_csprng_seed(s, s_len, pub_keys, m, m_len, num, 904 p_len, chacha20_seed, 905 sizeof(chacha20_seed)); EG(ret, err); 906 } 907 else{ 908 /* Get a pseudo-random scalar a for randomizing the linear combination */ 909 ret = _bip0340_compute_batch_csprng_scalars(chacha20_seed, sizeof(chacha20_seed), 910 chacha20_scalar, sizeof(chacha20_scalar), 911 &chacha20_scalar_counter, q, 912 q_bit_len, q_len, &a); EG(ret, err); 913 } 914 915 /***************************************************/ 916 /* Extract r and s */ 917 ret = fp_init(&rx, pub_key->params->ec_curve.a.ctx); EG(ret, err); 918 ret = fp_import_from_buf(&rx, &sig[0], p_len); EG(ret, err); 919 ret = nn_init_from_buf(&S, &sig[p_len], q_len); EG(ret, err); 920 ret = nn_cmp(&S, q, &cmp); EG(ret, err); 921 MUST_HAVE((cmp < 0), ret, err); 922 923 dbg_nn_print("r", &(rx.fp_val)); 924 dbg_nn_print("s", &S); 925 926 /***************************************************/ 927 /* Add S to the sum */ 928 /* Multiply S by a */ 929 if(i != 0){ 930 ret = nn_mod_mul(&S, &a, &S, q); EG(ret, err); 931 } 932 ret = nn_mod_add(&S_sum, &S_sum, &S, q); EG(ret, err); 933 934 /***************************************************/ 935 R = &Tmp; 936 /* Compute R from rx */ 937 ret = fp_copy(&(R->X), &rx); EG(ret, err); 938 ret = aff_pt_y_from_x(&(R->Y), &(R->Z), &rx, shortw_curve); EG(ret, err); 939 /* "Lift" R by choosing the even solution */ 940 ret = nn_isodd(&(R->Y.fp_val), &isodd); EG(ret, err); 941 if(isodd){ 942 ret = fp_copy(&(R->Y), &(R->Z)); EG(ret, err); 943 } 944 ret = fp_one(&(R->Z)); EG(ret, err); 945 /* Now multiply R by a */ 946 if(i != 0){ 947 ret = _prj_pt_unprotected_mult(R, &a, R); EG(ret, err); 948 } 949 /* Add to the sum */ 950 ret = prj_pt_add(&R_sum, &R_sum, R); EG(ret, err); 951 dbg_ec_point_print("aR", R); 952 953 /***************************************************/ 954 /* Compute P and add it to P_sum */ 955 Y = &Tmp; 956 /* Copy the public key point to work on the unique 957 * affine representative. 958 */ 959 ret = prj_pt_copy(Y, pub_key_y); EG(ret, err); 960 ret = prj_pt_unique(Y, Y); EG(ret, err); 961 /* Do we have to "lift" Y the public key ? */ 962 ret = nn_isodd(&(Y->Y.fp_val), &isodd); EG(ret, err); 963 if(isodd){ 964 /* If yes, negate the y coordinate */ 965 ret = fp_neg(&(Y->Y), &(Y->Y)); EG(ret, err); 966 } 967 dbg_ec_point_print("Y", Y); 968 /* Compute e */ 969 ret = _bip0340_hash((const u8*)BIP0340_CHALLENGE, sizeof(BIP0340_CHALLENGE) - 1, 970 &sig[0], p_len, hm, 971 &h_ctx); EG(ret, err); 972 ret = fp_export_to_buf(&Pubx[0], p_len, &(Y->X)); EG(ret, err); 973 ret = hm->hfunc_update(&h_ctx, &Pubx[0], p_len); EG(ret, err); 974 ret = hm->hfunc_update(&h_ctx, m[i], m_len[i]); EG(ret, err); 975 ret = hm->hfunc_finalize(&h_ctx, hash); EG(ret, err); 976 977 ret = nn_init_from_buf(&e, hash, hsize); EG(ret, err); 978 ret = nn_mod(&e, &e, q); EG(ret, err); 979 980 dbg_nn_print("e", &e); 981 982 /* Multiply e by 'a' */ 983 if(i != 0){ 984 ret = nn_mod_mul(&e, &e, &a, q); EG(ret, err); 985 } 986 ret = _prj_pt_unprotected_mult(Y, &e, Y); EG(ret, err); 987 dbg_ec_point_print("eY", Y); 988 /* Add to the sum */ 989 ret = prj_pt_add(&P_sum, &P_sum, Y); EG(ret, err); 990 } 991 992 /* Sanity check */ 993 MUST_HAVE((q != NULL) && (G != NULL), ret, err); 994 995 /* Compute S_sum * G */ 996 ret = nn_mod_neg(&S_sum, &S_sum, q); EG(ret, err); /* -S_sum = q - S_sum*/ 997 ret = _prj_pt_unprotected_mult(&Tmp, &S_sum, G); EG(ret, err); 998 /* Add P_sum and R_sum */ 999 ret = prj_pt_add(&Tmp, &Tmp, &R_sum); EG(ret, err); 1000 ret = prj_pt_add(&Tmp, &Tmp, &P_sum); EG(ret, err); 1001 /* The result should be point at infinity */ 1002 ret = prj_pt_iszero(&Tmp, &iszero); EG(ret, err); 1003 ret = (iszero == 1) ? 0 : -1; 1004 1005 err: 1006 PTR_NULLIFY(q); 1007 PTR_NULLIFY(pub_key); 1008 PTR_NULLIFY(pub_key0); 1009 PTR_NULLIFY(shortw_curve); 1010 PTR_NULLIFY(pub_key_y); 1011 PTR_NULLIFY(G); 1012 PTR_NULLIFY(R); 1013 PTR_NULLIFY(Y); 1014 1015 prj_pt_uninit(&R_sum); 1016 prj_pt_uninit(&P_sum); 1017 prj_pt_uninit(&Tmp); 1018 nn_uninit(&S); 1019 nn_uninit(&S_sum); 1020 nn_uninit(&e); 1021 nn_uninit(&a); 1022 fp_uninit(&rx); 1023 1024 return ret; 1025 } 1026 1027 static int _bip0340_verify_batch(const u8 **s, const u8 *s_len, const ec_pub_key **pub_keys, 1028 const u8 **m, const u32 *m_len, u32 num, ec_alg_type sig_type, 1029 hash_alg_type hash_type, const u8 **adata, const u16 *adata_len, 1030 verify_batch_scratch_pad *scratch_pad_area, u32 *scratch_pad_area_len) 1031 { 1032 nn_src_t q = NULL; 1033 prj_pt_src_t G = NULL; 1034 prj_pt_t R = NULL, Y = NULL; 1035 nn S, a; 1036 nn_t e = NULL; 1037 fp rx; 1038 u8 hash[MAX_DIGEST_SIZE]; 1039 u8 Pubx[NN_MAX_BYTE_LEN]; 1040 const ec_pub_key *pub_key, *pub_key0; 1041 int ret, iszero, isodd, cmp; 1042 prj_pt_src_t pub_key_y; 1043 hash_context h_ctx; 1044 const hash_mapping *hm; 1045 ec_shortw_crv_src_t shortw_curve; 1046 ec_alg_type key_type = UNKNOWN_ALG; 1047 bitcnt_t p_bit_len, q_bit_len = 0; 1048 u8 p_len, q_len; 1049 u16 hsize; 1050 u32 i; 1051 /* NN numbers and points pointers */ 1052 verify_batch_scratch_pad *elements = scratch_pad_area; 1053 u64 expected_len; 1054 u8 chacha20_seed[SHA256_DIGEST_SIZE]; 1055 u8 chacha20_scalar[BYTECEIL(CURVES_MAX_Q_BIT_LEN)]; 1056 u32 chacha20_scalar_counter = 1; 1057 1058 S.magic = a.magic = WORD(0); 1059 rx.magic = WORD(0); 1060 1061 FORCE_USED_VAR(adata_len); 1062 FORCE_USED_VAR(adata); 1063 1064 /* First, some sanity checks */ 1065 MUST_HAVE((s != NULL) && (pub_keys != NULL) && (m != NULL), ret, err); 1066 1067 MUST_HAVE((scratch_pad_area_len != NULL), ret, err); 1068 MUST_HAVE(((2 * num) >= num), ret, err); 1069 MUST_HAVE(((2 * num) + 1) >= num, ret, err); 1070 1071 /* Zeroize buffers */ 1072 ret = local_memset(hash, 0, sizeof(hash)); EG(ret, err); 1073 ret = local_memset(Pubx, 0, sizeof(Pubx)); EG(ret, err); 1074 ret = local_memset(chacha20_seed, 0,sizeof(chacha20_seed)); EG(ret, err); 1075 ret = local_memset(chacha20_scalar, 0,sizeof(chacha20_scalar)); EG(ret, err); 1076 1077 /* In oder to apply the algorithm, we must have at least two 1078 * elements to verify. If this is not the case, we fallback to 1079 * the regular "no memory" version. 1080 */ 1081 if(num <= 1){ 1082 if(scratch_pad_area == NULL){ 1083 /* We do not require any memory in this case */ 1084 (*scratch_pad_area_len) = 0; 1085 ret = 0; 1086 goto err; 1087 } 1088 else{ 1089 ret = _bip0340_verify_batch_no_memory(s, s_len, pub_keys, m, m_len, num, sig_type, 1090 hash_type, adata, adata_len); EG(ret, err); 1091 goto err; 1092 } 1093 } 1094 1095 expected_len = ((2 * num) + 1) * sizeof(verify_batch_scratch_pad); 1096 MUST_HAVE((expected_len < 0xffffffff), ret, err); 1097 1098 if(scratch_pad_area == NULL){ 1099 /* Return the needed size: we need to keep track of (2 * num) + 1 NN numbers 1100 * and (2 * num) + 1 projective points, plus (2 * num) + 1 indices 1101 */ 1102 (*scratch_pad_area_len) = (u32)expected_len; 1103 ret = 0; 1104 goto err; 1105 } 1106 else{ 1107 MUST_HAVE((*scratch_pad_area_len) >= expected_len, ret, err); 1108 } 1109 1110 pub_key0 = pub_keys[0]; 1111 MUST_HAVE((pub_key0 != NULL), ret, err); 1112 1113 /* Get our hash mapping */ 1114 ret = get_hash_by_type(hash_type, &hm); EG(ret, err); 1115 hsize = hm->digest_size; 1116 MUST_HAVE((hm != NULL), ret, err); 1117 1118 for(i = 0; i < num; i++){ 1119 u8 siglen; 1120 const u8 *sig = NULL; 1121 1122 ret = pub_key_check_initialized_and_type(pub_keys[i], BIP0340); EG(ret, err); 1123 1124 /* Make things more readable */ 1125 pub_key = pub_keys[i]; 1126 1127 /* Sanity check that all our public keys have the same parameters */ 1128 MUST_HAVE((pub_key->params) == (pub_key0->params), ret, err); 1129 1130 q = &(pub_key->params->ec_gen_order); 1131 shortw_curve = &(pub_key->params->ec_curve); 1132 pub_key_y = &(pub_key->y); 1133 key_type = pub_key->key_type; 1134 G = &(pub_key->params->ec_gen); 1135 p_bit_len = pub_key->params->ec_fp.p_bitlen; 1136 q_bit_len = pub_key->params->ec_gen_order_bitlen; 1137 p_len = (u8)BYTECEIL(p_bit_len); 1138 q_len = (u8)BYTECEIL(q_bit_len); 1139 1140 /* Check given signature length is the expected one */ 1141 siglen = s_len[i]; 1142 sig = s[i]; 1143 MUST_HAVE((siglen == BIP0340_SIGLEN(p_bit_len, q_bit_len)), ret, err); 1144 MUST_HAVE((siglen == (BIP0340_R_LEN(p_bit_len) + BIP0340_S_LEN(q_bit_len))), ret, err); 1145 1146 /* Check the key type versus the algorithm */ 1147 MUST_HAVE((key_type == sig_type), ret, err); 1148 1149 if(i == 0){ 1150 /* Initialize our sums to zero/point at infinity */ 1151 ret = nn_init(&a, 0); EG(ret, err); 1152 ret = nn_init(&elements[(2 * num)].number, 0); EG(ret, err); 1153 ret = prj_pt_copy(&elements[(2 * num)].point, G); EG(ret, err); 1154 /* Compute the ChaCha20 seed */ 1155 ret = _bip0340_compute_batch_csprng_seed(s, s_len, pub_keys, m, m_len, num, 1156 p_len, chacha20_seed, 1157 sizeof(chacha20_seed)); EG(ret, err); 1158 } 1159 else{ 1160 /* Get a pseudo-random scalar a for randomizing the linear combination */ 1161 ret = _bip0340_compute_batch_csprng_scalars(chacha20_seed, sizeof(chacha20_seed), 1162 chacha20_scalar, sizeof(chacha20_scalar), 1163 &chacha20_scalar_counter, q, 1164 q_bit_len, q_len, &a); EG(ret, err); 1165 } 1166 1167 /***************************************************/ 1168 /* Extract r and s */ 1169 ret = fp_init(&rx, pub_key->params->ec_curve.a.ctx); EG(ret, err); 1170 ret = fp_import_from_buf(&rx, &sig[0], p_len); EG(ret, err); 1171 ret = nn_init_from_buf(&S, &sig[p_len], q_len); EG(ret, err); 1172 ret = nn_cmp(&S, q, &cmp); EG(ret, err); 1173 MUST_HAVE((cmp < 0), ret, err); 1174 1175 dbg_nn_print("r", &(rx.fp_val)); 1176 dbg_nn_print("s", &S); 1177 1178 /***************************************************/ 1179 /* Add S to the sum */ 1180 /* Multiply S by a */ 1181 if(i != 0){ 1182 ret = nn_mod_mul(&S, &a, &S, q); EG(ret, err); 1183 } 1184 ret = nn_mod_add(&elements[(2 * num)].number, &elements[(2 * num)].number, 1185 &S, q); EG(ret, err); 1186 1187 /***************************************************/ 1188 /* Initialize R */ 1189 R = &elements[i].point; 1190 ret = prj_pt_init(R, shortw_curve); EG(ret, err); 1191 /* Compute R from rx */ 1192 ret = fp_copy(&(R->X), &rx); EG(ret, err); 1193 ret = aff_pt_y_from_x(&(R->Y), &(R->Z), &rx, shortw_curve); EG(ret, err); 1194 /* "Lift" R by choosing the even solution */ 1195 ret = nn_isodd(&(R->Y.fp_val), &isodd); EG(ret, err); 1196 if(isodd){ 1197 ret = fp_copy(&(R->Y), &(R->Z)); EG(ret, err); 1198 } 1199 ret = fp_one(&(R->Z)); EG(ret, err); 1200 1201 if(i != 0){ 1202 ret = nn_init(&elements[i].number, 0); EG(ret, err); 1203 ret = nn_copy(&elements[i].number, &a); EG(ret, err); 1204 } 1205 else{ 1206 ret = nn_init(&elements[i].number, 0); EG(ret, err); 1207 ret = nn_one(&elements[i].number); EG(ret, err); 1208 } 1209 dbg_ec_point_print("R", R); 1210 1211 /***************************************************/ 1212 /* Compute P and add it to P_sum */ 1213 Y = &elements[num + i].point; 1214 /* Copy the public key point to work on the unique 1215 * affine representative. 1216 */ 1217 ret = prj_pt_copy(Y, pub_key_y); EG(ret, err); 1218 ret = prj_pt_unique(Y, Y); EG(ret, err); 1219 /* Do we have to "lift" Y the public key ? */ 1220 ret = nn_isodd(&(Y->Y.fp_val), &isodd); EG(ret, err); 1221 if(isodd){ 1222 /* If yes, negate the y coordinate */ 1223 ret = fp_neg(&(Y->Y), &(Y->Y)); EG(ret, err); 1224 } 1225 dbg_ec_point_print("Y", Y); 1226 /* Compute e */ 1227 /* Store the coefficient */ 1228 e = &elements[num + i].number; 1229 ret = nn_init(e, 0); EG(ret, err); 1230 ret = _bip0340_hash((const u8*)BIP0340_CHALLENGE, sizeof(BIP0340_CHALLENGE) - 1, 1231 &sig[0], p_len, hm, 1232 &h_ctx); EG(ret, err); 1233 ret = fp_export_to_buf(&Pubx[0], p_len, &(Y->X)); EG(ret, err); 1234 ret = hm->hfunc_update(&h_ctx, &Pubx[0], p_len); EG(ret, err); 1235 ret = hm->hfunc_update(&h_ctx, m[i], m_len[i]); EG(ret, err); 1236 ret = hm->hfunc_finalize(&h_ctx, hash); EG(ret, err); 1237 1238 ret = nn_init_from_buf(e, hash, hsize); EG(ret, err); 1239 ret = nn_mod(e, e, q); EG(ret, err); 1240 1241 dbg_nn_print("e", e); 1242 1243 /* Multiply e by 'a' */ 1244 if(i != 0){ 1245 ret = nn_mod_mul(e, e, &a, q); EG(ret, err); 1246 } 1247 } 1248 1249 /* Sanity check */ 1250 MUST_HAVE((q != NULL) && (G != NULL) && (q_bit_len != 0), ret, err); 1251 1252 /********************************************/ 1253 /****** Bos-Coster algorithm ****************/ 1254 ret = ec_verify_bos_coster(elements, (2 * num) + 1, q_bit_len); 1255 if(ret){ 1256 if(ret == -2){ 1257 /* In case of Bos-Coster time out, we fall back to the 1258 * slower regular batch verification. 1259 */ 1260 ret = _bip0340_verify_batch_no_memory(s, s_len, pub_keys, m, m_len, num, sig_type, 1261 hash_type, adata, adata_len); EG(ret, err); 1262 } 1263 goto err; 1264 } 1265 1266 /* The first element should contain the sum: it should 1267 * be equal to zero. Reject the signature if this is not 1268 * the case. 1269 */ 1270 ret = prj_pt_iszero(&elements[elements[0].index].point, &iszero); EG(ret, err); 1271 ret = iszero ? 0 : -1; 1272 1273 err: 1274 PTR_NULLIFY(q); 1275 PTR_NULLIFY(e); 1276 PTR_NULLIFY(pub_key); 1277 PTR_NULLIFY(pub_key0); 1278 PTR_NULLIFY(shortw_curve); 1279 PTR_NULLIFY(pub_key_y); 1280 PTR_NULLIFY(G); 1281 PTR_NULLIFY(R); 1282 PTR_NULLIFY(Y); 1283 1284 /* Unitialize all our scratch_pad_area */ 1285 if((scratch_pad_area != NULL) && (scratch_pad_area_len != NULL)){ 1286 IGNORE_RET_VAL(local_memset((u8*)scratch_pad_area, 0, (*scratch_pad_area_len))); 1287 } 1288 1289 nn_uninit(&S); 1290 nn_uninit(&a); 1291 fp_uninit(&rx); 1292 1293 return ret; 1294 } 1295 1296 int bip0340_verify_batch(const u8 **s, const u8 *s_len, const ec_pub_key **pub_keys, 1297 const u8 **m, const u32 *m_len, u32 num, ec_alg_type sig_type, 1298 hash_alg_type hash_type, const u8 **adata, const u16 *adata_len, 1299 verify_batch_scratch_pad *scratch_pad_area, u32 *scratch_pad_area_len) 1300 { 1301 int ret; 1302 1303 if(scratch_pad_area != NULL){ 1304 MUST_HAVE((scratch_pad_area_len != NULL), ret, err); 1305 ret = _bip0340_verify_batch(s, s_len, pub_keys, m, m_len, num, sig_type, 1306 hash_type, adata, adata_len, 1307 scratch_pad_area, scratch_pad_area_len); EG(ret, err); 1308 1309 } 1310 else{ 1311 ret = _bip0340_verify_batch_no_memory(s, s_len, pub_keys, m, m_len, num, sig_type, 1312 hash_type, adata, adata_len); EG(ret, err); 1313 } 1314 1315 err: 1316 return ret; 1317 } 1318 1319 #else /* defined(WITH_SIG_BIP0340) */ 1320 1321 /* 1322 * Dummy definition to avoid the empty translation unit ISO C warning 1323 */ 1324 typedef int dummy; 1325 #endif /* defined(WITH_SIG_BIP0340) */ 1326