From a conversation with Thomas Pornin, a plausible explanation given the details provided in the DoD advisory:
Given an ECDSA signature and control over the curve domain parameters, it's straightforward to create a second private key that matches the original public key, without knowledge of the original signing private key. Here's how:
To start with, you need to understand a little bit about how curve cryptography works. A curve point is simply the solution to an equation like
y^2 = x^3 + ax + b mod p
The "curve" itself consists of the parameters a, b, and p; for instance, in P-256, a is -3, b is (ee35 3fca 5428 a930 0d4a ba75 4a44 c00f dfec 0c9a e4b1 a180 3075 ed96 7b7b b73f), and p is 2^256 - 2^224 + 2^192 + 2^96 - 1.
To use that curve for cryptography, we standardize a base point G, which generates all the points we'll use. A private key in ECC is simply a scalar number k mod p; the public key corresponding to that private key is kG (the curve scalar multiplication of the point G times our secret k). Everybody using P-256 uses the same base point; it's part of the standard.
Assume that we have a signature validator in CryptoAPI that allows us to specify our own nonstandard base point. We're ready to specify the attack; it's just algebra:
Let's call Q the public key corresponding to the signature; for instance, Q could be the ECC public key corresponding to an intermediate CA.
Q is a point on a named curve (like P-256). Q = xG for some private key x; we don't, and won't ever, know x. G is the standard generator point for (say) P-256.
What we'll do is define a "new curve", which is exactly P-256, but with a new generator point. We'll generate our own random private key --- call it x' --- and then from that random private key compute a malicious generator G' = (1/x')*Q.
On our "new curve", Q remains a valid point (in fact, our evil curve is the same curve as P-256, just with a different generator), but now Q' = x'G', and we know x'.
Now we sign a fake EE certificate with our evil private key x'. Presumably, Windows is just looking at the public key value and, reading between the lines of the DoD advisory, the curve equation, but not the base point. By swapping base points, we've tricked Windows into believing the private key corresponding to Q is x', a key we know, and not x, the key we don't know.
I'm paraphrasing a shorter writeup Pornin provided, and the basic curve explanation is mine and not his, so if I've worded any of this poorly, blame me and not Thomas Pornin. The actual exploit-development details of the attack will involve figuring out in what circumstances attackers can swap in their own base point; you'd hope that the actual details of the attack are subtle and clever, and not as simple as "anyone could have specified their own base point straightforwardly at any time".
See also this related exercise in Sean Devlin's Cryptopals Set 8:
I hope that the actual vulnerability is far more complicated. If we can't even get crypto libraries right (where you'd hope most of the formal verification folks are), then there's not much hope of security for the rest of the industry.
I'm normally not much of a pessimist but things like this really make me wish we could just burn all the things and start over.
This stuff often looks simpler and less subtle in hindsight.
Modern cryptography has gotten better at taking human (developer) error into account for designing secure API’s, but the fact of the matter is that the math is subtle, and cryptography in general is subtle due to the places where it collides with reality, so burning everything down and starting over is likely to just cause us to rediscover issues we already know about.
Say we stop using X509 certificates. We will continue to use signing to cryptographically bind claims, and we will still use PKI-like structures to attest trustworthiness, so we are still vulnerable to the same approaches of attacks even if we don’t use certificates.
We have actually learned a few things, such as that cryptographic agility seems to cause more issues than the problems it solves, so the field is improving in important ways, but if it’s not a key matching weakness, it’s going to be some Unicode encoding BS or some other critical but not validated data somewhere else, or... (because this is a real in the wild problem) using phone numbers to generate cryptographic keys for coin wallets.
This is true, but the bug here is not subtle. It would have been shocking to discover an ECC implementation that let attackers specify curve parameters even 10-15 years ago. When we blogged the e=3 debacle back in '07 or whatever, we linked to a Kaliski presentation from 1999 that called out validating curve parameters.
At least with the ACME vulnerability, there was a novel service model involved. Here, we're talking about certificates that allow you to embed what is in effect your own cryptographic algorithm to interpret the certificate under!
This is a rare instance where I'm happy to concede that closed source allowed a terrible bug to survive far longer than it would have if nobody needed to break out a copy of Ghidra to read the code that validated elliptic curve signatures.
There's a history of vulnerabilities like these, in some of the most important crypto libraries. For instance: until 2008, NSS, the TLS library used by Firefox, couldn't properly validate RSA signatures from e=3 RSA keys (it wasn't validating the full signature block, but rather parsing it and looking for the embedded hash). For e=3 roots, which were readily available at the time, you could simply build any signature block you wanted and then take its cube root.
There have been crypto vulnerabilities in Windows libraries before, but not the e=3 vulnerability; CryptoAPI parsed RSA signatures back-to-front, and so sidestepped the issue.
Signature verification is one of the hardest things to get right. One reason is, they're harder to test: when you encrypt or hash something, you have a whole bunch of bits you can check against test vectors. With signature verifications, you only have one bit: it's a match, or it's a fail.
Moreover, it's very easy to forget to check something (here, that we are using the same base point). Other constructions, like EdDSA, are simpler, and verification requires a single equality check. Harder to botch.
And even then, implementers can be tempted to get clever, which requires extra care. I've personally been bitten by not verifying mathematical jargon, and mistakenly thought "birational equivalence" was complicated speak for "bijection". Almost, but not quite. This single oversight lead to a critical, easy to find, easy to exploit vulnerability.
We found out 15 months later, 1 full year after public release, by tinkering with the tests. A cryptographer would have found it in 5 minutes, but as far as I can tell, they're all very busy.
That’s an interesting assessment. Rogaway just gave a talk at RWC about APIs for secret splitting schemes. IIRC he said that the API needed to be closer to what symmetric crypto was. But from the diagram it seemed like you were obtaining some associated data back to check that the secret was correct (not sure if this would work/is relevant with more recent DKG schemes).
A signature verification returning an actual AD would be interesting as well.
So the mitigation would be to add a check that the generator point in (for example) a CertificateVerify message is the one in the p256 spec (or otherwise the one on the cert, I’m not deep enough to know where it usually lives)?
In practice this means rejecting the "specifiedCurve" choice in ASN.1 ECParameters. ASN.1-based protocols are the only ones I'm aware of that permit specifying an arbitrary curve. For the PKIX ASN.1 standard(s) old-style EC public keys are specified with an ECParameters field:
PKIX, which is what TLS and most other standards use for ASN.1 message grammars, already mandates that "implicitCurve and specifiedCurve MUST NOT be used". See https://tools.ietf.org/html/rfc5480#section-2.1.1 (There are many other related RFCs. It gets very confusing, especially once you take into account obsolete and draft RFCs.)
Newer curves, like EdDSA curves, are always each specified with unique OIDs and have a simpler public key grammar. See https://tools.ietf.org/html/rfc8410 Older public curves share an OID and a more generic ("flexible") syntax, thus the ECParameters field. (RSA public keys also have a parameters field, but it's unused. However, annoyingly, some implementations omit the field altogether, others set a NULL value.)
https://eprint.iacr.org/2019/779 - Paper on the fun things you can do with signatures, including a write up of the Let's Encrypt Attack discovered in 2015 and some more recent attacks.
Given an ECDSA signature and control over the curve domain parameters, it's straightforward to create a second private key that matches the original public key, without knowledge of the original signing private key. Here's how:
To start with, you need to understand a little bit about how curve cryptography works. A curve point is simply the solution to an equation like
The "curve" itself consists of the parameters a, b, and p; for instance, in P-256, a is -3, b is (ee35 3fca 5428 a930 0d4a ba75 4a44 c00f dfec 0c9a e4b1 a180 3075 ed96 7b7b b73f), and p is 2^256 - 2^224 + 2^192 + 2^96 - 1.To use that curve for cryptography, we standardize a base point G, which generates all the points we'll use. A private key in ECC is simply a scalar number k mod p; the public key corresponding to that private key is kG (the curve scalar multiplication of the point G times our secret k). Everybody using P-256 uses the same base point; it's part of the standard.
Assume that we have a signature validator in CryptoAPI that allows us to specify our own nonstandard base point. We're ready to specify the attack; it's just algebra:
Let's call Q the public key corresponding to the signature; for instance, Q could be the ECC public key corresponding to an intermediate CA.
Q is a point on a named curve (like P-256). Q = xG for some private key x; we don't, and won't ever, know x. G is the standard generator point for (say) P-256.
What we'll do is define a "new curve", which is exactly P-256, but with a new generator point. We'll generate our own random private key --- call it x' --- and then from that random private key compute a malicious generator G' = (1/x')*Q.
On our "new curve", Q remains a valid point (in fact, our evil curve is the same curve as P-256, just with a different generator), but now Q' = x'G', and we know x'.
Now we sign a fake EE certificate with our evil private key x'. Presumably, Windows is just looking at the public key value and, reading between the lines of the DoD advisory, the curve equation, but not the base point. By swapping base points, we've tricked Windows into believing the private key corresponding to Q is x', a key we know, and not x, the key we don't know.
I'm paraphrasing a shorter writeup Pornin provided, and the basic curve explanation is mine and not his, so if I've worded any of this poorly, blame me and not Thomas Pornin. The actual exploit-development details of the attack will involve figuring out in what circumstances attackers can swap in their own base point; you'd hope that the actual details of the attack are subtle and clever, and not as simple as "anyone could have specified their own base point straightforwardly at any time".
See also this related exercise in Sean Devlin's Cryptopals Set 8:
https://toadstyle.org/cryptopals/61.txt
This attack --- related but not identical to what we suspect today's announcement is --- broke an earlier version of ACME (the LetsEncrypt protocol).