Construct a BN_gcd_nonct, based on BN_mod_inverse_no_branch, as suggested

by Alejandro Cabrera <aldaya@gmail.com> to avoid the possibility of a
sidechannel timing attack during RSA private key generation.

Modify BN_gcd to become not visible under LIBRESSL_INTERNAL and force
the use of the _ct or _nonct versions of the function only within
the library.

ok jsing@

6 files changed, 170 insertions, 10 deletions

diff --git a/src/lib/libcrypto/bn/bn.h b/src/lib/libcrypto/bn/bn.h
index 5d5de7e43a..0dde08a368 100644
--- a/src/lib/libcrypto/bn/bn.h
+++ b/src/lib/libcrypto/bn/bn.h
@@ -1,4 +1,4 @@
-/* $OpenBSD: bn.h,v 1.35 2017/01/21 11:00:46 beck Exp $ */
+/* $OpenBSD: bn.h,v 1.36 2017/01/25 06:15:44 beck Exp $ */
 /* Copyright (C) 1995-1997 Eric Young (eay@cryptsoft.com)
  * All rights reserved.
  *
@@ -452,7 +452,9 @@ char *	BN_bn2dec(const BIGNUM *a);
 int     BN_hex2bn(BIGNUM **a, const char *str);
 int     BN_dec2bn(BIGNUM **a, const char *str);
 int     BN_asc2bn(BIGNUM **a, const char *str);
+#ifndef LIBRESSL_INTERNAL
 int     BN_gcd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx);
+#endif
 int     BN_kronecker(const BIGNUM *a,const BIGNUM *b,BN_CTX *ctx); /* returns -2 for error */
 #ifndef LIBRESSL_INTERNAL
 BIGNUM *BN_mod_inverse(BIGNUM *ret,
diff --git a/src/lib/libcrypto/bn/bn_gcd.c b/src/lib/libcrypto/bn/bn_gcd.c
index 30896e4763..e2574c3304 100644
--- a/src/lib/libcrypto/bn/bn_gcd.c
+++ b/src/lib/libcrypto/bn/bn_gcd.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: bn_gcd.c,v 1.13 2017/01/21 23:02:53 beck Exp $ */
+/* $OpenBSD: bn_gcd.c,v 1.14 2017/01/25 06:15:44 beck Exp $ */
 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  * All rights reserved.
  *
@@ -114,6 +114,8 @@
 #include "bn_lcl.h"
 
 static BIGNUM *euclid(BIGNUM *a, BIGNUM *b);
+static BIGNUM *BN_gcd_no_branch(BIGNUM *in, const BIGNUM *a, const BIGNUM *n,
+    BN_CTX *ctx);
 
 int
 BN_gcd(BIGNUM *r, const BIGNUM *in_a, const BIGNUM *in_b, BN_CTX *ctx)
@@ -156,6 +158,21 @@ err:
         return (ret);
 }
 
+int
+BN_gcd_ct(BIGNUM *r, const BIGNUM *in_a, const BIGNUM *in_b, BN_CTX *ctx)
+{
+        if (BN_gcd_no_branch(r, in_a, in_b, ctx) == NULL)
+                return 0;
+        return 1;
+}
+
+int
+BN_gcd_nonct(BIGNUM *r, const BIGNUM *in_a, const BIGNUM *in_b, BN_CTX *ctx)
+{
+        return BN_gcd(r, in_a, in_b, ctx);
+}
+
+
 static BIGNUM *
 euclid(BIGNUM *a, BIGNUM *b)
 {
@@ -704,3 +721,142 @@ err:
         bn_check_top(ret);
         return (ret);
 }
