Use a blinding value when generating DSA and ECDSA signatures, in order to

reduce the possibility of a side-channel attack leaking the private key.

OpenBSD 6.3 errata 022

2 files changed, 104 insertions, 23 deletions

diff --git a/src/lib/libcrypto/dsa/dsa_ossl.c b/src/lib/libcrypto/dsa/dsa_ossl.c
index 4e75512df8..f29821059f 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.2.1 2018/06/13 15:08:08 jsing Exp $ */
+/* $OpenBSD: dsa_ossl.c,v 1.30.2.2 2018/11/17 18:46:43 tb Exp $ */
 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  * All rights reserved.
  *
@@ -94,16 +94,17 @@ DSA_OpenSSL(void)
 static DSA_SIG *
 dsa_do_sign(const unsigned char *dgst, int dlen, DSA *dsa)
 {
-        BIGNUM *kinv = NULL, *r = NULL, *s = NULL;
-        BIGNUM m;
-        BIGNUM xr;
+        BIGNUM b, bm, bxr, binv, m, *kinv = NULL, *r = NULL, *s = NULL;
         BN_CTX *ctx = NULL;
         int reason = ERR_R_BN_LIB;
         DSA_SIG *ret = NULL;
         int noredo = 0;
 
+        BN_init(&b);
+        BN_init(&binv);
+        BN_init(&bm);
+        BN_init(&bxr);
         BN_init(&m);
-        BN_init(&xr);
 
         if (!dsa->p || !dsa->q || !dsa->g) {
                 reason = DSA_R_MISSING_PARAMETERS;
@@ -139,10 +140,36 @@ redo:
         if (BN_bin2bn(dgst,dlen,&m) == NULL)
                 goto err;
 
-        /* Compute  s = inv(k) (m + xr) mod q */
-        if (!BN_mod_mul(&xr, dsa->priv_key, r, dsa->q, ctx))    /* s = xr */
+        /*
+         * Compute:
+         *
+         *  s = inv(k)(m + xr) mod q
+         *
+         * In order to reduce the possibility of a side-channel attack, the
+         * following is calculated using a blinding value:
+         *
+         *  s = inv(k)inv(b)(bm + bxr) mod q
+         *
+         * Where b is a random value in the range [1, q-1].
+         */
+        if (!BN_sub(&bm, dsa->q, BN_value_one()))
+                goto err;
+        if (!BN_rand_range(&b, &bm))
+                goto err;
+        if (!BN_add(&b, &b, BN_value_one()))
+                goto err;
+        if (BN_mod_inverse_ct(&binv, &b, dsa->q, ctx) == NULL)
+                goto err;
+
+        if (!BN_mod_mul(&bxr, &b, dsa->priv_key, dsa->q, ctx))  /* bx */
+                goto err;
+        if (!BN_mod_mul(&bxr, &bxr, r, dsa->q, ctx))            /* bxr */
+                goto err;
+        if (!BN_mod_mul(&bm, &b, &m, dsa->q, ctx))              /* bm */
+                goto err;
+        if (!BN_mod_add(s, &bxr, &bm, dsa->q, ctx))             /* s = bm + bxr */
                 goto err;
-        if (!BN_mod_add(s, &xr, &m, dsa->q, ctx))               /* s = m + xr */
+        if (!BN_mod_mul(s, s, &binv, dsa->q, ctx))              /* s = m + xr */
                 goto err;
         if (!BN_mod_mul(s, s, kinv, dsa->q, ctx))
                 goto err;
@@ -171,8 +198,11 @@ err:
                 BN_free(s);
         }
         BN_CTX_free(ctx);
+        BN_clear_free(&b);
+        BN_clear_free(&bm);
+        BN_clear_free(&bxr);
+        BN_clear_free(&binv);
         BN_clear_free(&m);
-        BN_clear_free(&xr);
         BN_clear_free(kinv);
         return ret;
 }
diff --git a/src/lib/libcrypto/ecdsa/ecs_ossl.c b/src/lib/libcrypto/ecdsa/ecs_ossl.c
index 09f3bf8416..75ecb19557 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.2.1 2018/06/13 15:08:08 jsing Exp $ */
+/* $OpenBSD: ecs_ossl.c,v 1.9.2.2 2018/11/17 18:46:43 tb Exp $ */
 /*
  * Written by Nils Larsch for the OpenSSL project
  */
