Fix a small timing side channel in dsa_sign_setup(). Simple adaptation

of OpenSSL commit c0caa945f6ef30363e0d01d75155f20248403df4 to our
version of this function.

ok beck, jsing

Original commit message:

commit c0caa945f6ef30363e0d01d75155f20248403df4
Author: Pauli <paul.dale@oracle.com>
Date:   Wed Nov 1 06:58:13 2017 +1000

    Address a timing side channel whereby it is possible to determine some
    information about the length of the scalar used in DSA operations from
    a large number (2^32) 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.

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

1 files changed, 25 insertions, 12 deletions

diff --git a/src/lib/libcrypto/dsa/dsa_ossl.c b/src/lib/libcrypto/dsa/dsa_ossl.c
index f1013fe547..301cdd5095 100644
--- a/src/lib/libcrypto/dsa/dsa_ossl.c
+++ b/src/lib/libcrypto/dsa/dsa_ossl.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: dsa_ossl.c,v 1.30 2017/01/29 17:49:22 beck Exp $ */
+/* $OpenBSD: dsa_ossl.c,v 1.31 2018/04/28 14:22:21 tb Exp $ */
 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  * All rights reserved.
  *
@@ -184,8 +184,8 @@ static int
 dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp)
 {
         BN_CTX *ctx;
-        BIGNUM k, *kinv = NULL, *r = NULL;
-        int ret = 0;
+        BIGNUM k, l, m, *kinv = NULL, *r = NULL;
+        int q_bits, ret = 0;
 
         if (!dsa->p || !dsa->q || !dsa->g) {
                 DSAerror(DSA_R_MISSING_PARAMETERS);
@@ -193,6 +193,8 @@ dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp)
         }
 
         BN_init(&k);
+        BN_init(&l);
+        BN_init(&m);
 
         if (ctx_in == NULL) {
                 if ((ctx = BN_CTX_new()) == NULL)
@@ -203,6 +205,13 @@ dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp)
         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))
@@ -221,19 +230,21 @@ dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp)
 
         /*
          * We do not want timing information to leak the length of k,
-         * so we compute g^k using an equivalent exponent of fixed
-         * length.
+         * so we compute G^k using an equivalent exponent 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.
          *
-         * (This is a kludge that we need because the BN_mod_exp_mont()
-         * does not let us specify the desired timing behaviour.)
+         * TODO: revisit the BN_copy aiming for a memory access agnostic
+         * conditional copy.
          */
 
-        if (!BN_add(&k, &k, dsa->q))
+        if (!BN_add(&l, &k, dsa->q) ||
+            !BN_add(&m, &l, dsa->q) ||
+            !BN_copy(&k, BN_num_bits(&l) > q_bits ? &l : &m))
                 goto err;
-        if (BN_num_bits(&k) <= BN_num_bits(dsa->q)) {
-                if (!BN_add(&k, &k, dsa->q))
-                        goto err;
-        }
 
         if (dsa->meth->bn_mod_exp != NULL) {
                 if (!dsa->meth->bn_mod_exp(dsa, r, dsa->g, &k, dsa->p, ctx,
@@ -265,6 +276,8 @@ err:
         if (ctx_in == NULL)
                 BN_CTX_free(ctx);
         BN_clear_free(&k);
+        BN_clear_free(&l);
+        BN_clear_free(&m);
         return ret;
 }