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_ECGDSA) && 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 "ECGDSA" 28 #endif 29 #include <libecc/utils/dbg_sig.h> 30 31 /* NOTE: the following versions of ECGDSA 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 #define ECGDSA_SIGN_MAGIC ((word_t)(0xe2f60ea3353ecc9eULL)) 37 #define ECGDSA_SIGN_CHECK_INITIALIZED(A, ret, err) \ 38 MUST_HAVE((((const void *)(A)) != NULL) && \ 39 ((A)->magic == ECGDSA_SIGN_MAGIC), ret, err) 40 41 int ecgdsa_sign_raw(struct ec_sign_context *ctx, const u8 *input, u8 inputlen, u8 *sig, u8 siglen, const u8 *nonce, u8 noncelen) 42 { 43 nn_src_t q, x; 44 /* NOTE: hash here is not really a hash ... */ 45 u8 e_buf[LOCAL_MIN(255, BIT_LEN_WORDS(NN_MAX_BIT_LEN) * (WORDSIZE / 8))]; 46 const ec_priv_key *priv_key; 47 prj_pt_src_t G; 48 u8 hsize, r_len, s_len; 49 bitcnt_t q_bit_len, p_bit_len, rshift; 50 prj_pt kG; 51 int ret, iszero; 52 nn tmp, tmp2, s, e, kr, k, r; 53 #ifdef USE_SIG_BLINDING 54 /* b is the blinding mask */ 55 nn b, binv; 56 b.magic = binv.magic = WORD(0); 57 #endif 58 tmp.magic = tmp2.magic = s.magic = e.magic = WORD(0); 59 kr.magic = k.magic = r.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 EC-GDSA 65 * signature one and we do not finalize() before init(). 66 */ 67 ret = sig_sign_check_initialized(ctx); EG(ret, err); 68 ECGDSA_SIGN_CHECK_INITIALIZED(&(ctx->sign_data.ecgdsa), ret, err); 69 MUST_HAVE((sig != NULL) && (input != NULL), ret, err); 70 71 /* Zero init points */ 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 G = &(priv_key->params->ec_gen); 77 q = &(priv_key->params->ec_gen_order); 78 x = &(priv_key->x); 79 q_bit_len = priv_key->params->ec_gen_order_bitlen; 80 p_bit_len = priv_key->params->ec_fp.p_bitlen; 81 MUST_HAVE(((u32)BYTECEIL(p_bit_len) <= NN_MAX_BYTE_LEN), ret, err); 82 r_len = (u8)ECGDSA_R_LEN(q_bit_len); 83 s_len = (u8)ECGDSA_S_LEN(q_bit_len); 84 hsize = inputlen; 85 86 MUST_HAVE((siglen == ECGDSA_SIGLEN(q_bit_len)), ret, err); 87 88 dbg_nn_print("p", &(priv_key->params->ec_fp.p)); 89 dbg_nn_print("q", q); 90 dbg_priv_key_print("x", priv_key); 91 dbg_ec_point_print("G", G); 92 dbg_pub_key_print("Y", &(ctx->key_pair->pub_key)); 93 94 /* 1. Compute h = H(m) */ 95 /* NOTE: here we have raw ECGDSA, this is the raw input */ 96 /* NOTE: the MUST_HAVE is protected by a preprocessing check 97 * to avoid -Werror=type-limits errors: 98 * "error: comparison is always true due to limited range of data type" 99 */ 100 #if LOCAL_MIN(255, BIT_LEN_WORDS(NN_MAX_BIT_LEN) * (WORDSIZE / 8)) < 255 101 MUST_HAVE(((u32)inputlen <= sizeof(e_buf)), ret, err); 102 #endif 103 ret = local_memset(e_buf, 0, sizeof(e_buf)); EG(ret, err); 104 ret = local_memcpy(e_buf, input, hsize); EG(ret, err); 105 dbg_buf_print("H(m)", e_buf, hsize); 106 107 /* 108 * If |h| > bitlen(q), set h to bitlen(q) 109 * leftmost bits of h. 110 * 111 */ 112 rshift = 0; 113 if ((hsize * 8) > q_bit_len) { 114 rshift = (bitcnt_t)((hsize * 8) - q_bit_len); 115 } 116 ret = nn_init_from_buf(&tmp, e_buf, hsize); EG(ret, err); 117 ret = local_memset(e_buf, 0, hsize); EG(ret, err); 118 if (rshift) { 119 ret = nn_rshift_fixedlen(&tmp, &tmp, rshift); EG(ret, err); 120 } 121 dbg_nn_print("H(m) truncated as nn", &tmp); 122 123 /* 124 * 2. Convert h to an integer and then compute e = -h mod q, 125 * i.e. compute e = - OS2I(h) mod q 126 * 127 * Because we only support positive integers, we compute 128 * e = q - (h mod q) (except when h is 0). 129 */ 130 ret = nn_mod(&tmp2, &tmp, q); EG(ret, err); 131 ret = nn_mod_neg(&e, &tmp2, q); EG(ret, err); 132 133 /* 134 NOTE: the restart label is removed in CRYPTOFUZZ mode as 135 we trigger MUST_HAVE instead of restarting in this mode. 136 restart: 137 */ 138 /* 3. Get a random value k in ]0,q[ */ 139 /* NOTE: copy our input nonce if not NULL */ 140 if(nonce != NULL){ 141 MUST_HAVE((noncelen <= (u8)(BYTECEIL(q_bit_len))), ret, err); 142 ret = nn_init_from_buf(&k, nonce, noncelen); EG(ret, err); 143 } 144 else{ 145 ret = ctx->rand(&k, q); EG(ret, err); 146 } 147 148 #ifdef USE_SIG_BLINDING 149 /* Note: if we use blinding, e and e are multiplied by 150 * a random value b in ]0,q[ */ 151 ret = nn_get_random_mod(&b, q); EG(ret, err); 152 dbg_nn_print("b", &b); 153 #endif /* USE_SIG_BLINDING */ 154 155 156 /* 4. Compute W = kG = (Wx, Wy) */ 157 #ifdef USE_SIG_BLINDING 158 /* We use blinding for the scalar multiplication */ 159 ret = prj_pt_mul_blind(&kG, &k, G); EG(ret, err); 160 #else 161 ret = prj_pt_mul(&kG, &k, G); EG(ret, err); 162 #endif /* USE_SIG_BLINDING */ 163 ret = prj_pt_unique(&kG, &kG); EG(ret, err); 164 165 dbg_nn_print("W_x", &(kG.X.fp_val)); 166 dbg_nn_print("W_y", &(kG.Y.fp_val)); 167 168 /* 5. Compute r = Wx mod q */ 169 ret = nn_mod(&r, &(kG.X.fp_val), q); EG(ret, err); 170 dbg_nn_print("r", &r); 171 172 /* 6. If r is 0, restart the process at step 4. */ 173 /* NOTE: for the CRYPTOFUZZ mode, we do not restart 174 * the procedure but throw an assert exception instead. 175 */ 176 ret = nn_iszero(&r, &iszero); EG(ret, err); 177 MUST_HAVE((!iszero), ret, err); 178 179 /* Export r */ 180 ret = nn_export_to_buf(sig, r_len, &r); EG(ret, err); 181 182 #ifdef USE_SIG_BLINDING 183 /* Blind e and r with b */ 184 ret = nn_mod_mul(&e, &e, &b, q); EG(ret, err); 185 ret = nn_mod_mul(&r, &r, &b, q); EG(ret, err); 186 #endif /* USE_SIG_BLINDING */ 187 /* 7. Compute s = x(kr + e) mod q */ 188 ret = nn_mod_mul(&kr, &k, &r, q); EG(ret, err); 189 ret = nn_mod_add(&tmp2, &kr, &e, q); EG(ret, err); 190 ret = nn_mod_mul(&s, x, &tmp2, q); EG(ret, err); 191 #ifdef USE_SIG_BLINDING 192 /* Unblind s */ 193 /* NOTE: we use Fermat's little theorem inversion for 194 * constant time here. This is possible since q is prime. 195 */ 196 ret = nn_modinv_fermat(&binv, &b, q); EG(ret, err); 197 ret = nn_mod_mul(&s, &s, &binv, q); EG(ret, err); 198 #endif 199 dbg_nn_print("s", &s); 200 201 /* 8. If s is 0, restart the process at step 4. */ 202 /* NOTE: for the CRYPTOFUZZ mode, we do not restart 203 * the procedure but throw an assert exception instead. 204 */ 205 ret = nn_iszero(&s, &iszero); EG(ret, err); 206 MUST_HAVE((!iszero), ret, err); 207 208 /* 9. Return (r,s) */ 209 ret = nn_export_to_buf(sig + r_len, s_len, &s); 210 211 err: 212 nn_uninit(&r); 213 nn_uninit(&s); 214 nn_uninit(&tmp2); 215 nn_uninit(&tmp); 216 nn_uninit(&e); 217 nn_uninit(&kr); 218 nn_uninit(&k); 219 220 prj_pt_uninit(&kG); 221 222 /* 223 * We can now clear data part of the context. This will clear 224 * magic and avoid further reuse of the whole context. 225 */ 226 if(ctx != NULL){ 227 IGNORE_RET_VAL(local_memset(&(ctx->sign_data.ecgdsa), 0, sizeof(ecgdsa_sign_data))); 228 } 229 230 /* Clean what remains on the stack */ 231 VAR_ZEROIFY(q_bit_len); 232 VAR_ZEROIFY(p_bit_len); 233 VAR_ZEROIFY(r_len); 234 VAR_ZEROIFY(s_len); 235 VAR_ZEROIFY(hsize); 236 PTR_NULLIFY(q); 237 PTR_NULLIFY(x); 238 PTR_NULLIFY(priv_key); 239 PTR_NULLIFY(G); 240 241 #ifdef USE_SIG_BLINDING 242 nn_uninit(&b); 243 nn_uninit(&binv); 244 #endif /* USE_SIG_BLINDING */ 245 246 return ret; 247 } 248 249 /******************************/ 250 #define ECGDSA_VERIFY_MAGIC ((word_t)(0xd4da37527288d1b6ULL)) 251 #define ECGDSA_VERIFY_CHECK_INITIALIZED(A, ret, err) \ 252 MUST_HAVE((((const void *)(A)) != NULL) && \ 253 ((A)->magic == ECGDSA_VERIFY_MAGIC), ret, err) 254 255 int ecgdsa_verify_raw(struct ec_verify_context *ctx, const u8 *input, u8 inputlen) 256 { 257 nn tmp, e, r_prime, rinv, uv, *r, *s; 258 prj_pt uG, vY; 259 prj_pt_t Wprime; 260 prj_pt_src_t G, Y; 261 /* NOTE: hash here is not really a hash ... */ 262 u8 e_buf[LOCAL_MIN(255, BIT_LEN_WORDS(NN_MAX_BIT_LEN) * (WORDSIZE / 8))]; 263 nn_src_t q; 264 u8 hsize; 265 bitcnt_t q_bit_len, rshift; 266 int ret, cmp; 267 268 tmp.magic = e.magic = r_prime.magic = rinv.magic = uv.magic = WORD(0); 269 uG.magic = vY.magic = WORD(0); 270 271 /* NOTE: we reuse uG for Wprime to optimize local variables */ 272 Wprime = &uG; 273 274 /* 275 * First, verify context has been initialized and public 276 * part too. This guarantees the context is an EC-GDSA 277 * verification one and we do not finalize() before init(). 278 */ 279 ret = sig_verify_check_initialized(ctx); EG(ret, err); 280 ECGDSA_VERIFY_CHECK_INITIALIZED(&(ctx->verify_data.ecgdsa), ret, err); 281 MUST_HAVE((input != NULL), ret, err); 282 283 /* Zero init points */ 284 ret = local_memset(&uG, 0, sizeof(prj_pt)); EG(ret, err); 285 ret = local_memset(&vY, 0, sizeof(prj_pt)); EG(ret, err); 286 287 /* Make things more readable */ 288 G = &(ctx->pub_key->params->ec_gen); 289 Y = &(ctx->pub_key->y); 290 q = &(ctx->pub_key->params->ec_gen_order); 291 r = &(ctx->verify_data.ecgdsa.r); 292 s = &(ctx->verify_data.ecgdsa.s); 293 q_bit_len = ctx->pub_key->params->ec_gen_order_bitlen; 294 hsize = inputlen; 295 296 /* 2. Compute h = H(m) */ 297 /* NOTE: here we have raw ECGDSA, this is the raw input */ 298 MUST_HAVE((input != NULL), ret, err); 299 /* NOTE: the MUST_HAVE is protected by a preprocessing check 300 * to avoid -Werror=type-limits errors: 301 * "error: comparison is always true due to limited range of data type" 302 */ 303 #if LOCAL_MIN(255, BIT_LEN_WORDS(NN_MAX_BIT_LEN) * (WORDSIZE / 8)) < 255 304 MUST_HAVE(((u32)inputlen <= sizeof(e_buf)), ret, err); 305 #endif 306 307 ret = local_memset(e_buf, 0, sizeof(e_buf)); EG(ret, err); 308 ret = local_memcpy(e_buf, input, hsize); EG(ret, err); 309 dbg_buf_print("H(m)", e_buf, hsize); 310 311 /* 312 * If |h| > bitlen(q), set h to bitlen(q) 313 * leftmost bits of h. 314 * 315 */ 316 rshift = 0; 317 if ((hsize * 8) > q_bit_len) { 318 rshift = (bitcnt_t)((hsize * 8) - q_bit_len); 319 } 320 ret = nn_init_from_buf(&tmp, e_buf, hsize); EG(ret, err); 321 ret = local_memset(e_buf, 0, hsize); EG(ret, err); 322 if (rshift) { 323 ret = nn_rshift_fixedlen(&tmp, &tmp, rshift); EG(ret, err); 324 } 325 dbg_nn_print("H(m) truncated as nn", &tmp); 326 327 /* 3. Compute e by converting h to an integer and reducing it mod q */ 328 ret = nn_mod(&e, &tmp, q); EG(ret, err); 329 330 /* 4. Compute u = (r^-1)e mod q */ 331 ret = nn_modinv(&rinv, r, q); EG(ret, err); /* r^-1 */ 332 ret = nn_mul(&tmp, &rinv, &e); EG(ret, err); /* r^-1 * e */ 333 ret = nn_mod(&uv, &tmp, q); EG(ret, err); /* (r^-1 * e) mod q */ 334 ret = prj_pt_mul(&uG, &uv, G); EG(ret, err); 335 336 /* 5. Compute v = (r^-1)s mod q */ 337 ret = nn_mul(&tmp, &rinv, s); EG(ret, err); /* r^-1 * s */ 338 ret = nn_mod(&uv, &tmp, q); EG(ret, err); /* (r^-1 * s) mod q */ 339 ret = prj_pt_mul(&vY, &uv, Y); EG(ret, err); 340 341 /* 6. Compute W' = uG + vY */ 342 ret = prj_pt_add(Wprime, &uG, &vY); EG(ret, err); 343 344 /* 7. Compute r' = W'_x mod q */ 345 ret = prj_pt_unique(Wprime, Wprime); EG(ret, err); 346 dbg_nn_print("W'_x", &(Wprime->X.fp_val)); 347 dbg_nn_print("W'_y", &(Wprime->Y.fp_val)); 348 ret = nn_mod(&r_prime, &(Wprime->X.fp_val), q); EG(ret, err); 349 350 /* 8. Accept the signature if and only if r equals r' */ 351 ret = nn_cmp(r, &r_prime, &cmp); EG(ret, err); 352 ret = (cmp != 0) ? -1 : 0; 353 354 err: 355 nn_uninit(&r_prime); 356 nn_uninit(&e); 357 nn_uninit(&uv); 358 nn_uninit(&tmp); 359 nn_uninit(&rinv); 360 361 prj_pt_uninit(&uG); 362 prj_pt_uninit(&vY); 363 364 /* 365 * We can now clear data part of the context. This will clear 366 * magic and avoid further reuse of the whole context. 367 */ 368 if(ctx != NULL){ 369 IGNORE_RET_VAL(local_memset(&(ctx->verify_data.ecgdsa), 0, 370 sizeof(ecgdsa_verify_data))); 371 } 372 373 PTR_NULLIFY(Wprime); 374 PTR_NULLIFY(r); 375 PTR_NULLIFY(s); 376 PTR_NULLIFY(G); 377 PTR_NULLIFY(Y); 378 PTR_NULLIFY(q); 379 VAR_ZEROIFY(hsize); 380 381 return ret; 382 } 383 384 385 #else /* WITH_SIG_ECGDSA && USE_CRYPTOFUZZ */ 386 387 /* 388 * Dummy definition to avoid the empty translation unit ISO C warning 389 */ 390 typedef int dummy; 391 #endif /* WITH_SIG_ECGDSA */ 392