# 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); }