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.

Richard, any reason to believe that this is worse than a DoS? We'd like to give it a security rating.

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.

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

If this is essentially a DOS does it need to remain hidden?

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!

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.

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.

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?

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.

(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

Comment on attachment 8485537 [details] [diff] [review] bug-1057161.2.patch Review of attachment 8485537 [details] [diff] [review]: ----------------------------------------------------------------- r+ rrelyea

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

(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.

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.)

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.

Comment on attachment 8497529 [details] [diff] [review] bug-1057161.4.patch Review of attachment 8497529 [details] [diff] [review]: ----------------------------------------------------------------- r+ good solution Richard. bob

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?

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).

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