[Cryptech-Commits] [sw/libhal] 03/07: Add hal_ecdsa_verify(). Move hashing out of ECDSA routines. Clean up a few bits that didn't pass self-review.
git at cryptech.is
git at cryptech.is
Tue Aug 25 05:03:24 UTC 2015
This is an automated email from the git hooks/post-receive script.
sra at hactrn.net pushed a commit to branch ecdsa
in repository sw/libhal.
commit 9e4c5edc6ef46b4c182379eab46abb45e5d2022f
Author: Rob Austein <sra at hactrn.net>
Date: Sat Aug 22 17:47:22 2015 -0400
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
@@ -218,35 +218,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_ */
/*
More information about the Commits
mailing list