+
+/*
+ * BN_gcd_no_branch is a special version of BN_mod_inverse_no_branch.
+ * that returns the GCD.
+ */
+static BIGNUM *
+BN_gcd_no_branch(BIGNUM *in, const BIGNUM *a, const BIGNUM *n,
+    BN_CTX *ctx)
+{
+        BIGNUM *A, *B, *X, *Y, *M, *D, *T, *R = NULL;
+        BIGNUM local_A, local_B;
+        BIGNUM *pA, *pB;
+        BIGNUM *ret = NULL;
+        int sign;
+
+        if (in == NULL)
+                goto err;
+        R = in;
+
+        bn_check_top(a);
+        bn_check_top(n);
+
+        BN_CTX_start(ctx);
+        if ((A = BN_CTX_get(ctx)) == NULL)
+                goto err;
+        if ((B = BN_CTX_get(ctx)) == NULL)
+                goto err;
+        if ((X = BN_CTX_get(ctx)) == NULL)
+                goto err;
+        if ((D = BN_CTX_get(ctx)) == NULL)
+                goto err;
+        if ((M = BN_CTX_get(ctx)) == NULL)
+                goto err;
+        if ((Y = BN_CTX_get(ctx)) == NULL)
+                goto err;
+        if ((T = BN_CTX_get(ctx)) == NULL)
+                goto err;
+
+        BN_one(X);
+        BN_zero(Y);
+        if (BN_copy(B, a) == NULL)
+                goto err;
+        if (BN_copy(A, n) == NULL)
+                goto err;
+        A->neg = 0;
+
+        if (B->neg || (BN_ucmp(B, A) >= 0)) {
+                /* Turn BN_FLG_CONSTTIME flag on, so that when BN_div is invoked,
+                 * BN_div_no_branch will be called eventually.
+                 */
+                pB = &local_B;
+                BN_with_flags(pB, B, BN_FLG_CONSTTIME);
+                if (!BN_nnmod(B, pB, A, ctx))
+                        goto err;
+        }
+        sign = -1;
+        /* From  B = a mod |n|,  A = |n|  it follows that
+         *
+         *      0 <= B < A,
+         *     -sign*X*a  ==  B   (mod |n|),
+         *      sign*Y*a  ==  A   (mod |n|).
+         */
+
+        while (!BN_is_zero(B)) {
+                BIGNUM *tmp;
+
+                /*
+                 *      0 < B < A,
+                 * (*) -sign*X*a  ==  B   (mod |n|),
+                 *      sign*Y*a  ==  A   (mod |n|)
+                 */
+
+                /* Turn BN_FLG_CONSTTIME flag on, so that when BN_div is invoked,
+                 * BN_div_no_branch will be called eventually.
+                 */
+                pA = &local_A;
+                BN_with_flags(pA, A, BN_FLG_CONSTTIME);
+
+                /* (D, M) := (A/B, A%B) ... */
+                if (!BN_div_ct(D, M, pA, B, ctx))
+                        goto err;
+
+                /* Now
+                 *      A = D*B + M;
+                 * thus we have
+                 * (**)  sign*Y*a  ==  D*B + M   (mod |n|).
+                 */
+                tmp = A; /* keep the BIGNUM object, the value does not matter */
+
+                /* (A, B) := (B, A mod B) ... */
+                A = B;
+                B = M;
+                /* ... so we have  0 <= B < A  again */
+
+                /* Since the former  M  is now  B  and the former  B  is now  A,
+                 * (**) translates into
+                 *       sign*Y*a  ==  D*A + B    (mod |n|),
+                 * i.e.
+                 *       sign*Y*a - D*A  ==  B    (mod |n|).
+                 * Similarly, (*) translates into
+                 *      -sign*X*a  ==  A          (mod |n|).
+                 *
+                 * Thus,
+                 *   sign*Y*a + D*sign*X*a  ==  B  (mod |n|),
+                 * i.e.
+                 *        sign*(Y + D*X)*a  ==  B  (mod |n|).
+                 *
+                 * So if we set  (X, Y, sign) := (Y + D*X, X, -sign),  we arrive back at
+                 *      -sign*X*a  ==  B   (mod |n|),
+                 *       sign*Y*a  ==  A   (mod |n|).
+                 * Note that  X  and  Y  stay non-negative all the time.
+                 */
+
+                if (!BN_mul(tmp, D, X, ctx))
+                        goto err;
+                if (!BN_add(tmp, tmp, Y))
+                        goto err;
+
+                M = Y; /* keep the BIGNUM object, the value does not matter */
+                Y = X;
+                X = tmp;
+                sign = -sign;
+        }
+
+        /*
+         * The while loop (Euclid's algorithm) ends when
+         *      A == gcd(a,n);
+         */
+
+        if (!BN_copy(R, A))
+                goto err;
+        ret = R;
+err:
+        if ((ret == NULL) && (in == NULL))
+                BN_free(R);
+        BN_CTX_end(ctx);
+        bn_check_top(ret);
+        return (ret);
+}
diff --git a/src/lib/libcrypto/bn/bn_lcl.h b/src/lib/libcrypto/bn/bn_lcl.h
index 75c35499a8..c010410cd1 100644
--- a/src/lib/libcrypto/bn/bn_lcl.h
+++ b/src/lib/libcrypto/bn/bn_lcl.h
@@ -1,4 +1,4 @@
-/* $OpenBSD: bn_lcl.h,v 1.26 2017/01/21 11:00:46 beck Exp $ */
+/* $OpenBSD: bn_lcl.h,v 1.27 2017/01/25 06:15:44 beck Exp $ */
 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  * All rights reserved.
  *
