Fix a small timing side channel in ecdsa_sign_setup(). Up to whitespace

this is OpennSSL commit 4a089bbdf11f9e231cc68f42bba934c954d81a49.

ok beck, jsing

Original commit message:

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

    Address a timing side channel whereby it is possible to determine some
    information about the length of the scalar used in ECDSA 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, 8 deletions

diff --git a/src/lib/libcrypto/ecdsa/ecs_ossl.c b/src/lib/libcrypto/ecdsa/ecs_ossl.c
index c7f4bcbe03..4ac140a020 100644
--- a/src/lib/libcrypto/ecdsa/ecs_ossl.c
+++ b/src/lib/libcrypto/ecdsa/ecs_ossl.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: ecs_ossl.c,v 1.9 2017/01/29 17:49:23 beck Exp $ */
+/* $OpenBSD: ecs_ossl.c,v 1.10 2018/04/28 14:17:56 tb Exp $ */
 /*
  * Written by Nils Larsch for the OpenSSL project
  */
@@ -92,7 +92,7 @@ ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp)
         BIGNUM   *k = NULL, *r = NULL, *order = NULL, *X = NULL;
         EC_POINT *tmp_point = NULL;
         const EC_GROUP *group;
-        int      ret = 0;
+        int      order_bits, ret = 0;
 
         if (eckey == NULL || (group = EC_KEY_get0_group(eckey)) == NULL) {
                 ECDSAerror(ERR_R_PASSED_NULL_PARAMETER);
@@ -124,6 +124,13 @@ ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp)
                 goto err;
         }
 
+        /* Preallocate space */
+        order_bits = BN_num_bits(order);
+        if (!BN_set_bit(k, order_bits) ||
+            !BN_set_bit(r, order_bits) ||
+            !BN_set_bit(X, order_bits))
+                goto err;
+
         do {
                 /* get random k */
                 do
@@ -133,14 +140,24 @@ ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp)
                         }
                 while (BN_is_zero(k));
 
-                /* We do not want timing information to leak the length of k,
+                /*
+                 * We do not want timing information to leak the length of k,
                  * so we compute G*k using an equivalent scalar of fixed
-                 * bit-length. */
-                if (!BN_add(k, k, order))
+                 * 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 order.  This guarantees the
+                 * code path used in the constant time implementations
+                 * elsewhere.
+                 *
+                 * TODO: revisit the BN_copy aiming for a memory access agnostic
+                 * conditional copy.
+                 */
+                if (!BN_add(r, k, order) ||
+                    !BN_add(X, r, order) ||
+                    !BN_copy(k, BN_num_bits(r) > order_bits ? r : X))
                         goto err;
-                if (BN_num_bits(k) <= BN_num_bits(order))
-                        if (!BN_add(k, k, order))
-                                goto err;
 
                 BN_set_flags(k, BN_FLG_CONSTTIME);