1*f0865ec9SKyle Evans /* 2*f0865ec9SKyle Evans * Copyright (C) 2017 - This file is part of libecc project 3*f0865ec9SKyle Evans * 4*f0865ec9SKyle Evans * Authors: 5*f0865ec9SKyle Evans * Ryad BENADJILA <ryadbenadjila@gmail.com> 6*f0865ec9SKyle Evans * Arnaud EBALARD <arnaud.ebalard@ssi.gouv.fr> 7*f0865ec9SKyle Evans * Jean-Pierre FLORI <jean-pierre.flori@ssi.gouv.fr> 8*f0865ec9SKyle Evans * 9*f0865ec9SKyle Evans * Contributors: 10*f0865ec9SKyle Evans * Nicolas VIVET <nicolas.vivet@ssi.gouv.fr> 11*f0865ec9SKyle Evans * Karim KHALFALLAH <karim.khalfallah@ssi.gouv.fr> 12*f0865ec9SKyle Evans * 13*f0865ec9SKyle Evans * This software is licensed under a dual BSD and GPL v2 license. 14*f0865ec9SKyle Evans * See LICENSE file at the root folder of the project. 15*f0865ec9SKyle Evans */ 16*f0865ec9SKyle Evans #include <libecc/lib_ecc_config.h> 17*f0865ec9SKyle Evans #ifdef WITH_SIG_ECGDSA 18*f0865ec9SKyle Evans 19*f0865ec9SKyle Evans #include <libecc/nn/nn.h> 20*f0865ec9SKyle Evans #include <libecc/nn/nn_rand.h> 21*f0865ec9SKyle Evans #include <libecc/nn/nn_mul_public.h> 22*f0865ec9SKyle Evans #include <libecc/nn/nn_logical.h> 23*f0865ec9SKyle Evans 24*f0865ec9SKyle Evans #include <libecc/sig/sig_algs_internal.h> 25*f0865ec9SKyle Evans #include <libecc/sig/ec_key.h> 26*f0865ec9SKyle Evans #ifdef VERBOSE_INNER_VALUES 27*f0865ec9SKyle Evans #define EC_SIG_ALG "ECGDSA" 28*f0865ec9SKyle Evans #endif 29*f0865ec9SKyle Evans #include <libecc/utils/dbg_sig.h> 30*f0865ec9SKyle Evans 31*f0865ec9SKyle Evans int ecgdsa_init_pub_key(ec_pub_key *out_pub, const ec_priv_key *in_priv) 32*f0865ec9SKyle Evans { 33*f0865ec9SKyle Evans prj_pt_src_t G; 34*f0865ec9SKyle Evans nn_src_t q; 35*f0865ec9SKyle Evans nn xinv; 36*f0865ec9SKyle Evans int ret, cmp; 37*f0865ec9SKyle Evans xinv.magic = WORD(0); 38*f0865ec9SKyle Evans 39*f0865ec9SKyle Evans MUST_HAVE((out_pub != NULL), ret, err); 40*f0865ec9SKyle Evans 41*f0865ec9SKyle Evans /* Zero init public key to be generated */ 42*f0865ec9SKyle Evans ret = local_memset(out_pub, 0, sizeof(ec_pub_key)); EG(ret, err); 43*f0865ec9SKyle Evans 44*f0865ec9SKyle Evans ret = priv_key_check_initialized_and_type(in_priv, ECGDSA); EG(ret, err); 45*f0865ec9SKyle Evans q = &(in_priv->params->ec_gen_order); 46*f0865ec9SKyle Evans 47*f0865ec9SKyle Evans /* Sanity check on key */ 48*f0865ec9SKyle Evans MUST_HAVE((!nn_cmp(&(in_priv->x), q, &cmp)) && (cmp < 0), ret, err); 49*f0865ec9SKyle Evans 50*f0865ec9SKyle Evans /* Y = (x^-1)G */ 51*f0865ec9SKyle Evans G = &(in_priv->params->ec_gen); 52*f0865ec9SKyle Evans /* NOTE: we use Fermat's little theorem inversion for 53*f0865ec9SKyle Evans * constant time here. This is possible since q is prime. 54*f0865ec9SKyle Evans */ 55*f0865ec9SKyle Evans ret = nn_modinv_fermat(&xinv, &(in_priv->x), &(in_priv->params->ec_gen_order)); EG(ret, err); 56*f0865ec9SKyle Evans /* Use blinding with scalar_b when computing point scalar multiplication */ 57*f0865ec9SKyle Evans ret = prj_pt_mul_blind(&(out_pub->y), &xinv, G); EG(ret, err); 58*f0865ec9SKyle Evans 59*f0865ec9SKyle Evans out_pub->key_type = ECGDSA; 60*f0865ec9SKyle Evans out_pub->params = in_priv->params; 61*f0865ec9SKyle Evans out_pub->magic = PUB_KEY_MAGIC; 62*f0865ec9SKyle Evans 63*f0865ec9SKyle Evans err: 64*f0865ec9SKyle Evans nn_uninit(&xinv); 65*f0865ec9SKyle Evans 66*f0865ec9SKyle Evans return ret; 67*f0865ec9SKyle Evans } 68*f0865ec9SKyle Evans 69*f0865ec9SKyle Evans int ecgdsa_siglen(u16 p_bit_len, u16 q_bit_len, u8 hsize, u8 blocksize, u8 *siglen) 70*f0865ec9SKyle Evans { 71*f0865ec9SKyle Evans int ret; 72*f0865ec9SKyle Evans 73*f0865ec9SKyle Evans MUST_HAVE((siglen != NULL), ret, err); 74*f0865ec9SKyle Evans MUST_HAVE((p_bit_len <= CURVES_MAX_P_BIT_LEN) && 75*f0865ec9SKyle Evans (q_bit_len <= CURVES_MAX_Q_BIT_LEN) && 76*f0865ec9SKyle Evans (hsize <= MAX_DIGEST_SIZE) && (blocksize <= MAX_BLOCK_SIZE), ret, err); 77*f0865ec9SKyle Evans 78*f0865ec9SKyle Evans (*siglen) = (u8)ECGDSA_SIGLEN(q_bit_len); 79*f0865ec9SKyle Evans 80*f0865ec9SKyle Evans ret = 0; 81*f0865ec9SKyle Evans 82*f0865ec9SKyle Evans err: 83*f0865ec9SKyle Evans return ret; 84*f0865ec9SKyle Evans } 85*f0865ec9SKyle Evans 86*f0865ec9SKyle Evans /* 87*f0865ec9SKyle Evans * Generic *internal* EC-GDSA signature functions (init, update and finalize). 88*f0865ec9SKyle Evans * Their purpose is to allow passing a specific hash function (along with 89*f0865ec9SKyle Evans * its output size) and the random ephemeral key k, so that compliance 90*f0865ec9SKyle Evans * tests against test vectors can be made without ugly hack in the code 91*f0865ec9SKyle Evans * itself. 92*f0865ec9SKyle Evans * 93*f0865ec9SKyle Evans * Global EC-GDSA signature process is as follows (I,U,F provides 94*f0865ec9SKyle Evans * information in which function(s) (init(), update() or finalize()) 95*f0865ec9SKyle Evans * a specific step is performed): 96*f0865ec9SKyle Evans * 97*f0865ec9SKyle Evans *| IUF - EC-GDSA signature 98*f0865ec9SKyle Evans *| 99*f0865ec9SKyle Evans *| UF 1. Compute h = H(m). If |h| > bitlen(q), set h to bitlen(q) 100*f0865ec9SKyle Evans *| leftmost (most significant) bits of h 101*f0865ec9SKyle Evans *| F 2. Compute e = - OS2I(h) mod q 102*f0865ec9SKyle Evans *| F 3. Get a random value k in ]0,q[ 103*f0865ec9SKyle Evans *| F 4. Compute W = (W_x,W_y) = kG 104*f0865ec9SKyle Evans *| F 5. Compute r = W_x mod q 105*f0865ec9SKyle Evans *| F 6. If r is 0, restart the process at step 4. 106*f0865ec9SKyle Evans *| F 7. Compute s = x(kr + e) mod q 107*f0865ec9SKyle Evans *| F 8. If s is 0, restart the process at step 4. 108*f0865ec9SKyle Evans *| F 9. Return (r,s) 109*f0865ec9SKyle Evans * 110*f0865ec9SKyle Evans * Implementation notes: 111*f0865ec9SKyle Evans * 112*f0865ec9SKyle Evans * a) Usually (this is for instance the case in ISO 14888-3 and X9.62), the 113*f0865ec9SKyle Evans * process starts with steps 4 to 7 and is followed by steps 1 to 3. 114*f0865ec9SKyle Evans * The order is modified here w/o impact on the result and the security 115*f0865ec9SKyle Evans * in order to allow the algorithm to be compatible with an 116*f0865ec9SKyle Evans * init/update/finish API. More explicitly, the generation of k, which 117*f0865ec9SKyle Evans * may later result in a (unlikely) restart of the whole process is 118*f0865ec9SKyle Evans * postponed until the hash of the message has been computed. 119*f0865ec9SKyle Evans * b) sig is built as the concatenation of r and s. Both r and s are 120*f0865ec9SKyle Evans * encoded on ceil(bitlen(q)/8) bytes. 121*f0865ec9SKyle Evans * c) in EC-GDSA, the public part of the key is not needed per se during the 122*f0865ec9SKyle Evans * signature but - as it is needed in other signature algs implemented 123*f0865ec9SKyle Evans * in the library - the whole key pair is passed instead of just the 124*f0865ec9SKyle Evans * private key. 125*f0865ec9SKyle Evans */ 126*f0865ec9SKyle Evans 127*f0865ec9SKyle Evans #define ECGDSA_SIGN_MAGIC ((word_t)(0xe2f60ea3353ecc9eULL)) 128*f0865ec9SKyle Evans #define ECGDSA_SIGN_CHECK_INITIALIZED(A, ret, err) \ 129*f0865ec9SKyle Evans MUST_HAVE((((void *)(A)) != NULL) && \ 130*f0865ec9SKyle Evans ((A)->magic == ECGDSA_SIGN_MAGIC), ret, err) 131*f0865ec9SKyle Evans 132*f0865ec9SKyle Evans int _ecgdsa_sign_init(struct ec_sign_context *ctx) 133*f0865ec9SKyle Evans { 134*f0865ec9SKyle Evans int ret; 135*f0865ec9SKyle Evans 136*f0865ec9SKyle Evans /* First, verify context has been initialized */ 137*f0865ec9SKyle Evans ret = sig_sign_check_initialized(ctx); EG(ret, err); 138*f0865ec9SKyle Evans 139*f0865ec9SKyle Evans /* Additional sanity checks on input params from context */ 140*f0865ec9SKyle Evans ret = key_pair_check_initialized_and_type(ctx->key_pair, ECGDSA); EG(ret, err); 141*f0865ec9SKyle Evans MUST_HAVE((ctx->h != NULL) && (ctx->h->digest_size <= MAX_DIGEST_SIZE) && 142*f0865ec9SKyle Evans (ctx->h->block_size <= MAX_BLOCK_SIZE), ret, err); 143*f0865ec9SKyle Evans 144*f0865ec9SKyle Evans /* 145*f0865ec9SKyle Evans * Initialize hash context stored in our private part of context 146*f0865ec9SKyle Evans * and record data init has been done 147*f0865ec9SKyle Evans */ 148*f0865ec9SKyle Evans /* Since we call a callback, sanity check our mapping */ 149*f0865ec9SKyle Evans ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err); 150*f0865ec9SKyle Evans ret = ctx->h->hfunc_init(&(ctx->sign_data.ecgdsa.h_ctx)); EG(ret, err); 151*f0865ec9SKyle Evans 152*f0865ec9SKyle Evans ctx->sign_data.ecgdsa.magic = ECGDSA_SIGN_MAGIC; 153*f0865ec9SKyle Evans 154*f0865ec9SKyle Evans err: 155*f0865ec9SKyle Evans return ret; 156*f0865ec9SKyle Evans } 157*f0865ec9SKyle Evans 158*f0865ec9SKyle Evans int _ecgdsa_sign_update(struct ec_sign_context *ctx, 159*f0865ec9SKyle Evans const u8 *chunk, u32 chunklen) 160*f0865ec9SKyle Evans { 161*f0865ec9SKyle Evans int ret; 162*f0865ec9SKyle Evans 163*f0865ec9SKyle Evans /* 164*f0865ec9SKyle Evans * First, verify context has been initialized and private 165*f0865ec9SKyle Evans * part too. This guarantees the context is an EC-GDSA 166*f0865ec9SKyle Evans * signature one and we do not update() or finalize() 167*f0865ec9SKyle Evans * before init(). 168*f0865ec9SKyle Evans */ 169*f0865ec9SKyle Evans ret = sig_sign_check_initialized(ctx); EG(ret, err); 170*f0865ec9SKyle Evans ECGDSA_SIGN_CHECK_INITIALIZED(&(ctx->sign_data.ecgdsa), ret, err); 171*f0865ec9SKyle Evans 172*f0865ec9SKyle Evans /* 1. Compute h = H(m) */ 173*f0865ec9SKyle Evans /* Since we call a callback, sanity check our mapping */ 174*f0865ec9SKyle Evans ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err); 175*f0865ec9SKyle Evans ret = ctx->h->hfunc_update(&(ctx->sign_data.ecgdsa.h_ctx), chunk, chunklen); 176*f0865ec9SKyle Evans 177*f0865ec9SKyle Evans err: 178*f0865ec9SKyle Evans return ret; 179*f0865ec9SKyle Evans } 180*f0865ec9SKyle Evans 181*f0865ec9SKyle Evans int _ecgdsa_sign_finalize(struct ec_sign_context *ctx, u8 *sig, u8 siglen) 182*f0865ec9SKyle Evans { 183*f0865ec9SKyle Evans nn_src_t q, x; 184*f0865ec9SKyle Evans u8 e_buf[MAX_DIGEST_SIZE]; 185*f0865ec9SKyle Evans const ec_priv_key *priv_key; 186*f0865ec9SKyle Evans prj_pt_src_t G; 187*f0865ec9SKyle Evans u8 hsize, r_len, s_len; 188*f0865ec9SKyle Evans bitcnt_t q_bit_len, p_bit_len, rshift; 189*f0865ec9SKyle Evans prj_pt kG; 190*f0865ec9SKyle Evans int ret, cmp, iszero; 191*f0865ec9SKyle Evans nn tmp, s, e, kr, k, r; 192*f0865ec9SKyle Evans #ifdef USE_SIG_BLINDING 193*f0865ec9SKyle Evans /* b is the blinding mask */ 194*f0865ec9SKyle Evans nn b, binv; 195*f0865ec9SKyle Evans b.magic = binv.magic = WORD(0); 196*f0865ec9SKyle Evans #endif 197*f0865ec9SKyle Evans 198*f0865ec9SKyle Evans tmp.magic = s.magic = e.magic = WORD(0); 199*f0865ec9SKyle Evans kr.magic = k.magic = r.magic = WORD(0); 200*f0865ec9SKyle Evans kG.magic = WORD(0); 201*f0865ec9SKyle Evans 202*f0865ec9SKyle Evans /* 203*f0865ec9SKyle Evans * First, verify context has been initialized and private 204*f0865ec9SKyle Evans * part too. This guarantees the context is an EC-GDSA 205*f0865ec9SKyle Evans * signature one and we do not finalize() before init(). 206*f0865ec9SKyle Evans */ 207*f0865ec9SKyle Evans ret = sig_sign_check_initialized(ctx); EG(ret, err); 208*f0865ec9SKyle Evans ECGDSA_SIGN_CHECK_INITIALIZED(&(ctx->sign_data.ecgdsa), ret, err); 209*f0865ec9SKyle Evans MUST_HAVE((sig != NULL), ret, err); 210*f0865ec9SKyle Evans 211*f0865ec9SKyle Evans /* Zero init points */ 212*f0865ec9SKyle Evans ret = local_memset(&kG, 0, sizeof(prj_pt)); EG(ret, err); 213*f0865ec9SKyle Evans 214*f0865ec9SKyle Evans /* Make things more readable */ 215*f0865ec9SKyle Evans priv_key = &(ctx->key_pair->priv_key); 216*f0865ec9SKyle Evans G = &(priv_key->params->ec_gen); 217*f0865ec9SKyle Evans q = &(priv_key->params->ec_gen_order); 218*f0865ec9SKyle Evans x = &(priv_key->x); 219*f0865ec9SKyle Evans q_bit_len = priv_key->params->ec_gen_order_bitlen; 220*f0865ec9SKyle Evans p_bit_len = priv_key->params->ec_fp.p_bitlen; 221*f0865ec9SKyle Evans MUST_HAVE(((u32)BYTECEIL(p_bit_len) <= NN_MAX_BYTE_LEN), ret, err); 222*f0865ec9SKyle Evans r_len = (u8)ECGDSA_R_LEN(q_bit_len); 223*f0865ec9SKyle Evans s_len = (u8)ECGDSA_S_LEN(q_bit_len); 224*f0865ec9SKyle Evans hsize = ctx->h->digest_size; 225*f0865ec9SKyle Evans 226*f0865ec9SKyle Evans /* Sanity check */ 227*f0865ec9SKyle Evans ret = nn_cmp(x, q, &cmp); EG(ret, err); 228*f0865ec9SKyle Evans /* This should not happen and means that our 229*f0865ec9SKyle Evans * private key is not compliant! 230*f0865ec9SKyle Evans */ 231*f0865ec9SKyle Evans MUST_HAVE((cmp < 0), ret, err); 232*f0865ec9SKyle Evans 233*f0865ec9SKyle Evans MUST_HAVE((siglen == ECGDSA_SIGLEN(q_bit_len)), ret, err); 234*f0865ec9SKyle Evans 235*f0865ec9SKyle Evans dbg_nn_print("p", &(priv_key->params->ec_fp.p)); 236*f0865ec9SKyle Evans dbg_nn_print("q", q); 237*f0865ec9SKyle Evans dbg_priv_key_print("x", priv_key); 238*f0865ec9SKyle Evans dbg_ec_point_print("G", G); 239*f0865ec9SKyle Evans dbg_pub_key_print("Y", &(ctx->key_pair->pub_key)); 240*f0865ec9SKyle Evans 241*f0865ec9SKyle Evans /* 1. Compute h = H(m) */ 242*f0865ec9SKyle Evans ret = local_memset(e_buf, 0, hsize); EG(ret, err); 243*f0865ec9SKyle Evans /* Since we call a callback, sanity check our mapping */ 244*f0865ec9SKyle Evans ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err); 245*f0865ec9SKyle Evans ret = ctx->h->hfunc_finalize(&(ctx->sign_data.ecgdsa.h_ctx), e_buf); EG(ret, err); 246*f0865ec9SKyle Evans dbg_buf_print("H(m)", e_buf, hsize); 247*f0865ec9SKyle Evans 248*f0865ec9SKyle Evans /* 249*f0865ec9SKyle Evans * If |h| > bitlen(q), set h to bitlen(q) 250*f0865ec9SKyle Evans * leftmost bits of h. 251*f0865ec9SKyle Evans * 252*f0865ec9SKyle Evans */ 253*f0865ec9SKyle Evans rshift = 0; 254*f0865ec9SKyle Evans if ((hsize * 8) > q_bit_len) { 255*f0865ec9SKyle Evans rshift = (bitcnt_t)((hsize * 8) - q_bit_len); 256*f0865ec9SKyle Evans } 257*f0865ec9SKyle Evans ret = nn_init_from_buf(&tmp, e_buf, hsize); EG(ret, err); 258*f0865ec9SKyle Evans ret = local_memset(e_buf, 0, hsize); EG(ret, err); 259*f0865ec9SKyle Evans if (rshift) { 260*f0865ec9SKyle Evans ret = nn_rshift_fixedlen(&tmp, &tmp, rshift); EG(ret, err); 261*f0865ec9SKyle Evans } 262*f0865ec9SKyle Evans dbg_nn_print("H(m) truncated as nn", &tmp); 263*f0865ec9SKyle Evans 264*f0865ec9SKyle Evans /* 265*f0865ec9SKyle Evans * 2. Convert h to an integer and then compute e = -h mod q, 266*f0865ec9SKyle Evans * i.e. compute e = - OS2I(h) mod q 267*f0865ec9SKyle Evans * 268*f0865ec9SKyle Evans * Because we only support positive integers, we compute 269*f0865ec9SKyle Evans * e = q - (h mod q) (except when h is 0). 270*f0865ec9SKyle Evans */ 271*f0865ec9SKyle Evans ret = nn_mod(&tmp, &tmp, q); EG(ret, err); 272*f0865ec9SKyle Evans ret = nn_mod_neg(&e, &tmp, q); EG(ret, err); 273*f0865ec9SKyle Evans 274*f0865ec9SKyle Evans restart: 275*f0865ec9SKyle Evans /* 3. Get a random value k in ]0,q[ */ 276*f0865ec9SKyle Evans #ifdef NO_KNOWN_VECTORS 277*f0865ec9SKyle Evans /* NOTE: when we do not need self tests for known vectors, 278*f0865ec9SKyle Evans * we can be strict about random function handler! 279*f0865ec9SKyle Evans * This allows us to avoid the corruption of such a pointer. 280*f0865ec9SKyle Evans */ 281*f0865ec9SKyle Evans /* Sanity check on the handler before calling it */ 282*f0865ec9SKyle Evans MUST_HAVE(ctx->rand == nn_get_random_mod, ret, err); 283*f0865ec9SKyle Evans #endif 284*f0865ec9SKyle Evans MUST_HAVE(ctx->rand != NULL, ret, err); 285*f0865ec9SKyle Evans 286*f0865ec9SKyle Evans ret = ctx->rand(&k, q); EG(ret, err); 287*f0865ec9SKyle Evans 288*f0865ec9SKyle Evans #ifdef USE_SIG_BLINDING 289*f0865ec9SKyle Evans /* Note: if we use blinding, e and e are multiplied by 290*f0865ec9SKyle Evans * a random value b in ]0,q[ */ 291*f0865ec9SKyle Evans ret = nn_get_random_mod(&b, q); EG(ret, err); 292*f0865ec9SKyle Evans dbg_nn_print("b", &b); 293*f0865ec9SKyle Evans #endif /* USE_SIG_BLINDING */ 294*f0865ec9SKyle Evans 295*f0865ec9SKyle Evans /* 4. Compute W = kG = (Wx, Wy) */ 296*f0865ec9SKyle Evans #ifdef USE_SIG_BLINDING 297*f0865ec9SKyle Evans /* We use blinding for the scalar multiplication */ 298*f0865ec9SKyle Evans ret = prj_pt_mul_blind(&kG, &k, G); EG(ret, err); 299*f0865ec9SKyle Evans #else 300*f0865ec9SKyle Evans ret = prj_pt_mul(&kG, &k, G); EG(ret, err); 301*f0865ec9SKyle Evans #endif /* USE_SIG_BLINDING */ 302*f0865ec9SKyle Evans ret = prj_pt_unique(&kG, &kG); EG(ret, err); 303*f0865ec9SKyle Evans 304*f0865ec9SKyle Evans dbg_nn_print("W_x", &(kG.X.fp_val)); 305*f0865ec9SKyle Evans dbg_nn_print("W_y", &(kG.Y.fp_val)); 306*f0865ec9SKyle Evans 307*f0865ec9SKyle Evans /* 5. Compute r = Wx mod q */ 308*f0865ec9SKyle Evans ret = nn_mod(&r, &(kG.X.fp_val), q); EG(ret, err); 309*f0865ec9SKyle Evans dbg_nn_print("r", &r); 310*f0865ec9SKyle Evans 311*f0865ec9SKyle Evans /* 6. If r is 0, restart the process at step 4. */ 312*f0865ec9SKyle Evans ret = nn_iszero(&r, &iszero); EG(ret, err); 313*f0865ec9SKyle Evans if (iszero) { 314*f0865ec9SKyle Evans goto restart; 315*f0865ec9SKyle Evans } 316*f0865ec9SKyle Evans 317*f0865ec9SKyle Evans /* Export r */ 318*f0865ec9SKyle Evans ret = nn_export_to_buf(sig, r_len, &r); EG(ret, err); 319*f0865ec9SKyle Evans 320*f0865ec9SKyle Evans #ifdef USE_SIG_BLINDING 321*f0865ec9SKyle Evans /* Blind e and r with b */ 322*f0865ec9SKyle Evans ret = nn_mod_mul(&e, &e, &b, q); EG(ret, err); 323*f0865ec9SKyle Evans ret = nn_mod_mul(&r, &r, &b, q); EG(ret, err); 324*f0865ec9SKyle Evans #endif /* USE_SIG_BLINDING */ 325*f0865ec9SKyle Evans /* 7. Compute s = x(kr + e) mod q */ 326*f0865ec9SKyle Evans ret = nn_mod_mul(&kr, &k, &r, q); EG(ret, err); 327*f0865ec9SKyle Evans ret = nn_mod_add(&tmp, &kr, &e, q); EG(ret, err); 328*f0865ec9SKyle Evans ret = nn_mod_mul(&s, x, &tmp, q); EG(ret, err); 329*f0865ec9SKyle Evans #ifdef USE_SIG_BLINDING 330*f0865ec9SKyle Evans /* Unblind s */ 331*f0865ec9SKyle Evans /* NOTE: we use Fermat's little theorem inversion for 332*f0865ec9SKyle Evans * constant time here. This is possible since q is prime. 333*f0865ec9SKyle Evans */ 334*f0865ec9SKyle Evans ret = nn_modinv_fermat(&binv, &b, q); EG(ret, err); 335*f0865ec9SKyle Evans ret = nn_mod_mul(&s, &s, &binv, q); EG(ret, err); 336*f0865ec9SKyle Evans #endif 337*f0865ec9SKyle Evans dbg_nn_print("s", &s); 338*f0865ec9SKyle Evans 339*f0865ec9SKyle Evans /* 8. If s is 0, restart the process at step 4. */ 340*f0865ec9SKyle Evans ret = nn_iszero(&s, &iszero); EG(ret, err); 341*f0865ec9SKyle Evans if (iszero) { 342*f0865ec9SKyle Evans goto restart; 343*f0865ec9SKyle Evans } 344*f0865ec9SKyle Evans 345*f0865ec9SKyle Evans /* 9. Return (r,s) */ 346*f0865ec9SKyle Evans ret = nn_export_to_buf(sig + r_len, s_len, &s); 347*f0865ec9SKyle Evans 348*f0865ec9SKyle Evans err: 349*f0865ec9SKyle Evans nn_uninit(&tmp); 350*f0865ec9SKyle Evans nn_uninit(&s); 351*f0865ec9SKyle Evans nn_uninit(&e); 352*f0865ec9SKyle Evans nn_uninit(&kr); 353*f0865ec9SKyle Evans nn_uninit(&k); 354*f0865ec9SKyle Evans nn_uninit(&r); 355*f0865ec9SKyle Evans prj_pt_uninit(&kG); 356*f0865ec9SKyle Evans #ifdef USE_SIG_BLINDING 357*f0865ec9SKyle Evans nn_uninit(&b); 358*f0865ec9SKyle Evans nn_uninit(&binv); 359*f0865ec9SKyle Evans #endif 360*f0865ec9SKyle Evans 361*f0865ec9SKyle Evans /* 362*f0865ec9SKyle Evans * We can now clear data part of the context. This will clear 363*f0865ec9SKyle Evans * magic and avoid further reuse of the whole context. 364*f0865ec9SKyle Evans */ 365*f0865ec9SKyle Evans if(ctx != NULL){ 366*f0865ec9SKyle Evans IGNORE_RET_VAL(local_memset(&(ctx->sign_data.ecgdsa), 0, sizeof(ecgdsa_sign_data))); 367*f0865ec9SKyle Evans } 368*f0865ec9SKyle Evans 369*f0865ec9SKyle Evans /* Clean what remains on the stack */ 370*f0865ec9SKyle Evans VAR_ZEROIFY(q_bit_len); 371*f0865ec9SKyle Evans VAR_ZEROIFY(p_bit_len); 372*f0865ec9SKyle Evans VAR_ZEROIFY(r_len); 373*f0865ec9SKyle Evans VAR_ZEROIFY(s_len); 374*f0865ec9SKyle Evans VAR_ZEROIFY(hsize); 375*f0865ec9SKyle Evans PTR_NULLIFY(q); 376*f0865ec9SKyle Evans PTR_NULLIFY(x); 377*f0865ec9SKyle Evans PTR_NULLIFY(priv_key); 378*f0865ec9SKyle Evans PTR_NULLIFY(G); 379*f0865ec9SKyle Evans 380*f0865ec9SKyle Evans return ret; 381*f0865ec9SKyle Evans } 382*f0865ec9SKyle Evans 383*f0865ec9SKyle Evans /* 384*f0865ec9SKyle Evans * Generic *internal* EC-GDSA verification functions (init, update and finalize). 385*f0865ec9SKyle Evans * Their purpose is to allow passing a specific hash function (along with 386*f0865ec9SKyle Evans * their output size) and the random ephemeral key k, so that compliance 387*f0865ec9SKyle Evans * tests against test vectors can be made without ugly hack in the code 388*f0865ec9SKyle Evans * itself. 389*f0865ec9SKyle Evans * 390*f0865ec9SKyle Evans * Global EC-GDSA verification process is as follows (I,U,F provides 391*f0865ec9SKyle Evans * information in which function(s) (init(), update() or finalize()) 392*f0865ec9SKyle Evans * a specific step is performed): 393*f0865ec9SKyle Evans * 394*f0865ec9SKyle Evans *| IUF - EC-GDSA verification 395*f0865ec9SKyle Evans *| 396*f0865ec9SKyle Evans *| I 1. Reject the signature if r or s is 0. 397*f0865ec9SKyle Evans *| UF 2. Compute h = H(m). If |h| > bitlen(q), set h to bitlen(q) 398*f0865ec9SKyle Evans *| leftmost (most significant) bits of h 399*f0865ec9SKyle Evans *| F 3. Compute e = OS2I(h) mod q 400*f0865ec9SKyle Evans *| F 4. Compute u = ((r^-1)e mod q) 401*f0865ec9SKyle Evans *| F 5. Compute v = ((r^-1)s mod q) 402*f0865ec9SKyle Evans *| F 6. Compute W' = uG + vY 403*f0865ec9SKyle Evans *| F 7. Compute r' = W'_x mod q 404*f0865ec9SKyle Evans *| F 8. Accept the signature if and only if r equals r' 405*f0865ec9SKyle Evans * 406*f0865ec9SKyle Evans */ 407*f0865ec9SKyle Evans 408*f0865ec9SKyle Evans #define ECGDSA_VERIFY_MAGIC ((word_t)(0xd4da37527288d1b6ULL)) 409*f0865ec9SKyle Evans #define ECGDSA_VERIFY_CHECK_INITIALIZED(A, ret, err) \ 410*f0865ec9SKyle Evans MUST_HAVE((((void *)(A)) != NULL) && \ 411*f0865ec9SKyle Evans ((A)->magic == ECGDSA_VERIFY_MAGIC), ret, err) 412*f0865ec9SKyle Evans 413*f0865ec9SKyle Evans int _ecgdsa_verify_init(struct ec_verify_context *ctx, 414*f0865ec9SKyle Evans const u8 *sig, u8 siglen) 415*f0865ec9SKyle Evans { 416*f0865ec9SKyle Evans u8 r_len, s_len; 417*f0865ec9SKyle Evans bitcnt_t q_bit_len; 418*f0865ec9SKyle Evans nn_src_t q; 419*f0865ec9SKyle Evans nn *s, *r; 420*f0865ec9SKyle Evans int ret, iszero1, iszero2, cmp1, cmp2; 421*f0865ec9SKyle Evans 422*f0865ec9SKyle Evans /* First, verify context has been initialized */ 423*f0865ec9SKyle Evans ret = sig_verify_check_initialized(ctx); EG(ret, err); 424*f0865ec9SKyle Evans 425*f0865ec9SKyle Evans /* Do some sanity checks on input params */ 426*f0865ec9SKyle Evans ret = pub_key_check_initialized_and_type(ctx->pub_key, ECGDSA); EG(ret, err); 427*f0865ec9SKyle Evans MUST_HAVE((ctx->h != NULL) && (ctx->h->digest_size <= MAX_DIGEST_SIZE) && 428*f0865ec9SKyle Evans (ctx->h->block_size <= MAX_BLOCK_SIZE), ret, err); 429*f0865ec9SKyle Evans MUST_HAVE((sig != NULL), ret, err); 430*f0865ec9SKyle Evans 431*f0865ec9SKyle Evans /* Make things more readable */ 432*f0865ec9SKyle Evans q = &(ctx->pub_key->params->ec_gen_order); 433*f0865ec9SKyle Evans q_bit_len = ctx->pub_key->params->ec_gen_order_bitlen; 434*f0865ec9SKyle Evans r = &(ctx->verify_data.ecgdsa.r); 435*f0865ec9SKyle Evans s = &(ctx->verify_data.ecgdsa.s); 436*f0865ec9SKyle Evans r_len = (u8)ECGDSA_R_LEN(q_bit_len); 437*f0865ec9SKyle Evans s_len = (u8)ECGDSA_S_LEN(q_bit_len); 438*f0865ec9SKyle Evans 439*f0865ec9SKyle Evans /* Check given signature length is the expected one */ 440*f0865ec9SKyle Evans MUST_HAVE((siglen == ECGDSA_SIGLEN(q_bit_len)), ret, err); 441*f0865ec9SKyle Evans 442*f0865ec9SKyle Evans /* 1. Reject the signature if r or s is 0. */ 443*f0865ec9SKyle Evans 444*f0865ec9SKyle Evans /* Let's first import r, the x coordinates of the point reduced mod q */ 445*f0865ec9SKyle Evans ret = nn_init_from_buf(r, sig, r_len); EG(ret, err); 446*f0865ec9SKyle Evans 447*f0865ec9SKyle Evans /* Import s as a nn */ 448*f0865ec9SKyle Evans ret = nn_init_from_buf(s, sig + r_len, s_len); EG(ret, err); 449*f0865ec9SKyle Evans 450*f0865ec9SKyle Evans /* Check that r and s are both in ]0,q[ */ 451*f0865ec9SKyle Evans ret = nn_iszero(s, &iszero1); EG(ret, err); 452*f0865ec9SKyle Evans ret = nn_iszero(r, &iszero2); EG(ret, err); 453*f0865ec9SKyle Evans ret = nn_cmp(s, q, &cmp1); EG(ret, err); 454*f0865ec9SKyle Evans ret = nn_cmp(r, q, &cmp2); EG(ret, err); 455*f0865ec9SKyle Evans 456*f0865ec9SKyle Evans MUST_HAVE((!iszero1) && (cmp1 < 0) && (!iszero2) && (cmp2 < 0), ret, err); 457*f0865ec9SKyle Evans 458*f0865ec9SKyle Evans /* Initialize the remaining of verify context */ 459*f0865ec9SKyle Evans /* Since we call a callback, sanity check our mapping */ 460*f0865ec9SKyle Evans ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err); 461*f0865ec9SKyle Evans ret = ctx->h->hfunc_init(&(ctx->verify_data.ecgdsa.h_ctx)); EG(ret, err); 462*f0865ec9SKyle Evans 463*f0865ec9SKyle Evans ctx->verify_data.ecgdsa.magic = ECGDSA_VERIFY_MAGIC; 464*f0865ec9SKyle Evans 465*f0865ec9SKyle Evans err: 466*f0865ec9SKyle Evans VAR_ZEROIFY(q_bit_len); 467*f0865ec9SKyle Evans VAR_ZEROIFY(r_len); 468*f0865ec9SKyle Evans VAR_ZEROIFY(s_len); 469*f0865ec9SKyle Evans PTR_NULLIFY(q); 470*f0865ec9SKyle Evans PTR_NULLIFY(s); 471*f0865ec9SKyle Evans PTR_NULLIFY(r); 472*f0865ec9SKyle Evans 473*f0865ec9SKyle Evans return ret; 474*f0865ec9SKyle Evans } 475*f0865ec9SKyle Evans 476*f0865ec9SKyle Evans int _ecgdsa_verify_update(struct ec_verify_context *ctx, 477*f0865ec9SKyle Evans const u8 *chunk, u32 chunklen) 478*f0865ec9SKyle Evans { 479*f0865ec9SKyle Evans int ret; 480*f0865ec9SKyle Evans 481*f0865ec9SKyle Evans /* 482*f0865ec9SKyle Evans * First, verify context has been initialized and public 483*f0865ec9SKyle Evans * part too. This guarantees the context is an EC-GDSA 484*f0865ec9SKyle Evans * verification one and we do not update() or finalize() 485*f0865ec9SKyle Evans * before init(). 486*f0865ec9SKyle Evans */ 487*f0865ec9SKyle Evans ret = sig_verify_check_initialized(ctx); EG(ret, err); 488*f0865ec9SKyle Evans ECGDSA_VERIFY_CHECK_INITIALIZED(&(ctx->verify_data.ecgdsa), ret, err); 489*f0865ec9SKyle Evans 490*f0865ec9SKyle Evans /* 2. Compute h = H(m) */ 491*f0865ec9SKyle Evans /* Since we call a callback, sanity check our mapping */ 492*f0865ec9SKyle Evans ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err); 493*f0865ec9SKyle Evans ret = ctx->h->hfunc_update(&(ctx->verify_data.ecgdsa.h_ctx), chunk, 494*f0865ec9SKyle Evans chunklen); 495*f0865ec9SKyle Evans 496*f0865ec9SKyle Evans err: 497*f0865ec9SKyle Evans return ret; 498*f0865ec9SKyle Evans } 499*f0865ec9SKyle Evans 500*f0865ec9SKyle Evans int _ecgdsa_verify_finalize(struct ec_verify_context *ctx) 501*f0865ec9SKyle Evans { 502*f0865ec9SKyle Evans nn e, r_prime, rinv, uv, *r, *s; 503*f0865ec9SKyle Evans prj_pt uG, vY; 504*f0865ec9SKyle Evans prj_pt_t Wprime; 505*f0865ec9SKyle Evans prj_pt_src_t G, Y; 506*f0865ec9SKyle Evans u8 e_buf[MAX_DIGEST_SIZE]; 507*f0865ec9SKyle Evans nn_src_t q; 508*f0865ec9SKyle Evans u8 hsize; 509*f0865ec9SKyle Evans bitcnt_t q_bit_len, rshift; 510*f0865ec9SKyle Evans int ret, cmp; 511*f0865ec9SKyle Evans 512*f0865ec9SKyle Evans e.magic = r_prime.magic = WORD(0); 513*f0865ec9SKyle Evans rinv.magic = uv.magic = WORD(0); 514*f0865ec9SKyle Evans uG.magic = vY.magic = WORD(0); 515*f0865ec9SKyle Evans 516*f0865ec9SKyle Evans /* NOTE: we reuse uG for Wprime to optimize local variables */ 517*f0865ec9SKyle Evans Wprime = &uG; 518*f0865ec9SKyle Evans 519*f0865ec9SKyle Evans /* 520*f0865ec9SKyle Evans * First, verify context has been initialized and public 521*f0865ec9SKyle Evans * part too. This guarantees the context is an EC-GDSA 522*f0865ec9SKyle Evans * verification one and we do not finalize() before init(). 523*f0865ec9SKyle Evans */ 524*f0865ec9SKyle Evans ret = sig_verify_check_initialized(ctx); EG(ret, err); 525*f0865ec9SKyle Evans ECGDSA_VERIFY_CHECK_INITIALIZED(&(ctx->verify_data.ecgdsa), ret, err); 526*f0865ec9SKyle Evans 527*f0865ec9SKyle Evans /* Zero init points */ 528*f0865ec9SKyle Evans ret = local_memset(&uG, 0, sizeof(prj_pt)); EG(ret, err); 529*f0865ec9SKyle Evans ret = local_memset(&vY, 0, sizeof(prj_pt)); EG(ret, err); 530*f0865ec9SKyle Evans 531*f0865ec9SKyle Evans /* Make things more readable */ 532*f0865ec9SKyle Evans G = &(ctx->pub_key->params->ec_gen); 533*f0865ec9SKyle Evans Y = &(ctx->pub_key->y); 534*f0865ec9SKyle Evans q = &(ctx->pub_key->params->ec_gen_order); 535*f0865ec9SKyle Evans r = &(ctx->verify_data.ecgdsa.r); 536*f0865ec9SKyle Evans s = &(ctx->verify_data.ecgdsa.s); 537*f0865ec9SKyle Evans q_bit_len = ctx->pub_key->params->ec_gen_order_bitlen; 538*f0865ec9SKyle Evans hsize = ctx->h->digest_size; 539*f0865ec9SKyle Evans 540*f0865ec9SKyle Evans /* 2. Compute h = H(m) */ 541*f0865ec9SKyle Evans /* Since we call a callback, sanity check our mapping */ 542*f0865ec9SKyle Evans ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err); 543*f0865ec9SKyle Evans ret = ctx->h->hfunc_finalize(&(ctx->verify_data.ecgdsa.h_ctx), e_buf); EG(ret, err); 544*f0865ec9SKyle Evans dbg_buf_print("H(m)", e_buf, hsize); 545*f0865ec9SKyle Evans 546*f0865ec9SKyle Evans /* 547*f0865ec9SKyle Evans * If |h| > bitlen(q), set h to bitlen(q) 548*f0865ec9SKyle Evans * leftmost bits of h. 549*f0865ec9SKyle Evans * 550*f0865ec9SKyle Evans */ 551*f0865ec9SKyle Evans rshift = 0; 552*f0865ec9SKyle Evans if ((hsize * 8) > q_bit_len) { 553*f0865ec9SKyle Evans rshift = (bitcnt_t)((hsize * 8) - q_bit_len); 554*f0865ec9SKyle Evans } 555*f0865ec9SKyle Evans ret = nn_init_from_buf(&e, e_buf, hsize); EG(ret, err); 556*f0865ec9SKyle Evans ret = local_memset(e_buf, 0, hsize); EG(ret, err); 557*f0865ec9SKyle Evans if (rshift) { 558*f0865ec9SKyle Evans ret = nn_rshift_fixedlen(&e, &e, rshift); EG(ret, err); 559*f0865ec9SKyle Evans } 560*f0865ec9SKyle Evans dbg_nn_print("H(m) truncated as nn", &e); 561*f0865ec9SKyle Evans 562*f0865ec9SKyle Evans /* 3. Compute e by converting h to an integer and reducing it mod q */ 563*f0865ec9SKyle Evans ret = nn_mod(&e, &e, q); EG(ret, err); 564*f0865ec9SKyle Evans 565*f0865ec9SKyle Evans /* 4. Compute u = (r^-1)e mod q */ 566*f0865ec9SKyle Evans ret = nn_modinv(&rinv, r, q); EG(ret, err); /* r^-1 */ 567*f0865ec9SKyle Evans ret = nn_mod_mul(&uv, &rinv, &e, q); EG(ret, err); 568*f0865ec9SKyle Evans ret = prj_pt_mul(&uG, &uv, G); EG(ret, err); 569*f0865ec9SKyle Evans 570*f0865ec9SKyle Evans /* 5. Compute v = (r^-1)s mod q */ 571*f0865ec9SKyle Evans ret = nn_mod_mul(&uv, &rinv, s, q); EG(ret, err); 572*f0865ec9SKyle Evans ret = prj_pt_mul(&vY, &uv, Y); EG(ret, err); 573*f0865ec9SKyle Evans 574*f0865ec9SKyle Evans /* 6. Compute W' = uG + vY */ 575*f0865ec9SKyle Evans ret = prj_pt_add(Wprime, &uG, &vY); EG(ret, err); 576*f0865ec9SKyle Evans 577*f0865ec9SKyle Evans /* 7. Compute r' = W'_x mod q */ 578*f0865ec9SKyle Evans ret = prj_pt_unique(Wprime, Wprime); EG(ret, err); 579*f0865ec9SKyle Evans dbg_nn_print("W'_x", &(Wprime->X.fp_val)); 580*f0865ec9SKyle Evans dbg_nn_print("W'_y", &(Wprime->Y.fp_val)); 581*f0865ec9SKyle Evans ret = nn_mod(&r_prime, &(Wprime->X.fp_val), q); EG(ret, err); 582*f0865ec9SKyle Evans 583*f0865ec9SKyle Evans /* 8. Accept the signature if and only if r equals r' */ 584*f0865ec9SKyle Evans ret = nn_cmp(r, &r_prime, &cmp); EG(ret, err); 585*f0865ec9SKyle Evans ret = (cmp != 0) ? -1 : 0; 586*f0865ec9SKyle Evans 587*f0865ec9SKyle Evans err: 588*f0865ec9SKyle Evans nn_uninit(&e); 589*f0865ec9SKyle Evans nn_uninit(&r_prime); 590*f0865ec9SKyle Evans nn_uninit(&rinv); 591*f0865ec9SKyle Evans nn_uninit(&uv); 592*f0865ec9SKyle Evans prj_pt_uninit(&uG); 593*f0865ec9SKyle Evans prj_pt_uninit(&vY); 594*f0865ec9SKyle Evans 595*f0865ec9SKyle Evans /* 596*f0865ec9SKyle Evans * We can now clear data part of the context. This will clear 597*f0865ec9SKyle Evans * magic and avoid further reuse of the whole context. 598*f0865ec9SKyle Evans */ 599*f0865ec9SKyle Evans if(ctx != NULL){ 600*f0865ec9SKyle Evans IGNORE_RET_VAL(local_memset(&(ctx->verify_data.ecgdsa), 0, 601*f0865ec9SKyle Evans sizeof(ecgdsa_verify_data))); 602*f0865ec9SKyle Evans } 603*f0865ec9SKyle Evans 604*f0865ec9SKyle Evans PTR_NULLIFY(Wprime); 605*f0865ec9SKyle Evans PTR_NULLIFY(r); 606*f0865ec9SKyle Evans PTR_NULLIFY(s); 607*f0865ec9SKyle Evans PTR_NULLIFY(G); 608*f0865ec9SKyle Evans PTR_NULLIFY(Y); 609*f0865ec9SKyle Evans PTR_NULLIFY(q); 610*f0865ec9SKyle Evans VAR_ZEROIFY(hsize); 611*f0865ec9SKyle Evans 612*f0865ec9SKyle Evans return ret; 613*f0865ec9SKyle Evans } 614*f0865ec9SKyle Evans 615*f0865ec9SKyle Evans #else /* WITH_SIG_ECGDSA */ 616*f0865ec9SKyle Evans 617*f0865ec9SKyle Evans /* 618*f0865ec9SKyle Evans * Dummy definition to avoid the empty translation unit ISO C warning 619*f0865ec9SKyle Evans */ 620*f0865ec9SKyle Evans typedef int dummy; 621*f0865ec9SKyle Evans #endif /* WITH_SIG_ECGDSA */ 622