DO NOT MERGE

Compute ECDSA modular inverses with Fermal's Little Theorem.

This is a partial cherry-pick of
18954938684e269ccd59152027d2244040e2b819.

Bug: 33752052
Change-Id: Iddba4b931f88d2a0d2f7b9b1904b294fff1d8501
(cherry picked from commit 1f170d0b00fbf42c023c3746dd36eb96115e2a6e)

3 files changed, 113 insertions, 17 deletions

diff --git a/src/crypto/ec/ec.c b/src/crypto/ec/ec.c
index f38eba6..1bc2e26 100644
--- a/src/crypto/ec/ec.c
+++ b/src/crypto/ec/ec.c
@@ -67,6 +67,7 @@
 
 #include <openssl/ec.h>
 
+#include <assert.h>
 #include <string.h>
 
 #include <openssl/bn.h>
@@ -75,6 +76,7 @@
 #include <openssl/obj.h>
 
 #include "internal.h"
+#include "../internal.h"
 
 
 static const struct curve_data P224 = {
@@ -233,6 +235,70 @@ const struct built_in_curve OPENSSL_built_in_curves[] = {
     {NID_undef, 0, 0},
 };
 
+/* built_in_curve_scalar_field_monts contains Montgomery contexts for
+ * performing inversions in the scalar fields of each of the built-in
+ * curves. It's protected by |built_in_curve_scalar_field_monts_once|. */
+static const BN_MONT_CTX **built_in_curve_scalar_field_monts;
+
+static CRYPTO_once_t built_in_curve_scalar_field_monts_once;
+
+static void built_in_curve_scalar_field_monts_init(void) {
+  unsigned num_built_in_curves;
+  for (num_built_in_curves = 0;; num_built_in_curves++) {
+    if (OPENSSL_built_in_curves[num_built_in_curves].nid == NID_undef) {
+      break;
+    }
+  }
+
+  assert(0 < num_built_in_curves);
+
+  built_in_curve_scalar_field_monts =
+      OPENSSL_malloc(sizeof(BN_MONT_CTX *) * num_built_in_curves);
+  if (built_in_curve_scalar_field_monts == NULL) {
+    return;
+  }
+
+  BIGNUM *order = BN_new();
+  BN_CTX *bn_ctx = BN_CTX_new();
+  BN_MONT_CTX *mont_ctx = NULL;
+
+  if (bn_ctx == NULL ||
+      order == NULL) {
+    goto err;
+  }
+
+  unsigned i;
+  for (i = 0; i < num_built_in_curves; i++) {
+    const struct curve_data *curve = OPENSSL_built_in_curves[i].data;
+    const unsigned param_len = curve->param_len;
+    const uint8_t *params = curve->data;
+
+    mont_ctx = BN_MONT_CTX_new();
+    if (mont_ctx == NULL) {
+      goto err;
+    }
+
+    if (!BN_bin2bn(params + 5 * param_len, param_len, order) ||
+        !BN_MONT_CTX_set(mont_ctx, order, bn_ctx)) {
+      goto err;
+    }
+
+    built_in_curve_scalar_field_monts[i] = mont_ctx;
+    mont_ctx = NULL;
+  }
+
+  goto out;
+
+err:
+  BN_MONT_CTX_free(mont_ctx);
+  OPENSSL_free(built_in_curve_scalar_field_monts);
+  built_in_curve_scalar_field_monts = NULL;
+
+out:
+  BN_free(order);
+  BN_CTX_free(bn_ctx);
+}
+
 EC_GROUP *ec_group_new(const EC_METHOD *meth) {
   EC_GROUP *ret;
 
@@ -325,25 +391,23 @@ int EC_GROUP_set_generator(EC_GROUP *group, const EC_POINT *generator,
   return 1;
 }
 
-static EC_GROUP *ec_group_new_from_data(const struct built_in_curve *curve) {
+static EC_GROUP *ec_group_new_from_data(unsigned built_in_index) {
+  const struct built_in_curve *curve = &OPENSSL_built_in_curves[built_in_index];
   EC_GROUP *group = NULL;
   EC_POINT *P = NULL;
-  BN_CTX *ctx = NULL;
   BIGNUM *p = NULL, *a = NULL, *b = NULL, *x = NULL, *y = NULL, *order = NULL;
-  int ok = 0;
-  unsigned param_len;
   const EC_METHOD *meth;
-  const struct curve_data *data;
-  const uint8_t *params;
 
-  if ((ctx = BN_CTX_new()) == NULL) {
+  int ok = 0;
+  BN_CTX *ctx = BN_CTX_new();
+  if (ctx == NULL) {
     OPENSSL_PUT_ERROR(EC, ec_group_new_from_data, ERR_R_MALLOC_FAILURE);
     goto err;
   }
 
-  data = curve->data;
-  param_len = data->param_len;
-  params = data->data;
+  const struct curve_data *data = curve->data;
+  const unsigned param_len = data->param_len;
+  const uint8_t *params = data->data;
 
   if (!(p = BN_bin2bn(params + 0 * param_len, param_len, NULL)) ||
       !(a = BN_bin2bn(params + 1 * param_len, param_len, NULL)) ||
@@ -387,6 +451,12 @@ static EC_GROUP *ec_group_new_from_data(const struct built_in_curve *curve) {
     goto err;
   }
 
+  CRYPTO_once(&built_in_curve_scalar_field_monts_once,
+              built_in_curve_scalar_field_monts_init);
+  if (built_in_curve_scalar_field_monts != NULL) {
+    group->mont_data = built_in_curve_scalar_field_monts[built_in_index];
+  }
+
   group->generator = P;
   P = NULL;
   if (!BN_copy(&group->order, order) ||
@@ -421,7 +491,7 @@ EC_GROUP *EC_GROUP_new_by_curve_name(int nid) {
   for (i = 0; OPENSSL_built_in_curves[i].nid != NID_undef; i++) {
     curve = &OPENSSL_built_in_curves[i];
     if (curve->nid == nid) {
-      ret = ec_group_new_from_data(curve);
+      ret = ec_group_new_from_data(i);
       break;
     }
   }
@@ -468,6 +538,7 @@ int ec_group_copy(EC_GROUP *dest, const EC_GROUP *src) {
 
   ec_pre_comp_free(dest->pre_comp);
   dest->pre_comp = ec_pre_comp_dup(src->pre_comp);
+  dest->mont_data = src->mont_data;
 
   if (src->generator != NULL) {
     if (dest->generator == NULL) {
@@ -480,11 +551,8 @@ int ec_group_copy(EC_GROUP *dest, const EC_GROUP *src) {
       return 0;
     }
   } else {
-    /* src->generator == NULL */
-    if (dest->generator != NULL) {
-      EC_POINT_clear_free(dest->generator);
-      dest->generator = NULL;
-    }
+    EC_POINT_clear_free(dest->generator);
+    dest->generator = NULL;
   }
 
   if (!BN_copy(&dest->order, &src->order) ||
@@ -497,6 +565,10 @@ int ec_group_copy(EC_GROUP *dest, const EC_GROUP *src) {
   return dest->meth->group_copy(dest, src);
 }
 
+const BN_MONT_CTX *ec_group_get_mont_data(const EC_GROUP *group) {
+  return group->mont_data;
+}
+
 EC_GROUP *EC_GROUP_dup(const EC_GROUP *a) {
   EC_GROUP *t = NULL;
   int ok = 0;
diff --git a/src/crypto/ec/internal.h b/src/crypto/ec/internal.h
index 71062c1..89d86fd 100644
--- a/src/crypto/ec/internal.h
+++ b/src/crypto/ec/internal.h
@@ -200,6 +200,7 @@ struct ec_group_st {
   int curve_name; /* optional NID for named curve */
 
   struct ec_pre_comp_st *pre_comp;
+  const BN_MONT_CTX *mont_data; /* data for ECDSA inverse */
 
   /* The following members are handled by the method functions,
    * even if they appear generic */
@@ -230,6 +231,11 @@ struct ec_point_st {
 EC_GROUP *ec_group_new(const EC_METHOD *meth);
 int ec_group_copy(EC_GROUP *dest, const EC_GROUP *src);
 
+/* ec_group_get_mont_data returns a Montgomery context for operations in the
+ * scalar field of |group|. It may return NULL in the case that |group| is not
+ * a built-in group. */
+const BN_MONT_CTX *ec_group_get_mont_data(const EC_GROUP *group);
+
 int ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
                 size_t num, const EC_POINT *points[], const BIGNUM *scalars[],
                 BN_CTX *);
@@ -321,6 +327,10 @@ void ec_GFp_nistp_recode_scalar_bits(uint8_t *sign, uint8_t *digit, uint8_t in);
 
 const EC_METHOD *EC_GFp_nistp256_method(void);
 
+/* Returns GFp methods using montgomery multiplication, with x86-64
+ * optimized P256. See http://eprint.iacr.org/2013/816. */
+const EC_METHOD *EC_GFp_nistz256_method(void);
+
 struct ec_key_st {
   int version;
 
diff --git a/src/crypto/ecdsa/ecdsa.c b/src/crypto/ecdsa/ecdsa.c
index b71799e..86e41bb 100644
--- a/src/crypto/ecdsa/ecdsa.c
+++ b/src/crypto/ecdsa/ecdsa.c
@@ -322,7 +322,21 @@ static int ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, BIGNUM **kinvp,
   } while (BN_is_zero(r));
 
   /* compute the inverse of k */
-  if (!BN_mod_inverse(k, k, order, ctx)) {
+  if (ec_group_get_mont_data(group) != NULL) {
+    /* We want inverse in constant time, therefore we use that the order must
+     * be prime and thus we can use Fermat's Little Theorem. */
+    if (!BN_set_word(X, 2) ||
+        !BN_sub(X, order, X)) {
+      OPENSSL_PUT_ERROR(ECDSA, ecdsa_sign_setup, ERR_R_BN_LIB);
+      goto err;
+    }
+    BN_set_flags(X, BN_FLG_CONSTTIME);
+    if (!BN_mod_exp_mont_consttime(k, k, X, order, ctx,
+                                   ec_group_get_mont_data(group))) {
+      OPENSSL_PUT_ERROR(ECDSA, ecdsa_sign_setup, ERR_R_BN_LIB);
+      goto err;
+    }
+  } else if (!BN_mod_inverse(k, k, order, ctx)) {
     OPENSSL_PUT_ERROR(ECDSA, ecdsa_sign_setup, ERR_R_BN_LIB);
     goto err;
   }