Change to mitigate branch prediction attacks

Submitted by: Matthew D Wood
Reviewed by: Bodo Moeller

5 files changed, 129 insertions, 23 deletions

diff --git a/crypto/rsa/rsa.h b/crypto/rsa/rsa.h
index 260fa43efe..898aafffae 100644
--- a/crypto/rsa/rsa.h
+++ b/crypto/rsa/rsa.h
@@ -196,13 +196,27 @@ struct rsa_st
                                                 * default (ignoring RSA_FLAG_BLINDING),
                                                 * but other engines might not need it
                                                 */
-#define RSA_FLAG_NO_EXP_CONSTTIME	0x0100 /* new with 0.9.7h; the built-in RSA
+#define RSA_FLAG_NO_CONSTTIME		0x0100 /* new with 0.9.8f; the built-in RSA
+						* implementation now uses constant time
+						* operations by default in private key operations,
+						* e.g., constant time modular exponentiation, 
+                                                * modular inverse without leaking branches, 
+                                                * division without leaking branches. This 
+                                                * flag disables these constant time 
+                                                * operations and results in faster RSA 
+                                                * private key operations.
+                                                */ 
+#ifndef OPENSSL_NO_DEPRECATED
+#define RSA_FLAG_NO_EXP_CONSTTIME RSA_FLAG_NO_CONSTTIME /* deprecated name for the flag*/
+                                                /* new with 0.9.7h; the built-in RSA
                                                 * implementation now uses constant time
                                                 * modular exponentiation for secret exponents
                                                 * by default. This flag causes the
                                                 * faster variable sliding window method to
                                                 * be used for all exponents.
                                                 */
+#endif
+
 
 #define EVP_PKEY_CTX_set_rsa_padding(ctx, pad) \
 	EVP_PKEY_CTX_ctrl(ctx, EVP_PKEY_RSA, -1, EVP_PKEY_CTRL_RSA_PADDING, \
diff --git a/crypto/rsa/rsa_eay.c b/crypto/rsa/rsa_eay.c
index 385439cdc9..15ebf5dfa3 100644
--- a/crypto/rsa/rsa_eay.c
+++ b/crypto/rsa/rsa_eay.c
@@ -429,11 +429,11 @@ static int RSA_eay_private_encrypt(int flen, const unsigned char *from,
 		BIGNUM local_d;
 		BIGNUM *d = NULL;
 		
-		if (!(rsa->flags & RSA_FLAG_NO_EXP_CONSTTIME))
+		if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME))
 			{
 			BN_init(&local_d);
 			d = &local_d;
-			BN_with_flags(d, rsa->d, BN_FLG_EXP_CONSTTIME);
+			BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
 			}
 		else
 			d = rsa->d;
@@ -551,10 +551,10 @@ static int RSA_eay_private_decrypt(int flen, const unsigned char *from,
 		BIGNUM local_d;
 		BIGNUM *d = NULL;
 		
-		if (!(rsa->flags & RSA_FLAG_NO_EXP_CONSTTIME))
+		if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME))
 			{
 			d = &local_d;
-			BN_with_flags(d, rsa->d, BN_FLG_EXP_CONSTTIME);
+			BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
 			}
 		else
 			d = rsa->d;
@@ -715,8 +715,9 @@ err:
 static int RSA_eay_mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx)
 	{
 	BIGNUM *r1,*m1,*vrfy;
-	BIGNUM local_dmp1, local_dmq1;
-	BIGNUM *dmp1, *dmq1;
+	BIGNUM local_dmp1,local_dmq1,local_c,local_r1;
+	BIGNUM *dmp1,*dmq1,*c,*pr1;
+	int bn_flags;
 	int ret=0;
 
 	BN_CTX_start(ctx);
@@ -724,26 +725,72 @@ static int RSA_eay_mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx)
 	m1 = BN_CTX_get(ctx);
 	vrfy = BN_CTX_get(ctx);
 
+	/* Make sure mod_inverse in montgomerey intialization use correct 
+	 * BN_FLG_CONSTTIME flag.
+	 */
+	bn_flags = rsa->p->flags;
+	if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME))
+		{
+		rsa->p->flags |= BN_FLG_CONSTTIME;
+		}
 	MONT_HELPER(rsa, ctx, p, rsa->flags & RSA_FLAG_CACHE_PRIVATE, goto err);
