992240 - RSA_PopulatePrivateKey fails for PKCS#1 valid keys

Status: RESOLVED FIXED

(NSS :: Libraries, defect, P2)

Description

[Richard Barnes [:rbarnes]]

Attachment: Validation of RSA-valid and PKCS#1-valid keys

Short version: RSA_PopulatePrivateKey fails for the keys specified in the RSA PKCS#1 test vectors
ftp://ftp.rsa.com/pub/rsalabs/tmp/pkcs1v15sign-vectors.txt

This appears to be because these keys meet only the PKCS#1 requirement for key pairs, namely:
> The private exponent shall be a positive integer d such that de-1 is
> divisible by both p-1 and q-1.

(Thus, e*d-1 is 0 mod lcm(p-1, q-1).)

In contrast, RSA_PopulatePrivateKey expects e*d - 1 to be 0 mod phi(N), which can be false for PKCS#1 keys, since phi(N) > lcm(p-1, q-1).  The algorithm that RSA_PopulatePrivateKey uses to find the factors p and q fails if this is not the case.

One possible alternative algorithm that is compatible with these keys is the one used by PyCrypto:
https://github.com/dlitz/pycrypto/blob/master/lib/Crypto/PublicKey/_slowmath.py#L82

Comment 1

[Wan-Teh Chang]

Bob: you added the RSA_PopulatePrivateKey function in bug 584257.
Could you take a look at this bug? Thanks.

Richard: do you need to use RSA_PopulatePrivateKey in WebCrypto?

Comment 2

[Richard Barnes [:rbarnes]]

So the general requirement is: For WebCrypto JWK import, I need a way to create a SECKEYPrivateKey using only the modulus and public/private exponents. 

Implementing JWK for WebCrypto is how I came across this bug.  My current implementation of importKey("jwk", ...) works by creating a PKCS#8 object and importing that via PK11_ImportDERPrivateKeyInfo.  Because JWK only requires the modulus and public/private exponents (not the other private key parameters), but PKCS#8 does, I use RSA_PopulatePrivateKey to derive them.   

RSleevi proposed an alternative approach using PK11_CreateGenericObject (https://codereview.chromium.org/203753009/#msg9), but I haven't yet figured out how to get a SECKEYPrivateKey (or SECKEYPublicKey for that matter) via that route.  So the PKCS#8 thing is all I have for now.

Comment 3

[Ryan Sleevi]

Richard: http://mxr.mozilla.org/security/ident?i=PK11_FindKeyByKeyID is what I recommended to Eric. It's a "private" (that is, exposed for JSS, ergo has the same use case as WebCrypto) function that looks up based on CKA_ID.

For getting the public key, we're doing a really gross thing of enumerating via PK11_ListPublicKeysInSlot

We could arguably add wrapper functions to both to take a CKA_ID and return the corresponding SECKEYPublic/PrivateKey, but thats best for a separate bug :)

Regardless of the approach - PK11_ImportDERPrivateKeyInfo or PK11_CreateGenericObject, both eventually pass through RSA_PopulatePrivateKey, so this applies.

Comment 4

[Filippo Valsorda]

Attachment: RSA_PopulatePrivateKey_PKCS1.patch

There seems not to be a way to adapt the current algorithm to the reduced modulus case, so I implemented a casually optimized version of the PyCrypto routine, added it as a fallback, and added the vectors to the tests.

Proof of Concept: The probabilities of this being a applicable patch as-is are nil, it needs at least to be documented and some vetting since it has been written offline on a plane and I'm not familiar with Bugzilla or Mercurial.

Comment 5

[Filippo Valsorda]

Attachment: RSA_PopulatePrivateKey_PKCS1_replace.patch

Here is a more polished patch. The function is commented inline explaining the
steps, as faithfully as possible to the Handbook nomenclature. Also,
the algorithm is slightly more optimized.

Since the new algorithm is actually faster than the old one when a modulus is
provided (see below for a poor-man's benchmark) I changed RSA_PopulatePrivateKey
behavior to use it exclusively in that cases, instead of as a fallback.

As a consequence the hasModulus mode of rsa_get_primes_from_exponents became
useless, and I removed it from the comments and code. To signal this behavioral
change, I changed the name of the function to rsa_get_prime_from_exponents.

I feel like the end result is two smaller simpler and faster functions, that
are probably more maintainable, even if it means using two different algorithms
in the codebase (thing that was anyway unavoidable to fix this bug).

---

OLD - only "pubExp privExp mod"
./bltest -R -r 100  22,16s user 0,01s system 99% cpu 22,178 total
NEW - only "pubExp privExp mod"
./bltest -R -r 100  17,42s user 0,01s system 99% cpu 17,434 total

OLD - only "pubExp privExp q"
./bltest -R -r 100  23,28s user 0,02s system 99% cpu 23,302 total
NEW - only "pubExp privExp q"
./bltest -R -r 100  23,84s user 0,02s system 99% cpu 23,873 total

NULL - only srcKey gen (baseline)
./bltest -R -r 100  16,78s user 0,01s system 99% cpu 16,802 total

Comment 6

[Watson Ladd]

Comment on attachment 8440273 [details] [diff] [review]
RSA_PopulatePrivateKey_PKCS1_replace.patch

Review of attachment 8440273 [details] [diff] [review]:
-----------------------------------------------------------------

This code looks good. Both of the new algorithms should work reliably and the code is easy to understand, and we have tests added confirming the new behavior works.

Comment 7

[Richard Barnes [:rbarnes]]

Comment on attachment 8440273 [details] [diff] [review]
RSA_PopulatePrivateKey_PKCS1_replace.patch

Review of attachment 8440273 [details] [diff] [review]:
-----------------------------------------------------------------

::: cmd/bltest/blapitest.c
@@ +3346,5 @@
>  	failed = 1;
>      }
>  
> +    /* test public exponent, private exponent, modulus cases from pkcs1v15sign-vectors.txt
> +       some are valid PKCS#1 key but not valid RSA ones (de = 1 mod lcm(p − 1, q − 1)) */

