make sure DSA signing exponentiations really are constant-time

diff --git a/CHANGES b/CHANGES
index 83ffbba552e1894a2a7eb9e94dfdd68b4c8c7a4c..33f106733026a4958fbe0add47aa6d6db9332a0d 100644 (file)
--- a/CHANGES
+++ b/CHANGES
@@ -4,6 +4,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 e668b079e3a9e24f28d7f5a3f09d70c5c3c33a5c..12509a708336ea65066687ac8efdb71b2ed1cfca 100644 (file)
--- a/crypto/dsa/dsa_ossl.c
+++ b/crypto/dsa/dsa_ossl.c
@@ -172,7 +172,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)
@@ -182,6 +182,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)
                {
@@ -191,7 +192,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
@@ -211,7 +211,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;
 
@@ -234,6 +257,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);
        }