+	/* We restore bn_flags back */
+	rsa->p->flags = bn_flags;
+
+        /* Make sure mod_inverse in montgomerey intialization use correct
+         * BN_FLG_CONSTTIME flag.
+         */
+	bn_flags = rsa->q->flags;
+	if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME))
+		{
+		rsa->q->flags |= BN_FLG_CONSTTIME;
+		}
 	MONT_HELPER(rsa, ctx, q, rsa->flags & RSA_FLAG_CACHE_PRIVATE, goto err);
+	/* We restore bn_flags back */
+	rsa->q->flags = bn_flags;	
+
 	MONT_HELPER(rsa, ctx, n, rsa->flags & RSA_FLAG_CACHE_PUBLIC, goto err);
 
-	if (!BN_mod(r1,I,rsa->q,ctx)) goto err;
-	if (!(rsa->flags & RSA_FLAG_NO_EXP_CONSTTIME))
+	/* compute I mod q */
+	if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME))
+		{
+		c = &local_c;
+		BN_with_flags(c, I, BN_FLG_CONSTTIME);
+		if (!BN_mod(r1,c,rsa->q,ctx)) goto err;
+		}
+	else
+		{
+		if (!BN_mod(r1,I,rsa->q,ctx)) goto err;
+		}
+
+	/* compute r1^dmq1 mod q */
+	if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME))
 		{
 		dmq1 = &local_dmq1;
-		BN_with_flags(dmq1, rsa->dmq1, BN_FLG_EXP_CONSTTIME);
+		BN_with_flags(dmq1, rsa->dmq1, BN_FLG_CONSTTIME);
 		}
 	else
 		dmq1 = rsa->dmq1;
 	if (!rsa->meth->bn_mod_exp(m1,r1,dmq1,rsa->q,ctx,
 		rsa->_method_mod_q)) goto err;
 
-	if (!BN_mod(r1,I,rsa->p,ctx)) goto err;
-	if (!(rsa->flags & RSA_FLAG_NO_EXP_CONSTTIME))
+	/* compute I mod p */
+	if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME))
+		{
+		c = &local_c;
+		BN_with_flags(c, I, BN_FLG_CONSTTIME);
+		if (!BN_mod(r1,c,rsa->p,ctx)) goto err;
+		}
+	else
+		{
+		if (!BN_mod(r1,I,rsa->p,ctx)) goto err;
+		}
+
+	/* compute r1^dmp1 mod p */
+	if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME))
 		{
 		dmp1 = &local_dmp1;
-		BN_with_flags(dmp1, rsa->dmp1, BN_FLG_EXP_CONSTTIME);
+		BN_with_flags(dmp1, rsa->dmp1, BN_FLG_CONSTTIME);
 		}
 	else
 		dmp1 = rsa->dmp1;
@@ -757,7 +804,17 @@ static int RSA_eay_mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx)
 		if (!BN_add(r0,r0,rsa->p)) goto err;
 
 	if (!BN_mul(r1,r0,rsa->iqmp,ctx)) goto err;
-	if (!BN_mod(r0,r1,rsa->p,ctx)) goto err;
+
+	/* Turn BN_FLG_CONSTTIME flag on before division operation */
+	if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME))
+		{
+		pr1 = &local_r1;
+		BN_with_flags(pr1, r1, BN_FLG_CONSTTIME);
+		}
+	else
+		pr1 = r1;
+	if (!BN_mod(r0,pr1,rsa->p,ctx)) goto err;
+
 	/* If p < q it is occasionally possible for the correction of
          * adding 'p' if r0 is negative above to leave the result still
 	 * negative. This can break the private key operations: the following
@@ -790,10 +847,10 @@ static int RSA_eay_mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx)
 			BIGNUM local_d;
 			BIGNUM *d = NULL;
 		
-			if (!(rsa->flags & RSA_FLAG_NO_EXP_CONSTTIME))
+			if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME))
 				{
 				d = &local_d;
-				BN_with_flags(d, rsa->d, BN_FLG_EXP_CONSTTIME);
+				BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
 				}
 			else
 				d = rsa->d;
diff --git a/crypto/rsa/rsa_gen.c b/crypto/rsa/rsa_gen.c
index 742f8b18e5..767f7ab682 100644
--- a/crypto/rsa/rsa_gen.c
+++ b/crypto/rsa/rsa_gen.c
@@ -85,6 +85,8 @@ int RSA_generate_key_ex(RSA *rsa, int bits, BIGNUM *e_value, BN_GENCB *cb)
 static int rsa_builtin_keygen(RSA *rsa, int bits, BIGNUM *e_value, BN_GENCB *cb)
 	{
 	BIGNUM *r0=NULL,*r1=NULL,*r2=NULL,*r3=NULL,*tmp;
+	BIGNUM local_r0,local_d,local_p;
+	BIGNUM *pr0,*d,*p;
 	int bitsp,bitsq,ok= -1,n=0;
 	BN_CTX *ctx=NULL;
 
@@ -165,16 +167,39 @@ static int rsa_builtin_keygen(RSA *rsa, int bits, BIGNUM *e_value, BN_GENCB *cb)
 	if (!BN_sub(r1,rsa->p,BN_value_one())) goto err;	/* p-1 */
 	if (!BN_sub(r2,rsa->q,BN_value_one())) goto err;	/* q-1 */
 	if (!BN_mul(r0,r1,r2,ctx)) goto err;	/* (p-1)(q-1) */
