Closed Bug 1021102 Opened 6 years ago Closed 6 years ago

NSS_3_16_2_BETA3 causes mochitest-2 failures in test_WebCrypto.html

Categories

(NSS :: Libraries, defect, P1, major)

3.16.2

Tracking

(firefox31 unaffected, firefox32 fixed, firefox33 fixed, b2g-v2.0 fixed, b2g-v2.1 fixed)

RESOLVED FIXED
3.16.2
Tracking Status
firefox31 --- unaffected
firefox32 --- fixed
firefox33 --- fixed
b2g-v2.0 --- fixed
b2g-v2.1 --- fixed

People

(Reporter: wtc, Assigned: rbarnes)

Details

Attachments

(4 files, 6 obsolete files)

3.92 KB, patch
Details | Diff | Splinter Review
995 bytes, patch
rbarnes
: review+
ryan.sleevi
: superreview+
Details | Diff | Splinter Review
2.97 KB, patch
wtc
: review+
Details | Diff | Splinter Review
2.91 KB, text/x-python-script
Details
Richard: could you please help us track down these mochitest-2 failures in
test_WebCrypto.html after the NSS_3_16_2_BETA3 update?

The mozilla-inbound changeset for the NSS_3_16_2_BETA3 update is:
https://hg.mozilla.org/integration/mozilla-inbound/rev/189492a9a115

It caused mochitest-2 failures in test_WebCrypto.html:
https://tbpl.mozilla.org/php/getParsedLog.php?id=41119166&tree=Mozilla-Inbound
https://tbpl.mozilla.org/php/getParsedLog.php?id=41119060&tree=Mozilla-Inbound

The update has been backed out. You should be able to apply the NSS
update as a patch. Alternatively, the instructions for updating NSS
to a static tag are at
https://developer.mozilla.org/en-US/docs/Updating_NSPR_or_NSS_in_mozilla-central

The relevant NSS changes should be these two changes of Ryan's:

Bug 1016836 - Make RSA_PrivateKeyCheck robust against 'bad' (empty) parameters.
https://hg.mozilla.org/projects/nss/rev/7dc83fd04549

Bug 1016811 - Ensure softoken performs RSA consistency checks for private keys
https://hg.mozilla.org/projects/nss/rev/3b3baf9909f2

It should be easy for someone who knows how to run mochitest to
determine whether the bug is in the tests or in one of Ryan's
changes. Thanks for your help!
Richard:

If you apply https://hg.mozilla.org/integration/mozilla-inbound/rev/189492a9a115
as a patch, please exclude the CLOBBER change. Just remove libnss3.so or libnss3.dylib
in your build tree. There may be multiple copies. Remove them all.
Taking a look at this now.  Thanks for the CLOBBER tip, but it turns out that something in moz-central required a CLOBBER anyway :)  Oh well, time for a coffee...
Attached patch nss-1021102.patch (obsolete) — Splinter Review
This patch does two things: (1) Fix the test vector (copy/paste error from the RSA text file), and (2) Add some printfs to note when things go wrong with the private key.

I'm posting this intermediate solution because it might highlight an issue with Ryan's patch.

What I see when I run the RSAES-PKCS1-v1_5 tests with this patch is as follows:

> Error in SECKEY_CopyPrivateKey: [ffffe002]
>
> Key::SetPrivateKey: [21e94020] -> [00000000]

So it looks like PK11_ImportDERPrivateKeyInfoAndReturnKey successfully returns a SECKEYPublicKey*, but when we call SECKEY_CopyPrivateKey on this key, it returns NULL and sets SEC_ERROR_BAD_DATA.  Any thoughts on how this could arise?
Flags: needinfo?(ryan.sleevi)
Comment on attachment 8435979 [details] [diff] [review]
nss-1021102.patch

Richard: your patch is empty. Please regenerate it. Thanks.
Attached patch nss-1021102.patch (obsolete) — Splinter Review
Attachment #8435979 - Attachment is obsolete: true
Sorry, posted.  I'm working on reproducing this as a pure NSS bug.
Comment on attachment 8436055 [details] [diff] [review]
nss-1021102.patch

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

