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/lib/libcrypto/bn/bn.h b/lib/libcrypto/bn/bn.h
index 5d5de7e43a0..0dde08a3688 100644
--- a/lib/libcrypto/bn/bn.h
+++ b/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/lib/libcrypto/bn/bn_gcd.c b/lib/libcrypto/bn/bn_gcd.c
index 30896e4763f..e2574c3304f 100644
--- a/lib/libcrypto/bn/bn_gcd.c
+++ b/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/lib/libcrypto/bn/bn_lcl.h b/lib/libcrypto/bn/bn_lcl.h
index 75c35499a83..c010410cd15 100644
--- a/lib/libcrypto/bn/bn_lcl.h
+++ b/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/lib/libcrypto/bn/bn_x931p.c b/lib/libcrypto/bn/bn_x931p.c
index 84c998d4e10..45b61c91280 100644
--- a/lib/libcrypto/bn/bn_x931p.c
+++ b/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/lib/libcrypto/rsa/rsa_chk.c b/lib/libcrypto/rsa/rsa_chk.c
index 91616d17cbe..dd9104f3043 100644
--- a/lib/libcrypto/rsa/rsa_chk.c
+++ b/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/lib/libcrypto/rsa/rsa_gen.c b/lib/libcrypto/rsa/rsa_gen.c
index 300b292b7be..e09dccb4a86 100644
--- a/lib/libcrypto/rsa/rsa_gen.c
+++ b/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;