-	if (!BN_mod_inverse(rsa->d,rsa->e,r0,ctx)) goto err;	/* d */
+	if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME))
+		{
+		  pr0 = &local_r0;
+		  BN_with_flags(pr0, r0, BN_FLG_CONSTTIME);
+		}
+	else
+	  pr0 = r0;
+	if (!BN_mod_inverse(rsa->d,rsa->e,pr0,ctx)) goto err;	/* d */
+
+	/* set up d for correct BN_FLG_CONSTTIME flag */
+	if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME))
+		{
+		d = &local_d;
+		BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
+		}
+	else
+		d = rsa->d;
 
 	/* calculate d mod (p-1) */
-	if (!BN_mod(rsa->dmp1,rsa->d,r1,ctx)) goto err;
+	if (!BN_mod(rsa->dmp1,d,r1,ctx)) goto err;
 
 	/* calculate d mod (q-1) */
-	if (!BN_mod(rsa->dmq1,rsa->d,r2,ctx)) goto err;
+	if (!BN_mod(rsa->dmq1,d,r2,ctx)) goto err;
 
 	/* calculate inverse of q mod p */
-	if (!BN_mod_inverse(rsa->iqmp,rsa->q,rsa->p,ctx)) goto err;
+	if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME))
+		{
+		p = &local_p;
+		BN_with_flags(p, rsa->p, BN_FLG_CONSTTIME);
+		}
+	else
+		p = rsa->p;
+	if (!BN_mod_inverse(rsa->iqmp,rsa->q,p,ctx)) goto err;
 
 	ok=1;
 err:
diff --git a/crypto/rsa/rsa_lib.c b/crypto/rsa/rsa_lib.c
index c4b5b4731d..dd09609743 100644
--- a/crypto/rsa/rsa_lib.c
+++ b/crypto/rsa/rsa_lib.c
@@ -361,7 +361,8 @@ err:
 
 BN_BLINDING *RSA_setup_blinding(RSA *rsa, BN_CTX *in_ctx)
 {
-	BIGNUM *e;
+	BIGNUM local_n;
+	BIGNUM *e,*n;
 	BN_CTX *ctx;
 	BN_BLINDING *ret = NULL;
 
@@ -400,7 +401,16 @@ BN_BLINDING *RSA_setup_blinding(RSA *rsa, BN_CTX *in_ctx)
 		RAND_add(rsa->d->d, rsa->d->dmax * sizeof rsa->d->d[0], 0.0);
 		}
 
-	ret = BN_BLINDING_create_param(NULL, e, rsa->n, ctx,
+	if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME))
+		{
+		/* Set BN_FLG_CONSTTIME flag */
+		n = &local_n;
+		BN_with_flags(n, rsa->n, BN_FLG_CONSTTIME);
+		}
+	else
+		n = rsa->n;
+
+	ret = BN_BLINDING_create_param(NULL, e, n, ctx,
 			rsa->meth->bn_mod_exp, rsa->_method_mod_n);
 	if (ret == NULL)
 		{
diff --git a/crypto/rsa/rsa_test.c b/crypto/rsa/rsa_test.c
index 0f8059ccfd..51135ea3e0 100644
--- a/crypto/rsa/rsa_test.c
+++ b/crypto/rsa/rsa_test.c
@@ -242,7 +242,7 @@ int main(int argc, char *argv[])
 	clen = key3(key, ctext_ex);
 	break;
 	}
-	if (v/3 > 1) key->flags |= RSA_FLAG_NO_EXP_CONSTTIME;
+	if (v/3 >= 1) key->flags |= RSA_FLAG_NO_CONSTTIME;
 
 	num = RSA_public_encrypt(plen, ptext_ex, ctext, key,
 				 RSA_PKCS1_PADDING);