::: dom/crypto/Key.cpp
@@ +231,5 @@
>    if (!aPrivateKey || isAlreadyShutDown()) {
>      mPrivateKey = nullptr;
>      return;
>    }
>    mPrivateKey = SECKEY_CopyPrivateKey(aPrivateKey);

I guess |aPrivateKey| is a manually constructed SECKEYPrivateKey,
rather than a SECKEYPrivateKey created by NSS? Otherwise it is
strange that SECKEY_CopyPrivateKey can't copy a key that it created.
Attached patch bug-1021102-nss-only.patch (obsolete) — Splinter Review
Ok, this looks to be an NSS issue, not a WebCrypto issue.  This patch to NSS creates a small test case that reproduces the WebCrypto failure, but using only NSS.
Richard, thank you for the NSS test program.

This is a strange bug. It is caused by the following.

1. https://hg.mozilla.org/projects/nss/rev/3b3baf9909f2
added a RSA_PrivateKeyCheck call.

2. RSA_PrivateKeyCheck may swap the prime1 and prime2,
and the exponent1 and exponent2 members of the input
RSAPrivateKey.

3. The caller of RSA_PrivateKeyCheck calls sftk_forceAttribute
on the members of RSAPrivateKey modified by RSA_PrivateKeyCheck.
The SFTKAttribute pointers in question all point to SFTKAttribute
objects in a hash table, so the sftk_forceAttribute directly
modifies the SFTKAttribute objects in the hash table.

Since RSA_PrivateKeyCheck does a "shallow" swap of SECItem objects,
we end up with a problem similar to:
  unsigned char prime1[64];
  unsigned char prime2[64];

  // Force update CKA_PRIME1, with the original value of CKA_PRIME2
  memcpy(prime1, prime2, 64);
  // Force update CKA_PRIME2, with the original value of CKA_PRIME1
  memcpy(prime2, prime1, 64);

(I grossly simplified the problem. The actual damage caused by
pointer aliasing in sftk_forceAttribute is quite complicated
and may be worse than what my simplified example suggests.)

Possible fixes:

1. Change RSA_PrivateKeyCheck to not mutate its input RSAPrivateKey.
This patch does this.

2. Change RSA_PrivateKeyCheck to do a "deep" swap of SECItem members.
This will require allocating new buffer spaces from the arena of the
RSAPrivateKey.

3. Audit the callers of sftk_forceAttribute to ensure they don't pass
another SFTKAttribute value from the hash table as the source of the
new value. I haven't fully understand the code to know the exact scope
of this approach. But it seems that after each sftk_forceAttribute call,
the attribute->attrib.pValue pointer may change, so if we use a saved
copy of the old attribute->attrib.pValue pointer, that may be a
use-after-free error.
Attachment #8436378 - Flags: superreview?(rrelyea)
Attachment #8436378 - Flags: review?(ryan.sleevi)
Comment on attachment 8436378 [details] [diff] [review]
Fix 1: RSA_PrivateKeyCheck should not swap the prime1 and prime2, and exponent1 and exponent2 members of the input RSAPrivateKey

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

So, an r+ in spirit, but more like an r?