@@ -603,5 +603,7 @@ BIGNUM *BN_mod_inverse_ct(BIGNUM *ret, const BIGNUM *a, const BIGNUM *n,
     BN_CTX *ctx);
 BIGNUM *BN_mod_inverse_nonct(BIGNUM *ret, const BIGNUM *a, const BIGNUM *n,
     BN_CTX *ctx);
+int     BN_gcd_ct(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx);
+int     BN_gcd_nonct(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx);
 __END_HIDDEN_DECLS
 #endif
diff --git a/src/lib/libcrypto/bn/bn_x931p.c b/src/lib/libcrypto/bn/bn_x931p.c
index 84c998d4e1..45b61c9128 100644
--- a/src/lib/libcrypto/bn/bn_x931p.c
+++ b/src/lib/libcrypto/bn/bn_x931p.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: bn_x931p.c,v 1.9 2017/01/21 11:00:46 beck Exp $ */
+/* $OpenBSD: bn_x931p.c,v 1.10 2017/01/25 06:15:44 beck Exp $ */
 /* Written by Dr Stephen N Henson (steve@openssl.org) for the OpenSSL
  * project 2005.
  */
@@ -171,7 +171,7 @@ BN_X931_derive_prime_ex(BIGNUM *p, BIGNUM *p1, BIGNUM *p2, const BIGNUM *Xp,
                         goto err;
                 if (!BN_sub_word(pm1, 1))
                         goto err;
-                if (!BN_gcd(t, pm1, e, ctx))
+                if (!BN_gcd_ct(t, pm1, e, ctx))
                         goto err;
                 if (BN_is_one(t)
                 /* X9.31 specifies 8 MR and 1 Lucas test or any prime test
diff --git a/src/lib/libcrypto/rsa/rsa_chk.c b/src/lib/libcrypto/rsa/rsa_chk.c
index 91616d17cb..dd9104f304 100644
--- a/src/lib/libcrypto/rsa/rsa_chk.c
+++ b/src/lib/libcrypto/rsa/rsa_chk.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: rsa_chk.c,v 1.11 2017/01/21 11:00:47 beck Exp $ */
+/* $OpenBSD: rsa_chk.c,v 1.12 2017/01/25 06:15:44 beck Exp $ */
 /* ====================================================================
  * Copyright (c) 1999 The OpenSSL Project.  All rights reserved.
  *
@@ -129,7 +129,7 @@ RSA_check_key(const RSA *key)
                 ret = -1;
                 goto err;
         }
-        r = BN_gcd(m, i, j, ctx);
+        r = BN_gcd_ct(m, i, j, ctx);
         if (!r) {
                 ret = -1;
                 goto err;
diff --git a/src/lib/libcrypto/rsa/rsa_gen.c b/src/lib/libcrypto/rsa/rsa_gen.c
index 300b292b7b..e09dccb4a8 100644
--- a/src/lib/libcrypto/rsa/rsa_gen.c
+++ b/src/lib/libcrypto/rsa/rsa_gen.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: rsa_gen.c,v 1.20 2017/01/21 11:00:47 beck Exp $ */
+/* $OpenBSD: rsa_gen.c,v 1.21 2017/01/25 06:15:44 beck Exp $ */
 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  * All rights reserved.
  *
@@ -138,7 +138,7 @@ rsa_builtin_keygen(RSA *rsa, int bits, BIGNUM *e_value, BN_GENCB *cb)
                         goto err;
                 if (!BN_sub(r2, rsa->p, BN_value_one()))
                         goto err;
-                if (!BN_gcd(r1, r2, rsa->e, ctx))
+                if (!BN_gcd_ct(r1, r2, rsa->e, ctx))
                         goto err;
                 if (BN_is_one(r1))
                         break;
@@ -168,7 +168,7 @@ rsa_builtin_keygen(RSA *rsa, int bits, BIGNUM *e_value, BN_GENCB *cb)
                 }
                 if (!BN_sub(r2, rsa->q, BN_value_one()))
                         goto err;
-                if (!BN_gcd(r1, r2, rsa->e, ctx))
+                if (!BN_gcd_ct(r1, r2, rsa->e, ctx))
                         goto err;
                 if (BN_is_one(r1))
                         break;