Nit: Please wrap to 80 columns.

@@ +3364,5 @@
> +        rv = RSA_PopulatePrivateKey(&tstKey);
> +        if (rv != SECSuccess) {
> +            fprintf(stderr, "RSA Populate failed: pkcs1v15sign-vector %d\n", i);
> +            failed = 1;
> +        } else if (memcmp(v->q, tstKey.prime1.data, v->q_len) || tstKey.prime1.len != v->q_len) {

Nit: 80 columns through here.

::: lib/freebl/rsa.c
@@ +386,5 @@
> +    CHECK_MPI_OK( mp_sub_d(&n_minus_one, 1, &n_minus_one) );
> +
> +    /* pick random bases a, each one has a 50% leading to a factorization */
> +    CHECK_MPI_OK( mp_set_int(&a, 2) );
> +    while (mp_cmp_int(&a, 128) <= 0) {

Should we turn 128 into a constant / #define ?

Comment 8

[Robert Relyea]

Comment on attachment 8440273 [details] [diff] [review]
RSA_PopulatePrivateKey_PKCS1_replace.patch

Review of attachment 8440273 [details] [diff] [review]:
-----------------------------------------------------------------

I have just a few places I'd like some comments added. I agree with Richard on the magic 128. I suggest a few error checks.
None of those changes I would insist on.

bob

::: lib/freebl/rsa.c
@@ +384,5 @@
> +    /* precompute n_minus_one = n - 1 */
> +    CHECK_MPI_OK( mp_copy(n, &n_minus_one) );
> +    CHECK_MPI_OK( mp_sub_d(&n_minus_one, 1, &n_minus_one) );
> +
> +    /* pick random bases a, each one has a 50% leading to a factorization */

This is basically a 'for' loop , coded as a while because we need to check the mp return code. A comment here showing the virtual for would be good:
/* for (a=2, a <= 128, a+=2) { */

@@ +386,5 @@
> +    CHECK_MPI_OK( mp_sub_d(&n_minus_one, 1, &n_minus_one) );
> +
> +    /* pick random bases a, each one has a 50% leading to a factorization */
> +    CHECK_MPI_OK( mp_set_int(&a, 2) );
> +    while (mp_cmp_int(&a, 128) <= 0) {

Yes the define should be MAX_ITERATIONS and the value here should be MAX_ITERATIONS*2.

@@ +403,5 @@
> +            /* condition 2: a^(t * 2^(i+1)) = 1 mod n */
> +            if (mp_cmp_d(&next_cand, 1) == 0) {
> +                /* conditions verified, gcd(a^(t * 2^i) - 1, n) is a factor */
> +                CHECK_MPI_OK( mp_sub_d(&cand, 1, &cand) );
> +                CHECK_MPI_OK( mp_gcd(&cand, n, p) );

My paranoia says check p != 1. The algorithm should not yeild a p==1, but the check makes it emphatic.

@@ +404,5 @@
> +            if (mp_cmp_d(&next_cand, 1) == 0) {
> +                /* conditions verified, gcd(a^(t * 2^i) - 1, n) is a factor */
> +                CHECK_MPI_OK( mp_sub_d(&cand, 1, &cand) );
> +                CHECK_MPI_OK( mp_gcd(&cand, n, p) );
> +                CHECK_MPI_OK( mp_div(n, p, q, NULL) );

I might be tempted to check the remainder == 0, but we know it has to be because the p returned as from gcd, which means p has to be a factor of n, even if p == 1. A comment to that effect would be sufficient then. A check for remainder == 0 would simple be a paranoia check of the mpi gcd function (in which case we would want to error out of the this whole function if we do this check and the gcd function fails).

Comment 9

[Martin Thomson [:mt:]]

Comment on attachment 8440273 [details] [diff] [review]
RSA_PopulatePrivateKey_PKCS1_replace.patch

Review of attachment 8440273 [details] [diff] [review]:
-----------------------------------------------------------------

Nits

::: cmd/bltest/blapitest.c
@@ +3348,5 @@
>  
> +    /* test public exponent, private exponent, modulus cases from pkcs1v15sign-vectors.txt
> +       some are valid PKCS#1 key but not valid RSA ones (de = 1 mod lcm(p − 1, q − 1)) */
> +
> +    for (int i = 0; i < sizeof(PKCS1_VECTORS)/sizeof(struct pkcs1_test_vector); ++i)

PR_ARRAY_SIZE

::: cmd/bltest/pkcs1_vectors.h
@@ +1,5 @@
> +/* This Source Code Form is subject to the terms of the Mozilla Public
> + * License, v. 2.0. If a copy of the MPL was not distributed with this
> + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
> +
> +// Vectors from pkcs1v15sign-vectors.txt

/* comment */

Comment 10

[Franziskus Kiefer [:franziskus]]

I addressed the comments, enabled the tests, and landed as
https://hg.mozilla.org/projects/nss/rev/df4ebf05c2af