/* * Copyright (C) 2017 - This file is part of libecc project * * Authors: * Ryad BENADJILA * Arnaud EBALARD * Jean-Pierre FLORI * * Contributors: * Nicolas VIVET * Karim KHALFALLAH * * This software is licensed under a dual BSD and GPL v2 license. * See LICENSE file at the root folder of the project. */ #include #ifdef WITH_SIG_ECGDSA #include #include #include #include #include #include #ifdef VERBOSE_INNER_VALUES #define EC_SIG_ALG "ECGDSA" #endif #include int ecgdsa_init_pub_key(ec_pub_key *out_pub, const ec_priv_key *in_priv) { prj_pt_src_t G; nn_src_t q; nn xinv; int ret, cmp; xinv.magic = WORD(0); MUST_HAVE((out_pub != NULL), ret, err); /* Zero init public key to be generated */ ret = local_memset(out_pub, 0, sizeof(ec_pub_key)); EG(ret, err); ret = priv_key_check_initialized_and_type(in_priv, ECGDSA); EG(ret, err); q = &(in_priv->params->ec_gen_order); /* Sanity check on key */ MUST_HAVE((!nn_cmp(&(in_priv->x), q, &cmp)) && (cmp < 0), ret, err); /* Y = (x^-1)G */ G = &(in_priv->params->ec_gen); /* NOTE: we use Fermat's little theorem inversion for * constant time here. This is possible since q is prime. */ ret = nn_modinv_fermat(&xinv, &(in_priv->x), &(in_priv->params->ec_gen_order)); EG(ret, err); /* Use blinding with scalar_b when computing point scalar multiplication */ ret = prj_pt_mul_blind(&(out_pub->y), &xinv, G); EG(ret, err); out_pub->key_type = ECGDSA; out_pub->params = in_priv->params; out_pub->magic = PUB_KEY_MAGIC; err: nn_uninit(&xinv); return ret; } int ecgdsa_siglen(u16 p_bit_len, u16 q_bit_len, u8 hsize, u8 blocksize, u8 *siglen) { int ret; MUST_HAVE((siglen != NULL), ret, err); MUST_HAVE((p_bit_len <= CURVES_MAX_P_BIT_LEN) && (q_bit_len <= CURVES_MAX_Q_BIT_LEN) && (hsize <= MAX_DIGEST_SIZE) && (blocksize <= MAX_BLOCK_SIZE), ret, err); (*siglen) = (u8)ECGDSA_SIGLEN(q_bit_len); ret = 0; err: return ret; } /* * Generic *internal* EC-GDSA signature functions (init, update and finalize). * Their purpose is to allow passing a specific hash function (along with * its output size) and the random ephemeral key k, so that compliance * tests against test vectors can be made without ugly hack in the code * itself. * * Global EC-GDSA signature process is as follows (I,U,F provides * information in which function(s) (init(), update() or finalize()) * a specific step is performed): * *| IUF - EC-GDSA signature *| *| UF 1. Compute h = H(m). If |h| > bitlen(q), set h to bitlen(q) *| leftmost (most significant) bits of h *| F 2. Compute e = - OS2I(h) mod q *| F 3. Get a random value k in ]0,q[ *| F 4. Compute W = (W_x,W_y) = kG *| F 5. Compute r = W_x mod q *| F 6. If r is 0, restart the process at step 4. *| F 7. Compute s = x(kr + e) mod q *| F 8. If s is 0, restart the process at step 4. *| F 9. Return (r,s) * * Implementation notes: * * a) Usually (this is for instance the case in ISO 14888-3 and X9.62), the * process starts with steps 4 to 7 and is followed by steps 1 to 3. * The order is modified here w/o impact on the result and the security * in order to allow the algorithm to be compatible with an * init/update/finish API. More explicitly, the generation of k, which * may later result in a (unlikely) restart of the whole process is * postponed until the hash of the message has been computed. * b) sig is built as the concatenation of r and s. Both r and s are * encoded on ceil(bitlen(q)/8) bytes. * c) in EC-GDSA, the public part of the key is not needed per se during the * signature but - as it is needed in other signature algs implemented * in the library - the whole key pair is passed instead of just the * private key. */ #define ECGDSA_SIGN_MAGIC ((word_t)(0xe2f60ea3353ecc9eULL)) #define ECGDSA_SIGN_CHECK_INITIALIZED(A, ret, err) \ MUST_HAVE((((void *)(A)) != NULL) && \ ((A)->magic == ECGDSA_SIGN_MAGIC), ret, err) int _ecgdsa_sign_init(struct ec_sign_context *ctx) { int ret; /* First, verify context has been initialized */ ret = sig_sign_check_initialized(ctx); EG(ret, err); /* Additional sanity checks on input params from context */ ret = key_pair_check_initialized_and_type(ctx->key_pair, ECGDSA); EG(ret, err); MUST_HAVE((ctx->h != NULL) && (ctx->h->digest_size <= MAX_DIGEST_SIZE) && (ctx->h->block_size <= MAX_BLOCK_SIZE), ret, err); /* * Initialize hash context stored in our private part of context * and record data init has been done */ /* Since we call a callback, sanity check our mapping */ ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err); ret = ctx->h->hfunc_init(&(ctx->sign_data.ecgdsa.h_ctx)); EG(ret, err); ctx->sign_data.ecgdsa.magic = ECGDSA_SIGN_MAGIC; err: return ret; } int _ecgdsa_sign_update(struct ec_sign_context *ctx, const u8 *chunk, u32 chunklen) { int ret; /* * First, verify context has been initialized and private * part too. This guarantees the context is an EC-GDSA * signature one and we do not update() or finalize() * before init(). */ ret = sig_sign_check_initialized(ctx); EG(ret, err); ECGDSA_SIGN_CHECK_INITIALIZED(&(ctx->sign_data.ecgdsa), ret, err); /* 1. Compute h = H(m) */ /* Since we call a callback, sanity check our mapping */ ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err); ret = ctx->h->hfunc_update(&(ctx->sign_data.ecgdsa.h_ctx), chunk, chunklen); err: return ret; } int _ecgdsa_sign_finalize(struct ec_sign_context *ctx, u8 *sig, u8 siglen) { nn_src_t q, x; u8 e_buf[MAX_DIGEST_SIZE]; const ec_priv_key *priv_key; prj_pt_src_t G; u8 hsize, r_len, s_len; bitcnt_t q_bit_len, p_bit_len, rshift; prj_pt kG; int ret, cmp, iszero; nn tmp, s, e, kr, k, r; #ifdef USE_SIG_BLINDING /* b is the blinding mask */ nn b, binv; b.magic = binv.magic = WORD(0); #endif tmp.magic = s.magic = e.magic = WORD(0); kr.magic = k.magic = r.magic = WORD(0); kG.magic = WORD(0); /* * First, verify context has been initialized and private * part too. This guarantees the context is an EC-GDSA * signature one and we do not finalize() before init(). */ ret = sig_sign_check_initialized(ctx); EG(ret, err); ECGDSA_SIGN_CHECK_INITIALIZED(&(ctx->sign_data.ecgdsa), ret, err); MUST_HAVE((sig != NULL), ret, err); /* Zero init points */ ret = local_memset(&kG, 0, sizeof(prj_pt)); EG(ret, err); /* Make things more readable */ priv_key = &(ctx->key_pair->priv_key); G = &(priv_key->params->ec_gen); q = &(priv_key->params->ec_gen_order); x = &(priv_key->x); q_bit_len = priv_key->params->ec_gen_order_bitlen; p_bit_len = priv_key->params->ec_fp.p_bitlen; MUST_HAVE(((u32)BYTECEIL(p_bit_len) <= NN_MAX_BYTE_LEN), ret, err); r_len = (u8)ECGDSA_R_LEN(q_bit_len); s_len = (u8)ECGDSA_S_LEN(q_bit_len); hsize = ctx->h->digest_size; /* Sanity check */ ret = nn_cmp(x, q, &cmp); EG(ret, err); /* This should not happen and means that our * private key is not compliant! */ MUST_HAVE((cmp < 0), ret, err); MUST_HAVE((siglen == ECGDSA_SIGLEN(q_bit_len)), ret, err); dbg_nn_print("p", &(priv_key->params->ec_fp.p)); dbg_nn_print("q", q); dbg_priv_key_print("x", priv_key); dbg_ec_point_print("G", G); dbg_pub_key_print("Y", &(ctx->key_pair->pub_key)); /* 1. Compute h = H(m) */ ret = local_memset(e_buf, 0, hsize); EG(ret, err); /* Since we call a callback, sanity check our mapping */ ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err); ret = ctx->h->hfunc_finalize(&(ctx->sign_data.ecgdsa.h_ctx), e_buf); EG(ret, err); dbg_buf_print("H(m)", e_buf, hsize); /* * If |h| > bitlen(q), set h to bitlen(q) * leftmost bits of h. * */ rshift = 0; if ((hsize * 8) > q_bit_len) { rshift = (bitcnt_t)((hsize * 8) - q_bit_len); } ret = nn_init_from_buf(&tmp, e_buf, hsize); EG(ret, err); ret = local_memset(e_buf, 0, hsize); EG(ret, err); if (rshift) { ret = nn_rshift_fixedlen(&tmp, &tmp, rshift); EG(ret, err); } dbg_nn_print("H(m) truncated as nn", &tmp); /* * 2. Convert h to an integer and then compute e = -h mod q, * i.e. compute e = - OS2I(h) mod q * * Because we only support positive integers, we compute * e = q - (h mod q) (except when h is 0). */ ret = nn_mod(&tmp, &tmp, q); EG(ret, err); ret = nn_mod_neg(&e, &tmp, q); EG(ret, err); restart: /* 3. Get a random value k in ]0,q[ */ #ifdef NO_KNOWN_VECTORS /* NOTE: when we do not need self tests for known vectors, * we can be strict about random function handler! * This allows us to avoid the corruption of such a pointer. */ /* Sanity check on the handler before calling it */ MUST_HAVE(ctx->rand == nn_get_random_mod, ret, err); #endif MUST_HAVE(ctx->rand != NULL, ret, err); ret = ctx->rand(&k, q); EG(ret, err); #ifdef USE_SIG_BLINDING /* Note: if we use blinding, e and e are multiplied by * a random value b in ]0,q[ */ ret = nn_get_random_mod(&b, q); EG(ret, err); dbg_nn_print("b", &b); #endif /* USE_SIG_BLINDING */ /* 4. Compute W = kG = (Wx, Wy) */ #ifdef USE_SIG_BLINDING /* We use blinding for the scalar multiplication */ ret = prj_pt_mul_blind(&kG, &k, G); EG(ret, err); #else ret = prj_pt_mul(&kG, &k, G); EG(ret, err); #endif /* USE_SIG_BLINDING */ ret = prj_pt_unique(&kG, &kG); EG(ret, err); dbg_nn_print("W_x", &(kG.X.fp_val)); dbg_nn_print("W_y", &(kG.Y.fp_val)); /* 5. Compute r = Wx mod q */ ret = nn_mod(&r, &(kG.X.fp_val), q); EG(ret, err); dbg_nn_print("r", &r); /* 6. If r is 0, restart the process at step 4. */ ret = nn_iszero(&r, &iszero); EG(ret, err); if (iszero) { goto restart; } /* Export r */ ret = nn_export_to_buf(sig, r_len, &r); EG(ret, err); #ifdef USE_SIG_BLINDING /* Blind e and r with b */ ret = nn_mod_mul(&e, &e, &b, q); EG(ret, err); ret = nn_mod_mul(&r, &r, &b, q); EG(ret, err); #endif /* USE_SIG_BLINDING */ /* 7. Compute s = x(kr + e) mod q */ ret = nn_mod_mul(&kr, &k, &r, q); EG(ret, err); ret = nn_mod_add(&tmp, &kr, &e, q); EG(ret, err); ret = nn_mod_mul(&s, x, &tmp, q); EG(ret, err); #ifdef USE_SIG_BLINDING /* Unblind s */ /* NOTE: we use Fermat's little theorem inversion for * constant time here. This is possible since q is prime. */ ret = nn_modinv_fermat(&binv, &b, q); EG(ret, err); ret = nn_mod_mul(&s, &s, &binv, q); EG(ret, err); #endif dbg_nn_print("s", &s); /* 8. If s is 0, restart the process at step 4. */ ret = nn_iszero(&s, &iszero); EG(ret, err); if (iszero) { goto restart; } /* 9. Return (r,s) */ ret = nn_export_to_buf(sig + r_len, s_len, &s); err: nn_uninit(&tmp); nn_uninit(&s); nn_uninit(&e); nn_uninit(&kr); nn_uninit(&k); nn_uninit(&r); prj_pt_uninit(&kG); #ifdef USE_SIG_BLINDING nn_uninit(&b); nn_uninit(&binv); #endif /* * We can now clear data part of the context. This will clear * magic and avoid further reuse of the whole context. */ if(ctx != NULL){ IGNORE_RET_VAL(local_memset(&(ctx->sign_data.ecgdsa), 0, sizeof(ecgdsa_sign_data))); } /* Clean what remains on the stack */ VAR_ZEROIFY(q_bit_len); VAR_ZEROIFY(p_bit_len); VAR_ZEROIFY(r_len); VAR_ZEROIFY(s_len); VAR_ZEROIFY(hsize); PTR_NULLIFY(q); PTR_NULLIFY(x); PTR_NULLIFY(priv_key); PTR_NULLIFY(G); return ret; } /* * Generic *internal* EC-GDSA verification functions (init, update and finalize). * Their purpose is to allow passing a specific hash function (along with * their output size) and the random ephemeral key k, so that compliance * tests against test vectors can be made without ugly hack in the code * itself. * * Global EC-GDSA verification process is as follows (I,U,F provides * information in which function(s) (init(), update() or finalize()) * a specific step is performed): * *| IUF - EC-GDSA verification *| *| I 1. Reject the signature if r or s is 0. *| UF 2. Compute h = H(m). If |h| > bitlen(q), set h to bitlen(q) *| leftmost (most significant) bits of h *| F 3. Compute e = OS2I(h) mod q *| F 4. Compute u = ((r^-1)e mod q) *| F 5. Compute v = ((r^-1)s mod q) *| F 6. Compute W' = uG + vY *| F 7. Compute r' = W'_x mod q *| F 8. Accept the signature if and only if r equals r' * */ #define ECGDSA_VERIFY_MAGIC ((word_t)(0xd4da37527288d1b6ULL)) #define ECGDSA_VERIFY_CHECK_INITIALIZED(A, ret, err) \ MUST_HAVE((((void *)(A)) != NULL) && \ ((A)->magic == ECGDSA_VERIFY_MAGIC), ret, err) int _ecgdsa_verify_init(struct ec_verify_context *ctx, const u8 *sig, u8 siglen) { u8 r_len, s_len; bitcnt_t q_bit_len; nn_src_t q; nn *s, *r; int ret, iszero1, iszero2, cmp1, cmp2; /* First, verify context has been initialized */ ret = sig_verify_check_initialized(ctx); EG(ret, err); /* Do some sanity checks on input params */ ret = pub_key_check_initialized_and_type(ctx->pub_key, ECGDSA); EG(ret, err); MUST_HAVE((ctx->h != NULL) && (ctx->h->digest_size <= MAX_DIGEST_SIZE) && (ctx->h->block_size <= MAX_BLOCK_SIZE), ret, err); MUST_HAVE((sig != NULL), ret, err); /* Make things more readable */ q = &(ctx->pub_key->params->ec_gen_order); q_bit_len = ctx->pub_key->params->ec_gen_order_bitlen; r = &(ctx->verify_data.ecgdsa.r); s = &(ctx->verify_data.ecgdsa.s); r_len = (u8)ECGDSA_R_LEN(q_bit_len); s_len = (u8)ECGDSA_S_LEN(q_bit_len); /* Check given signature length is the expected one */ MUST_HAVE((siglen == ECGDSA_SIGLEN(q_bit_len)), ret, err); /* 1. Reject the signature if r or s is 0. */ /* Let's first import r, the x coordinates of the point reduced mod q */ ret = nn_init_from_buf(r, sig, r_len); EG(ret, err); /* Import s as a nn */ ret = nn_init_from_buf(s, sig + r_len, s_len); EG(ret, err); /* Check that r and s are both in ]0,q[ */ ret = nn_iszero(s, &iszero1); EG(ret, err); ret = nn_iszero(r, &iszero2); EG(ret, err); ret = nn_cmp(s, q, &cmp1); EG(ret, err); ret = nn_cmp(r, q, &cmp2); EG(ret, err); MUST_HAVE((!iszero1) && (cmp1 < 0) && (!iszero2) && (cmp2 < 0), ret, err); /* Initialize the remaining of verify context */ /* Since we call a callback, sanity check our mapping */ ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err); ret = ctx->h->hfunc_init(&(ctx->verify_data.ecgdsa.h_ctx)); EG(ret, err); ctx->verify_data.ecgdsa.magic = ECGDSA_VERIFY_MAGIC; err: VAR_ZEROIFY(q_bit_len); VAR_ZEROIFY(r_len); VAR_ZEROIFY(s_len); PTR_NULLIFY(q); PTR_NULLIFY(s); PTR_NULLIFY(r); return ret; } int _ecgdsa_verify_update(struct ec_verify_context *ctx, const u8 *chunk, u32 chunklen) { int ret; /* * First, verify context has been initialized and public * part too. This guarantees the context is an EC-GDSA * verification one and we do not update() or finalize() * before init(). */ ret = sig_verify_check_initialized(ctx); EG(ret, err); ECGDSA_VERIFY_CHECK_INITIALIZED(&(ctx->verify_data.ecgdsa), ret, err); /* 2. Compute h = H(m) */ /* Since we call a callback, sanity check our mapping */ ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err); ret = ctx->h->hfunc_update(&(ctx->verify_data.ecgdsa.h_ctx), chunk, chunklen); err: return ret; } int _ecgdsa_verify_finalize(struct ec_verify_context *ctx) { nn e, r_prime, rinv, uv, *r, *s; prj_pt uG, vY; prj_pt_t Wprime; prj_pt_src_t G, Y; u8 e_buf[MAX_DIGEST_SIZE]; nn_src_t q; u8 hsize; bitcnt_t q_bit_len, rshift; int ret, cmp; e.magic = r_prime.magic = WORD(0); rinv.magic = uv.magic = WORD(0); uG.magic = vY.magic = WORD(0); /* NOTE: we reuse uG for Wprime to optimize local variables */ Wprime = &uG; /* * First, verify context has been initialized and public * part too. This guarantees the context is an EC-GDSA * verification one and we do not finalize() before init(). */ ret = sig_verify_check_initialized(ctx); EG(ret, err); ECGDSA_VERIFY_CHECK_INITIALIZED(&(ctx->verify_data.ecgdsa), ret, err); /* Zero init points */ ret = local_memset(&uG, 0, sizeof(prj_pt)); EG(ret, err); ret = local_memset(&vY, 0, sizeof(prj_pt)); EG(ret, err); /* Make things more readable */ G = &(ctx->pub_key->params->ec_gen); Y = &(ctx->pub_key->y); q = &(ctx->pub_key->params->ec_gen_order); r = &(ctx->verify_data.ecgdsa.r); s = &(ctx->verify_data.ecgdsa.s); q_bit_len = ctx->pub_key->params->ec_gen_order_bitlen; hsize = ctx->h->digest_size; /* 2. Compute h = H(m) */ /* Since we call a callback, sanity check our mapping */ ret = hash_mapping_callbacks_sanity_check(ctx->h); EG(ret, err); ret = ctx->h->hfunc_finalize(&(ctx->verify_data.ecgdsa.h_ctx), e_buf); EG(ret, err); dbg_buf_print("H(m)", e_buf, hsize); /* * If |h| > bitlen(q), set h to bitlen(q) * leftmost bits of h. * */ rshift = 0; if ((hsize * 8) > q_bit_len) { rshift = (bitcnt_t)((hsize * 8) - q_bit_len); } ret = nn_init_from_buf(&e, e_buf, hsize); EG(ret, err); ret = local_memset(e_buf, 0, hsize); EG(ret, err); if (rshift) { ret = nn_rshift_fixedlen(&e, &e, rshift); EG(ret, err); } dbg_nn_print("H(m) truncated as nn", &e); /* 3. Compute e by converting h to an integer and reducing it mod q */ ret = nn_mod(&e, &e, q); EG(ret, err); /* 4. Compute u = (r^-1)e mod q */ ret = nn_modinv(&rinv, r, q); EG(ret, err); /* r^-1 */ ret = nn_mod_mul(&uv, &rinv, &e, q); EG(ret, err); ret = prj_pt_mul(&uG, &uv, G); EG(ret, err); /* 5. Compute v = (r^-1)s mod q */ ret = nn_mod_mul(&uv, &rinv, s, q); EG(ret, err); ret = prj_pt_mul(&vY, &uv, Y); EG(ret, err); /* 6. Compute W' = uG + vY */ ret = prj_pt_add(Wprime, &uG, &vY); EG(ret, err); /* 7. Compute r' = W'_x mod q */ ret = prj_pt_unique(Wprime, Wprime); EG(ret, err); dbg_nn_print("W'_x", &(Wprime->X.fp_val)); dbg_nn_print("W'_y", &(Wprime->Y.fp_val)); ret = nn_mod(&r_prime, &(Wprime->X.fp_val), q); EG(ret, err); /* 8. Accept the signature if and only if r equals r' */ ret = nn_cmp(r, &r_prime, &cmp); EG(ret, err); ret = (cmp != 0) ? -1 : 0; err: nn_uninit(&e); nn_uninit(&r_prime); nn_uninit(&rinv); nn_uninit(&uv); prj_pt_uninit(&uG); prj_pt_uninit(&vY); /* * We can now clear data part of the context. This will clear * magic and avoid further reuse of the whole context. */ if(ctx != NULL){ IGNORE_RET_VAL(local_memset(&(ctx->verify_data.ecgdsa), 0, sizeof(ecgdsa_verify_data))); } PTR_NULLIFY(Wprime); PTR_NULLIFY(r); PTR_NULLIFY(s); PTR_NULLIFY(G); PTR_NULLIFY(Y); PTR_NULLIFY(q); VAR_ZEROIFY(hsize); return ret; } #else /* WITH_SIG_ECGDSA */ /* * Dummy definition to avoid the empty translation unit ISO C warning */ typedef int dummy; #endif /* WITH_SIG_ECGDSA */