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 #if defined(WITH_SIG_ECDSA) && defined(USE_CRYPTOFUZZ) 18 19 #include <libecc/nn/nn_rand.h> 20 #include <libecc/nn/nn_mul.h> 21 #include <libecc/nn/nn_logical.h> 22 23 #include <libecc/sig/sig_algs_internal.h> 24 #include <libecc/sig/ec_key.h> 25 #include <libecc/utils/utils.h> 26 #ifdef VERBOSE_INNER_VALUES 27 #define EC_SIG_ALG "ECDSA" 28 #endif 29 #include <libecc/utils/dbg_sig.h> 30 31 /* NOTE: the following versions of ECDSA are "raw" with 32 * no hash functions and nonce override. They are DANGEROUS and 33 * should NOT be used in production mode! They are however useful 34 * for corner cases tests and fuzzing. 35 */ 36 37 #define ECDSA_SIGN_MAGIC ((word_t)(0x80299a2bf630945bULL)) 38 #define ECDSA_SIGN_CHECK_INITIALIZED(A, ret, err) \ 39 MUST_HAVE((((void *)(A)) != NULL) && ((A)->magic == ECDSA_SIGN_MAGIC), ret, err) 40 41 int ecdsa_sign_raw(struct ec_sign_context *ctx, const u8 *input, u8 inputlen, u8 *sig, u8 siglen, const u8 *nonce, u8 noncelen) 42 { 43 const ec_priv_key *priv_key; 44 prj_pt_src_t G; 45 /* NOTE: hash here is not really a hash ... */ 46 u8 hash[LOCAL_MIN(255, BIT_LEN_WORDS(NN_MAX_BIT_LEN) * (WORDSIZE / 8))]; 47 bitcnt_t rshift, q_bit_len; 48 prj_pt kG; 49 nn_src_t q, x; 50 u8 hsize, q_len; 51 int ret, iszero, cmp; 52 nn k, r, e, tmp, s, kinv; 53 #ifdef USE_SIG_BLINDING 54 /* b is the blinding mask */ 55 nn b; 56 b.magic = WORD(0); 57 #endif 58 k.magic = r.magic = e.magic = WORD(0); 59 tmp.magic = s.magic = kinv.magic = WORD(0); 60 kG.magic = WORD(0); 61 62 /* 63 * First, verify context has been initialized and private 64 * part too. This guarantees the context is an ECDSA 65 * signature one and we do not finalize() before init(). 66 */ 67 ret = sig_sign_check_initialized(ctx); EG(ret, err); 68 ECDSA_SIGN_CHECK_INITIALIZED(&(ctx->sign_data.ecdsa), ret, err); 69 MUST_HAVE((input != NULL) && (sig != NULL), ret, err); 70 71 /* Zero init out poiny */ 72 ret = local_memset(&kG, 0, sizeof(prj_pt)); EG(ret, err); 73 74 /* Make things more readable */ 75 priv_key = &(ctx->key_pair->priv_key); 76 q = &(priv_key->params->ec_gen_order); 77 q_bit_len = priv_key->params->ec_gen_order_bitlen; 78 G = &(priv_key->params->ec_gen); 79 q_len = (u8)BYTECEIL(q_bit_len); 80 x = &(priv_key->x); 81 hsize = inputlen; 82 83 dbg_nn_print("p", &(priv_key->params->ec_fp.p)); 84 dbg_nn_print("q", &(priv_key->params->ec_gen_order)); 85 dbg_priv_key_print("x", priv_key); 86 dbg_ec_point_print("G", &(priv_key->params->ec_gen)); 87 dbg_pub_key_print("Y", &(ctx->key_pair->pub_key)); 88 89 /* Check given signature buffer length has the expected size */ 90 MUST_HAVE((siglen == ECDSA_SIGLEN(q_bit_len)), ret, err); 91 92 /* 1. Compute h = H(m) */ 93 /* NOTE: here we have raw ECDSA, this is the raw input */ 94 /* NOTE: the MUST_HAVE is protected by a preprocessing check 95 * to avoid -Werror=type-limits errors: 96 * "error: comparison is always true due to limited range of data type" 97 */ 98 #if LOCAL_MIN(255, BIT_LEN_WORDS(NN_MAX_BIT_LEN) * (WORDSIZE / 8)) < 255 99 MUST_HAVE(((u32)inputlen <= sizeof(hash)), ret, err); 100 #endif 101 ret = local_memset(hash, 0, sizeof(hash)); EG(ret, err); 102 ret = local_memcpy(hash, input, hsize); EG(ret, err); 103 104 dbg_buf_print("h", hash, hsize); 105 106 /* 107 * 2. If |h| > bitlen(q), set h to bitlen(q) 108 * leftmost bits of h. 109 * 110 * Note that it's easier to check if the truncation has 111 * to be done here but only implement it using a logical 112 * shift at the beginning of step 3. below once the hash 113 * has been converted to an integer. 114 */ 115 rshift = 0; 116 if ((hsize * 8) > q_bit_len) { 117 rshift = (bitcnt_t)((hsize * 8) - q_bit_len); 118 } 119 120 /* 121 * 3. Compute e = OS2I(h) mod q, i.e. by converting h to an 122 * integer and reducing it mod q 123 */ 124 ret = nn_init_from_buf(&e, hash, hsize); EG(ret, err); 125 ret = local_memset(hash, 0, hsize); EG(ret, err); 126 dbg_nn_print("h initial import as nn", &e); 127 if (rshift) { 128 ret = nn_rshift_fixedlen(&e, &e, rshift); EG(ret, err); 129 } 130 dbg_nn_print("h final import as nn", &e); 131 ret = nn_mod(&e, &e, q); EG(ret, err); 132 dbg_nn_print("e", &e); 133 134 /* 135 NOTE: the restart label is removed in CRYPTOFUZZ mode as 136 we trigger MUST_HAVE instead of restarting in this mode. 137 restart: 138 */ 139 /* 4. get a random value k in ]0,q[ */ 140 /* NOTE: copy our input nonce if not NULL */ 141 if(nonce != NULL){ 142 MUST_HAVE((noncelen <= (u8)(BYTECEIL(q_bit_len))), ret, err); 143 ret = nn_init_from_buf(&k, nonce, noncelen); EG(ret, err); 144 } 145 else{ 146 ret = ctx->rand(&k, q); EG(ret, err); 147 } 148 dbg_nn_print("k", &k); 149 150 #ifdef USE_SIG_BLINDING 151 /* Note: if we use blinding, r and e are multiplied by 152 * a random value b in ]0,q[ */ 153 ret = nn_get_random_mod(&b, q); EG(ret, err); 154 dbg_nn_print("b", &b); 155 #endif /* USE_SIG_BLINDING */ 156 157 158 /* 5. Compute W = (W_x,W_y) = kG */ 159 #ifdef USE_SIG_BLINDING 160 ret = prj_pt_mul_blind(&kG, &k, G); EG(ret, err); 161 #else 162 ret = prj_pt_mul(&kG, &k, G); EG(ret, err); 163 #endif /* USE_SIG_BLINDING */ 164 ret = prj_pt_unique(&kG, &kG); EG(ret, err); 165 166 dbg_nn_print("W_x", &(kG.X.fp_val)); 167 dbg_nn_print("W_y", &(kG.Y.fp_val)); 168 169 /* 6. Compute r = W_x mod q */ 170 ret = nn_mod(&r, &(kG.X.fp_val), q); EG(ret, err); 171 dbg_nn_print("r", &r); 172 173 /* 7. If r is 0, restart the process at step 4. */ 174 /* NOTE: for the CRYPTOFUZZ mode, we do not restart 175 * the procedure but throw an assert exception instead. 176 */ 177 ret = nn_iszero(&r, &iszero); EG(ret, err); 178 MUST_HAVE((!iszero), ret, err); 179 180 /* Export r */ 181 ret = nn_export_to_buf(sig, q_len, &r); EG(ret, err); 182 183 #ifdef USE_SIG_BLINDING 184 /* Blind r with b */ 185 ret = nn_mod_mul(&r, &r, &b, q); EG(ret, err); 186 187 /* Blind the message e */ 188 ret = nn_mod_mul(&e, &e, &b, q); EG(ret, err); 189 #endif /* USE_SIG_BLINDING */ 190 191 /* tmp = xr mod q */ 192 ret = nn_mod_mul(&tmp, x, &r, q); EG(ret, err); 193 dbg_nn_print("x*r mod q", &tmp); 194 195 /* 8. If e == rx, restart the process at step 4. */ 196 /* NOTE: for the CRYPTOFUZZ mode, we do not restart 197 * the procedure but throw an assert exception instead. 198 */ 199 ret = nn_cmp(&e, &tmp, &cmp); EG(ret, err); 200 MUST_HAVE(cmp, ret, err); 201 202 /* 9. Compute s = k^-1 * (xr + e) mod q */ 203 204 /* tmp2 = (e + xr) mod q */ 205 ret = nn_mod_add(&tmp, &tmp, &e, q); EG(ret, err); 206 dbg_nn_print("(xr + e) mod q", &tmp); 207 208 #ifdef USE_SIG_BLINDING 209 /* In case of blinding, we compute (b*k)^-1, and 210 * b^-1 will automatically unblind (r*x) in the following 211 */ 212 ret = nn_mod_mul(&k, &k, &b, q); EG(ret, err); 213 #endif 214 /* Compute k^-1 mod q */ 215 /* NOTE: we use Fermat's little theorem inversion for 216 * constant time here. This is possible since q is prime. 217 */ 218 ret = nn_modinv_fermat(&kinv, &k, q); EG(ret, err); 219 220 dbg_nn_print("k^-1 mod q", &kinv); 221 222 /* s = k^-1 * tmp2 mod q */ 223 ret = nn_mod_mul(&s, &tmp, &kinv, q); EG(ret, err); 224 225 dbg_nn_print("s", &s); 226 227 /* 10. If s is 0, restart the process at step 4. */ 228 /* NOTE: for the CRYPTOFUZZ mode, we do not restart 229 * the procedure but throw an assert exception instead. 230 */ 231 ret = nn_iszero(&s, &iszero); EG(ret, err); 232 MUST_HAVE((!iszero), ret, err); 233 234 /* 11. return (r,s) */ 235 ret = nn_export_to_buf(sig + q_len, q_len, &s); 236 237 err: 238 239 nn_uninit(&r); 240 nn_uninit(&s); 241 nn_uninit(&e); 242 nn_uninit(&tmp); 243 nn_uninit(&k); 244 nn_uninit(&kinv); 245 prj_pt_uninit(&kG); 246 247 /* 248 * We can now clear data part of the context. This will clear 249 * magic and avoid further reuse of the whole context. 250 */ 251 if(ctx != NULL){ 252 IGNORE_RET_VAL(local_memset(&(ctx->sign_data.ecdsa), 0, sizeof(ecdsa_sign_data))); 253 } 254 255 /* Clean what remains on the stack */ 256 PTR_NULLIFY(priv_key); 257 PTR_NULLIFY(G); 258 PTR_NULLIFY(q); 259 PTR_NULLIFY(x); 260 VAR_ZEROIFY(q_len); 261 VAR_ZEROIFY(q_bit_len); 262 VAR_ZEROIFY(rshift); 263 VAR_ZEROIFY(hsize); 264 265 #ifdef USE_SIG_BLINDING 266 nn_uninit(&b); 267 #endif /* USE_SIG_BLINDING */ 268 269 return ret; 270 } 271 272 /******************************/ 273 #define ECDSA_VERIFY_MAGIC ((word_t)(0x5155fe73e7fd51beULL)) 274 #define ECDSA_VERIFY_CHECK_INITIALIZED(A, ret, err) \ 275 MUST_HAVE((((void *)(A)) != NULL) && ((A)->magic == ECDSA_VERIFY_MAGIC), ret, err) 276 277 int ecdsa_verify_raw(struct ec_verify_context *ctx, const u8 *input, u8 inputlen) 278 { 279 prj_pt uG, vY; 280 prj_pt_t W_prime; 281 nn e, sinv, uv, r_prime; 282 prj_pt_src_t G, Y; 283 /* NOTE: hash here is not really a hash ... */ 284 u8 hash[LOCAL_MIN(255, BIT_LEN_WORDS(NN_MAX_BIT_LEN) * (WORDSIZE / 8))]; 285 bitcnt_t rshift, q_bit_len; 286 nn_src_t q; 287 nn *s, *r; 288 u8 hsize; 289 int ret, iszero, cmp; 290 291 e.magic = sinv.magic = uv.magic = r_prime.magic = WORD(0); 292 uG.magic = vY.magic = WORD(0); 293 294 /* NOTE: we reuse uG for W_prime to optimize local variables */ 295 W_prime = &uG; 296 297 /* 298 * First, verify context has been initialized and public 299 * part too. This guarantees the context is an ECDSA 300 * verification one and we do not finalize() before init(). 301 */ 302 ret = sig_verify_check_initialized(ctx); EG(ret, err); 303 ECDSA_VERIFY_CHECK_INITIALIZED(&(ctx->verify_data.ecdsa), ret, err); 304 MUST_HAVE((input != NULL), ret, err); 305 306 /* Zero init points */ 307 ret = local_memset(&uG, 0, sizeof(prj_pt)); EG(ret, err); 308 ret = local_memset(&vY, 0, sizeof(prj_pt)); EG(ret, err); 309 310 /* Make things more readable */ 311 G = &(ctx->pub_key->params->ec_gen); 312 Y = &(ctx->pub_key->y); 313 q = &(ctx->pub_key->params->ec_gen_order); 314 q_bit_len = ctx->pub_key->params->ec_gen_order_bitlen; 315 hsize = inputlen; 316 r = &(ctx->verify_data.ecdsa.r); 317 s = &(ctx->verify_data.ecdsa.s); 318 319 /* 2. Compute h = H(m) */ 320 /* NOTE: here we have raw ECDSA, this is the raw input */ 321 MUST_HAVE((input != NULL), ret, err); 322 /* NOTE: the MUST_HAVE is protected by a preprocessing check 323 * to avoid -Werror=type-limits errors: 324 * "error: comparison is always true due to limited range of data type" 325 */ 326 #if LOCAL_MIN(255, BIT_LEN_WORDS(NN_MAX_BIT_LEN) * (WORDSIZE / 8)) < 255 327 MUST_HAVE(((u32)inputlen <= sizeof(hash)), ret, err); 328 #endif 329 330 ret = local_memset(hash, 0, sizeof(hash)); EG(ret, err); 331 ret = local_memcpy(hash, input, hsize); EG(ret, err); 332 333 dbg_buf_print("h = H(m)", hash, hsize); 334 335 /* 336 * 3. If |h| > bitlen(q), set h to bitlen(q) 337 * leftmost bits of h. 338 * 339 * Note that it's easier to check here if the truncation 340 * needs to be done but implement it using a logical 341 * shift at the beginning of step 3. below once the hash 342 * has been converted to an integer. 343 */ 344 rshift = 0; 345 if ((hsize * 8) > q_bit_len) { 346 rshift = (bitcnt_t)((hsize * 8) - q_bit_len); 347 } 348 349 /* 350 * 4. Compute e = OS2I(h) mod q, by converting h to an integer 351 * and reducing it mod q 352 */ 353 ret = nn_init_from_buf(&e, hash, hsize); EG(ret, err); 354 ret = local_memset(hash, 0, hsize); EG(ret, err); 355 dbg_nn_print("h initial import as nn", &e); 356 if (rshift) { 357 ret = nn_rshift_fixedlen(&e, &e, rshift); EG(ret, err); 358 } 359 dbg_nn_print("h final import as nn", &e); 360 361 ret = nn_mod(&e, &e, q); EG(ret, err); 362 dbg_nn_print("e", &e); 363 364 /* Compute s^-1 mod q */ 365 ret = nn_modinv(&sinv, s, q); EG(ret, err); 366 dbg_nn_print("s", s); 367 dbg_nn_print("sinv", &sinv); 368 nn_uninit(s); 369 370 /* 5. Compute u = (s^-1)e mod q */ 371 ret = nn_mod_mul(&uv, &e, &sinv, q); EG(ret, err); 372 dbg_nn_print("u = (s^-1)e mod q", &uv); 373 ret = prj_pt_mul(&uG, &uv, G); EG(ret, err); 374 375 /* 6. Compute v = (s^-1)r mod q */ 376 ret = nn_mod_mul(&uv, r, &sinv, q); EG(ret, err); 377 dbg_nn_print("v = (s^-1)r mod q", &uv); 378 ret = prj_pt_mul(&vY, &uv, Y); EG(ret, err); 379 380 /* 7. Compute W' = uG + vY */ 381 ret = prj_pt_add(W_prime, &uG, &vY); EG(ret, err); 382 383 /* 8. If W' is the point at infinity, reject the signature. */ 384 ret = prj_pt_iszero(W_prime, &iszero); EG(ret, err); 385 MUST_HAVE((!iszero), ret, err); 386 387 /* 9. Compute r' = W'_x mod q */ 388 ret = prj_pt_unique(W_prime, W_prime); EG(ret, err); 389 dbg_nn_print("W'_x", &(W_prime->X.fp_val)); 390 dbg_nn_print("W'_y", &(W_prime->Y.fp_val)); 391 ret = nn_mod(&r_prime, &(W_prime->X.fp_val), q); EG(ret, err); 392 393 /* 10. Accept the signature if and only if r equals r' */ 394 ret = nn_cmp(&r_prime, r, &cmp); EG(ret, err); 395 ret = (cmp != 0) ? -1 : 0; 396 397 err: 398 nn_uninit(&r_prime); 399 nn_uninit(&uv); 400 nn_uninit(&e); 401 nn_uninit(&sinv); 402 prj_pt_uninit(&uG); 403 prj_pt_uninit(&vY); 404 405 /* 406 * We can now clear data part of the context. This will clear 407 * magic and avoid further reuse of the whole context. 408 */ 409 if(ctx != NULL){ 410 IGNORE_RET_VAL(local_memset(&(ctx->verify_data.ecdsa), 0, sizeof(ecdsa_verify_data))); 411 } 412 413 /* Clean what remains on the stack */ 414 PTR_NULLIFY(W_prime); 415 PTR_NULLIFY(G); 416 PTR_NULLIFY(Y); 417 VAR_ZEROIFY(rshift); 418 VAR_ZEROIFY(q_bit_len); 419 PTR_NULLIFY(q); 420 PTR_NULLIFY(s); 421 PTR_NULLIFY(r); 422 VAR_ZEROIFY(hsize); 423 424 return ret; 425 } 426 427 428 #else /* WITH_SIG_ECDSA && USE_CRYPTOFUZZ */ 429 430 /* 431 * Dummy definition to avoid the empty translation unit ISO C warning 432 */ 433 typedef int dummy; 434 #endif /* WITH_SIG_ECDSA */ 435