make sure DSA signing exponentiations really are constant-time
diff --git a/CHANGES b/CHANGES
index 9711d56..3b68628 100644
--- a/CHANGES
+++ b/CHANGES
@@ -803,6 +803,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 2e5ede7..3fd8a35 100644
--- a/crypto/dsa/dsa_ossl.c
+++ b/crypto/dsa/dsa_ossl.c
@@ -202,7 +202,7 @@
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 @@
}
BN_init(&k);
+ BN_init(&kq);
if (ctx_in == NULL)
{
@@ -221,7 +222,6 @@
ctx=ctx_in;
if ((r=BN_new()) == NULL) goto err;
- kinv=NULL;
/* Get random k */
do
@@ -241,7 +241,30 @@
}
/* 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 @@
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);
}
