From 31def5ae590b4faa3901455e5f58baf55caf34a9 Mon Sep 17 00:00:00 2001
From: Andy Polyakov <appro@openssl.org>
Date: Fri, 27 May 2005 06:42:11 +0000
Subject: [PATCH] Constant-time DSA signing [sync with mainstream].

Submitted by: bodo
---
 fips/dsa/fips_dsa_ossl.c | 30 +++++++++++++++++++++++++++---
 fips/fipshashes.c        |  2 +-
 2 files changed, 28 insertions(+), 4 deletions(-)

diff --git a/fips/dsa/fips_dsa_ossl.c b/fips/dsa/fips_dsa_ossl.c
index 07eb1da936..8529c52a4c 100644
--- a/fips/dsa/fips_dsa_ossl.c
+++ b/fips/dsa/fips_dsa_ossl.c
@@ -187,7 +187,7 @@ err:
 static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp)
 	{
 	BN_CTX *ctx;
-	BIGNUM k,*kinv=NULL,*r=NULL;
+	BIGNUM k,kq,*K,*kinv=NULL,*r=NULL;
 	int ret=0;
 
 	if (!dsa->p || !dsa->q || !dsa->g)
@@ -197,6 +197,7 @@ static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp)
 		}
 
 	BN_init(&k);
+	BN_init(&kq);
 
 	if (ctx_in == NULL)
 		{
@@ -206,7 +207,6 @@ static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp)
 		ctx=ctx_in;
 
 	if ((r=BN_new()) == NULL) goto err;
-	kinv=NULL;
 
 	/* Get random k */
 	do
@@ -222,7 +222,30 @@ static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp)
 		}
 
 	/* Compute r = (g^k mod p) mod q */
-	if (!dsa->meth->bn_mod_exp(dsa, r,dsa->g,&k,dsa->p,ctx,
+	if ((dsa->flags & DSA_FLAG_NO_EXP_CONSTTIME) == 0)
+		{
+		if (!BN_copy(&kq, &k)) goto err;
+
+		/* We do not want timing information to leak the length of k,
+		 * so we compute g^k using an equivalent exponent of fixed length.
+		 *
+		 * (This is a kludge that we need because the BN_mod_exp_mont()
+		 * does not let us specify the desired timing behaviour.) */
+
+		if (!BN_add(&kq, &kq, dsa->q)) goto err;
+		if (BN_num_bits(&kq) <= BN_num_bits(dsa->q))
+			{
+			if (!BN_add(&kq, &kq, dsa->q)) goto err;
+			}
+
+		K = &kq;
+		}
+	else
+		{
+		K = &k;
+		}
+
+	if (!dsa->meth->bn_mod_exp(dsa, r,dsa->g,K,dsa->p,ctx,
 		(BN_MONT_CTX *)dsa->method_mont_p)) goto err;
 	if (!BN_mod(r,r,dsa->q,ctx)) goto err;
 
@@ -245,6 +268,7 @@ err:
 	if (ctx_in == NULL) BN_CTX_free(ctx);
 	if (kinv != NULL) BN_clear_free(kinv);
 	BN_clear_free(&k);
+	BN_clear_free(&kq);
 	return(ret);
 	}
 
diff --git a/fips/fipshashes.c b/fips/fipshashes.c
index e97575e22b..8a7c1745e1 100644
--- a/fips/fipshashes.c
+++ b/fips/fipshashes.c
@@ -15,7 +15,7 @@ const char * const FIPS_source_hashes[] = {
 "HMAC-SHA1(dh/fips_dh_check.c)= 63347e2007e224381d4a7b6d871633889de72cf3",
 "HMAC-SHA1(dh/fips_dh_gen.c)= 93fe69b758ca9d70d70cda1c57fff4eb5c668e85",
 "HMAC-SHA1(dh/fips_dh_key.c)= 0b810d411090abd6b676a7ca730c35362fbd04a4",
-"HMAC-SHA1(dsa/fips_dsa_ossl.c)= 8bb943c0fd1adf04f6a845f4d1727c5472697e93",
+"HMAC-SHA1(dsa/fips_dsa_ossl.c)= ee0fbfd18d6b67a40f9a3716e6b890a487b0bbd4",
 "HMAC-SHA1(dsa/fips_dsa_gen.c)= 78c879484fd849312ca4828b957df3842b70efc0",
 "HMAC-SHA1(dsa/fips_dsa_selftest.c)= 7c2ba8d82feda2aadc8b769a3b6c4c25a6356e01",
 "HMAC-SHA1(rand/fips_rand.c)= 7e3964447a81cfe4e75df981827d14a5fe0c2923",
-- 
2.25.1