# HG changeset patch
# User Franziskus Kiefer <franziskuskiefer@gmail.com>
# Date 1527579529 -7200
# Node ID ca18ca4ba00d97ac9683d92d3a16d9832342ba75
# Parent  db7f6facd8dfa0ec4f91612b62c563ecf3892063
Bug 1464971 - improve ecdsa and dsa, r=mt

Differential Revision: https://phabricator.services.mozilla.com/D1441

diff --git a/lib/freebl/dsa.c b/lib/freebl/dsa.c
--- a/lib/freebl/dsa.c
+++ b/lib/freebl/dsa.c
@@ -11,24 +11,21 @@
 #include "prerror.h"
 #include "secerr.h"
 
 #include "prtypes.h"
 #include "prinit.h"
 #include "blapi.h"
 #include "nssilock.h"
 #include "secitem.h"
-#include "blapi.h"
+#include "blapit.h"
 #include "mpi.h"
 #include "secmpi.h"
 #include "pqg.h"
 
-/* XXX to be replaced by define in blapit.h */
-#define NSS_FREEBL_DSA_DEFAULT_CHUNKSIZE 2048
-
 /*
  * FIPS 186-2 requires result from random output to be reduced mod q when
  * generating random numbers for DSA.
  *
  * Input: w, 2*qLen bytes
  *        q, qLen bytes
  * Output: xj, qLen bytes
  */
