From 9e4c5edc6ef46b4c182379eab46abb45e5d2022f Mon Sep 17 00:00:00 2001 From: Rob Austein Date: Sat, 22 Aug 2015 17:47:22 -0400 Subject: Add hal_ecdsa_verify(). Move hashing out of ECDSA routines. Clean up a few bits that didn't pass self-review. --- asn1.c | 11 +++ ecdsa.c | 259 ++++++++++++++++++++++++++++++++++++++++++++++++---------------- hal.h | 18 ++--- 3 files changed, 214 insertions(+), 74 deletions(-) diff --git a/asn1.c b/asn1.c index f4b3610..cfbd319 100644 --- a/asn1.c +++ b/asn1.c @@ -144,6 +144,11 @@ hal_error_t hal_asn1_encode_integer(fp_int *bn, return HAL_OK; } +/* + * Parse tag and length of an ASN.1 object. Tag must match value + * specified by the caller. On success, sets hlen and vlen to lengths + * of header and value, respectively. + */ hal_error_t hal_asn1_decode_header(const uint8_t tag, const uint8_t * const der, size_t der_max, @@ -176,6 +181,12 @@ hal_error_t hal_asn1_decode_header(const uint8_t tag, return HAL_OK; } +/* + * Decode an ASN.1 INTEGER into a libtfm bignum. Since we only + * support (or need to support, or expect to see) unsigned integers, + * we return failure if the sign bit is set in the ASN.1 INTEGER. + */ + hal_error_t hal_asn1_decode_integer(fp_int *bn, const uint8_t * const der, size_t *der_len, const size_t der_max) { diff --git a/ecdsa.c b/ecdsa.c index 8e715f4..38a5b31 100644 --- a/ecdsa.c +++ b/ecdsa.c @@ -217,35 +217,6 @@ static const ecdsa_curve_t * const get_curve(const hal_ecdsa_curve_t curve) } } -/* - * Test whether two points are equal: x and z coordinates identical, y - * coordinates either identical or negated. - */ - -static inline int point_equal(const ec_point_t * const P, - const ec_point_t * const Q, - const ecdsa_curve_t * const curve) -{ - assert(P != NULL && Q != NULL && curve != NULL); - - if (fp_cmp(unconst_fp_int(P->x), unconst_fp_int(Q->x)) != FP_EQ || - fp_cmp(unconst_fp_int(P->z), unconst_fp_int(Q->z)) != FP_EQ) - return 0; - - if (fp_cmp(unconst_fp_int(P->y), unconst_fp_int(Q->y)) == FP_EQ) - return 1; - - fp_int Qy_neg[1]; - - fp_sub(unconst_fp_int(curve->q), unconst_fp_int(Q->y), Qy_neg); - - const int result = fp_cmp(unconst_fp_int(P->y), Qy_neg) == FP_EQ; - - fp_zero(Qy_neg); - - return result; -} - /* * Finite field operations (hence "ff_"). These are basically just * the usual bignum operations, constrained by the field modulus. @@ -314,6 +285,47 @@ static inline void ff_sqr(const ecdsa_curve_t * const curve, fp_montgomery_reduce(b, unconst_fp_int(curve->q), curve->rho); } +/* + * Test whether a point is the point at infinity. + * + * In Jacobian projective coordinate, any point of the form + * + * (j ** 2, j **3, 0) for j in [1..q-1] + * + * is on the line at infinity, but for practical purposes simply + * checking the z coordinate is probably sufficient. + */ + +static inline int point_is_infinite(const ec_point_t * const P) +{ + assert(P != NULL); + return fp_iszero(P->z); +} + +/* + * Set a point to be the point at infinity. For Jacobian projective + * coordinates, it's customary to use (1 : 1 : 0) as the + * representitive value. + */ + +static inline void point_set_infinite(ec_point_t *P) +{ + assert(P != NULL); + fp_set(P->x, 1); + fp_set(P->y, 1); + fp_set(P->z, 0); +} + +/* + * Copy a point. + */ + +static inline void point_copy(const ec_point_t * const P, ec_point_t *R) +{ + if (P != NULL && R != NULL && P != R) + *R = *P; +} + /** * Double an EC point. * @param P The point to double @@ -330,6 +342,8 @@ static inline void point_double(const ec_point_t * const P, { assert(P != NULL && R != NULL && curve != NULL); + assert(!point_is_infinite(P)); + fp_int alpha[1], beta[1], gamma[1], delta[1], t1[1], t2[1]; fp_init(alpha); fp_init(beta); fp_init(gamma); fp_init(delta); fp_init(t1); fp_init(t2); @@ -376,6 +390,9 @@ static inline void point_double(const ec_point_t * const P, * * Algorithm is add-2007-bl from * http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html + * + * The special cases for P == Q and P == -Q are unfortunate, but are + * probably unavoidable for this type of curve. */ static inline void point_add(const ec_point_t * const P, @@ -385,8 +402,30 @@ static inline void point_add(const ec_point_t * const P, { assert(P != NULL && Q != NULL && R != NULL && curve != NULL); - if (point_equal(P, Q, curve)) - return point_double(P, R, curve); + if (fp_cmp(unconst_fp_int(P->x), unconst_fp_int(Q->x)) == FP_EQ && + fp_cmp(unconst_fp_int(P->z), unconst_fp_int(Q->z)) == FP_EQ) { + + /* + * If P == Q, we have to use the doubling algorithm instead. + */ + + if (fp_cmp(unconst_fp_int(P->y), unconst_fp_int(Q->y)) == FP_EQ) + return point_double(P, R, curve); + + fp_int Qy_neg[1]; + fp_sub(unconst_fp_int(curve->q), unconst_fp_int(Q->y), Qy_neg); + const int zero_sum = fp_cmp(unconst_fp_int(P->y), Qy_neg) == FP_EQ; + fp_zero(Qy_neg); + + /* + * If P == -Q, P + Q is the point at infinity. Which can't be + * expressed in affine coordinates, but that's not this function's + * problem. + */ + + if (zero_sum) + return point_set_infinite(R); + } fp_int Z1Z1[1], Z2Z2[1], U1[1], U2[1], S1[1], S2[1], H[1], I[1], J[1], r[1], V[1], t[1]; @@ -441,9 +480,14 @@ static inline void point_add(const ec_point_t * const P, } /** - * Map a projective jacbobian point back to affine space + * Map a point in projective Jacbobian coordinates back to affine space * @param P [in/out] The point to map * @param curve The curve parameters structure + * + * It's not possible to represent the point at infinity in affine + * coordinates, and the calling function will have to handle this + * specially in any case, so we declare this to be the calling + * function's problem. */ static inline hal_error_t point_to_affine(ec_point_t *P, @@ -451,6 +495,9 @@ static inline hal_error_t point_to_affine(ec_point_t *P, { assert(P != NULL && curve != NULL); + if (point_is_infinite(P)) + return HAL_ERROR_IMPOSSIBLE; + hal_error_t err = HAL_ERROR_IMPOSSIBLE; fp_int t1[1]; fp_init(t1); @@ -585,20 +632,25 @@ static hal_error_t point_pick_random(const ecdsa_curve_t * const curve, * * We're picking a point out of the subgroup generated by the base * point on the elliptic curve, so the modulus for this calculation - * is order of the base point. + * is the order of the base point. * * Zero is an excluded value, but the chance of a non-broken CSPRNG * returning zero is so low that it would almost certainly indicate * an undiagnosed bug in the CSPRNG. */ + uint8_t k_buf[fp_unsigned_bin_size(unconst_fp_int(curve->n)) + 8]; do { + if ((err = hal_get_random(k_buf, sizeof(k_buf))) != HAL_OK) return err; + fp_read_unsigned_bin(k, k_buf, sizeof(k_buf)); + if (fp_iszero(k) || fp_mod(k, unconst_fp_int(curve->n), k) != FP_OKAY) return HAL_ERROR_IMPOSSIBLE; + } while (fp_iszero(k)); memset(k_buf, 0, sizeof(k_buf)); @@ -970,13 +1022,15 @@ hal_error_t hal_ecdsa_key_from_der(hal_ecdsa_key_t **key_, return err; } +/* + * Sign a caller-supplied hash. + */ + hal_error_t hal_ecdsa_sign(const hal_ecdsa_key_t * const key, - const hal_hash_descriptor_t * const hash_descriptor, - const uint8_t * const input, const size_t input_len, - uint8_t *output, size_t *output_len, const size_t output_max) + const uint8_t * const hash, const size_t hash_len, + uint8_t *signature, size_t *signature_len, const size_t signature_max) { - if (key == NULL || hash_descriptor == NULL || input == NULL || - output == NULL || output_len == NULL || key->type != HAL_ECDSA_PRIVATE) + if (key == NULL || hash == NULL || signature == NULL || signature_len == NULL || key->type != HAL_ECDSA_PRIVATE) return HAL_ERROR_BAD_ARGUMENTS; const ecdsa_curve_t * const curve = get_curve(key->curve); @@ -996,25 +1050,7 @@ hal_error_t hal_ecdsa_sign(const hal_ecdsa_key_t * const key, hal_error_t err; -#warning Should we be hashing here, or should API have caller do it? What does PKCS 11 do for ECDSA? - - /* - * Hash the input and load result into e. - */ - - { - uint8_t statebuf[hash_descriptor->hash_state_length]; - uint8_t hashbuf[hash_descriptor->digest_length]; - hal_hash_state_t state = { NULL }; - - if ((err = hal_hash_initialize(hash_descriptor, &state, - statebuf, sizeof(statebuf))) != HAL_OK || - (err = hal_hash_update(state, input, input_len)) != HAL_OK || - (err = hal_hash_finalize(state, hashbuf, sizeof(hashbuf))) != HAL_OK) - return err; - - fp_read_unsigned_bin(e, hashbuf, sizeof(hashbuf)); - } + fp_read_unsigned_bin(e, unconst_uint8_t(hash), sizeof(hash_len)); do { @@ -1059,16 +1095,17 @@ hal_error_t hal_ecdsa_sign(const hal_ecdsa_key_t * const key, if ((err = hal_asn1_encode_integer(r, NULL, &r_len, 0)) != HAL_OK || (err = hal_asn1_encode_integer(s, NULL, &s_len, 0)) != HAL_OK || - (err = hal_asn1_encode_header(ASN1_SEQUENCE, r_len + s_len, output, output_len, output_max)) != HAL_OK) + (err = hal_asn1_encode_header(ASN1_SEQUENCE, r_len + s_len, + signature, signature_len, signature_max)) != HAL_OK) goto fail; - uint8_t * const r_out = output + *output_len; + uint8_t * const r_out = signature + *signature_len; uint8_t * const s_out = r_out + r_len; - output_len += r_len + s_len; - assert(*output_len <= output_max); + signature_len += r_len + s_len; + assert(*signature_len <= signature_max); - if ((err = hal_asn1_encode_integer(r, r_out, NULL, output_max - (r_out - output))) != HAL_OK || - (err = hal_asn1_encode_integer(s, s_out, NULL, output_max - (s_out - output))) != HAL_OK) + if ((err = hal_asn1_encode_integer(r, r_out, NULL, signature_max - (r_out - signature))) != HAL_OK || + (err = hal_asn1_encode_integer(s, s_out, NULL, signature_max - (s_out - signature))) != HAL_OK) goto fail; err = HAL_OK; @@ -1080,9 +1117,101 @@ hal_error_t hal_ecdsa_sign(const hal_ecdsa_key_t * const key, } hal_error_t hal_ecdsa_verify(const hal_ecdsa_key_t * const key, - const hal_hash_descriptor_t * const hash_descriptor, - const uint8_t * const input, const size_t input_len) + const uint8_t * const hash, const size_t hash_len, + const uint8_t * const signature, const size_t signature_len) { + assert(key != NULL && hash != NULL && signature != NULL); + + const ecdsa_curve_t * const curve = get_curve(key->curve); + + if (curve == NULL) + return HAL_ERROR_IMPOSSIBLE; + + fp_int * const n = unconst_fp_int(curve->n); + + size_t len1, len2; + hal_error_t err; + fp_int r[1], s[1], e[1], w[1], u1[1], u2[1], v[1]; + ec_point_t u1G[1], u2Q[1], R[1]; + + fp_init(w); fp_init(u1); fp_init(u2); fp_init(v); + memset(u1G, 0, sizeof(u1G)); + memset(u2Q, 0, sizeof(u2Q)); + memset(R, 0, sizeof(R)); + + /* + * First, we have to parse the ASN.1 SEQUENCE { INTEGER r, INTEGER s }. + */ + + if ((err = hal_asn1_decode_header(ASN1_SEQUENCE, signature, signature_len, &len1, &len2)) != HAL_OK) + return err; + + const uint8_t * der = signature + len1; + const uint8_t * const der_end = der + len2; + + if ((err = hal_asn1_decode_integer(r, der, &len1, der_end - der)) != HAL_OK) + return err; + der += len1; + + if ((err = hal_asn1_decode_integer(s, der, &len1, der_end - der)) != HAL_OK) + return err; + der += len1; + + if (der != der_end) + return HAL_ERROR_ASN1_PARSE_FAILED; + + /* + * Check that r and s are in the allowed range, read the hash, then + * compute: + * + * w = 1 / s + * u1 = e * w + * u2 = r * w + * R = u1 * G + u2 * Q. + */ + + if (fp_cmp_d(r, 1) == FP_LT || fp_cmp(r, n) != FP_LT || + fp_cmp_d(s, 1) == FP_LT || fp_cmp(s, n) != FP_LT) + return HAL_ERROR_INVALID_SIGNATURE; + + fp_read_unsigned_bin(e, unconst_uint8_t(hash), sizeof(hash_len)); + + if (fp_invmod(s, n, w) != FP_OKAY || + fp_mulmod(e, w, n, u1) != FP_OKAY || + fp_mulmod(r, w, n, u2) != FP_OKAY) + return HAL_ERROR_IMPOSSIBLE; + + fp_copy(unconst_fp_int(curve->Gx), u1G->x); + fp_copy(unconst_fp_int(curve->Gy), u1G->y); + fp_set(u1G->z, 1); + + if ((err = point_scalar_multiply(u1, u1G, u1G, curve, 0)) != HAL_OK || + (err = point_scalar_multiply(u2, key->Q, u2Q, curve, 0)) != HAL_OK) + return err; + + if (point_is_infinite(u1G)) + point_copy(u2Q, R); + else if (point_is_infinite(u2Q)) + point_copy(u1G, R); + else + point_add(u1G, u2Q, R, curve); + + /* + * Signature is OK if + * R is not the point at infinity, and + * Rx is congruent to r mod n. + */ + + if (point_is_infinite(R)) + return HAL_ERROR_INVALID_SIGNATURE; + + if ((err = point_to_affine(R, curve)) != HAL_OK) + return err; + + if (fp_mod(R->x, n, v) != FP_OKAY) + return HAL_ERROR_IMPOSSIBLE; + + return fp_cmp(v, r) == FP_EQ ? HAL_OK : HAL_ERROR_INVALID_SIGNATURE; } /* diff --git a/hal.h b/hal.h index 9e7bd67..4417af8 100644 --- a/hal.h +++ b/hal.h @@ -447,6 +447,7 @@ DEFINE_HAL_ERROR(HAL_ERROR_RESULT_TOO_LONG, "Result too long for buffer") \ DEFINE_HAL_ERROR(HAL_ERROR_ASN1_PARSE_FAILED, "ASN.1 parse failed") \ DEFINE_HAL_ERROR(HAL_ERROR_KEY_NOT_ON_CURVE, "EC key is not on its purported curve") \ + DEFINE_HAL_ERROR(HAL_ERROR_INVALID_SIGNATURE, "Invalid signature") \ END_OF_HAL_ERROR_LIST /* Marker to forestall silly line continuation errors */ @@ -711,15 +712,6 @@ extern hal_error_t hal_ecdsa_key_get_public(const hal_ecdsa_key_t * const key, extern void hal_ecdsa_key_clear(hal_ecdsa_key_t *key); -extern hal_error_t hal_ecdsa_sign(const hal_ecdsa_key_t * const key, - const hal_hash_descriptor_t * const hash_descriptor, - const uint8_t * const input, const size_t input_len, - uint8_t *output, size_t *output_len, const size_t output_max); - -extern hal_error_t hal_ecdsa_verify(const hal_ecdsa_key_t * const key, - const hal_hash_descriptor_t * const hash_descriptor, - const uint8_t * const input, const size_t input_len); - extern hal_error_t hal_ecdsa_key_gen(hal_ecdsa_key_t **key, void *keybuf, const size_t keybuf_len, const hal_ecdsa_curve_t curve); @@ -733,6 +725,14 @@ extern hal_error_t hal_ecdsa_key_from_der(hal_ecdsa_key_t **key, void *keybuf, const size_t keybuf_len, const uint8_t * const der, const size_t der_len); +extern hal_error_t hal_ecdsa_sign(const hal_ecdsa_key_t * const key, + const uint8_t * const hash, const size_t hash_len, + uint8_t *signature, size_t *signature_len, const size_t signature_max); + +extern hal_error_t hal_ecdsa_verify(const hal_ecdsa_key_t * const key, + const uint8_t * const hash, const size_t hash_len, + const uint8_t * const signature, const size_t signature_len); + #endif /* _HAL_H_ */ /* -- cgit v1.2.3