From cdfe0fdde6a966bdb0447de66aa04a85d99a0551 Mon Sep 17 00:00:00 2001
From: =?utf8?q?Bodo=20M=C3=B6ller?= <bodo@openssl.org>
Date: Thu, 13 Oct 2011 12:35:10 +0000
Subject: [PATCH] Fix OPENSSL_BN_ASM_MONT5 for corner cases; add a test.

Submitted by: Emilia Kasper
---
 crypto/bn/asm/x86_64-mont5.pl |  3 ++
 crypto/bn/bn_exp.c            | 22 ++++++++--
 crypto/bn/bntest.c            | 77 +++++++++++++++++++++++++++++++++++
 3 files changed, 98 insertions(+), 4 deletions(-)

diff --git a/crypto/bn/asm/x86_64-mont5.pl b/crypto/bn/asm/x86_64-mont5.pl
index fe335dfd44..d6e4c63df1 100755
--- a/crypto/bn/asm/x86_64-mont5.pl
+++ b/crypto/bn/asm/x86_64-mont5.pl
@@ -836,6 +836,8 @@ $code.=<<___;
 .type	bn_scatter5,\@abi-omnipotent
 .align	16
 bn_scatter5:
+	cmp	\$0, $num
+	jz	.Lscatter_epilogue
 	lea	($tbl,$idx,8),$tbl
 .Lscatter:
 	mov	($inp),%rax
@@ -844,6 +846,7 @@ bn_scatter5:
 	lea	32*8($tbl),$tbl
 	sub	\$1,$num
 	jnz	.Lscatter
+.Lscatter_epilogue:
 	ret
 .size	bn_scatter5,.-bn_scatter5
 ___
diff --git a/crypto/bn/bn_exp.c b/crypto/bn/bn_exp.c
index aae00491db..c69cd2c2f0 100644
--- a/crypto/bn/bn_exp.c
+++ b/crypto/bn/bn_exp.c
@@ -693,9 +693,6 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
 
 	if (!BN_copy(&computeTemp, am)) goto err;
 
-	if (bn_wexpand(am,top)==NULL ||	bn_wexpand(r,top)==NULL)
-		goto err;
-
 #if defined(OPENSSL_BN_ASM_MONT5)
     /* This optimization uses ideas from http://eprint.iacr.org/2011/239,
      * specifically optimization of cache-timing attack countermeasures
@@ -717,6 +714,24 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
 	bn_scatter5(am->d,am->top,powerbuf,1);
 
 	acc = computeTemp.d;
+	/* bn_mul_mont() and bn_mul_mont_gather5() assume fixed length inputs.
+	 * Pad the inputs with zeroes.
+	 */
+	if (bn_wexpand(am,top)==NULL ||	bn_wexpand(r,top)==NULL ||
+	    bn_wexpand(&computeTemp,top)==NULL)
+		goto err;
+	for (i = am->top; i < top; ++i)
+		{
+		am->d[i] = 0;
+		}
+	for (i = computeTemp.top; i < top; ++i)
+		{
+		computeTemp.d[i] = 0;
+		}
+	for (i = r->top; i < top; ++i)
+		{
+		r->d[i] = 0;
+		}
 #if 0
 	for (i=2; i<32; i++)
 		{
@@ -1102,4 +1117,3 @@ err:
 	bn_check_top(r);
 	return(ret);
 	}
-
diff --git a/crypto/bn/bntest.c b/crypto/bn/bntest.c
index 06f5954acc..8bc6d462e7 100644
--- a/crypto/bn/bntest.c
+++ b/crypto/bn/bntest.c
@@ -107,6 +107,7 @@ int test_mod(BIO *bp,BN_CTX *ctx);
 int test_mod_mul(BIO *bp,BN_CTX *ctx);
 int test_mod_exp(BIO *bp,BN_CTX *ctx);
 int test_mod_exp_mont_consttime(BIO *bp,BN_CTX *ctx);
+int test_mod_exp_mont5(BIO *bp, BN_CTX *ctx);
 int test_exp(BIO *bp,BN_CTX *ctx);
 int test_gf2m_add(BIO *bp);
 int test_gf2m_mod(BIO *bp);
@@ -249,6 +250,7 @@ int main(int argc, char *argv[])
 
 	message(out,"BN_mod_exp_mont_consttime");
 	if (!test_mod_exp_mont_consttime(out,ctx)) goto err;
+	if (!test_mod_exp_mont5(out,ctx)) goto err;
 	(void)BIO_flush(out);
 
 	message(out,"BN_exp");
@@ -1012,6 +1014,81 @@ int test_mod_exp_mont_consttime(BIO *bp, BN_CTX *ctx)
 	return(1);
 	}
 
+/* Test constant-time modular exponentiation with 1024-bit inputs,
+ * which on x86_64 cause a different code branch to be taken.
+ */
+int test_mod_exp_mont5(BIO *bp, BN_CTX *ctx)
+	{
+	BIGNUM *a,*p,*m,*d,*e;
+	int i;
+
+	BN_MONT_CTX *mont;
+
+	a=BN_new();
+	p=BN_new();
+	m=BN_new();
+	d=BN_new();
+	e=BN_new();
+
+	mont = BN_MONT_CTX_new();
+
+	BN_bntest_rand(m,1024,0,1); /* must be odd for montgomery */
+	/* Zero exponent */
+	BN_bntest_rand(a,1024,0,0);
+	BN_zero(p);
+	if(!BN_mod_exp_mont_consttime(d,a,p,m,ctx,NULL))
+		return 0;
+	if(!BN_is_one(d))
+		{
+		fprintf(stderr, "Modular exponentiation test failed!\n");
+		return 0;
+		}
+	/* Zero input */
+	BN_bntest_rand(p,1024,0,0);
+	BN_zero(a);
+	if(!BN_mod_exp_mont_consttime(d,a,p,m,ctx,NULL))
+		return 0;
+	if(!BN_is_zero(d))
+		{
+		fprintf(stderr, "Modular exponentiation test failed!\n");
+		return 0;
+		}
+	/* Craft an input whose Montgomery representation is 1,
+	 * i.e., shorter than the modulus m, in order to test
+	 * the const time precomputation scattering/gathering.
+	 */
+	BN_one(a);
+	BN_MONT_CTX_set(mont,m,ctx);
+	if(!BN_from_montgomery(e,a,mont,ctx))
+		return 0;
+	if(!BN_mod_exp_mont_consttime(d,e,p,m,ctx,NULL))
+		return 0;
+	if(!BN_mod_exp_simple(a,e,p,m,ctx))
+		return 0;
+	if(BN_cmp(a,d) != 0)
+		{
+		fprintf(stderr,"Modular exponentiation test failed!\n");
+		return 0;
+		}
+	/* Finally, some regular test vectors. */
+	BN_bntest_rand(e,1024,0,0);
+	if(!BN_mod_exp_mont_consttime(d,e,p,m,ctx,NULL))
+		return 0;
+	if(!BN_mod_exp_simple(a,e,p,m,ctx))
+		return 0;
+	if(BN_cmp(a,d) != 0)
+		{
+		fprintf(stderr,"Modular exponentiation test failed!\n");
+		return 0;
+		}
+	BN_free(a);
+	BN_free(p);
+	BN_free(m);
+	BN_free(d);
+	BN_free(e);
+	return(1);
+	}
+
 int test_exp(BIO *bp, BN_CTX *ctx)
 	{
 	BIGNUM *a,*b,*d,*e,*one;
-- 
2.40.0