1 /* 2 * Copyright (C) 2017 - 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 * Jean-Pierre FLORI <jean-pierre.flori@ssi.gouv.fr> 8 * 9 * Contributors: 10 * Nicolas VIVET <nicolas.vivet@ssi.gouv.fr> 11 * Karim KHALFALLAH <karim.khalfallah@ssi.gouv.fr> 12 * 13 * This software is licensed under a dual BSD and GPL v2 license. 14 * See LICENSE file at the root folder of the project. 15 */ 16 #include <libecc/lib_ecc_config.h> 17 #ifdef WITH_SIG_ECFSDSA 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 "ECFSDSA" 28 #endif 29 #include <libecc/utils/dbg_sig.h> 30 31 int ecfsdsa_init_pub_key(ec_pub_key *out_pub, const ec_priv_key *in_priv) 32 { 33 int ret, cmp; 34 prj_pt_src_t G; 35 nn_src_t q; 36 37 MUST_HAVE((out_pub != NULL), ret, err); 38 39 /* Zero init public key to be generated */ 40 ret = local_memset(out_pub, 0, sizeof(ec_pub_key)); EG(ret, err); 41 42 ret = priv_key_check_initialized_and_type(in_priv, ECFSDSA); EG(ret, err); 43 q = &(in_priv->params->ec_gen_order); 44 45 /* Sanity check on key compliance */ 46 MUST_HAVE(!nn_cmp(&(in_priv->x), q, &cmp) && (cmp < 0), ret, err); 47 48 /* Y = xG */ 49 G = &(in_priv->params->ec_gen); 50 /* Use blinding when computing point scalar multiplication */ 51 ret = prj_pt_mul_blind(&(out_pub->y), &(in_priv->x), G); EG(ret, err); 52 53 out_pub->key_type = ECFSDSA; 54 out_pub->params = in_priv->params; 55 out_pub->magic = PUB_KEY_MAGIC; 56 57 err: 58 return ret; 59 } 60 61 int ecfsdsa_siglen(u16 p_bit_len, u16 q_bit_len, u8 hsize, u8 blocksize, u8 *siglen) 62 { 63 int ret; 64 65 MUST_HAVE((siglen != NULL), ret, err); 66 MUST_HAVE((p_bit_len <= CURVES_MAX_P_BIT_LEN) && 67 (q_bit_len <= CURVES_MAX_Q_BIT_LEN) && 68 (hsize <= MAX_DIGEST_SIZE) && (blocksize <= MAX_BLOCK_SIZE), ret, err); 69 (*siglen) = (u8)ECFSDSA_SIGLEN(p_bit_len, q_bit_len); 70 ret = 0; 71 72 err: 73 return ret; 74 } 75 76 /* 77 * Generic *internal* ECFSDSA signature functions (init, update and finalize). 78 * Their purpose is to allow passing a specific hash function (along with 79 * their output size) and the random ephemeral key k, so that compliance 80 * tests against test vectors can be made without ugly hack in the code 81 * itself. 82 * 83 * Global EC-FSDSA signature process is as follows (I,U,F provides 84 * information in which function(s) (init(), update() or finalize()) 85 * a specific step is performed): 86 * 87 *| IUF - ECFSDSA signature 88 *| 89 *| I 1. Get a random value k in ]0,q[ 90 *| I 2. Compute W = (W_x,W_y) = kG 91 *| I 3. Compute r = FE2OS(W_x)||FE2OS(W_y) 92 *| I 4. If r is an all zero string, restart the process at step 1. 93 *| IUF 5. Compute h = H(r||m) 94 *| F 6. Compute e = OS2I(h) mod q 95 *| F 7. Compute s = (k + ex) mod q 96 *| F 8. If s is 0, restart the process at step 1 (see c. below) 97 *| F 9. Return (r,s) 98 * 99 * Implementation notes: 100 * 101 * a) sig is built as the concatenation of r and s. r is encoded on 102 * 2*ceil(bitlen(p)) bytes and s on ceil(bitlen(q)) bytes. 103 * b) in EC-FSDSA, the public part of the key is not needed per se during 104 * the signature but - as it is needed in other signature algs implemented 105 * in the library - the whole key pair is passed instead of just the 106 * private key. 107 * c) Implementation of EC-FSDSA in an init()/update()/finalize() logic 108 * cannot be made deterministic, in the sense that if s is 0 at step 109 * 8 above, there is no way to restart the whole signature process 110 * w/o rehashing m. So, even if the event is extremely unlikely, 111 * signature process may fail to provide a signature of the data 112 * during finalize() call. 113 */ 114 115 #define ECFSDSA_SIGN_MAGIC ((word_t)(0x1ed9635924b48ddaULL)) 116 #define ECFSDSA_SIGN_CHECK_INITIALIZED(A, ret, err) \ 117 MUST_HAVE((((void *)(A)) != NULL) && \ 118 ((A)->magic == ECFSDSA_SIGN_MAGIC), ret, err) 119 120 int _ecfsdsa_sign_init(struct ec_sign_context *ctx) 121 { 122 prj_pt_src_t G; 123 nn_src_t q; 124 nn *k; 125 u8 *r; 126 prj_pt kG; 127 const ec_priv_key *priv_key; 128 bitcnt_t p_bit_len; 129 u8 i, p_len, r_len; 130 int ret; 131 kG.magic = WORD(0); 132 133 /* First, verify context has been initialized */ 134 ret = sig_sign_check_initialized(ctx); EG(ret, err); 135 136 /* Zero init points */ 137 ret = local_memset(&kG, 0, sizeof(prj_pt)); EG(ret, err); 138 139 /* Additional sanity checks on input params from context */ 140 ret = key_pair_check_initialized_and_type(ctx->key_pair, ECFSDSA); EG(ret, err); 141 MUST_HAVE((ctx->h != NULL) && (ctx->h->digest_size <= MAX_DIGEST_SIZE) && 142 (ctx->h->block_size <= MAX_BLOCK_SIZE), ret, err); 143 144 /* Make things more readable */ 145 priv_key = &(ctx->key_pair->priv_key); 146 G = &(priv_key->params->ec_gen); 147 q = &(priv_key->params->ec_gen_order); 148 r = ctx->sign_data.ecfsdsa.r; 149 k = &(ctx->sign_data.ecfsdsa.k); 150 p_bit_len = priv_key->params->ec_fp.p_bitlen; 151 MUST_HAVE(((u32)BYTECEIL(p_bit_len) <= NN_MAX_BYTE_LEN), ret, err); 152 p_len = (u8)BYTECEIL(p_bit_len); 153 r_len = (u8)ECFSDSA_R_LEN(p_bit_len); 154 155 dbg_nn_print("p", &(priv_key->params->ec_fp.p)); 156 dbg_nn_print("q", q); 157 dbg_priv_key_print("x", priv_key); 158 dbg_ec_point_print("G", G); 159 dbg_pub_key_print("Y", &(ctx->key_pair->pub_key)); 160 161 restart: 162 163 /* 1. Get a random value k in ]0,q[ */ 164 #ifdef NO_KNOWN_VECTORS 165 /* NOTE: when we do not need self tests for known vectors, 166 * we can be strict about random function handler! 167 * This allows us to avoid the corruption of such a pointer. 168 */ 169 /* Sanity check on the handler before calling it */ 170 MUST_HAVE((ctx->rand == nn_get_random_mod), ret, err); 171 #endif 172 MUST_HAVE((ctx->rand != NULL), ret, err); 173 ret = ctx->rand(k, q); EG(ret, err); 174 175 /* 2. Compute W = (W_x,W_y) = kG */ 176 #ifdef USE_SIG_BLINDING 177 /* We use blinding for the scalar multiplication */ 178 ret = prj_pt_mul_blind(&kG, k, G); EG(ret, err); 179 #else 180 ret = prj_pt_mul(&kG, k, G); EG(ret, err); 181 #endif 182 ret = prj_pt_unique(&kG, &kG); EG(ret, err); 183 184 dbg_nn_print("Wx", &(kG.X.fp_val)); 185 dbg_nn_print("Wy", &(kG.Y.fp_val)); 186 187 /* 3. Compute r = FE2OS(W_x)||FE2OS(W_y) */ 188 ret = fp_export_to_buf(r, p_len, &(kG.X)); EG(ret, err); 189 ret = fp_export_to_buf(r + p_len, p_len, &(kG.Y)); EG(ret, err); 190 dbg_buf_print("r: ", r, r_len); 191 192 /* 4. If r is an all zero string, restart the process at step 1. */ 193 ret = 0; 194 for (i = 0; i < r_len; i++) { 195 ret |= r[i]; 196 } 197 if (ret == 0) { 198 goto restart; 199 } 200 201 /* 5. Compute h = H(r||m). 202 * 203 * Note that we only start the hash work here by initializing the hash 204 * context and processing r. Message m will be handled during following 205 * update() calls. 206 */ 207 /* Since we call a callback, sanity check our mapping */ 208 ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err); 209 ret = ctx->h->hfunc_init(&(ctx->sign_data.ecfsdsa.h_ctx)); EG(ret, err); 210 /* Since we call a callback, sanity check our mapping */ 211 ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err); 212 ret = ctx->h->hfunc_update(&(ctx->sign_data.ecfsdsa.h_ctx), r, r_len); EG(ret, err); 213 214 ctx->sign_data.ecfsdsa.magic = ECFSDSA_SIGN_MAGIC; 215 216 err: 217 prj_pt_uninit(&kG); 218 219 PTR_NULLIFY(G); 220 PTR_NULLIFY(q); 221 PTR_NULLIFY(k); 222 PTR_NULLIFY(r); 223 PTR_NULLIFY(priv_key); 224 VAR_ZEROIFY(i); 225 VAR_ZEROIFY(p_len); 226 VAR_ZEROIFY(r_len); 227 228 return ret; 229 } 230 231 int _ecfsdsa_sign_update(struct ec_sign_context *ctx, 232 const u8 *chunk, u32 chunklen) 233 { 234 int ret; 235 236 /* 237 * First, verify context has been initialized and private 238 * part too. This guarantees the context is an ECFSDSA 239 * signature one and we do not update() or finalize() 240 * before init(). 241 */ 242 ret = sig_sign_check_initialized(ctx); EG(ret, err); 243 ECFSDSA_SIGN_CHECK_INITIALIZED(&(ctx->sign_data.ecfsdsa), ret, err); 244 245 /* 5. Compute h = H(r||m) */ 246 /* Since we call a callback, sanity check our mapping */ 247 ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err); 248 ret = ctx->h->hfunc_update(&(ctx->sign_data.ecfsdsa.h_ctx), chunk, chunklen); EG(ret, err); 249 250 err: 251 return ret; 252 } 253 254 int _ecfsdsa_sign_finalize(struct ec_sign_context *ctx, u8 *sig, u8 siglen) 255 { 256 nn_src_t q, x; 257 nn s, e, ex, *k; 258 const ec_priv_key *priv_key; 259 u8 e_buf[MAX_DIGEST_SIZE]; 260 bitcnt_t p_bit_len, q_bit_len; 261 u8 hsize, s_len, r_len; 262 int ret, iszero, cmp; 263 u8 *r; 264 265 #ifdef USE_SIG_BLINDING 266 /* b is the blinding mask */ 267 nn b, binv; 268 b.magic = binv.magic = WORD(0); 269 #endif /* USE_SIG_BLINDING */ 270 271 s.magic = e.magic = ex.magic = WORD(0); 272 273 /* 274 * First, verify context has been initialized and private 275 * part too. This guarantees the context is an ECFSDSA 276 * signature one and we do not finalize() before init(). 277 */ 278 ret = sig_sign_check_initialized(ctx); EG(ret, err); 279 ECFSDSA_SIGN_CHECK_INITIALIZED(&(ctx->sign_data.ecfsdsa), ret, err); 280 MUST_HAVE((sig != NULL), ret, err); 281 282 /* Make things more readable */ 283 priv_key = &(ctx->key_pair->priv_key); 284 q = &(priv_key->params->ec_gen_order); 285 x = &(priv_key->x); 286 p_bit_len = ctx->key_pair->priv_key.params->ec_fp.p_bitlen; 287 q_bit_len = ctx->key_pair->priv_key.params->ec_gen_order_bitlen; 288 k = &(ctx->sign_data.ecfsdsa.k); 289 r_len = (u8)ECFSDSA_R_LEN(p_bit_len); 290 s_len = (u8)ECFSDSA_S_LEN(q_bit_len); 291 hsize = ctx->h->digest_size; 292 r = ctx->sign_data.ecfsdsa.r; 293 294 /* Sanity check */ 295 ret = nn_cmp(x, q, &cmp); EG(ret, err); 296 /* This should not happen and means that our 297 * private key is not compliant! 298 */ 299 MUST_HAVE((cmp < 0), ret, err); 300 301 MUST_HAVE((siglen == ECFSDSA_SIGLEN(p_bit_len, q_bit_len)), ret, err); 302 303 #ifdef USE_SIG_BLINDING 304 ret = nn_get_random_mod(&b, q); EG(ret, err); 305 dbg_nn_print("b", &b); 306 #endif /* USE_SIG_BLINDING */ 307 308 /* Since we call a callback, sanity check our mapping */ 309 ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err); 310 /* 5. Compute h = H(r||m) */ 311 /* Since we call a callback, sanity check our mapping */ 312 ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err); 313 ret = ctx->h->hfunc_finalize(&(ctx->sign_data.ecfsdsa.h_ctx), e_buf); EG(ret, err); 314 dbg_buf_print("h(R||m)", e_buf, hsize); 315 316 /* 6. Compute e by converting h to an integer and reducing it mod q */ 317 ret = nn_init_from_buf(&e, e_buf, hsize); EG(ret, err); 318 ret = local_memset(e_buf, 0, hsize); EG(ret, err); 319 ret = nn_mod(&e, &e, q); EG(ret, err); 320 321 #ifdef USE_SIG_BLINDING 322 /* Blind e with b */ 323 ret = nn_mod_mul(&e, &e, &b, q); EG(ret, err); 324 #endif /* USE_SIG_BLINDING */ 325 /* 7. Compute s = (k + ex) mod q */ 326 ret = nn_mod_mul(&ex, &e, x, q); EG(ret, err); 327 #ifdef USE_SIG_BLINDING 328 /* Blind k with b */ 329 ret = nn_mod_mul(&s, k, &b, q); EG(ret, err); 330 ret = nn_mod_add(&s, &s, &ex, q); EG(ret, err); 331 #else 332 ret = nn_mod_add(&s, k, &ex, q); EG(ret, err); 333 #endif /* USE_SIG_BLINDING */ 334 #ifdef USE_SIG_BLINDING 335 /* Unblind s */ 336 /* NOTE: we use Fermat's little theorem inversion for 337 * constant time here. This is possible since q is prime. 338 */ 339 ret = nn_modinv_fermat(&binv, &b, q); EG(ret, err); 340 ret = nn_mod_mul(&s, &s, &binv, q); EG(ret, err); 341 #endif /* USE_SIG_BLINDING */ 342 dbg_nn_print("s: ", &s); 343 344 /* 345 * 8. If s is 0, restart the process at step 1. 346 * 347 * In practice, as we cannot restart the whole process in 348 * finalize() we just report an error. 349 */ 350 MUST_HAVE((!nn_iszero(&s, &iszero)) && (!iszero), ret, err); 351 352 /* 9. Return (r,s) */ 353 ret = local_memcpy(sig, r, r_len); EG(ret, err); 354 ret = local_memset(r, 0, r_len); EG(ret, err); 355 ret = nn_export_to_buf(sig + r_len, s_len, &s); 356 357 err: 358 nn_uninit(&s); 359 nn_uninit(&e); 360 nn_uninit(&ex); 361 #ifdef USE_SIG_BLINDING 362 nn_uninit(&b); 363 nn_uninit(&binv); 364 #endif 365 366 /* 367 * We can now clear data part of the context. This will clear 368 * magic and avoid further reuse of the whole context. 369 */ 370 if(ctx != NULL){ 371 IGNORE_RET_VAL(local_memset(&(ctx->sign_data.ecfsdsa), 0, sizeof(ecfsdsa_sign_data))); 372 } 373 374 PTR_NULLIFY(q); 375 PTR_NULLIFY(x); 376 PTR_NULLIFY(k); 377 PTR_NULLIFY(priv_key); 378 PTR_NULLIFY(r); 379 VAR_ZEROIFY(hsize); 380 VAR_ZEROIFY(p_bit_len); 381 VAR_ZEROIFY(q_bit_len); 382 VAR_ZEROIFY(r_len); 383 VAR_ZEROIFY(s_len); 384 385 return ret; 386 } 387 388 /* 389 * Generic *internal* ECFSDSA verification functions (init, update and 390 * finalize). Their purpose is to allow passing a specific hash function 391 * (along with their output size) and the random ephemeral key k, so 392 * that compliance tests against test vectors can be made without ugly 393 * hack in the code itself. 394 * 395 * Global EC-FSDSA verification process is as follows (I,U,F provides 396 * information in which function(s) (init(), update() or finalize()) 397 * a specific step is performed): 398 * 399 *| IUF - ECFSDSA verification 400 *| 401 *| I 1. Reject the signature if r is not a valid point on the curve. 402 *| I 2. Reject the signature if s is not in ]0,q[ 403 *| IUF 3. Compute h = H(r||m) 404 *| F 4. Convert h to an integer and then compute e = -h mod q 405 *| F 5. compute W' = sG + eY, where Y is the public key 406 *| F 6. Compute r' = FE2OS(W'_x)||FE2OS(W'_y) 407 *| F 7. Accept the signature if and only if r equals r' 408 * 409 */ 410 411 #define ECFSDSA_VERIFY_MAGIC ((word_t)(0x26afb13ccd96fa04ULL)) 412 #define ECFSDSA_VERIFY_CHECK_INITIALIZED(A, ret, err) \ 413 MUST_HAVE((((void *)(A)) != NULL) && \ 414 ((A)->magic == ECFSDSA_VERIFY_MAGIC), ret, err) 415 416 int _ecfsdsa_verify_init(struct ec_verify_context *ctx, 417 const u8 *sig, u8 siglen) 418 { 419 bitcnt_t p_bit_len, q_bit_len; 420 u8 p_len, r_len, s_len; 421 int ret, iszero, on_curve, cmp; 422 const u8 *r; 423 nn_src_t q; 424 fp rx, ry; 425 nn *s; 426 427 rx.magic = ry.magic = WORD(0); 428 429 /* First, verify context has been initialized */ 430 ret = sig_verify_check_initialized(ctx); EG(ret, err); 431 432 /* Do some sanity checks on input params */ 433 ret = pub_key_check_initialized_and_type(ctx->pub_key, ECFSDSA); EG(ret, err); 434 MUST_HAVE((ctx->h != NULL) && (ctx->h->digest_size <= MAX_DIGEST_SIZE) && 435 (ctx->h->block_size <= MAX_BLOCK_SIZE), ret, err); 436 MUST_HAVE((sig != NULL), ret, err); 437 438 /* Make things more readable */ 439 q = &(ctx->pub_key->params->ec_gen_order); 440 p_bit_len = ctx->pub_key->params->ec_fp.p_bitlen; 441 q_bit_len = ctx->pub_key->params->ec_gen_order_bitlen; 442 p_len = (u8)BYTECEIL(p_bit_len); 443 r_len = (u8)ECFSDSA_R_LEN(p_bit_len); 444 s_len = (u8)ECFSDSA_S_LEN(q_bit_len); 445 s = &(ctx->verify_data.ecfsdsa.s); 446 447 MUST_HAVE((siglen == ECFSDSA_SIGLEN(p_bit_len, q_bit_len)), ret, err); 448 449 /* 1. Reject the signature if r is not a valid point on the curve. */ 450 451 /* Let's first import r, i.e. x and y coordinates of the point */ 452 r = sig; 453 ret = fp_init(&rx, ctx->pub_key->params->ec_curve.a.ctx); EG(ret, err); 454 ret = fp_import_from_buf(&rx, r, p_len); EG(ret, err); 455 ret = fp_init(&ry, ctx->pub_key->params->ec_curve.a.ctx); EG(ret, err); 456 ret = fp_import_from_buf(&ry, r + p_len, p_len); EG(ret, err); 457 458 /* Let's now check that r represents a point on the curve */ 459 ret = is_on_shortw_curve(&rx, &ry, &(ctx->pub_key->params->ec_curve), &on_curve); EG(ret, err); 460 MUST_HAVE(on_curve, ret, err); 461 462 /* 2. Reject the signature if s is not in ]0,q[ */ 463 464 /* Import s as a nn */ 465 ret = nn_init_from_buf(s, sig + r_len, s_len); EG(ret, err); 466 467 /* Check that s is in ]0,q[ */ 468 ret = nn_iszero(s, &iszero); EG(ret, err); 469 ret = nn_cmp(s, q, &cmp); EG(ret, err); 470 MUST_HAVE((!iszero) && (cmp < 0), ret, err); 471 472 /* 3. Compute h = H(r||m) */ 473 474 /* Initialize the verify context */ 475 ret = local_memcpy(&(ctx->verify_data.ecfsdsa.r), r, r_len); EG(ret, err); 476 /* Since we call a callback, sanity check our mapping */ 477 ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err); 478 ret = ctx->h->hfunc_init(&(ctx->verify_data.ecfsdsa.h_ctx)); EG(ret, err); 479 480 /* Since we call a callback, sanity check our mapping */ 481 ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err); 482 ret = ctx->h->hfunc_update(&(ctx->verify_data.ecfsdsa.h_ctx), r, r_len); EG(ret, err); 483 484 ctx->verify_data.ecfsdsa.magic = ECFSDSA_VERIFY_MAGIC; 485 486 err: 487 fp_uninit(&rx); 488 fp_uninit(&ry); 489 490 if (ret && (ctx != NULL)) { 491 /* 492 * Signature is invalid. Clear data part of the context. 493 * This will clear magic and avoid further reuse of the 494 * whole context. 495 */ 496 IGNORE_RET_VAL(local_memset(&(ctx->verify_data.ecfsdsa), 0, 497 sizeof(ecfsdsa_verify_data))); 498 } 499 500 VAR_ZEROIFY(p_len); 501 VAR_ZEROIFY(r_len); 502 VAR_ZEROIFY(s_len); 503 VAR_ZEROIFY(p_bit_len); 504 VAR_ZEROIFY(q_bit_len); 505 PTR_NULLIFY(r); 506 PTR_NULLIFY(q); 507 PTR_NULLIFY(s); 508 509 return ret; 510 } 511 512 int _ecfsdsa_verify_update(struct ec_verify_context *ctx, 513 const u8 *chunk, u32 chunklen) 514 { 515 int ret; 516 517 /* 518 * First, verify context has been initialized and public 519 * part too. This guarantees the context is an ECFSDSA 520 * verification one and we do not update() or finalize() 521 * before init(). 522 */ 523 ret = sig_verify_check_initialized(ctx); EG(ret, err); 524 ECFSDSA_VERIFY_CHECK_INITIALIZED(&(ctx->verify_data.ecfsdsa), ret, err); 525 526 /* 3. Compute h = H(r||m) */ 527 /* Since we call a callback, sanity check our mapping */ 528 ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err); 529 ret = ctx->h->hfunc_update(&(ctx->verify_data.ecfsdsa.h_ctx), chunk, 530 chunklen); 531 532 err: 533 return ret; 534 } 535 536 int _ecfsdsa_verify_finalize(struct ec_verify_context *ctx) 537 { 538 prj_pt_src_t G, Y; 539 nn_src_t q; 540 nn tmp, e, *s; 541 prj_pt sG, eY; 542 prj_pt_t Wprime; 543 bitcnt_t p_bit_len, r_len; 544 u8 r_prime[2 * NN_MAX_BYTE_LEN]; 545 u8 e_buf[MAX_DIGEST_SIZE]; 546 u8 hsize, p_len; 547 const u8 *r; 548 int ret, check; 549 550 tmp.magic = e.magic = WORD(0); 551 sG.magic = eY.magic = WORD(0); 552 553 /* NOTE: we reuse sG for Wprime to optimize local variables */ 554 Wprime = &sG; 555 556 /* 557 * First, verify context has been initialized and public 558 * part too. This guarantees the context is an ECFSDSA 559 * verification one and we do not finalize() before init(). 560 */ 561 ret = sig_verify_check_initialized(ctx); EG(ret, err); 562 ECFSDSA_VERIFY_CHECK_INITIALIZED(&(ctx->verify_data.ecfsdsa), ret, err); 563 564 /* Zero init points */ 565 ret = local_memset(&sG, 0, sizeof(prj_pt)); EG(ret, err); 566 ret = local_memset(&eY, 0, sizeof(prj_pt)); EG(ret, err); 567 568 /* Make things more readable */ 569 G = &(ctx->pub_key->params->ec_gen); 570 Y = &(ctx->pub_key->y); 571 q = &(ctx->pub_key->params->ec_gen_order); 572 hsize = ctx->h->digest_size; 573 s = &(ctx->verify_data.ecfsdsa.s); 574 r = ctx->verify_data.ecfsdsa.r; 575 p_bit_len = ctx->pub_key->params->ec_fp.p_bitlen; 576 p_len = (u8)BYTECEIL(p_bit_len); 577 r_len = (u8)ECFSDSA_R_LEN(p_bit_len); 578 579 /* 3. Compute h = H(r||m) */ 580 /* Since we call a callback, sanity check our mapping */ 581 ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err); 582 ret = ctx->h->hfunc_finalize(&(ctx->verify_data.ecfsdsa.h_ctx), e_buf); EG(ret, err); 583 584 /* 585 * 4. Convert h to an integer and then compute e = -h mod q 586 * 587 * Because we only support positive integers, we compute 588 * e = q - (h mod q) (except when h is 0). 589 */ 590 ret = nn_init_from_buf(&tmp, e_buf, hsize); EG(ret, err); 591 ret = local_memset(e_buf, 0, hsize); EG(ret, err); 592 ret = nn_mod(&tmp, &tmp, q); EG(ret, err); 593 594 ret = nn_mod_neg(&e, &tmp, q); EG(ret, err); 595 596 /* 5. compute W' = (W'_x,W'_y) = sG + tY, where Y is the public key */ 597 ret = prj_pt_mul(&sG, s, G); EG(ret, err); 598 ret = prj_pt_mul(&eY, &e, Y); EG(ret, err); 599 ret = prj_pt_add(Wprime, &sG, &eY); EG(ret, err); 600 ret = prj_pt_unique(Wprime, Wprime); EG(ret, err); 601 602 /* 6. Compute r' = FE2OS(W'_x)||FE2OS(W'_y) */ 603 ret = fp_export_to_buf(r_prime, p_len, &(Wprime->X)); EG(ret, err); 604 ret = fp_export_to_buf(r_prime + p_len, p_len, &(Wprime->Y)); EG(ret, err); 605 606 dbg_buf_print("r_prime: ", r_prime, r_len); 607 608 /* 7. Accept the signature if and only if r equals r' */ 609 ret = are_equal(r, r_prime, r_len, &check); EG(ret, err); 610 ret = check ? 0 : -1; 611 612 err: 613 IGNORE_RET_VAL(local_memset(r_prime, 0, sizeof(r_prime))); 614 615 nn_uninit(&tmp); 616 nn_uninit(&e); 617 prj_pt_uninit(&sG); 618 prj_pt_uninit(&eY); 619 620 /* 621 * We can now clear data part of the context. This will clear 622 * magic and avoid further reuse of the whole context. 623 */ 624 if(ctx != NULL){ 625 IGNORE_RET_VAL(local_memset(&(ctx->verify_data.ecfsdsa), 0, 626 sizeof(ecfsdsa_verify_data))); 627 } 628 629 /* Clean what remains on the stack */ 630 PTR_NULLIFY(Wprime); 631 PTR_NULLIFY(G); 632 PTR_NULLIFY(Y); 633 PTR_NULLIFY(q); 634 PTR_NULLIFY(s); 635 PTR_NULLIFY(r); 636 VAR_ZEROIFY(p_len); 637 VAR_ZEROIFY(r_len); 638 VAR_ZEROIFY(hsize); 639 640 return ret; 641 } 642 643 /* 644 * NOTE: among all the EC-SDSA ISO14888-3 variants, only EC-FSDSA supports 645 * batch verification as it is the only one allowing the recovery of the 646 * underlying signature point from the signature value (other variants make 647 * use of a hash of (parts) of this point. 648 */ 649 /* Batch verification function: 650 * This function takes multiple signatures/messages/public keys, and 651 * checks in an optimized way all the signatures. 652 * 653 * This returns 0 if *all* the signatures are correct, and -1 if at least 654 * one signature is not correct. 655 * 656 */ 657 static int _ecfsdsa_verify_batch_no_memory(const u8 **s, const u8 *s_len, const ec_pub_key **pub_keys, 658 const u8 **m, const u32 *m_len, u32 num, ec_alg_type sig_type, 659 hash_alg_type hash_type, const u8 **adata, const u16 *adata_len) 660 { 661 nn_src_t q = NULL; 662 prj_pt_src_t G = NULL; 663 prj_pt_t W = NULL, Y = NULL; 664 prj_pt Tmp, W_sum, Y_sum; 665 nn S, S_sum, e, a; 666 u8 hash[MAX_DIGEST_SIZE]; 667 const ec_pub_key *pub_key, *pub_key0; 668 int ret, iszero, cmp; 669 prj_pt_src_t pub_key_y; 670 hash_context h_ctx; 671 const hash_mapping *hm; 672 ec_shortw_crv_src_t shortw_curve; 673 ec_alg_type key_type = UNKNOWN_ALG; 674 bitcnt_t p_bit_len, q_bit_len; 675 u8 p_len, q_len; 676 u16 hsize; 677 u32 i; 678 679 Tmp.magic = W_sum.magic = Y_sum.magic = WORD(0); 680 S.magic = S_sum.magic = e.magic = a.magic = WORD(0); 681 682 FORCE_USED_VAR(adata_len); 683 FORCE_USED_VAR(adata); 684 685 /* First, some sanity checks */ 686 MUST_HAVE((s != NULL) && (pub_keys != NULL) && (m != NULL), ret, err); 687 /* We need at least one element in our batch data bags */ 688 MUST_HAVE((num > 0), ret, err); 689 690 /* Zeroize buffers */ 691 ret = local_memset(hash, 0, sizeof(hash)); EG(ret, err); 692 693 pub_key0 = pub_keys[0]; 694 MUST_HAVE((pub_key0 != NULL), ret, err); 695 696 /* Get our hash mapping */ 697 ret = get_hash_by_type(hash_type, &hm); EG(ret, err); 698 hsize = hm->digest_size; 699 MUST_HAVE((hm != NULL), ret, err); 700 701 for(i = 0; i < num; i++){ 702 u8 siglen; 703 const u8 *sig = NULL; 704 705 ret = pub_key_check_initialized_and_type(pub_keys[i], ECFSDSA); EG(ret, err); 706 707 /* Make things more readable */ 708 pub_key = pub_keys[i]; 709 710 /* Sanity check that all our public keys have the same parameters */ 711 MUST_HAVE((pub_key->params) == (pub_key0->params), ret, err); 712 713 q = &(pub_key->params->ec_gen_order); 714 shortw_curve = &(pub_key->params->ec_curve); 715 pub_key_y = &(pub_key->y); 716 key_type = pub_key->key_type; 717 G = &(pub_key->params->ec_gen); 718 p_bit_len = pub_key->params->ec_fp.p_bitlen; 719 q_bit_len = pub_key->params->ec_gen_order_bitlen; 720 p_len = (u8)BYTECEIL(p_bit_len); 721 q_len = (u8)BYTECEIL(q_bit_len); 722 723 /* Check given signature length is the expected one */ 724 siglen = s_len[i]; 725 sig = s[i]; 726 MUST_HAVE((siglen == ECFSDSA_SIGLEN(p_bit_len, q_bit_len)), ret, err); 727 MUST_HAVE((siglen == (ECFSDSA_R_LEN(p_bit_len) + ECFSDSA_S_LEN(q_bit_len))), ret, err); 728 729 /* Check the key type versus the algorithm */ 730 MUST_HAVE((key_type == sig_type), ret, err); 731 732 if(i == 0){ 733 /* Initialize our sums to zero/point at infinity */ 734 ret = nn_init(&S_sum, 0); EG(ret, err); 735 ret = prj_pt_init(&W_sum, shortw_curve); EG(ret, err); 736 ret = prj_pt_zero(&W_sum); EG(ret, err); 737 ret = prj_pt_init(&Y_sum, shortw_curve); EG(ret, err); 738 ret = prj_pt_zero(&Y_sum); EG(ret, err); 739 ret = prj_pt_init(&Tmp, shortw_curve); EG(ret, err); 740 ret = nn_init(&e, 0); EG(ret, err); 741 ret = nn_init(&a, 0); EG(ret, err); 742 } 743 744 /* Get a pseudo-random scalar a for randomizing the linear combination */ 745 ret = nn_get_random_mod(&a, q); EG(ret, err); 746 747 /***************************************************/ 748 /* Extract s */ 749 ret = nn_init_from_buf(&S, &sig[2 * p_len], q_len); EG(ret, err); 750 ret = nn_cmp(&S, q, &cmp); EG(ret, err); 751 MUST_HAVE((cmp < 0), ret, err); 752 753 dbg_nn_print("s", &S); 754 755 /***************************************************/ 756 /* Add S to the sum */ 757 /* Multiply S by a */ 758 ret = nn_mod_mul(&S, &a, &S, q); EG(ret, err); 759 ret = nn_mod_add(&S_sum, &S_sum, 760 &S, q); EG(ret, err); 761 762 /***************************************************/ 763 /* Compute Y and add it to Y_sum */ 764 Y = &Tmp; 765 /* Copy the public key point to work on the unique 766 * affine representative. 767 */ 768 ret = prj_pt_copy(Y, pub_key_y); EG(ret, err); 769 ret = prj_pt_unique(Y, Y); EG(ret, err); 770 dbg_ec_point_print("Y", Y); 771 772 /* Compute e */ 773 ret = hm->hfunc_init(&h_ctx); EG(ret, err); 774 ret = hm->hfunc_update(&h_ctx, &sig[0], (u32)(2 * p_len)); EG(ret, err); 775 ret = hm->hfunc_update(&h_ctx, m[i], m_len[i]); EG(ret, err); 776 ret = hm->hfunc_finalize(&h_ctx, hash); EG(ret, err); 777 778 ret = nn_init_from_buf(&e, hash, hsize); EG(ret, err); 779 ret = nn_mod(&e, &e, q); EG(ret, err); 780 ret = nn_mod_neg(&e, &e, q); EG(ret, err); 781 782 dbg_nn_print("e", &e); 783 784 /* Multiply e by 'a' */ 785 ret = nn_mod_mul(&e, &e, &a, q); EG(ret, err); 786 787 ret = _prj_pt_unprotected_mult(Y, &e, Y); EG(ret, err); 788 dbg_ec_point_print("eY", Y); 789 /* Add to the sum */ 790 ret = prj_pt_add(&Y_sum, &Y_sum, Y); EG(ret, err); 791 792 /***************************************************/ 793 W = &Tmp; 794 /* Compute W from rx and ry */ 795 ret = prj_pt_import_from_aff_buf(W, &sig[0], (u16)(2 * p_len), shortw_curve); EG(ret, err); 796 797 /* Now multiply W by -a */ 798 ret = nn_mod_neg(&a, &a, q); EG(ret, err); 799 ret = _prj_pt_unprotected_mult(W, &a, W); EG(ret, err); 800 801 /* Add to the sum */ 802 ret = prj_pt_add(&W_sum, &W_sum, W); EG(ret, err); 803 dbg_ec_point_print("aW", W); 804 } 805 /* Sanity check */ 806 MUST_HAVE((q != NULL) && (G != NULL), ret, err); 807 808 /* Compute S_sum * G */ 809 ret = _prj_pt_unprotected_mult(&Tmp, &S_sum, G); EG(ret, err); 810 /* Add P_sum and R_sum */ 811 ret = prj_pt_add(&Tmp, &Tmp, &W_sum); EG(ret, err); 812 ret = prj_pt_add(&Tmp, &Tmp, &Y_sum); EG(ret, err); 813 /* The result should be point at infinity */ 814 ret = prj_pt_iszero(&Tmp, &iszero); EG(ret, err); 815 ret = (iszero == 1) ? 0 : -1; 816 817 err: 818 PTR_NULLIFY(q); 819 PTR_NULLIFY(pub_key); 820 PTR_NULLIFY(pub_key0); 821 PTR_NULLIFY(shortw_curve); 822 PTR_NULLIFY(pub_key_y); 823 PTR_NULLIFY(G); 824 PTR_NULLIFY(W); 825 PTR_NULLIFY(Y); 826 827 prj_pt_uninit(&W_sum); 828 prj_pt_uninit(&Y_sum); 829 prj_pt_uninit(&Tmp); 830 nn_uninit(&S); 831 nn_uninit(&S_sum); 832 nn_uninit(&e); 833 nn_uninit(&a); 834 835 return ret; 836 } 837 838 839 static int _ecfsdsa_verify_batch(const u8 **s, const u8 *s_len, const ec_pub_key **pub_keys, 840 const u8 **m, const u32 *m_len, u32 num, ec_alg_type sig_type, 841 hash_alg_type hash_type, const u8 **adata, const u16 *adata_len, 842 verify_batch_scratch_pad *scratch_pad_area, u32 *scratch_pad_area_len) 843 { 844 nn_src_t q = NULL; 845 prj_pt_src_t G = NULL; 846 prj_pt_t W = NULL, Y = NULL; 847 nn S, a; 848 nn_t e = NULL; 849 u8 hash[MAX_DIGEST_SIZE]; 850 const ec_pub_key *pub_key, *pub_key0; 851 int ret, iszero, cmp; 852 prj_pt_src_t pub_key_y; 853 hash_context h_ctx; 854 const hash_mapping *hm; 855 ec_shortw_crv_src_t shortw_curve; 856 ec_alg_type key_type = UNKNOWN_ALG; 857 bitcnt_t p_bit_len, q_bit_len = 0; 858 u8 p_len, q_len; 859 u16 hsize; 860 u32 i; 861 /* NN numbers and points pointers */ 862 verify_batch_scratch_pad *elements = scratch_pad_area; 863 u64 expected_len; 864 865 S.magic = a.magic = WORD(0); 866 867 FORCE_USED_VAR(adata_len); 868 FORCE_USED_VAR(adata); 869 870 /* First, some sanity checks */ 871 MUST_HAVE((s != NULL) && (pub_keys != NULL) && (m != NULL), ret, err); 872 873 MUST_HAVE((scratch_pad_area_len != NULL), ret, err); 874 MUST_HAVE(((2 * num) >= num), ret, err); 875 MUST_HAVE(((2 * num) + 1) >= num, ret, err); 876 877 /* Zeroize buffers */ 878 ret = local_memset(hash, 0, sizeof(hash)); EG(ret, err); 879 880 /* In oder to apply the algorithm, we must have at least two 881 * elements to verify. If this is not the case, we fallback to 882 * the regular "no memory" version. 883 */ 884 if(num <= 1){ 885 if(scratch_pad_area == NULL){ 886 /* We do not require any memory in this case */ 887 (*scratch_pad_area_len) = 0; 888 ret = 0; 889 goto err; 890 } 891 else{ 892 ret = _ecfsdsa_verify_batch_no_memory(s, s_len, pub_keys, m, m_len, num, sig_type, 893 hash_type, adata, adata_len); 894 goto err; 895 } 896 } 897 898 expected_len = ((2 * num) + 1) * sizeof(verify_batch_scratch_pad); 899 MUST_HAVE((expected_len < 0xffffffff), ret, err); 900 901 if(scratch_pad_area == NULL){ 902 /* Return the needed size: we need to keep track of (2 * num) + 1 NN numbers 903 * and (2 * num) + 1 projective points, plus (2 * num) + 1 indices 904 */ 905 (*scratch_pad_area_len) = (u32)expected_len; 906 ret = 0; 907 goto err; 908 } 909 else{ 910 MUST_HAVE((*scratch_pad_area_len) >= expected_len, ret, err); 911 } 912 913 pub_key0 = pub_keys[0]; 914 MUST_HAVE((pub_key0 != NULL), ret, err); 915 916 /* Get our hash mapping */ 917 ret = get_hash_by_type(hash_type, &hm); EG(ret, err); 918 hsize = hm->digest_size; 919 MUST_HAVE((hm != NULL), ret, err); 920 921 for(i = 0; i < num; i++){ 922 u8 siglen; 923 const u8 *sig = NULL; 924 925 ret = pub_key_check_initialized_and_type(pub_keys[i], ECFSDSA); EG(ret, err); 926 927 /* Make things more readable */ 928 pub_key = pub_keys[i]; 929 930 /* Sanity check that all our public keys have the same parameters */ 931 MUST_HAVE((pub_key->params) == (pub_key0->params), ret, err); 932 933 q = &(pub_key->params->ec_gen_order); 934 shortw_curve = &(pub_key->params->ec_curve); 935 pub_key_y = &(pub_key->y); 936 key_type = pub_key->key_type; 937 G = &(pub_key->params->ec_gen); 938 p_bit_len = pub_key->params->ec_fp.p_bitlen; 939 q_bit_len = pub_key->params->ec_gen_order_bitlen; 940 p_len = (u8)BYTECEIL(p_bit_len); 941 q_len = (u8)BYTECEIL(q_bit_len); 942 943 /* Check given signature length is the expected one */ 944 siglen = s_len[i]; 945 sig = s[i]; 946 MUST_HAVE((siglen == ECFSDSA_SIGLEN(p_bit_len, q_bit_len)), ret, err); 947 MUST_HAVE((siglen == (ECFSDSA_R_LEN(p_bit_len) + ECFSDSA_S_LEN(q_bit_len))), ret, err); 948 949 /* Check the key type versus the algorithm */ 950 MUST_HAVE((key_type == sig_type), ret, err); 951 952 if(i == 0){ 953 /* Initialize our sums to zero/point at infinity */ 954 ret = nn_init(&a, 0); EG(ret, err); 955 ret = nn_init(&elements[(2 * num)].number, 0); EG(ret, err); 956 ret = prj_pt_copy(&elements[(2 * num)].point, G); EG(ret, err); 957 } 958 959 /* Get a pseudo-random scalar a for randomizing the linear combination */ 960 ret = nn_get_random_mod(&a, q); EG(ret, err); 961 962 /***************************************************/ 963 /* Extract s */ 964 ret = nn_init_from_buf(&S, &sig[2 * p_len], q_len); EG(ret, err); 965 ret = nn_cmp(&S, q, &cmp); EG(ret, err); 966 MUST_HAVE((cmp < 0), ret, err); 967 968 dbg_nn_print("s", &S); 969 970 /***************************************************/ 971 /* Add S to the sum */ 972 /* Multiply S by a */ 973 ret = nn_mod_mul(&S, &a, &S, q); EG(ret, err); 974 ret = nn_mod_add(&elements[(2 * num)].number, &elements[(2 * num)].number, 975 &S, q); EG(ret, err); 976 977 /***************************************************/ 978 /* Compute Y */ 979 Y = &elements[num + i].point; 980 /* Copy the public key point to work on the unique 981 * affine representative. 982 */ 983 ret = prj_pt_copy(Y, pub_key_y); EG(ret, err); 984 ret = prj_pt_unique(Y, Y); EG(ret, err); 985 dbg_ec_point_print("Y", Y); 986 987 /* Compute e */ 988 e = &elements[num + i].number; 989 ret = nn_init(e, 0); EG(ret, err); 990 ret = hm->hfunc_init(&h_ctx); EG(ret, err); 991 ret = hm->hfunc_update(&h_ctx, &sig[0], (u32)(2 * p_len)); EG(ret, err); 992 ret = hm->hfunc_update(&h_ctx, m[i], m_len[i]); EG(ret, err); 993 ret = hm->hfunc_finalize(&h_ctx, hash); EG(ret, err); 994 995 ret = nn_init_from_buf(e, hash, hsize); EG(ret, err); 996 ret = nn_mod(e, e, q); EG(ret, err); 997 ret = nn_mod_neg(e, e, q); EG(ret, err); 998 999 dbg_nn_print("e", e); 1000 1001 /* Multiply e by 'a' */ 1002 ret = nn_mod_mul(e, e, &a, q); EG(ret, err); 1003 1004 /***************************************************/ 1005 W = &elements[i].point; 1006 /* Compute W from rx and ry */ 1007 ret = prj_pt_import_from_aff_buf(W, &sig[0], (u16)(2 * p_len), shortw_curve); EG(ret, err); 1008 ret = nn_init(&elements[i].number, 0); EG(ret, err); 1009 ret = nn_copy(&elements[i].number, &a); EG(ret, err); 1010 ret = nn_mod_neg(&elements[i].number, &elements[i].number, q); EG(ret, err); 1011 dbg_ec_point_print("W", W); 1012 } 1013 1014 /* Sanity check */ 1015 MUST_HAVE((q != NULL) && (G != NULL) && (q_bit_len != 0), ret, err); 1016 1017 /********************************************/ 1018 /****** Bos-Coster algorithm ****************/ 1019 ret = ec_verify_bos_coster(elements, (2 * num) + 1, q_bit_len); 1020 if(ret){ 1021 if(ret == -2){ 1022 /* In case of Bos-Coster time out, we fall back to the 1023 * slower regular batch verification. 1024 */ 1025 ret = _ecfsdsa_verify_batch_no_memory(s, s_len, pub_keys, m, m_len, num, sig_type, 1026 hash_type, adata, adata_len); EG(ret, err); 1027 } 1028 goto err; 1029 } 1030 1031 1032 /* The first element should contain the sum: it should 1033 * be equal to zero. Reject the signature if this is not 1034 * the case. 1035 */ 1036 ret = prj_pt_iszero(&elements[elements[0].index].point, &iszero); EG(ret, err); 1037 ret = iszero ? 0 : -1; 1038 1039 err: 1040 PTR_NULLIFY(q); 1041 PTR_NULLIFY(e); 1042 PTR_NULLIFY(pub_key); 1043 PTR_NULLIFY(pub_key0); 1044 PTR_NULLIFY(shortw_curve); 1045 PTR_NULLIFY(pub_key_y); 1046 PTR_NULLIFY(G); 1047 PTR_NULLIFY(W); 1048 PTR_NULLIFY(Y); 1049 1050 nn_uninit(&S); 1051 nn_uninit(&a); 1052 1053 return ret; 1054 } 1055 1056 1057 int ecfsdsa_verify_batch(const u8 **s, const u8 *s_len, const ec_pub_key **pub_keys, 1058 const u8 **m, const u32 *m_len, u32 num, ec_alg_type sig_type, 1059 hash_alg_type hash_type, const u8 **adata, const u16 *adata_len, 1060 verify_batch_scratch_pad *scratch_pad_area, u32 *scratch_pad_area_len) 1061 { 1062 int ret; 1063 1064 if(scratch_pad_area != NULL){ 1065 MUST_HAVE((scratch_pad_area_len != NULL), ret, err); 1066 ret = _ecfsdsa_verify_batch(s, s_len, pub_keys, m, m_len, num, sig_type, 1067 hash_type, adata, adata_len, 1068 scratch_pad_area, scratch_pad_area_len); EG(ret, err); 1069 1070 } 1071 else{ 1072 ret = _ecfsdsa_verify_batch_no_memory(s, s_len, pub_keys, m, m_len, num, sig_type, 1073 hash_type, adata, adata_len); EG(ret, err); 1074 } 1075 1076 err: 1077 return ret; 1078 } 1079 1080 1081 #else /* WITH_SIG_ECFSDSA */ 1082 1083 /* 1084 * Dummy definition to avoid the empty translation unit ISO C warning 1085 */ 1086 typedef int dummy; 1087 #endif /* WITH_SIG_ECFSDSA */ 1088