fuzzing_ecrdsa.c
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_ECRDSA) && 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 "ECRDSA" 28 #endif 29 #include <libecc/utils/dbg_sig.h> 30 31 /* NOTE: the following versions of ECRDSA 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 /* 38 * NOTE: ISO/IEC 14888-3 standard seems to diverge from the existing implementations 39 * of ECRDSA when treating the message hash, and from the examples of certificates provided 40 * in RFC 7091 and draft-deremin-rfc4491-bis. While in ISO/IEC 14888-3 it is explicitely asked 41 * to proceed with the hash of the message as big endian, the RFCs derived from the Russian 42 * standard expect the hash value to be treated as little endian when importing it as an integer 43 * (this discrepancy is exhibited and confirmed by test vectors present in ISO/IEC 14888-3, and 44 * by X.509 certificates present in the RFCs). This seems (to be confirmed) to be a discrepancy of 45 * ISO/IEC 14888-3 algorithm description that must be fixed there. 46 * 47 * In order to be conservative, libecc uses the Russian standard behavior as expected to be in line with 48 * other implemetations, but keeps the ISO/IEC 14888-3 behavior if forced/asked by the user using 49 * the USE_ISO14888_3_ECRDSA toggle. This allows to keep backward compatibility with previous versions of the 50 * library if needed. 51 * 52 */ 53 #ifndef USE_ISO14888_3_ECRDSA 54 /* Reverses the endiannes of a buffer in place */ 55 ATTRIBUTE_WARN_UNUSED_RET static inline int _reverse_endianness(u8 *buf, u16 buf_size) 56 { 57 u16 i; 58 u8 tmp; 59 int ret; 60 61 MUST_HAVE((buf != NULL), ret, err); 62 63 if(buf_size > 1){ 64 for(i = 0; i < (buf_size / 2); i++){ 65 tmp = buf[i]; 66 buf[i] = buf[buf_size - 1 - i]; 67 buf[buf_size - 1 - i] = tmp; 68 } 69 } 70 71 ret = 0; 72 err: 73 return ret; 74 } 75 #endif 76 77 #define ECRDSA_SIGN_MAGIC ((word_t)(0xcc97bbc8ada8973cULL)) 78 #define ECRDSA_SIGN_CHECK_INITIALIZED(A, ret, err) \ 79 MUST_HAVE((((const void *)(A)) != NULL) && \ 80 ((A)->magic == ECRDSA_SIGN_MAGIC), ret, err) 81 82 int ecrdsa_sign_raw(struct ec_sign_context *ctx, const u8 *input, u8 inputlen, u8 *sig, u8 siglen, const u8 *nonce, u8 noncelen) 83 { 84 bitcnt_t q_bit_len, p_bit_len; 85 const ec_priv_key *priv_key; 86 /* NOTE: hash here is not really a hash ... */ 87 u8 h_buf[LOCAL_MIN(255, BIT_LEN_WORDS(NN_MAX_BIT_LEN) * (WORDSIZE / 8))]; 88 prj_pt_src_t G; 89 prj_pt kG; 90 nn_src_t q, x; 91 u8 hsize, r_len, s_len; 92 int ret, iszero; 93 nn tmp, s, rx, ke, k, r, e; 94 #ifdef USE_SIG_BLINDING 95 /* b is the blinding mask */ 96 nn b, binv; 97 b.magic = binv.magic = WORD(0); 98 #endif /* USE_SIG_BLINDING */ 99 100 tmp.magic = s.magic = rx.magic = ke.magic = WORD(0); 101 k.magic = r.magic = e.magic = WORD(0); 102 kG.magic = WORD(0); 103 104 /* 105 * First, verify context has been initialized and private 106 * part too. This guarantees the context is an EC-RDSA 107 * signature one and we do not finalize() before init(). 108 */ 109 ret = sig_sign_check_initialized(ctx); EG(ret, err); 110 ECRDSA_SIGN_CHECK_INITIALIZED(&(ctx->sign_data.ecrdsa), ret, err); 111 112 /* Zero init points */ 113 ret = local_memset(&kG, 0, sizeof(prj_pt)); EG(ret, err); 114 115 /* Make things more readable */ 116 priv_key = &(ctx->key_pair->priv_key); 117 G = &(priv_key->params->ec_gen); 118 q = &(priv_key->params->ec_gen_order); 119 p_bit_len = priv_key->params->ec_fp.p_bitlen; 120 q_bit_len = priv_key->params->ec_gen_order_bitlen; 121 x = &(priv_key->x); 122 r_len = (u8)ECRDSA_R_LEN(q_bit_len); 123 s_len = (u8)ECRDSA_S_LEN(q_bit_len); 124 hsize = inputlen; 125 126 MUST_HAVE((NN_MAX_BIT_LEN >= p_bit_len), ret, err); 127 128 MUST_HAVE((siglen == ECRDSA_SIGLEN(q_bit_len)), ret, err); 129 130 dbg_nn_print("p", &(priv_key->params->ec_fp.p)); 131 dbg_nn_print("q", q); 132 dbg_priv_key_print("x", priv_key); 133 dbg_pub_key_print("Y", &(ctx->key_pair->pub_key)); 134 dbg_ec_point_print("G", G); 135 136 /* 137 NOTE: the restart label is removed in CRYPTOFUZZ mode as 138 we trigger MUST_HAVE instead of restarting in this mode. 139 restart: 140 */ 141 /* 2. Get a random value k in ]0, q[ ... */ 142 /* NOTE: copy our input nonce if not NULL */ 143 if(nonce != NULL){ 144 MUST_HAVE((noncelen <= (u8)(BYTECEIL(q_bit_len))), ret, err); 145 ret = nn_init_from_buf(&k, nonce, noncelen); EG(ret, err); 146 } 147 else{ 148 ret = ctx->rand(&k, q); EG(ret, err); 149 } 150 151 dbg_nn_print("k", &k); 152 #ifdef USE_SIG_BLINDING 153 /* Note: if we use blinding, k and e are multiplied by 154 * a random value b in ]0,q[ */ 155 ret = nn_get_random_mod(&b, q); EG(ret, err); 156 dbg_nn_print("b", &b); 157 #endif /* USE_SIG_BLINDING */ 158 159 /* 3. Compute W = kG = (Wx, Wy) */ 160 #ifdef USE_SIG_BLINDING 161 /* We use blinding for the scalar multiplication */ 162 ret = prj_pt_mul_blind(&kG, &k, G); EG(ret, err); 163 #else 164 ret = prj_pt_mul(&kG, &k, G); EG(ret, err); 165 #endif /* USE_SIG_BLINDING */ 166 ret = prj_pt_unique(&kG, &kG); EG(ret, err); 167 dbg_nn_print("W_x", &(kG.X.fp_val)); 168 dbg_nn_print("W_y", &(kG.Y.fp_val)); 169 170 /* 4. Compute r = Wx mod q */ 171 ret = nn_mod(&r, &(kG.X.fp_val), q); EG(ret, err); 172 173 /* 5. If r is 0, restart the process at step 2. */ 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 dbg_nn_print("r", &r); 181 182 /* Export r */ 183 ret = nn_export_to_buf(sig, r_len, &r); EG(ret, err); 184 185 /* 6. Compute e = OS2I(h) mod q. If e is 0, set e to 1. */ 186 /* NOTE: here we have raw ECRDSA, this is the raw input */ 187 MUST_HAVE((input != NULL), ret, err); 188 /* NOTE: the MUST_HAVE is protected by a preprocessing check 189 * to avoid -Werror=type-limits errors: 190 * "error: comparison is always true due to limited range of data type" 191 */ 192 #if LOCAL_MIN(255, BIT_LEN_WORDS(NN_MAX_BIT_LEN) * (WORDSIZE / 8)) < 255 193 MUST_HAVE(((u32)inputlen <= sizeof(h_buf)), ret, err); 194 #endif 195 ret = local_memset(h_buf, 0, sizeof(h_buf)); EG(ret, err); 196 ret = local_memcpy(h_buf, input, hsize); EG(ret, err); 197 dbg_buf_print("H(m)", h_buf, hsize); 198 /* NOTE: this handles a discrepancy between ISO/IEC 14888-3 and 199 * Russian standard based RFCs. 200 */ 201 #ifndef USE_ISO14888_3_ECRDSA 202 ret = _reverse_endianness(h_buf, hsize); EG(ret, err); 203 #endif 204 205 ret = nn_init_from_buf(&tmp, h_buf, hsize); EG(ret, err); 206 ret = local_memset(h_buf, 0, hsize); EG(ret, err); 207 ret = nn_mod(&e, &tmp, q); EG(ret, err); 208 ret = nn_iszero(&e, &iszero); EG(ret, err); 209 if (iszero) { 210 ret = nn_inc(&e, &e); EG(ret, err); 211 } 212 dbg_nn_print("e", &e); 213 214 #ifdef USE_SIG_BLINDING 215 /* In case of blinding, we blind r and e */ 216 ret = nn_mod_mul(&r, &r, &b, q); EG(ret, err); 217 ret = nn_mod_mul(&e, &e, &b, q); EG(ret, err); 218 #endif /* USE_SIG_BLINDING */ 219 220 /* Compute s = (rx + ke) mod q */ 221 ret = nn_mod_mul(&rx, &r, x, q); EG(ret, err); 222 ret = nn_mod_mul(&ke, &k, &e, q); EG(ret, err); 223 ret = nn_mod_add(&s, &rx, &ke, q); EG(ret, err); 224 #ifdef USE_SIG_BLINDING 225 /* Unblind s */ 226 /* NOTE: we use Fermat's little theorem inversion for 227 * constant time here. This is possible since q is prime. 228 */ 229 ret = nn_modinv_fermat(&binv, &b, q); EG(ret, err); 230 ret = nn_mod_mul(&s, &s, &binv, q); EG(ret, err); 231 #endif /* USE_SIG_BLINDING */ 232 233 /* If s is 0, restart the process at step 2. */ 234 /* 10. If s is 0, restart the process at step 4. */ 235 /* NOTE: for the CRYPTOFUZZ mode, we do not restart 236 * the procedure but throw an assert exception instead. 237 */ 238 ret = nn_iszero(&s, &iszero); EG(ret, err); 239 MUST_HAVE((!iszero), ret, err); 240 241 dbg_nn_print("s", &s); 242 243 /* Return (r,s) */ 244 ret = nn_export_to_buf(sig + r_len, s_len, &s); EG(ret, err); 245 246 err: 247 nn_uninit(&r); 248 nn_uninit(&s); 249 nn_uninit(&tmp); 250 nn_uninit(&rx); 251 nn_uninit(&ke); 252 nn_uninit(&k); 253 nn_uninit(&e); 254 prj_pt_uninit(&kG); 255 256 /* 257 * We can now clear data part of the context. This will clear 258 * magic and avoid further reuse of the whole context. 259 */ 260 if(ctx != NULL){ 261 IGNORE_RET_VAL(local_memset(&(ctx->sign_data.ecrdsa), 0, sizeof(ecrdsa_sign_data))); 262 } 263 264 /* Clean what remains on the stack */ 265 VAR_ZEROIFY(r_len); 266 VAR_ZEROIFY(s_len); 267 VAR_ZEROIFY(q_bit_len); 268 VAR_ZEROIFY(p_bit_len); 269 VAR_ZEROIFY(hsize); 270 PTR_NULLIFY(priv_key); 271 PTR_NULLIFY(G); 272 PTR_NULLIFY(q); 273 PTR_NULLIFY(x); 274 275 #ifdef USE_SIG_BLINDING 276 nn_uninit(&b); 277 nn_uninit(&binv); 278 #endif /* USE_SIG_BLINDING */ 279 280 return ret; 281 } 282 283 /******************************/ 284 #define ECRDSA_VERIFY_MAGIC ((word_t)(0xa8e16b7e8180cb9aULL)) 285 #define ECRDSA_VERIFY_CHECK_INITIALIZED(A, ret, err) \ 286 MUST_HAVE((((const void *)(A)) != NULL) && \ 287 ((A)->magic == ECRDSA_VERIFY_MAGIC), ret, err) 288 289 int ecrdsa_verify_raw(struct ec_verify_context *ctx, const u8 *input, u8 inputlen) 290 { 291 prj_pt_src_t G, Y; 292 nn_src_t q; 293 nn tmp, h, r_prime, e, v, u; 294 prj_pt vY, uG; 295 prj_pt_t Wprime; 296 /* NOTE: hash here is not really a hash ... */ 297 u8 h_buf[LOCAL_MIN(255, BIT_LEN_WORDS(NN_MAX_BIT_LEN) * (WORDSIZE / 8))]; 298 nn *r, *s; 299 u8 hsize; 300 int ret, iszero, cmp; 301 302 tmp.magic = h.magic = r_prime.magic = e.magic = WORD(0); 303 v.magic = u.magic = WORD(0); 304 vY.magic = uG.magic = WORD(0); 305 306 /* NOTE: we reuse uG for Wprime to optimize local variables */ 307 Wprime = &uG; 308 309 /* 310 * First, verify context has been initialized and public 311 * part too. This guarantees the context is an EC-RDSA 312 * verification one and we do not finalize() before init(). 313 */ 314 ret = sig_verify_check_initialized(ctx); EG(ret, err); 315 ECRDSA_VERIFY_CHECK_INITIALIZED(&(ctx->verify_data.ecrdsa), ret, err); 316 317 /* Zero init points */ 318 ret = local_memset(&uG, 0, sizeof(prj_pt)); EG(ret, err); 319 ret = local_memset(&vY, 0, sizeof(prj_pt)); EG(ret, err); 320 321 /* Make things more readable */ 322 G = &(ctx->pub_key->params->ec_gen); 323 Y = &(ctx->pub_key->y); 324 q = &(ctx->pub_key->params->ec_gen_order); 325 r = &(ctx->verify_data.ecrdsa.r); 326 s = &(ctx->verify_data.ecrdsa.s); 327 hsize = inputlen; 328 329 /* 2. Compute h = H(m) */ 330 /* NOTE: here we have raw ECRDSA, this is the raw input */ 331 MUST_HAVE((input != NULL), ret, err); 332 /* NOTE: the MUST_HAVE is protected by a preprocessing check 333 * to avoid -Werror=type-limits errors: 334 * "error: comparison is always true due to limited range of data type" 335 */ 336 #if LOCAL_MIN(255, BIT_LEN_WORDS(NN_MAX_BIT_LEN) * (WORDSIZE / 8)) < 255 337 MUST_HAVE(((u32)inputlen <= sizeof(h_buf)), ret, err); 338 #endif 339 340 ret = local_memset(h_buf, 0, sizeof(h_buf)); EG(ret, err); 341 ret = local_memcpy(h_buf, input, hsize); EG(ret, err); 342 dbg_buf_print("H(m)", h_buf, hsize); 343 /* NOTE: this handles a discrepancy between ISO/IEC 14888-3 and 344 * Russian standard based RFCs. 345 */ 346 #ifndef USE_ISO14888_3_ECRDSA 347 ret = _reverse_endianness(h_buf, hsize); EG(ret, err); 348 #endif 349 350 /* 3. Compute e = OS2I(h)^-1 mod q */ 351 ret = nn_init_from_buf(&tmp, h_buf, hsize); EG(ret, err); 352 ret = local_memset(h_buf, 0, hsize); EG(ret, err); 353 ret = nn_mod(&h, &tmp, q); EG(ret, err); /* h = OS2I(h) mod q */ 354 ret = nn_iszero(&h, &iszero); EG(ret, err); 355 if (iszero) { /* If h is equal to 0, set it to 1 */ 356 ret = nn_inc(&h, &h); EG(ret, err); 357 } 358 ret = nn_modinv(&e, &h, q); EG(ret, err); /* e = h^-1 mod q */ 359 360 /* 4. Compute u = es mod q */ 361 ret = nn_mul(&tmp, &e, s); EG(ret, err); 362 ret = nn_mod(&u, &tmp, q); EG(ret, err); 363 364 /* 5. Compute v = -er mod q 365 * 366 * Because we only support positive integers, we compute 367 * v = -er mod q = q - (er mod q) (except when er is 0). 368 */ 369 ret = nn_mul(&tmp, &e, r); EG(ret, err); /* tmp = er */ 370 ret = nn_mod(&tmp, &tmp, q); EG(ret, err); /* tmp = er mod q */ 371 ret = nn_mod_neg(&v, &tmp, q); EG(ret, err); /* negate tmp */ 372 373 /* 6. Compute W' = uG + vY = (W'_x, W'_y) */ 374 ret = prj_pt_mul(&uG, &u, G); EG(ret, err); 375 ret = prj_pt_mul(&vY, &v, Y); EG(ret, err); 376 ret = prj_pt_add(Wprime, &uG, &vY); EG(ret, err); 377 ret = prj_pt_unique(Wprime, Wprime); EG(ret, err); 378 dbg_nn_print("W'_x", &(Wprime->X.fp_val)); 379 dbg_nn_print("W'_y", &(Wprime->Y.fp_val)); 380 381 /* 7. Compute r' = W'_x mod q */ 382 ret = nn_mod(&r_prime, &(Wprime->X.fp_val), q); EG(ret, err); 383 384 /* 8. Check r and r' are the same */ 385 ret = nn_cmp(r, &r_prime, &cmp); EG(ret, err); 386 ret = (cmp == 0) ? 0 : -1; 387 388 err: 389 nn_uninit(&r_prime); 390 nn_uninit(&tmp); 391 nn_uninit(&h); 392 nn_uninit(&e); 393 nn_uninit(&u); 394 nn_uninit(&v); 395 prj_pt_uninit(&vY); 396 prj_pt_uninit(&uG); 397 398 /* 399 * We can now clear data part of the context. This will clear 400 * magic and avoid further reuse of the whole context. 401 */ 402 if(ctx != NULL){ 403 IGNORE_RET_VAL(local_memset(&(ctx->verify_data.ecrdsa), 0, 404 sizeof(ecrdsa_verify_data))); 405 } 406 407 /* Clean what remains on the stack */ 408 PTR_NULLIFY(Wprime); 409 PTR_NULLIFY(G); 410 PTR_NULLIFY(Y); 411 PTR_NULLIFY(q); 412 PTR_NULLIFY(r); 413 PTR_NULLIFY(s); 414 VAR_ZEROIFY(hsize); 415 416 return ret; 417 } 418 419 #else /* WITH_SIG_ECRDSA && USE_CRYPTOFUZZ */ 420 421 /* 422 * Dummy definition to avoid the empty translation unit ISO C warning 423 */ 424 typedef int dummy; 425 #endif /* WITH_SIG_ECRDSA */