Address a timing side channel whereby it is possible to determine some

information about the length of a value used in DSA operations from
a large number of signatures.

This doesn't rate as a CVE because:

* For the non-constant time code, there are easier ways to extract
  more information.

* For the constant time code, it requires a significant number of signatures
  to leak a small amount of information.

Thanks to Neals Fournaise, Eliane Jaulmes and Jean-Rene Reinhard for
reporting this issue.

Original commit by Paul Dale. Backported to 1.0.2 by Matt Caswell

Reviewed-by: Andy Polyakov <appro@openssl.org>
Reviewed-by: Matt Caswell <matt@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/4642)

1 files changed, 27 insertions, 15 deletions

diff --git a/crypto/dsa/dsa_ossl.c b/crypto/dsa/dsa_ossl.c
index 58013a4a13..aa10dd12f6 100644
--- a/crypto/dsa/dsa_ossl.c
+++ b/crypto/dsa/dsa_ossl.c
@@ -224,7 +224,9 @@ static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp,
 {
     BN_CTX *ctx;
     BIGNUM k, kq, *K, *kinv = NULL, *r = NULL;
+    BIGNUM l, m;
     int ret = 0;
+    int q_bits;
 
     if (!dsa->p || !dsa->q || !dsa->g) {
         DSAerr(DSA_F_DSA_SIGN_SETUP, DSA_R_MISSING_PARAMETERS);
@@ -233,6 +235,8 @@ static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp,
 
     BN_init(&k);
     BN_init(&kq);
+    BN_init(&l);
+    BN_init(&m);
 
     if (ctx_in == NULL) {
         if ((ctx = BN_CTX_new()) == NULL)
@@ -243,6 +247,13 @@ static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp,
     if ((r = BN_new()) == NULL)
         goto err;
 
+    /* Preallocate space */
+    q_bits = BN_num_bits(dsa->q);
+    if (!BN_set_bit(&k, q_bits)
+        || !BN_set_bit(&l, q_bits)
+        || !BN_set_bit(&m, q_bits))
+        goto err;
+
     /* Get random k */
     do
         if (!BN_rand_range(&k, dsa->q))
@@ -263,24 +274,23 @@ static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp,
     /* Compute r = (g^k mod p) mod q */
 
     if ((dsa->flags & DSA_FLAG_NO_EXP_CONSTTIME) == 0) {
-        if (!BN_copy(&kq, &k))
-            goto err;
-
-        BN_set_flags(&kq, BN_FLG_CONSTTIME);
-
         /*
          * 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.)
+         * compute G^k using an equivalent scalar of fixed bit-length.
+         *
+         * We unconditionally perform both of these additions to prevent a
+         * small timing information leakage.  We then choose the sum that is
+         * one bit longer than the modulus.
+         *
+         * TODO: revisit the BN_copy aiming for a memory access agnostic
+         * conditional copy.
          */
-
-        if (!BN_add(&kq, &kq, dsa->q))
+        if (!BN_add(&l, &k, dsa->q)
+            || !BN_add(&m, &l, dsa->q)
+            || !BN_copy(&kq, BN_num_bits(&l) > q_bits ? &l : &m))
             goto err;
-        if (BN_num_bits(&kq) <= BN_num_bits(dsa->q)) {
-            if (!BN_add(&kq, &kq, dsa->q))
-                goto err;
-        }
+
+        BN_set_flags(&kq, BN_FLG_CONSTTIME);
 
         K = &kq;
     } else {
@@ -314,7 +324,9 @@ static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp,
         BN_CTX_free(ctx);
     BN_clear_free(&k);
     BN_clear_free(&kq);
-    return (ret);
+    BN_clear_free(&l);
+    BN_clear_free(&m);
+    return ret;
 }
 
 static int dsa_do_verify(const unsigned char *dgst, int dgst_len,