From e4106a4e242c75287484834ebac48cbba1045e3f Mon Sep 17 00:00:00 2001
From: =?utf8?q?Bodo=20M=C3=B6ller?= <bodo@openssl.org>
Date: Thu, 26 May 2005 04:40:57 +0000
Subject: [PATCH] make sure DSA signing exponentiations really are
 constant-time

---
 CHANGES               |  7 +++++++
 crypto/dsa/dsa_ossl.c | 30 +++++++++++++++++++++++++++---
 2 files changed, 34 insertions(+), 3 deletions(-)

diff --git a/CHANGES b/CHANGES
index d02d20e161..5be91d613c 100644
--- a/CHANGES
+++ b/CHANGES
@@ -799,6 +799,13 @@
 
  Changes between 0.9.7g and 0.9.7h  [XX xxx XXXX]
 
+  *) For DSA signing, unless DSA_FLAG_NO_EXP_CONSTTIME is set, perform
+     the exponentiation using a fixed-length exponent.  (Otherwise,
+     the information leaked through timing could expose the secret key
+     after many signatures; cf. Bleichenbacher's attack on DSA with
+     biased k.)
+     [Bodo Moeller]
+
   *) Make a new fixed-window mod_exp implementation the default for
      RSA, DSA, and DH private-key operations so that the sequence of
      squares and multiplies and the memory access pattern are
diff --git a/crypto/dsa/dsa_ossl.c b/crypto/dsa/dsa_ossl.c
index 2e5ede7826..3fd8a35613 100644
--- a/crypto/dsa/dsa_ossl.c
+++ b/crypto/dsa/dsa_ossl.c
@@ -202,7 +202,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)
@@ -212,6 +212,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)
 		{
@@ -221,7 +222,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
@@ -241,7 +241,30 @@ static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp)
 		}
 
 	/* Compute r = (g^k mod p) mod q */
-	DSA_BN_MOD_EXP(goto err, 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;
+		}
+	DSA_BN_MOD_EXP(goto err, dsa, r, dsa->g, K, dsa->p, ctx,
 			dsa->method_mont_p);
 	if (!BN_mod(r,r,dsa->q,ctx)) goto err;
 
@@ -264,6 +287,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);
 	}
 
-- 
2.25.1