Closed Bug 1057161 Opened 5 years ago Closed 5 years ago

NSS hangs with 100% CPU on invalid EC key

Categories

(NSS :: Libraries, defect, P1)

defect

Tracking

(firefox-esr31 wontfix)

RESOLVED FIXED
3.17.2
Tracking Status
firefox-esr31 --- wontfix

People

(Reporter: rbarnes, Assigned: rbarnes)

References

Details

(Keywords: csectype-dos, sec-other)

Attachments

(8 files, 4 obsolete files)

Attached file infinitude.c
Once again, a copy/paste error in a WebCrypto test case exposes an NSS issue :)

If you construct a SECKEYPublicKey containing coordinates for a point that is not on the curve, then NSS will hang and go to 100% CPU.  The attached test program triggers the bug on my machine.

Poking around a bit with the debugger, it looks like the infinite loop is somewhere in mpi.c.  In the attached stack trace, points in the code indicated above the line seem to recur an indefinite number of times, while points below only a small (but non-constant) number of times.  Which leads me to believe the problem is something to do with this succinctly specified loop:

> for (;;)

http://dxr.mozilla.org/mozilla-central/source/security/nss/lib/freebl/mpi/mpi.c#2074

In any case, the solution is probably for EC_ValidatePublicKey to be called at the right point, either at key creation time or at the time of ECDSA operation (or ECDH, presumably).

For WebCrypto, whence this bug arises, we will have a need to create keys directly, outside of NSS.  So my preference would be to either solve it in the ECDSA method, or expose a method in the PK11 interface that would validate the key.
Attached file stack trace
Richard, any reason to believe that this is worse than a DoS? We'd like to give it a security rating.
Flags: needinfo?(rlb)
I don't have any reason to believe it's worse than DoS.  It just appears that the MPI code spins endlessly, not that it enters some indeterminate state.  So ISTM that it merits a pretty low security rating.
Flags: needinfo?(rlb)
Attached file ca_cert.pem
Attached file ca_cert_bad.pem
Attached file server_cert.pem
Attached file server_key.pem
I tried and failed to replicate this with TLS/PKIX.  I created the attached cert chain, with root certificate containing an ECDSA public key used to sign an EE certificate.  In ca_cert.pem, the key is as generated by OpenSSL.  In ca_cert_bad.pem, I replaced the low-order 128 bits of the Y coordinate with random data (uuidgen).  This should almost certainly (p=2^-128) have resulted in a point not on the curve.

Experiment 1: Good chain
1. Import ca_cert.pem into the Nightly root store
2. openssl s_server -accept 8888 -CAfile ca_cert.pem -key server_key.pem -cert server_cert.pem
3. Open https://localhost:8888

Result 1: Wireshark confirms both certificates presented in handshake (root and EE). Nightly connects normally, does HTTPS (with me typing in HTTP/1.1 in the terminal).


Experiment 2: Bad chain
1. Import ca_cert_bad.pem into the Nightly root store
2. openssl s_server -accept 8888 -CAfile ca_cert_bad.pem -key server_key.pem -cert server_cert.pem
3. Open https://localhost:8888

Result 2: Wireshark confirms both certificates presented in handshake (root and EE).  Nightly fails with sec_error_bad_signature.

So there's something in the way the PKIX verification is importing the ECDSA public key and invoking ECDSA verification such that the process fails cleanly instead of hanging.  The comparable NSS invocation is here:
http://dxr.mozilla.org/mozilla-central/source/security/pkix/lib/pkixnss.cpp#143

The primary differences are (1) the key is created by importing SPKI, and (2) verification is done in a single call to VFY_VerifyDataDirect(), rather than using the multi-stage API.  I guess the next step in figuring this out is to see if making the same changes in infinitude.c results in the hang not happening.
We don't need to use the more restrictive component-specific security groups unless a bug is sec-high or sec-critical
Group: crypto-core-security → core-security
If this is essentially a DOS does it need to remain hidden?
Group: core-security
Attached patch bug-1057161.patch (obsolete) — Splinter Review
Wan-Teh: This patch proposes to fix this bug by checking the key before performing an ECDSA verify operation.  Two main questions:

1. Does this approach seem OK to you?  On the one hand, it might be papering over a problem in the underlying math library.  On the other hand, it might be perfectly reasonable for some EC algorithm to not terminate on a non-curve point.

2. Are there other EC operations where this fix might be necessary?  I didn't apply it to ECDSA signature, because that shouldn't be using a public key. ECDH seems to be covered, at least for non-cofactor derivation.  Maybe we should remove the conditional validation here?

Thanks!
Assignee: nobody → rlb
Status: NEW → ASSIGNED
Attachment #8483775 - Flags: feedback?(wtc)
Also: I have verified that the above test file (infinitude.c) successfully terminates with a signature validation failure when linked against NSS with this patch.  (Rather than looping endlessly.)


