Add hal_ecdsa_verify(). Move hashing out of ECDSA routines. Clean up

a few bits that didn't pass self-review.

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_ */
 
 /*