I agree, RSA_PrivateKeyCheck shouldn't be mutating the underlying structure. You're absolutely correct that there can be issues when it does - this is part of what led me to the defensive attempts at crash-proofing (for cases where CRT wasn't filled in). So I think it's r+ for the change, but I think Bob will need to weigh-in on this further.

I do think it's weird that we'd let the key pass when p < q. I don't see anything (spec wise) that would seem to assert the requirement in RSAPrivateKey or PKCS#11, so I think your change is probably more spec compliant, but Bob may know if there are 'hidden' bugs that may be tickled out if we allow such keys in w/o mutating.

That said, we've been allowing these keys in for a long time (by never checking), so maybe it's OK.
Attachment #8436378 - Flags: review?(ryan.sleevi) → review+
Regardless of how NSS gets fixed, this PKCS#8 structure needs to be corrected.  Right now, the "qi" value has the primes in the wrong order (it's p^-1 mod (q-1) instead of q^-1 mod (p-1).
Attachment #8436055 - Attachment is obsolete: true
Attachment #8436114 - Attachment is obsolete: true
Richard: How did you get the test vectors? More PKCS test vector data? And your description of qi doesn't match A.1.2 of RFC 3447 / 6.3.2.5 of JWA - that coefficient / qi is "q^(-1) mod p"

Note also "Note 1" of Section 3.2

"The definition of the CRT coefficients here and the formulas that
      use them in the primitives in Section 5 generally follow Garner's
      algorithm [22] (see also Algorithm 14.71 in [37]). However, for
      compatibility with the representations of RSA private keys in PKCS
      #1 v2.0 and previous versions, the roles of p and q are reversed
      compared to the rest of the primes.  Thus, the first CRT
      coefficient, qInv, is defined as the inverse of q mod p, rather
      than as the inverse of R_1 mod r_2, i.e., of p mod q."

If your key stored q in prime1, then I would expect that both exponent1 and coefficient are incorrect. I can't find anything within 3447, at least, that dictates the relationship between p and q, other than p = r_1 and q = r_2

Perhaps this is something that needs to be explicitly handled when importing RSAPrivateKey. I would also suspect that if this reading is correct, than JWA either needs to explicitly describe itself as compatible with PKCS#1, or explicitly describe itself as more restrictive. Absent clarification, I would expect it to adhere to RFC 3447 - and thus be liberal in encoding.
Flags: needinfo?(ryan.sleevi)
(In reply to Ryan Sleevi from comment #12)
> Richard: How did you get the test vectors? More PKCS test vector data? And
> your description of qi doesn't match A.1.2 of RFC 3447 / 6.3.2.5 of JWA -
> that coefficient / qi is "q^(-1) mod p"

The values in the test vector are from the RSA test suite, as noted in the source
<ftp://ftp.rsa.com/pub/rsalabs/tmp/pkcs1v15crypt-vectors.txt>

The PKCS#8 I assembled myself, which is the origin of the error.  The definition for qi above is just a typo on my part. 


> Note also "Note 1" of Section 3.2
> 
> "The definition of the CRT coefficients here and the formulas that
>       use them in the primitives in Section 5 generally follow Garner's
>       algorithm [22] (see also Algorithm 14.71 in [37]). However, for
>       compatibility with the representations of RSA private keys in PKCS
>       #1 v2.0 and previous versions, the roles of p and q are reversed
>       compared to the rest of the primes.  Thus, the first CRT
>       coefficient, qInv, is defined as the inverse of q mod p, rather
>       than as the inverse of R_1 mod r_2, i.e., of p mod q."
> 
> If your key stored q in prime1, then I would expect that both exponent1 and
> coefficient are incorrect. I can't find anything within 3447, at least, that
> dictates the relationship between p and q, other than p = r_1 and q = r_2
> 
> Perhaps this is something that needs to be explicitly handled when importing
> RSAPrivateKey. I would also suspect that if this reading is correct, than
> JWA either needs to explicitly describe itself as compatible with PKCS#1, or
> explicitly describe itself as more restrictive. Absent clarification, I
> would expect it to adhere to RFC 3447 - and thus be liberal in encoding.

It seems to me that the comments in the definition of the RSAPrivateKey data structure are pretty clear on this.  The first prime is p, the second is q, and qi is q^{-1} mod p == prime2^{-1} mod prime1.  That should align with RSA_PrivateKeyCheck, assuming that the primes in the RSAPrivateKey are in the same order as in the PKCS#1 structure, which seems to be the case. 

>      RSAPrivateKey ::= SEQUENCE {
>          version           Version,
>          modulus           INTEGER,  -- n
>          publicExponent    INTEGER,  -- e
>          privateExponent   INTEGER,  -- d
>          prime1            INTEGER,  -- p
>          prime2            INTEGER,  -- q
>          exponent1         INTEGER,  -- d mod (p-1)
>          exponent2         INTEGER,  -- d mod (q-1)
>          coefficient       INTEGER,  -- (inverse of q) mod p
>          otherPrimeInfos   OtherPrimeInfos OPTIONAL
>      }

If you want to be a little generous, you could always test the coefficient both ways, and replace it with the one that aligns with the ordering of the primes (rather than swapping the primes).  Based on Wan-Teh's description, it sounds like that could be done with less peril than swapping the primes.
I missed a change to rsa.c in the previous version of this patch.
Patch checked in: https://hg.mozilla.org/projects/nss/rev/ce26341fb3b7
Attachment #8436378 - Attachment is obsolete: true
Attachment #8436378 - Flags: superreview?(rrelyea)
Attachment #8437295 - Flags: review?(rrelyea)
Attachment #8437295 - Flags: checked-in+
Comment on attachment 8437295 [details] [diff] [review]
Fix 1: RSA_PrivateKeyCheck should not swap the prime1 and prime2, and exponent1 and exponent2 members of the input RSAPrivateKey, v2

Richard:

My try build with this NSS patch still fails in test_WebCrypto.html:

https://tbpl.mozilla.org/?tree=Try&rev=b91966c4e513

Do you know why?  Thanks.
Did you apply the Firefox patch I posted above?  It fixes the test case, and it's not in mozilla-central yet.  (Setting checkin-needed now...)
Keywords: checkin-needed
Richard:

I didn't apply the Firefox patch you posted. I don't understand
why we still need to fix the test case if we already fixed NSS.

I submitted a new try build with the Firefox patch you posted.
Here are the try server results:
https://tbpl.mozilla.org/?tree=Try&rev=36fc0d5756f2

There is still one test failure in test_WebCrypto.html:

1304 INFO TEST-UNEXPECTED-FAIL | /tests/dom/crypto/test/test_WebCrypto.html | RSAES-PKCS#1 encrypt/decrypt round-trip
1305 INFO TEST-UNEXPECTED-FAIL | /tests/dom/crypto/test/test_WebCrypto.html | Test timed out.
Comment on attachment 8436578 [details] [diff] [review]
Fix 2: Correct test vector for RSAES-PKCS1-v1_5

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

r=wtc.
Attachment #8436578 - Flags: review+
Ryan pointed out that if RSA_PrivateKeyCheck doesn't require p > q
or swap struct members to make that true, we may allow an RSAPrivateKey
with an invalid 'coefficient' member that will fail when we do a
private key operation using CRT. So this patch enforces p > q.
Attachment #8438795 - Flags: superreview?(ryan.sleevi)
Attachment #8438795 - Flags: review?(rlb)
I now know a bit more about the test failures, but I still don't
fully understand the problem. One of us really needs to get to the
bottom of this. Richard, I'm afraid that you are in the best
position to do this.

The following results all assume my "Fix 1" patch for NSS has been
applied.

1. Without Richard's patch for dom/crypto/test/test-vectors.js,
"RSAES-PKCS#1 encrypt/decrypt round-trip" fails. In addition,
"RSAES-PKCS#1 decryption known answer" hangs (reported as "pending"
on the test page) badly, so that the subsequent tests are not
run.

2. With Richard's patch for dom/crypto/test/test-vectors.js applied,
"RSAES-PKCS#1 encrypt/decrypt round-trip" still fails.
"RSAES-PKCS#1 decryption known answer" still hangs, but the
subsequent tests get to run (and pass).

3. This patch allows "RSAES-PKCS#1 encrypt/decrypt round-trip" and
"RSAES-PKCS#1 decryption known answer" to pass. This patch makes
NSS swap p and q (temporarily) when it performs RSA private key
operation using the Chinese Remainder Theorem, matching what
RSA_PrivateKeyCheck does.
Attachment #8439513 - Flags: superreview?(ryan.sleevi)
Attachment #8439513 - Flags: review?(rlb)
Flags: needinfo?(rlb)
Everything now in the same order as in the RSA file.
Attachment #8436578 - Attachment is obsolete: true
Flags: needinfo?(rlb)
Attached file test-vectors.py
Python script to generate test vectors for PKCS#8 ordering sensitivity.
Attachment #8438795 - Flags: review?(rlb) → review+
Comment on attachment 8439513 [details] [diff] [review]
Make rsa_PrivateKeyOpCRTNoCheck swap p and q temporarily

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

::: security/nss/lib/freebl/rsa.c
@@ +931,5 @@
>      SECITEM_TO_MPINT(key->coefficient, &qInv); /* qInv = q**-1 mod p */
> +    if (mp_cmp(&p, &q) <= 0) {
> +	/* mind the p's and q's (and d_p's and d_q's) */
> +	mp_exch(&p, &q);
> +	mp_exch(&d_p,&d_q);

Is it possible that qInv is actually the inverse of q mod p, before the switch?  If so, then it seems like this would cause the result to be incorrect, since qInv will not be the inverse of the new q.  So it seems like you should check here q*qinv == 1 mod p, and fail if not.
Attachment #8439513 - Flags: review?(rlb) → review-
Comment on attachment 8438795 [details] [diff] [review]
RSA_PrivateKeyCheck should require p > q

Patch checked in: https://hg.mozilla.org/projects/nss/rev/8da5fd3ea88d

Let's be strict unless our tests show other major implementations accept
such RSA private keys.
Attachment #8438795 - Flags: checked-in+
Comment on attachment 8439513 [details] [diff] [review]
Make rsa_PrivateKeyOpCRTNoCheck swap p and q temporarily

Marked this patch obsolete. This patch is only worth considering
if RSA_PrivateKeyCheck does the same thing.
Attachment #8439513 - Attachment is obsolete: true
Attachment #8439513 - Flags: superreview?(ryan.sleevi)
Comment on attachment 8439513 [details] [diff] [review]
Make rsa_PrivateKeyOpCRTNoCheck swap p and q temporarily

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

r-

We should never get to this point, and we shouldn't be trying to fix it up.

As discussed on today's call, Richard was going to fix the test data structure to ensure that prime_1 = p, prime_2 = q, coefficient = prime_2^-1 mod prime_1 , which, as Bob noted, means that p > q.
Attachment #8439513 - Attachment is obsolete: false
Attachment #8439513 - Attachment is obsolete: true
Comment on attachment 8439528 [details] [diff] [review]
Fix 2: Correct test vector for RSAES-PKCS1-v1_5

r=wtc.
Attachment #8439528 - Flags: review+
Comment on attachment 8439528 [details] [diff] [review]
Fix 2: Correct test vector for RSAES-PKCS1-v1_5

Pushed to mozilla-inbound: https://hg.mozilla.org/integration/mozilla-inbound/rev/bf14fea1179c
Attachment #8439528 - Flags: checked-in+
I now fully understand this bug. Nothing else needs to be done.

The reason Richard's old RSAES-PKCS1-v1_5 test vector worked with
the old NSS is that 'coefficient' had the correct value with respect
to 'prime1' and 'prime2' in the test vector, and RSA private key
operation with CRT doesn't care which prime is 'prime1'.

So we just need to watch out for RSA private key import failure
due to prime1 <= prime2.
Keywords: checkin-needed
https://hg.mozilla.org/mozilla-central/rev/bf14fea1179c
Status: ASSIGNED → RESOLVED
Closed: 6 years ago
Resolution: --- → FIXED
Landed the WebCrypto test fix on Aurora along with the NSS 3.16.2 uplift.
https://hg.mozilla.org/releases/mozilla-aurora/rev/9475b48d42e8
Attachment #8438795 - Flags: superreview?(ryan.sleevi) → superreview+
Attachment #8437295 - Flags: review?(rrelyea)
You need to log in before you can comment on or make changes to this bug.