Add blinding in BN_GF2m_mod_inv for binary field inversions

Reviewed-by: Richard Levitte <levitte@openssl.org>
Reviewed-by: Andy Polyakov <appro@openssl.org>
Reviewed-by: Rich Salz <rsalz@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/6070)

2 files changed, 46 insertions, 90 deletions

diff --git a/CHANGES b/CHANGES
index 742b673aa6..f0e23ca765 100644
--- a/CHANGES
+++ b/CHANGES
@@ -9,6 +9,10 @@
 
  Changes between 1.1.0h and 1.1.1 [xx XXX xxxx]
 
+  *) Apply blinding to binary field modular inversion and remove patent
+     pending (OPENSSL_SUN_GF2M_DIV) BN_GF2m_mod_div implementation.
+     [Billy Bob Brumley]
+
   *) Deprecate ec2_mult.c and unify scalar multiplication code paths for
      binary and prime elliptic curves.
      [Billy Bob Brumley]
diff --git a/crypto/bn/bn_gf2m.c b/crypto/bn/bn_gf2m.c
index 16868f79a0..287adf305a 100644
--- a/crypto/bn/bn_gf2m.c
+++ b/crypto/bn/bn_gf2m.c
@@ -547,7 +547,8 @@ int BN_GF2m_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
  * Hernandez, J.L., and Menezes, A.  "Software Implementation of Elliptic
  * Curve Cryptography Over Binary Fields".
  */
-int BN_GF2m_mod_inv(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
+static int BN_GF2m_mod_inv_vartime(BIGNUM *r, const BIGNUM *a,
+                                   const BIGNUM *p, BN_CTX *ctx)
 {
     BIGNUM *b, *c = NULL, *u = NULL, *v = NULL, *tmp;
     int ret = 0;
@@ -713,6 +714,46 @@ int BN_GF2m_mod_inv(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
     return ret;
 }
 
+/*-
+ * Wrapper for BN_GF2m_mod_inv_vartime that blinds the input before calling.
+ * This is not constant time.
+ * But it does eliminate first order deduction on the input.
+ */
+int BN_GF2m_mod_inv(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
+{
+    BIGNUM *b = NULL;
+    int ret = 0;
+
+    BN_CTX_start(ctx);
+    if ((b = BN_CTX_get(ctx)) == NULL)
+        goto err;
+
+    /* generate blinding value */
+    do {
+        if (!BN_priv_rand(b, BN_num_bits(p) - 1,
+                          BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY))
+            goto err;
+    } while (BN_is_zero(b));
+
+    /* r := a * b */
+    if (!BN_GF2m_mod_mul(r, a, b, p, ctx))
+        goto err;
+
+    /* r := 1/(a * b) */
+    if (!BN_GF2m_mod_inv_vartime(r, r, p, ctx))
+        goto err;
+
+    /* r := b/(a * b) = 1/a */
+    if (!BN_GF2m_mod_mul(r, r, b, p, ctx))
+        goto err;
+
+    ret = 1;
+
+ err:
+    BN_CTX_end(ctx);
+    return ret;
+}
+
 /*
  * Invert xx, reduce modulo p, and store the result in r. r could be xx.
  * This function calls down to the BN_GF2m_mod_inv implementation; this
@@ -740,7 +781,6 @@ int BN_GF2m_mod_inv_arr(BIGNUM *r, const BIGNUM *xx, const int p[],
     return ret;
 }
 
-# ifndef OPENSSL_SUN_GF2M_DIV
 /*
  * Divide y by x, reduce modulo p, and store the result in r. r could be x
  * or y, x could equal y.
@@ -771,94 +811,6 @@ int BN_GF2m_mod_div(BIGNUM *r, const BIGNUM *y, const BIGNUM *x,
     BN_CTX_end(ctx);
     return ret;
 }
-# else
-/*
- * Divide y by x, reduce modulo p, and store the result in r. r could be x
- * or y, x could equal y. Uses algorithm Modular_Division_GF(2^m) from
- * Chang-Shantz, S.  "From Euclid's GCD to Montgomery Multiplication to the
- * Great Divide".
- */
-int BN_GF2m_mod_div(BIGNUM *r, const BIGNUM *y, const BIGNUM *x,
-                    const BIGNUM *p, BN_CTX *ctx)
-{
-    BIGNUM *a, *b, *u, *v;
-    int ret = 0;
-
-    bn_check_top(y);
-    bn_check_top(x);
-    bn_check_top(p);
-
-    BN_CTX_start(ctx);
-
-    a = BN_CTX_get(ctx);
-    b = BN_CTX_get(ctx);
-    u = BN_CTX_get(ctx);
-    v = BN_CTX_get(ctx);
-    if (v == NULL)
-        goto err;
-
-    /* reduce x and y mod p */
-    if (!BN_GF2m_mod(u, y, p))
-        goto err;
-    if (!BN_GF2m_mod(a, x, p))
-        goto err;
-    if (!BN_copy(b, p))
-        goto err;
-
-    while (!BN_is_odd(a)) {
-        if (!BN_rshift1(a, a))
-            goto err;
-        if (BN_is_odd(u))
-            if (!BN_GF2m_add(u, u, p))
-                goto err;
-        if (!BN_rshift1(u, u))
-            goto err;
-    }
-
-    do {
-        if (BN_GF2m_cmp(b, a) > 0) {
-            if (!BN_GF2m_add(b, b, a))
-                goto err;
-            if (!BN_GF2m_add(v, v, u))
-                goto err;
-            do {
-                if (!BN_rshift1(b, b))
-                    goto err;
-                if (BN_is_odd(v))
-                    if (!BN_GF2m_add(v, v, p))
-                        goto err;
-                if (!BN_rshift1(v, v))
-                    goto err;
-            } while (!BN_is_odd(b));
-        } else if (BN_abs_is_word(a, 1))
-            break;
-        else {
-            if (!BN_GF2m_add(a, a, b))
-                goto err;
-            if (!BN_GF2m_add(u, u, v))
-                goto err;
-            do {
-                if (!BN_rshift1(a, a))
-                    goto err;
-                if (BN_is_odd(u))
-                    if (!BN_GF2m_add(u, u, p))
-                        goto err;
-                if (!BN_rshift1(u, u))
-                    goto err;
-            } while (!BN_is_odd(a));
-        }
-    } while (1);
-
-    if (!BN_copy(r, u))
-        goto err;
-    bn_check_top(r);
-    ret = 1;
-
- err:
-    BN_CTX_end(ctx);
-    return ret;
-}
-# endif
 
 /*
  * Divide yy by xx, reduce modulo p, and store the result in r. r could be xx