Bug 1602379 - Provide secure variants of mpp_pprime and mpp_make_prime. r=mt

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

11 files changed, 80 insertions, 18 deletions

diff --git a/cmd/mpitests/mpi-test.c b/cmd/mpitests/mpi-test.c
index b7953b6f6..80c0f951a 100644
--- a/cmd/mpitests/mpi-test.c
+++ b/cmd/mpitests/mpi-test.c
@@ -17,7 +17,9 @@
 #include <limits.h>
 #include <time.h>
 
+#include "blapi.h"
 #include "mpi.h"
+#include "secmpi.h"
 #include "mpprime.h"
 
 #include "test-info.c"
@@ -2045,31 +2047,32 @@ test_pprime(void)
     int err = 0;
     mp_err res;
 
+    RNG_RNGInit();
     mp_init(&p);
     mp_read_radix(&p, mp7, 16);
 
-    if (mpp_pprime(&p, 5) != MP_YES) {
+    if (mpp_pprime_secure(&p, 5) != MP_YES) {
         reason("error: %s failed Rabin-Miller test, but is prime\n", mp7);
         err = 1;
     }
 
     IFOK(mp_set_int(&p, 9));
-    res = mpp_pprime(&p, 50);
+    res = mpp_pprime_secure(&p, 50);
     if (res == MP_YES) {
         reason("error: 9 is composite but passed Rabin-Miller test\n");
         err = 1;
     } else if (res != MP_NO) {
-        reason("test mpp_pprime(9, 50) failed: error %d\n", res);
+        reason("test mpp_pprime_secure(9, 50) failed: error %d\n", res);
         err = 1;
     }
 
     IFOK(mp_set_int(&p, 15));
-    res = mpp_pprime(&p, 50);
+    res = mpp_pprime_secure(&p, 50);
     if (res == MP_YES) {
         reason("error: 15 is composite but passed Rabin-Miller test\n");
         err = 1;
     } else if (res != MP_NO) {
-        reason("test mpp_pprime(15, 50) failed: error %d\n", res);
+        reason("test mpp_pprime_secure(15, 50) failed: error %d\n", res);
         err = 1;
     }
 
diff --git a/lib/freebl/Makefile b/lib/freebl/Makefile
index 0b8c6f42f..767335730 100644
--- a/lib/freebl/Makefile
+++ b/lib/freebl/Makefile
@@ -659,7 +659,7 @@ INCLUDES += -Impi -Iecl -Iverified -Iverified/kremlin/include -Iverified/kremlin
 
 DEFINES += -DMP_API_COMPATIBLE
 
-MPI_USERS = dh.c pqg.c dsa.c rsa.c ec.c
+MPI_USERS = secmpi.c dh.c pqg.c dsa.c rsa.c ec.c
 
 MPI_OBJS = $(addprefix $(OBJDIR)/$(PROG_PREFIX), $(MPI_SRCS:.c=$(OBJ_SUFFIX)))
 MPI_OBJS += $(addprefix $(OBJDIR)/$(PROG_PREFIX), $(MPI_USERS:.c=$(OBJ_SUFFIX)))
diff --git a/lib/freebl/dh.c b/lib/freebl/dh.c
index aa3a3ee32..bdd5dd63a 100644
--- a/lib/freebl/dh.c
+++ b/lib/freebl/dh.c
@@ -17,7 +17,6 @@
 #include "blapii.h"
 #include "secitem.h"
 #include "mpi.h"
-#include "mpprime.h"
 #include "secmpi.h"
 
 #define KEA_DERIVED_SECRET_LEN 128
@@ -437,7 +436,7 @@ KEA_PrimeCheck(SECItem *prime)
     MP_DIGITS(&p) = 0;
     CHECK_MPI_OK(mp_init(&p));
     SECITEM_TO_MPINT(*prime, &p);
-    CHECK_MPI_OK(mpp_pprime(&p, dh_prime_testcount(prime->len)));
+    CHECK_MPI_OK(mpp_pprime_secure(&p, dh_prime_testcount(prime->len)));
 cleanup:
     mp_clear(&p);
     return err ? PR_FALSE : PR_TRUE;
diff --git a/lib/freebl/freebl_base.gypi b/lib/freebl/freebl_base.gypi
index d3b71d7da..34b6b3c81 100644
--- a/lib/freebl/freebl_base.gypi
+++ b/lib/freebl/freebl_base.gypi
@@ -60,6 +60,7 @@
     'shvfy.c',
     'sysrand.c',
     'tlsprfalg.c',
+    'secmpi.c',
   ],
   'conditions': [
     [ 'OS=="linux" or OS=="android"', {
diff --git a/lib/freebl/manifest.mn b/lib/freebl/manifest.mn
index 9dac2106f..b6c5fb358 100644
--- a/lib/freebl/manifest.mn
+++ b/lib/freebl/manifest.mn
@@ -150,6 +150,7 @@ CSRCS = \
 	shvfy.c \
 	tlsprfalg.c \
 	jpake.c \
+	secmpi.c \
 	$(MPI_SRCS) \
 	$(MPCPU_SRCS) \
 	$(ECL_SRCS) \
diff --git a/lib/freebl/mpi/mpprime.c b/lib/freebl/mpi/mpprime.c
index 9d6232c29..b757150e7 100644
--- a/lib/freebl/mpi/mpprime.c
+++ b/lib/freebl/mpi/mpprime.c
@@ -126,6 +126,8 @@ mpp_random(mp_int *a)
 
 /* }}} */
 
+static mpp_random_fn mpp_random_insecure = &mpp_random;
+
 /* {{{ mpp_random_size(a, prec) */
 
 mp_err
@@ -138,7 +140,7 @@ mpp_random_size(mp_int *a, mp_size prec)
     if ((res = s_mp_pad(a, prec)) != MP_OKAY)
         return res;
 
-    return mpp_random(a);
+    return (*mpp_random_insecure)(a);
 
 } /* end mpp_random_size() */
 
@@ -272,6 +274,12 @@ mpp_fermat_list(mp_int *a, const mp_digit *primes, mp_size nPrimes)
 mp_err
 mpp_pprime(mp_int *a, int nt)
 {
+    return mpp_pprime_ext_random(a, nt, mpp_random_insecure);
+}
+
+mp_err
+mpp_pprime_ext_random(mp_int *a, int nt, mpp_random_fn random)
+{
     mp_err res;
     mp_int x, amo, m, z; /* "amo" = "a minus one" */
     int iter;
@@ -306,7 +314,7 @@ mpp_pprime(mp_int *a, int nt)
 
         /* Choose a random value for 1 < x < a      */
         MP_CHECKOK(s_mp_pad(&x, USED(a)));
-        mpp_random(&x);
+        MP_CHECKOK((*random)(&x));
         MP_CHECKOK(mp_mod(&x, a, &x));
         if (mp_cmp_d(&x, 1) <= 0) {
             iter--;   /* don't count this iteration */
@@ -404,6 +412,12 @@ mpp_sieve(mp_int *trial, const mp_digit *primes, mp_size nPrimes,
 mp_err
 mpp_make_prime(mp_int *start, mp_size nBits, mp_size strong)
 {
+    return mpp_make_prime_ext_random(start, nBits, strong, mpp_random_insecure);
+}
+
+mp_err
+mpp_make_prime_ext_random(mp_int *start, mp_size nBits, mp_size strong, mpp_random_fn random)
+{
     mp_digit np;
     mp_err res;
     unsigned int i = 0;
@@ -490,7 +504,7 @@ mpp_make_prime(mp_int *start, mp_size nBits, mp_size strong)
 
         FPUTC('+', stderr);
         /* If that passed, run some Miller-Rabin tests  */
-        res = mpp_pprime(&trial, num_tests);
+        res = mpp_pprime_ext_random(&trial, num_tests, random);
         if (res != MP_OKAY) {
             if (res == MP_NO)
                 continue; /* was composite */
@@ -528,7 +542,7 @@ mpp_make_prime(mp_int *start, mp_size nBits, mp_size strong)
         }
 
         /* And test with Miller-Rabin, as with its parent ... */
-        res = mpp_pprime(&q, num_tests);
+        res = mpp_pprime_ext_random(&q, num_tests, random);
         if (res != MP_YES) {
             mp_clear(&q);
             if (res == MP_NO)
diff --git a/lib/freebl/mpi/mpprime.h b/lib/freebl/mpi/mpprime.h
index acd888d4a..0bdc6598c 100644
--- a/lib/freebl/mpi/mpprime.h
+++ b/lib/freebl/mpi/mpprime.h
@@ -26,6 +26,9 @@ mp_err mpp_divis_d(mp_int *a, mp_digit d);
 mp_err mpp_random(mp_int *a);
 mp_err mpp_random_size(mp_int *a, mp_size prec);
 
+/* Type for a pointer to a user-provided mpp_random implementation */
+typedef mp_err (*mpp_random_fn)(mp_int *);
+
 /* Pseudo-primality testing  */
 mp_err mpp_divis_vector(mp_int *a, const mp_digit *vec, int size, int *which);
 mp_err mpp_divis_primes(mp_int *a, mp_digit *np);
@@ -36,6 +39,10 @@ mp_err mpp_sieve(mp_int *trial, const mp_digit *primes, mp_size nPrimes,
                  unsigned char *sieve, mp_size nSieve);
 mp_err mpp_make_prime(mp_int *start, mp_size nBits, mp_size strong);
 
+/* Pseudo-primality tests using a user-provided mpp_random implementation */
+mp_err mpp_pprime_ext_random(mp_int *a, int nt, mpp_random_fn random);
+mp_err mpp_make_prime_ext_random(mp_int *start, mp_size nBits, mp_size strong, mpp_random_fn random);
+
 SEC_END_PROTOS
 
 #endif /* end _H_MP_PRIME_ */
diff --git a/lib/freebl/pqg.c b/lib/freebl/pqg.c
index 1b03278a2..dc3b350e0 100644
--- a/lib/freebl/pqg.c
+++ b/lib/freebl/pqg.c
@@ -1432,7 +1432,7 @@ step_5:
     ** "will give an acceptable probability of error."
     */
     /*CHECK_SEC_OK( prm_RabinTest(&Q, &passed) );*/
-    err = mpp_pprime(&Q, prime_testcount_q(L, N));
+    err = mpp_pprime_secure(&Q, prime_testcount_q(L, N));
     passed = (err == MP_YES) ? SECSuccess : SECFailure;
     /* ******************************************************************
     ** Step 9. (Step 5 in 186-1) "If q is not prime, goto step 5 (1 in 186-1)."
@@ -1485,7 +1485,7 @@ step_5:
     ** "Perform a robust primality test on p."
     */
         /*CHECK_SEC_OK( prm_RabinTest(&P, &passed) );*/
-        err = mpp_pprime(&P, prime_testcount_p(L, N));
+        err = mpp_pprime_secure(&P, prime_testcount_p(L, N));
         passed = (err == MP_YES) ? SECSuccess : SECFailure;
         /* ******************************************************************
     ** Step 11.8. "If p is determined to be primed return VALID
@@ -1713,9 +1713,9 @@ PQG_VerifyParams(const PQGParams *params,
     CHECK_MPI_OK(mp_mod(&P, &Q, &r));
     CHECKPARAM(mp_cmp_d(&r, 1) == 0);
     /* 5.  Q is prime */
-    CHECKPARAM(mpp_pprime(&Q, prime_testcount_q(L, N)) == MP_YES);
+    CHECKPARAM(mpp_pprime_secure(&Q, prime_testcount_q(L, N)) == MP_YES);
     /* 6.  P is prime */
-    CHECKPARAM(mpp_pprime(&P, prime_testcount_p(L, N)) == MP_YES);
+    CHECKPARAM(mpp_pprime_secure(&P, prime_testcount_p(L, N)) == MP_YES);
     /* Steps 7-12 are done only if the optional PQGVerify is supplied. */
     /* continue processing P */
     /* 7.  counter < 4*L */
diff --git a/lib/freebl/rsa.c b/lib/freebl/rsa.c
index 5a4e4096f..89bdd6857 100644
--- a/lib/freebl/rsa.c
+++ b/lib/freebl/rsa.c
@@ -208,7 +208,7 @@ generate_prime(mp_int *prime, int primeLen)
         pb[0] |= 0xC0;            /* set two high-order bits */
         pb[primeLen - 1] |= 0x01; /* set low-order bit       */
         CHECK_MPI_OK(mp_read_unsigned_octets(prime, pb, primeLen));
-        err = mpp_make_prime(prime, primeLen * 8, PR_FALSE);
+        err = mpp_make_prime_secure(prime, primeLen * 8, PR_FALSE);
         if (err != MP_NO)
             goto cleanup;
         /* keep going while err == MP_NO */
@@ -391,7 +391,7 @@ rsa_is_prime(mp_int *p)
     }
 
     /* If that passed, run some Miller-Rabin tests */
-    res = mpp_pprime(p, 2);
+    res = mpp_pprime_secure(p, 2);
     return res;
 }
 
diff --git a/lib/freebl/secmpi.c b/lib/freebl/secmpi.c
new file mode 100644
index 000000000..7d6ee4405
--- /dev/null
+++ b/lib/freebl/secmpi.c
@@ -0,0 +1,28 @@
+#include "blapi.h"
+
+#include "mpi.h"
+#include "mpprime.h"
+
+mp_err
+mpp_random_secure(mp_int *a)
+{
+    SECStatus rv;
+    rv = RNG_GenerateGlobalRandomBytes((unsigned char *)MP_DIGITS(a), MP_USED(a) * sizeof(mp_digit));
+    if (rv != SECSuccess) {
+        return MP_UNDEF;
+    }
+    MP_SIGN(a) = MP_ZPOS;
+    return MP_OKAY;
+}
+
+mp_err
+mpp_pprime_secure(mp_int *a, int nt)
+{
+    return mpp_pprime_ext_random(a, nt, &mpp_random_secure);
+}
+
+mp_err
+mpp_make_prime_secure(mp_int *start, mp_size nBits, mp_size strong)
+{
+    return mpp_make_prime_ext_random(start, nBits, strong, &mpp_random_secure);
+}
diff --git a/lib/freebl/secmpi.h b/lib/freebl/secmpi.h
index 5e8fd1105..53f9a53c1 100644
--- a/lib/freebl/secmpi.h
+++ b/lib/freebl/secmpi.h
@@ -52,3 +52,12 @@
             PORT_SetError(SEC_ERROR_LIBRARY_FAILURE); \
             break;                                    \
     }
+
+/* Fill the `used` digits of an mp_int with random bits */
+mp_err mpp_random_secure(mp_int *a);
+
+/* Pseudo-primality testing using `mpp_random_secure` to choose Miller-Rabin base */
+mp_err mpp_pprime_secure(mp_int *a, int nt);
+
+/* Variant of `mpp_make_prime` using `mpp_random_secure` to choose Miller-Rabin base */
+mp_err mpp_make_prime_secure(mp_int *start, mp_size nBits, mp_size strong);