@@ -163,17 +160,17 @@ dsa_NewKeyExtended(const PQGParams *para
     PLArenaPool *arena;
     DSAPrivateKey *key;
     /* Check args. */
     if (!params || !privKey || !seed || !seed->data) {
         PORT_SetError(SEC_ERROR_INVALID_ARGS);
         return SECFailure;
     }
     /* Initialize an arena for the DSA key. */
-    arena = PORT_NewArena(NSS_FREEBL_DSA_DEFAULT_CHUNKSIZE);
+    arena = PORT_NewArena(NSS_FREEBL_DEFAULT_CHUNKSIZE);
     if (!arena) {
         PORT_SetError(SEC_ERROR_NO_MEMORY);
         return SECFailure;
     }
     key = (DSAPrivateKey *)PORT_ArenaZAlloc(arena, sizeof(DSAPrivateKey));
     if (!key) {
         PORT_SetError(SEC_ERROR_NO_MEMORY);
         PORT_FreeArena(arena, PR_TRUE);
@@ -208,18 +205,19 @@ dsa_NewKeyExtended(const PQGParams *para
     MPINT_TO_SECITEM(&y, &key->publicValue, arena);
     *privKey = key;
     key = NULL;
 cleanup:
     mp_clear(&p);
     mp_clear(&g);
     mp_clear(&x);
     mp_clear(&y);
-    if (key)
+    if (key) {
         PORT_FreeArena(key->params.arena, PR_TRUE);
+    }
     if (err) {
         translate_mpi_error(err);
         return SECFailure;
     }
     return SECSuccess;
 }
 
 SECStatus
@@ -316,16 +314,17 @@ DSA_NewKeyFromSeed(const PQGParams *para
 static SECStatus
 dsa_SignDigest(DSAPrivateKey *key, SECItem *signature, const SECItem *digest,
                const unsigned char *kb)
 {
     mp_int p, q, g; /* PQG parameters */
     mp_int x, k;    /* private key & pseudo-random integer */
     mp_int r, s;    /* tuple (r, s) is signature) */
     mp_int t;       /* holding tmp values */
+    mp_int ar;      /* holding blinding values */
     mp_err err = MP_OKAY;
     SECStatus rv = SECSuccess;
     unsigned int dsa_subprime_len, dsa_signature_len, offset;
     SECItem localDigest;
     unsigned char localDigestData[DSA_MAX_SUBPRIME_LEN];
     SECItem t2 = { siBuffer, NULL, 0 };
 
     /* FIPS-compliance dictates that digest is a SHA hash. */
@@ -359,24 +358,26 @@ dsa_SignDigest(DSAPrivateKey *key, SECIt
     MP_DIGITS(&p) = 0;
     MP_DIGITS(&q) = 0;
     MP_DIGITS(&g) = 0;
     MP_DIGITS(&x) = 0;
     MP_DIGITS(&k) = 0;
     MP_DIGITS(&r) = 0;
     MP_DIGITS(&s) = 0;
     MP_DIGITS(&t) = 0;
+    MP_DIGITS(&ar) = 0;
     CHECK_MPI_OK(mp_init(&p));
     CHECK_MPI_OK(mp_init(&q));
     CHECK_MPI_OK(mp_init(&g));
     CHECK_MPI_OK(mp_init(&x));
     CHECK_MPI_OK(mp_init(&k));
     CHECK_MPI_OK(mp_init(&r));
     CHECK_MPI_OK(mp_init(&s));
     CHECK_MPI_OK(mp_init(&t));
+    CHECK_MPI_OK(mp_init(&ar));
     /*
     ** Convert stored PQG and private key into MPI integers.
     */
     SECITEM_TO_MPINT(key->params.prime, &p);
     SECITEM_TO_MPINT(key->params.subPrime, &q);
     SECITEM_TO_MPINT(key->params.base, &g);
     SECITEM_TO_MPINT(key->privateValue, &x);
     OCTETS_TO_MPINT(kb, &k, dsa_subprime_len);
@@ -392,24 +393,38 @@ dsa_SignDigest(DSAPrivateKey *key, SECIt
     **
     ** s = (k**-1 * (HASH(M) + x*r)) mod q
     */
     if (DSA_NewRandom(NULL, &key->params.subPrime, &t2) != SECSuccess) {
         PORT_SetError(SEC_ERROR_NEED_RANDOM);
         rv = SECFailure;
         goto cleanup;
     }
-    SECITEM_TO_MPINT(t2, &t);                /* t <-$ Zq */
+    SECITEM_TO_MPINT(t2, &t); /* t <-$ Zq */
+    SECITEM_FreeItem(&t2, PR_FALSE);
+    if (DSA_NewRandom(NULL, &key->params.subPrime, &t2) != SECSuccess) {
+        PORT_SetError(SEC_ERROR_NEED_RANDOM);
+        rv = SECFailure;
+        goto cleanup;
+    }
+    SECITEM_TO_MPINT(t2, &ar); /* ar <-$ Zq */
+    SECITEM_FreeItem(&t2, PR_FALSE);
+
+    /* Using mp_invmod on k directly would leak bits from k. */
+    CHECK_MPI_OK(mp_mul(&k, &ar, &k));       /* k = k * ar */
     CHECK_MPI_OK(mp_mulmod(&k, &t, &q, &k)); /* k = k * t mod q */
     CHECK_MPI_OK(mp_invmod(&k, &q, &k));     /* k = k**-1 mod q */
     CHECK_MPI_OK(mp_mulmod(&k, &t, &q, &k)); /* k = k * t mod q */
     SECITEM_TO_MPINT(localDigest, &s);       /* s = HASH(M)     */
-    CHECK_MPI_OK(mp_mulmod(&x, &r, &q, &x)); /* x = x * r mod q */
-    CHECK_MPI_OK(mp_addmod(&s, &x, &q, &s)); /* s = s + x mod q */
-    CHECK_MPI_OK(mp_mulmod(&s, &k, &q, &s)); /* s = s * k mod q */
+    /* To avoid leaking secret bits here the addition is blinded. */
+    CHECK_MPI_OK(mp_mul(&x, &ar, &x));        /* x = x * ar */
+    CHECK_MPI_OK(mp_mulmod(&x, &r, &q, &x));  /* x = x * r mod q */
+    CHECK_MPI_OK(mp_mulmod(&s, &ar, &q, &t)); /* t = s * ar mod q */
+    CHECK_MPI_OK(mp_add(&t, &x, &s));         /* s = t + x */
+    CHECK_MPI_OK(mp_mulmod(&s, &k, &q, &s));  /* s = s * k mod q */
     /*
     ** verify r != 0 and s != 0
     ** mentioned as optional in FIPS 186-1.
     */
     if (mp_cmp_z(&r) == 0 || mp_cmp_z(&s) == 0) {
         PORT_SetError(SEC_ERROR_NEED_RANDOM);
         rv = SECFailure;
         goto cleanup;
@@ -433,17 +448,17 @@ cleanup:
     mp_clear(&p);
     mp_clear(&q);
     mp_clear(&g);
     mp_clear(&x);
     mp_clear(&k);
     mp_clear(&r);
     mp_clear(&s);
     mp_clear(&t);
-    SECITEM_FreeItem(&t2, PR_FALSE);
+    mp_clear(&ar);
     if (err) {
         translate_mpi_error(err);
         rv = SECFailure;
     }
     return rv;
 }
 
 /* signature is caller-supplied buffer of at least 40 bytes.
diff --git a/lib/freebl/ec.c b/lib/freebl/ec.c
--- a/lib/freebl/ec.c
+++ b/lib/freebl/ec.c
@@ -648,16 +648,17 @@ ECDSA_SignDigestWithSeed(ECPrivateKey *k
                          const SECItem *digest, const unsigned char *kb, const int kblen)
 {
     SECStatus rv = SECFailure;
     mp_int x1;
     mp_int d, k; /* private key, random integer */
     mp_int r, s; /* tuple (r, s) is the signature */
     mp_int t;    /* holding tmp values */
     mp_int n;
+    mp_int ar; /* blinding value */
     mp_err err = MP_OKAY;
     ECParams *ecParams = NULL;
     SECItem kGpoint = { siBuffer, NULL, 0 };
     int flen = 0;   /* length in bytes of the field size */
     unsigned olen;  /* length in bytes of the base point order */
     unsigned obits; /* length in bits  of the base point order */
     unsigned char *t2 = NULL;
 
@@ -669,16 +670,17 @@ ECDSA_SignDigestWithSeed(ECPrivateKey *k
     /* must happen before the first potential call to cleanup */
     MP_DIGITS(&x1) = 0;
     MP_DIGITS(&d) = 0;
     MP_DIGITS(&k) = 0;
     MP_DIGITS(&r) = 0;
     MP_DIGITS(&s) = 0;
     MP_DIGITS(&n) = 0;
     MP_DIGITS(&t) = 0;
+    MP_DIGITS(&ar) = 0;
 
     /* Check args */
     if (!key || !signature || !digest || !kb || (kblen < 0)) {
         PORT_SetError(SEC_ERROR_INVALID_ARGS);
         goto cleanup;
     }
 
     ecParams = &(key->ecParams);
@@ -695,16 +697,17 @@ ECDSA_SignDigestWithSeed(ECPrivateKey *k
 
     CHECK_MPI_OK(mp_init(&x1));
     CHECK_MPI_OK(mp_init(&d));
     CHECK_MPI_OK(mp_init(&k));
     CHECK_MPI_OK(mp_init(&r));
     CHECK_MPI_OK(mp_init(&s));
     CHECK_MPI_OK(mp_init(&n));
     CHECK_MPI_OK(mp_init(&t));
+    CHECK_MPI_OK(mp_init(&ar));
 
     SECITEM_TO_MPINT(ecParams->order, &n);
     SECITEM_TO_MPINT(key->privateValue, &d);
 
     CHECK_MPI_OK(mp_read_unsigned_octets(&k, kb, kblen));
     /* Make sure k is in the interval [1, n-1] */
     if ((mp_cmp_z(&k) <= 0) || (mp_cmp(&k, &n) >= 0)) {
 #if EC_DEBUG
@@ -810,22 +813,35 @@ ECDSA_SignDigestWithSeed(ECPrivateKey *k
         goto cleanup;
     }
     if (RNG_GenerateGlobalRandomBytes(t2, 2 * ecParams->order.len) != SECSuccess) {
         PORT_SetError(SEC_ERROR_NEED_RANDOM);
         rv = SECFailure;
         goto cleanup;
     }
     CHECK_MPI_OK(mp_read_unsigned_octets(&t, t2, 2 * ecParams->order.len)); /* t <-$ Zn */
-    CHECK_MPI_OK(mp_mulmod(&k, &t, &n, &k));                                /* k = k * t mod n */
-    CHECK_MPI_OK(mp_invmod(&k, &n, &k));                                    /* k = k**-1 mod n */
-    CHECK_MPI_OK(mp_mulmod(&k, &t, &n, &k));                                /* k = k * t mod n */
-    CHECK_MPI_OK(mp_mulmod(&d, &r, &n, &d));                                /* d = d * r mod n */
-    CHECK_MPI_OK(mp_addmod(&s, &d, &n, &s));                                /* s = s + d mod n */
-    CHECK_MPI_OK(mp_mulmod(&s, &k, &n, &s));                                /* s = s * k mod n */
+    PORT_Memset(t2, 0, 2 * ecParams->order.len);
+    if (RNG_GenerateGlobalRandomBytes(t2, 2 * ecParams->order.len) != SECSuccess) {
+        PORT_SetError(SEC_ERROR_NEED_RANDOM);
+        rv = SECFailure;
+        goto cleanup;
+    }
+    CHECK_MPI_OK(mp_read_unsigned_octets(&ar, t2, 2 * ecParams->order.len)); /* ar <-$ Zn */
+
+    /* Using mp_invmod on k directly would leak bits from k. */
+    CHECK_MPI_OK(mp_mul(&k, &ar, &k));       /* k = k * ar */
+    CHECK_MPI_OK(mp_mulmod(&k, &t, &n, &k)); /* k = k * t mod n */
+    CHECK_MPI_OK(mp_invmod(&k, &n, &k));     /* k = k**-1 mod n */
+    CHECK_MPI_OK(mp_mulmod(&k, &t, &n, &k)); /* k = k * t mod n */
+    /* To avoid leaking secret bits here the addition is blinded. */
+    CHECK_MPI_OK(mp_mul(&d, &ar, &t));        /* t = d * ar */
+    CHECK_MPI_OK(mp_mulmod(&t, &r, &n, &d));  /* d = t * r mod n */
+    CHECK_MPI_OK(mp_mulmod(&s, &ar, &n, &t)); /* t = s * ar mod n */
+    CHECK_MPI_OK(mp_add(&t, &d, &s));         /* s = t + d */
+    CHECK_MPI_OK(mp_mulmod(&s, &k, &n, &s));  /* s = s * k mod n */
 
 #if EC_DEBUG
     mp_todecimal(&s, mpstr);
     printf("s : %s (dec)\n", mpstr);
     mp_tohex(&s, mpstr);
     printf("s : %s\n", mpstr);
 #endif
 
@@ -853,16 +869,17 @@ finish:
 cleanup:
     mp_clear(&x1);
     mp_clear(&d);
     mp_clear(&k);
     mp_clear(&r);
     mp_clear(&s);
     mp_clear(&n);
     mp_clear(&t);
+    mp_clear(&ar);
 
     if (t2) {
         PORT_Free(t2);
     }
 
     if (kGpoint.data) {
         PORT_ZFree(kGpoint.data, kGpoint.len);
     }