@@ -204,14 +204,14 @@ static ECDSA_SIG *
 ecdsa_do_sign(const unsigned char *dgst, int dgst_len,
     const BIGNUM *in_kinv, const BIGNUM *in_r, EC_KEY *eckey)
 {
-        int     ok = 0, i;
-        BIGNUM *kinv = NULL, *s, *m = NULL, *tmp = NULL, *order = NULL;
-        const BIGNUM *ckinv;
-        BN_CTX     *ctx = NULL;
-        const EC_GROUP   *group;
+        BIGNUM *b = NULL, *binv = NULL, *bm = NULL, *bxr = NULL;
+        BIGNUM *kinv = NULL, *m = NULL, *order = NULL, *range = NULL, *s;
+        const BIGNUM *ckinv, *priv_key;
+        BN_CTX *ctx = NULL;
+        const EC_GROUP *group;
         ECDSA_SIG  *ret;
         ECDSA_DATA *ecdsa;
-        const BIGNUM *priv_key;
+        int     ok = 0, i;
 
         ecdsa = ecdsa_check(eckey);
         group = EC_KEY_get0_group(eckey);
@@ -230,7 +230,9 @@ ecdsa_do_sign(const unsigned char *dgst, int dgst_len,
         s = ret->s;
 
         if ((ctx = BN_CTX_new()) == NULL || (order = BN_new()) == NULL ||
-            (tmp = BN_new()) == NULL || (m = BN_new()) == NULL) {
+            (range = BN_new()) == NULL || (b = BN_new()) == NULL ||
+            (binv = BN_new()) == NULL || (bm = BN_new()) == NULL ||
+            (bxr = BN_new()) == NULL || (m = BN_new()) == NULL) {
                 ECDSAerror(ERR_R_MALLOC_FAILURE);
                 goto err;
         }
@@ -269,11 +271,53 @@ ecdsa_do_sign(const unsigned char *dgst, int dgst_len,
                         }
                 }
 
-                if (!BN_mod_mul(tmp, priv_key, ret->r, order, ctx)) {
+                /*
+                 * Compute s = inv(k)(m + xr) mod order.
+                 *
+                 * In order to reduce the possibility of a side-channel attack,
+                 * the following is calculated using a blinding value:
+                 *
+                 *  s = inv(k)inv(b)(bm + bxr) mod order
+                 *
+                 * where b is a random value in the range [1, order-1].
+                 */
+                
+                /* Generate b in range [1, order-1]. */
+                if (!BN_sub(range, order, BN_value_one())) {
+                        ECDSAerror(ERR_R_BN_LIB);
+                        goto err;
+                }
+                if (!BN_rand_range(b, range)) {
                         ECDSAerror(ERR_R_BN_LIB);
                         goto err;
                 }
-                if (!BN_mod_add(s, tmp, m, order, ctx)) {
+                if (!BN_add(b, b, BN_value_one())) {
+                        ECDSAerror(ERR_R_BN_LIB);
+                        goto err;
+                }
+
+                if (BN_mod_inverse_ct(binv, b, order, ctx) == NULL) {
+                        ECDSAerror(ERR_R_BN_LIB);
+                        goto err;
+                }
+
+                if (!BN_mod_mul(bxr, b, priv_key, order, ctx)) { /* bx */
+                        ECDSAerror(ERR_R_BN_LIB);
+                        goto err;
+                }
+                if (!BN_mod_mul(bxr, bxr, ret->r, order, ctx)) { /* bxr */
+                        ECDSAerror(ERR_R_BN_LIB);
+                        goto err;
+                }
+                if (!BN_mod_mul(bm, b, m, order, ctx)) { /* bm */
+                        ECDSAerror(ERR_R_BN_LIB);
+                        goto err;
+                }
+                if (!BN_mod_add(s, bm, bxr, order, ctx)) { /* s = bm + bxr */
+                        ECDSAerror(ERR_R_BN_LIB);
+                        goto err;
+                }
+                if (!BN_mod_mul(s, s, binv, order, ctx)) { /* s = m + xr */
                         ECDSAerror(ERR_R_BN_LIB);
                         goto err;
                 }
@@ -281,9 +325,12 @@ ecdsa_do_sign(const unsigned char *dgst, int dgst_len,
                         ECDSAerror(ERR_R_BN_LIB);
                         goto err;
                 }
+
                 if (BN_is_zero(s)) {
-                        /* if kinv and r have been supplied by the caller
-                         * don't to generate new kinv and r values */
+                        /*
+                         * If kinv and r have been supplied by the caller,
+                         * don't generate new kinv and r values
+                         */
                         if (in_kinv != NULL && in_r != NULL) {
                                 ECDSAerror(ECDSA_R_NEED_NEW_SETUP_VALUES);
                                 goto err;
@@ -301,10 +348,14 @@ err:
                 ret = NULL;
         }
         BN_CTX_free(ctx);
+        BN_clear_free(b);
+        BN_clear_free(binv);
+        BN_clear_free(bm);
+        BN_clear_free(bxr);
+        BN_clear_free(kinv);
         BN_clear_free(m);
-        BN_clear_free(tmp);
         BN_free(order);
-        BN_clear_free(kinv);
+        BN_free(range);
         return ret;
 }