(In reply to Richard Barnes [:rbarnes] from comment #11)
> Created attachment 8483775 [details] [diff] [review]
> bug-1057161.patch
> 
> Wan-Teh: This patch proposes to fix this bug by checking the key before
> performing an ECDSA verify operation.  Two main questions:
> 
> 1. Does this approach seem OK to you?  On the one hand, it might be papering
> over a problem in the underlying math library.  On the other hand, it might
> be perfectly reasonable for some EC algorithm to not terminate on a
> non-curve point.
> 
> 2. Are there other EC operations where this fix might be necessary?  I
> didn't apply it to ECDSA signature, because that shouldn't be using a public
> key. ECDH seems to be covered, at least for non-cofactor derivation.  Maybe
> we should remove the conditional validation here?
> 
> Thanks!
Comment on attachment 8483775 [details] [diff] [review]
bug-1057161.patch

We discussed this on the NSS call today.  In addition to validating the EC public key at ECDSA time, we should check it when EC keys are created in softoken, mainly:
* sftk_handlePublicKeyObject
* seckey_ExtractPublicKey

Those are all the places I see right now where new SECKEYPublicKey objects are minted from untrusted data.  There might be others that I'm missing.
Attachment #8483775 - Flags: feedback?(wtc)
Attached file infinitude-spki.c
This test program demonstrates that the flaw can be triggered using an SPKI-decoded key as well.
Comment on attachment 8483775 [details] [diff] [review]
bug-1057161.patch

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

Richard,

This is a reasonable solution, but I agree with the conclusion
reached in the NSS conference call that it's better to validate
the public key at key import time.

Bob Relyea is the best person to review changes to nss/lib/softoken.

::: lib/softoken/pkcs11c.c
@@ +2278,5 @@
>      SECItem signature, digest;
>      NSSLOWKEYPublicKey *key = (NSSLOWKEYPublicKey *)ctx;
>  
> +    // Verify that the public key actually represents a valid curve point
> +    if (EC_ValidatePublicKey(&(key->u.ec.ecParams), &(key->u.ec.publicValue)) 

Nit: omit the parentheses after '&'. This kind of expression (taking
the address of a struct member) is very common in C code.
Attached patch bug-1057161.1.patch (obsolete) — Splinter Review
Ok, this patch addresses all three cases called out above (ECDSA verify, sftk_handlePublicKeyObject, seckey_ExtractPublicKey).  It compiles, but unfortunately doesn't link.   

> Undefined symbols for architecture i386:
>  "_EC_DecodeParams", referenced from:
>      _seckey_ExtractPublicKey in seckey.o
>  "_EC_ValidatePublicKey", referenced from:
>      _seckey_ExtractPublicKey in seckey.o

Bob: Does this approach look OK to you?  Any suggestions on how to resolve the linking errors?
Attachment #8483775 - Attachment is obsolete: true
Attachment #8484614 - Flags: feedback?(rrelyea)
seckey is not allowed to call those freebl functions. Only softoken is.
So, a more concrete solution for the SECKEY case is to create a pubkey object and try to import it, then see if you got a CRV.

I don't think that is necessarily a responsibility of the SECKEY interface (which is opaque to these issues of point validity), but you'd have to create a new PKCS#11 object, which force validation to occur (for any/all public key types). For inherited DSA attributes (*snerk*), that'd be hard to represent at SECKEY, which is why I don't think this conceptually belongs there.
Attached patch bug-1057161.2.patch (obsolete) — Splinter Review
(In reply to Ryan Sleevi from comment #18)
> So, a more concrete solution for the SECKEY case is to create a pubkey
> object and try to import it, then see if you got a CRV.

And even more concretely: PK11_ImportPublicKey() and check for CK_INVALID_HANDLE.  I could live with that, even though it means that it's incumbent on the application using SECKEY to do that check if it wants to fail at import time.

I'm a little more split on whether this would let us get away with not doing the check at verification time.  On the one hand, it seems safe, since the only way to provide a key to softoken is for it to come through sftk_handlePublicKeyObject.  On the other hand, if there's any other route to ECDSA_VerifyDigest, then there could be trouble.  For now, I've removed the check at verify time, and add a comment to ECDSA_VerifyDigest.

This patch does just two things, then:
1. Add the comment to ECDSA_VerifyDigest
2. Add the check to sftk_handlePublicKeyObject
Attachment #8484614 - Attachment is obsolete: true
Attachment #8484614 - Flags: feedback?(rrelyea)
Attachment #8485537 - Flags: review?(rrelyea)
Comment on attachment 8485537 [details] [diff] [review]
bug-1057161.2.patch

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

r+ rrelyea
Attachment #8485537 - Flags: review?(rrelyea) → review+
Flags: needinfo?(martin.thomson)
Status: ASSIGNED → RESOLVED
Closed: 5 years ago
Resolution: --- → FIXED
Are you aware that you should watch http://test.nss-crypto.org after checking in to NSS?

All platforms report failure after your checkin. Can you please back out, and make sure you get successful local testing, prior to landing an updated patch?
backed out because tests failed on all platforms.
https://hg.mozilla.org/projects/nss/rev/70ae6afde27f
Status: RESOLVED → REOPENED
Resolution: FIXED → ---
Attached patch bug-1057161.3.patch (obsolete) — Splinter Review
(Carrying forward r+ from rrelyea)

This patch should address the test failures that Kai noticed (and I should have).  I had missed that the CKA_EC_POINT attribute on an EC public key object is sometimes DER encoded.  With this patch, all tests pass on my local system except for one network issue that I think is just a problem with my test setup.
Attachment #8485537 - Attachment is obsolete: true
Attachment #8492785 - Flags: review+
Comment on attachment 8492785 [details] [diff] [review]
bug-1057161.3.patch

Bob, could you please give this a quick re-review?  The reason tests were failing is that I didn't take into account that NSS allows both encoded and decoded points, depending on an environment variable: 
http://dxr.mozilla.org/mozilla-central/source/security/nss/lib/pk11wrap/pk11akey.c#172

(I would also be happy to get rid of that "feature", but that's a separate bug.)
Attachment #8492785 - Flags: review+ → review?(rrelyea)
We do need to deal with both encoded and decoded points, but we shouldn't use an environment variable for the decode case. We should autodetect. There is code in pkcs11c.c (sftk_GetPubKey()) to do this. It's a little bit tricky because the first byte of a decoded point which is the point type (uncompressed, compressed) is the same value as the first byte of the encoded point (ASN1_OCTET), so we need to look at the point length.

if (crv == CKR_OK) {
            int keyLen,curveLen;

            curveLen = (pubKey->u.ec.ecParams.fieldID.size +7)/8;
            keyLen = (2*curveLen)+1;

            /* special note: We can't just use the first byte to determine
             * between these 2 cases because both EC_POINT_FORM_UNCOMPRESSED
             * and SEC_ASN1_OCTET_STRING are 0x04 */

            /* handle the non-DER encoded case (UNCOMPRESSED only) */
            if (pubKey->u.ec.publicValue.data[0] == EC_POINT_FORM_UNCOMPRESSED
                && pubKey->u.ec.publicValue.len == keyLen) {
                break; /* key was not DER encoded, no need to unwrap */
            }

            /* if we ever support compressed, handle it here */

            /* handle the encoded case */
            if ((pubKey->u.ec.publicValue.data[0] == SEC_ASN1_OCTET_STRING)
                && pubKey->u.ec.publicValue.len > keyLen) {
                SECItem publicValue;
                SECStatus rv;

                rv = SEC_QuickDERDecodeItem(arena, &publicValue,
                                         SEC_ASN1_GET(SEC_OctetStringTemplate),
                                         &pubKey->u.ec.publicValue);
                /* nope, didn't decode correctly */
                if ((rv != SECSuccess)
                    || (publicValue.data[0] != EC_POINT_FORM_UNCOMPRESSED)
                    || (publicValue.len != keyLen)) {
                    crv = CKR_ATTRIBUTE_VALUE_INVALID;
                    break;
                }
                /* replace our previous with the decoded key */
                pubKey->u.ec.publicValue = publicValue;
                break;
            }
           crv = CKR_ATTRIBUTE_VALUE_INVALID;
        }

bob
Actually, given that sftk_handlePublicKeyObject already uses sftk_GetPubKey, we don't need to replicate all that effort.  We can just use the ECPublicKey that it stores in the object.
Attachment #8492785 - Attachment is obsolete: true
Attachment #8492785 - Flags: review?(rrelyea)
Attachment #8497529 - Flags: review?(rrelyea)
Comment on attachment 8497529 [details] [diff] [review]
bug-1057161.4.patch

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

r+ good solution Richard.

bob
Attachment #8497529 - Flags: review?(rrelyea) → review+
kaie: This is looking pretty much green on the build bot.  (Modulo some red that's not due to this patch.)  What do we need to do to move it over to mozilla-central?
Flags: needinfo?(kaie)
Blocks: 1034854
Because the fix has landed into NSS, this bug can be marked fixed.

In addition I just landed an NSS beta into mozilla inbound (see bug 1075686).
Status: REOPENED → RESOLVED
Closed: 5 years ago5 years ago
Flags: needinfo?(kaie)
Resolution: --- → FIXED
Target Milestone: --- → 3.17.2
OS: Mac OS X → All
Priority: -- → P1
Hardware: x86 → All
Thanks to Wan-Teh for noticing that a C++ style comment has landed into NSS.
Checked in the fix:
https://hg.mozilla.org/projects/nss/rev/fb8925f6648d
Also checked in to the NSS_3_16_2_BRANCH
https://hg.mozilla.org/projects/nss/rev/dc27c7658628
to be released as part of 3.16.2.3
You need to log in before you can comment on or make changes to this bug.