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.
That would make things worse because we'd make the same mistakes again. I've been on many start over projects (Xeon Phi, for example, threw out the P4 pipeline and went back to the Pentium U/V). It doesn't work. You know what the most robust project I've worked on? The instruction decoder on Intel CPUs. The validation tests go back to the late 1980's!
You make progress by building on top and fixing your mistakes because there literally IS NO OTHER WAY.
Go read about hemoglobin, its the one of the oldest genes in the genome, used by everything that uses blood to transport oxygen, and it is a GIGANTIC gene, full of redundancies. Essentially a billion years of evolution accreted one of the most robust and useful genes in our body, and there's nothing elegant about it.
I think that's where we are headed. Large systems that bulge with heft but contain so many redundant checking code that they become statistically more robust.
It really pisses me off when devs start ripping out asserts and tests that fail "But have been doing so for a while, so clearly they aren't needed."
How about... no. Review the code and determine our undefined behavior is understood well enough that we can accept the bad inputs. Those asserts & tests were created for a reason, and need to be maintained. Not just removed because no one can spot the subtle failure modes.
> You make progress by building on top and fixing your mistakes because there literally IS NO OTHER WAY.
As long as you are talking about knowledge, not artefacts. There is indeed no choice but accrete, organise, and correct knowledge over time, because anything you forget is something you might get wrong all over again.
Artefacts are different. It often makes sense to rebuild some of them from scratch, using more recent knowledge. We rarely do that, because short terms considerations usually win out (case in point: Qwerty).
> I think that's where we are headed. Large systems that bulge with heft but contain so many redundant checking code that they become statistically more robust.
Only if we give up any hope of improving performance, energy consumption, or die area. Right now the biggest gains can be found by removing cruft. See Vulkan for instance.
Most studios end up putting middleware on top of it to reduce Vulkan boilerplate to some more manageable code level, which ironically makes some Vulkan code bases run slower than OpenGL AZDO, due to misunderstandings how to do the low level work in a proper way.
Vulkan tries to remove the "bloat" of the driver by moving it into the engine (or the middleware the engine uses), which, yes, reimplements a pretty sizable chunk of what the driver used to do.
But it exposes the API in a way that requires domain-specific knowledge of how modern GPUs work, which requires, frankly, smarter engine developers. They need to stop only thinking in the ways OGL/D3D taught them to think, and need to also think like a driver developer, or possibly even a compiler developer.
OpenGL was written wrong because no one knew what modern GPUs would eventually look like, and tried to solve the problem at the wrong layer; and fixed function hardware worked pretty much the way OpenGL worked in the beginning, not realizing stuff would eventually become, basically, absolutely massive highly parallel DSP-esque math coprocessors that are more complex than the system that hosts it. OpenGL became a mess because they kept bolting newer styles of hardware onto it (VBOs/IBOs/VAOs, the eventual move to unified buffers, compute shaders, fixed function geometry then non-fixed function geometry shaders, ubershaders and the move from direct to deferred back to direct, etc)
> They need to stop only thinking in the ways OGL/D3D taught them to think, and need to also think like a driver developer, or possibly even a compiler developer.
Which is exactly the opposite than anyone that wants to draw something wants to think about.
Also Vulkan is on its merry path to have endless list of extensions, so it will eventually match OpenGL's complexity about what code paths to take, with the required cleverness of having to be a graphics programmer, driver developer and compiler developer at the same time.
No wonder anyone that wants to stay sane rather picks up a middleware engine instead.
Vulkan was never meant to be directly used by people who “just want to draw stuff”. It was meant to give engine developers the tools required to squeeze more performance out of the GPUs.
This is a case of working as designed. The people trying to directly use Vulkan in their games without any middleware layer are just generally wrong here.
Regarding extensions, this is just what happens when you specify something that keeps evolving - there’s no getting around this. What you can do to minimise the complexity is decide to require certain extensions once they’ve been around for long enough. That’s what everyone does.
It would help if Khronos would promote an API for people who “just want to draw stuff”, given that OpenGL 5.0 will never happen most likely and those people don't want to be stuck with OpenGL 4.6 forever.
That is not what everyone does, because Vulkan gets new extensions updates almost every week.
> It would help if Khronos would promote an API for people who “just want to draw stuff”
Would it?
What you really want is a stable API to talk to the hardware. It doesn't really matter if the API is nigh unusable, as long as it is stable. Only when such stability is reached, can we reliably build stuff on top of it. Including a "just draw stuff" engine.
We could for instance re-implement Flash on top of Vulkan. Such a thing wouldn't need a standard body to get done and be usable by a wide range of people. (Though in this particular case, we'd likely have some standard body involved anyway, since there's already so much Flash code out there.)
You implement OpenGL as a middleware that speaks Vulkan.
Basically, ANGLE it, but for desktop OpenGL instead of GLES.
As an aside, Google is adding a Vulkan backend for ANGLE, and Microsoft seems to be adding a DX12 (which is basically DXVulkan) backend (to match the DX11 backend they gave Google) at some point in the future.
So, GLES, in its entirety, is now a community supported, open source, Vulkan middleware. No reason why we can't do that with desktop GL too.
So 10 years from now those that don't want to be a mix of graphical developer, driver author and compiler designers, have to keep using a frozen API from 2018, without any access to whatever has changed on their computers during the next decade.
All because providing something like MetalKit or DirectXTK is too much to ask for to Khronos and LunarG.
But should it change? There are issues where updating OpenGL support in drivers broke earlier apps due to accidental changes in how existing features were implemented.
Vulkan and DX12 are far less likely to break existing apps i the future due to far fewer core features.
It makes no sense to have what is essentially an entire legacy middleware in the driver when it no longer represents modern hardware.
Unlike GLES, OpenGL basically can never deprecate features, and D3D9 support will never, truly, die. It's a lot easier to just package a universal shim into existing legacy apps than it is to keep mangling drivers over the issue.
> It makes no sense to have what is essentially an entire legacy middleware in the driver when it no longer represents modern hardware.
Exactly, but it is the only API that Khronos is offering for those that don't want to be Vulkan experts.
Which leaves middleware engines, something totally unrelated to Khronos APIs, as the only future proof path for accessing GPU features on modern hardware.
As for drivers breaking down, the main reason why Vulkan is now compulsory on Android as of version 10, is because while it was optional, the few OEMs that bothered to support it did a very lousy job, so Google hopes by making it compulsory and part of Android CTS, the situation will improve.
> Vulkan and DX12 are far less likely to break existing apps i the future due to far fewer core features.
This is questionable. Vulkan by definition has basically no error checking in the driver, and while developers are supposed to use the validation layer, they may not do so, and even if they do, there are certain plenty of incorrect things an application can do that won't be caught by validation.
Incorrect programs may still happen to run correctly on existing drivers, but then fail with a driver update that happens to change the undefined behavior.
C compiler writers have answered that conundrum a long time ago: "if you (even accidentally) rely on undefined behaviour, the warranty is void".
I don't necessarily agree, but if we have a way to avoid undefined behaviour (and at least in C there are ways to make pretty thorough checks), then it works in practice.
It won't, unless only a fairly small elite ends up using Vulkan. And I believe that's what will happen indeed: Vulkan is low level enough that most likely, only engine devs and middleware devs will touch it.
You will of course have the occasional cowboy (which I personally am, though in a different domain), but that shouldn't matter that much in the grand scheme of things.
Now if you ask me, Vulkan is not enough. What we really want is a stable, usable hardware interface. Basically an ISA. The thing will have close to zero bug, because hardware folks know how to properly test their designs. Undefined behaviour is likely unavoidable, but I believe it can be reduced to a reasonable minimum.
If AMD and NVidia started something like RISC-V, except for graphics cards, it will likely have a greater impact than RISC-V itself.
> That LoadLibrary call is ugly but it makes the code work on old versions of Windows 95.
with the proper code comments for the hair (in the code or in the source repo) and regression tests it becomes possible to clean up and even rewrite.
floppy disks are no longer a thing and neither is windows 95. RAM & swap space are abundant, so that OOM may never happen any more IRL.
the app's whole architecture may have been carefully chosen for the hardware and simplistic compilers of another age.
is it okay never to rewrite a webpage where 50% of the codebase is IE6 hacks?
if it is code that must be maintained, then at some point the hair may need to be shaved; it simply cannot grow forever as the world moves on around it. the doma of "never rewrite" is silly without further context.
>if it is code that must be maintained, then at some point the hair may need to be shaved; it simply cannot grow forever as the world moves on around it. the doma of "never rewrite" is silly without further context.
"Shaving" seems more close to refactoring & partial rewrite than starting from scratch. Which is what we are talking about.
Still, You make good points. Maybe, we should think of "restarting from scratch" the same way we do premature optimization - (1. don't do it. 2. Don't do it too early. 3. if you must do, measure first)
I think every developer dreams of rewriting from scratch because they hate how hacky and ugly their code is probably due to rushed deadlines and because it was just supposed to be an mvp. And they think about throwing it away and starting clean and doing it the 'proper way'. This imo is the wrong reason to start from scratch.
But if your technical debt is genuinely preventing your product from going where it needs to go or do its job. That is the right reason. Again you have to make the calculation whether the technical debt is greater than the cost of rewriting from scratch, re-opening old bugs and introducing new ones, breaking your customers workflow - they also invested a lot into your old program. How many times have you liked a program until 'the damn devs went and ruined a good thing' by 'fixing what wasn't broken'. Again, customers don't see or care about the code or technical debt. They just need to get their work done.
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.
Most people implementing ECC signatures are going to end up only handling a chosen group of named curves whereupon there aren't any curve parameters to check.
For example in Signal IIRC they use Curve25519. So there isn't any code about parsing or checking parameters, it's just here's some code that implements Curve25519.
NSS (the library used in Firefox on every platform) only accepts NIST's P-256 and P-384 named curves. It is parsing an ASN.1 data structure which can have parameters for curves, but if parameters are present instead of a name NSS's code gives up immediately because it's only looking for those specific names. (These aren't actually human readable names, they are OIDs such as 1.2.840.10045.3.1.7 for curve P-256)
> cryptographic agility seems to cause more issues than the problems it solves,
Is that so? The ability to shift to new hash functions and ciphers within the bounds of a single protocol seems to have accelerated the adoption of better primitives.
We don't need the ability to switch to new algorithms as much as we need the ability to ditch old ones. Agility in cryptography only needs to mean the ability to deprecate what's broken. We're still going to see newer and more robust algorithms implemented in new software and protocol versions anyway.
What we need is 1 or 2 strong cipher suites and exactly zero weak ones, not 10 strong ones and 5 weak ones.
How is that not cryptographic agility? Which cipher suites to support is a question separate from whether the cryptography should be runtime configurable at all.
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.
EdDSA can have something close. Long story short, an EdDSA signature has two parts, often called "R" and "s". Verification works by producing a number using the public key and "s", then checking that this number is the same as "R". There are basically 3 steps:
Steps 1 and 3 are straightforward (the hash and the constant time comparison are almost always implemented in dedicated routines, tested separately). Step 2 is the most dangerous (that's where the elliptic curve magic happens).
EdDSA Implementations would be easier to check against one another if they all exposed step 2 as part of the public API. Bonus points if step 2 can handle invalid inputs (low order point, point on the twist...) in a standard manner. I haven't seen such a thing though, probably because end users never need a separate step 2.
Still, I can already envision the benefits. I'll probably use it myself.
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.
> If we can't even get crypto libraries right (where you'd hope most of the formal verification folks are)
Personally, I'd hope most of the formal verification folks are working in firmware for industrial/medical embedded systems, and/or the microcontroller designs that go into those same systems. A lack of encryption (outside of military contexts) doesn't usually directly cause people to die.
Hmm. Maybe I'll generate some high quality OTPs for myself with a good CSPRNG. I could use any decent block cipher in counter mode, just need to guard against counter re-use, and then ship my OTPs off to anyone I need to communicate with.
Hang on, if I could come up with a way of securely sharing the key I used with my recipient, I wouldn't need to actually mail the OTP to them, since they could generate it themselves. Should probably include a nonce too.
Now, if only there were a secure method to share the key...
> Now, if only there were a secure method to share the key...
... that doesn't include a critical cryptographic vulnerability. :)
To be generous to the now greyed GP, there's probably a way to teach a recipient a short pad and its proper use so that the recipient can later decode a short ciphertext sent over Twitter. Perhaps even performing that feat in their head. None of the cryptography that could fit your quip has that property.
And if the recipient does something catastrophic like resend the pad over Twitter to confirm they memorized it correctly, there's at least a chance they may catch their error. Perhaps they may even correct it without the goddamned Department of Defense coming into it.
I don't get cryptographers' condescension toward OTP zealots. All they want is a better boat. At least have the decency of the captain from Titanic and apologize while we sink for not having delivered it.
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.
This attack is similar in nature to some JWT implementations' bug where you could pass "no-encryption" as encryption scheme to use, effectively rendering the whole scheme open to any arbitrary payload which will pass validation; in this case you can pass arbitrary G, which effectivley allows you to generate (private key, G) pair for any public key so you can inpersonate as any identity with it, right?
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.)
My guess is somebody at Microsoft responded to a customer need or claimed customer need to support specifiedCurve arguing that it was OK so long as said curve was a standard curve. I just don't see why you wouldn't stop at "PKIX forbids this, let's just not implement it" otherwise.
There probably aren't any such certificates out in the Web PKI because Mozilla's rules prohibit them (and almost as important Firefox won't validate them). But Microsoft trusts a whole bunch of dubious kinda sorta wanna be Certificate Authorities, maybe one of those issued crap with specifiedCurve for a standard curve ? Or maybe a corporate internal CA?
That's a test somebody can do: If you use a Microsoft internal CA can you easily mint these stupid specifiedCurve certificates with it? Or does it make you pick a named curve and emit the OID properly? How about other popular private CA solutions? EJBCA maybe?
Who on earth has a corporate internal CA that issues certificates signed on non-standard curves? Who would ever do that? It's not like you're just a couple parameters away from Curve25519; a serious alternative curve will always come with alternative curve code.
Curve25519 was only introduced in 2005, so it's entirely plausible that MS had a customer prior to that with the attitude "we don't trust those NSA curves, we'd rather use our own" (though whether those customers would choose to use the MS crypto library is another question...)
In the scenario I'm describing specifiedCurve is NOT being used to sign with non-standard curves, it's being used to sign with the standard curves but expressed using specifiedCurve anyway.
As a crypto/ security person your instinct is to say "No" because if something is more complicated but adds no apparent benefit that's a problem. That's why PKIX says "No" here, and it's why Mozilla policy says "No" here. But for a Microsoft sales person trying to land a large deal before the quarter ends the instinctive answer is "Yes" unless one of the technical people can explain why it's inherently unsafe.
This is how Microsoft ends up supporting six different bad ways to do something in Windows - not because they're lousy engineers but because they are willing to do what it takes to make the sale. Of course specifically in security arguably that does make them lousy engineers.
The worst part about such requirements is that they can often turn out to be bogus. One technical person pastes in a description of NIST's P-256 with all the curve details and a game of telephone results in the idea that they want to use specifiedCurve when actually they'll use a named curve because duh, of course they will. But if nobody says "No" the specifiedCurve feature gets backed into a requirements document and actioned.
I have had non-security "requirements" that I pushed back on and six transatlantic conference calls later I'm talking to the person who supposedly "had" the requirement and they go "I have no idea how this got made into a requirement, we don't need this at all" and a bunch of work vanishes instantly. But I do that sort of thing because I'm stubborn, it might well be easier and faster (and more profitable) to just fulfil the unnecessary requirement.
It's not even that: the AlgorithmIdentifier structure in the SubjectPublicKeyInfo is allowed to contain parameters, the one in the Signature should not. This is arguably a spec bug.
There's even a timely question about this to m.d.s.policy as a result of a Mozilla policy revision which spells out byte-by-byte what a conformant AlgorithmIdentifier looks like:
This gave Ryan a chance to point people at Adam Langley's wise observation that you should not parse things like signatures when you can instead calculate the entire value you expected and then just binary compare - anything that doesn't match is wrong and you needn't care why.
The mitigation should be to remove all code that supports custom elliptic curves. This is a misfeature, it shouldn't exist. I also don't think anyone uses it for real.
This stems from a time where people thought maximum flexibility in cryptography is a good idea. It's not.
So this explains the math and crypto part, but how does that tie into X.509 and certificates?
From what I understand we can put custom parameters into a certificate, but the parameters come with the key, not the signature.
So we have
CA cert + key A + parameters A
signs
My cert + key B + parameters B + forged signature from A
Now we can only mount this attack if we can somehow control a part of the parameters (the basepoint) that is used to verify the forged signature. Is the bug that windows is using parameters B to verify signature from A? Or am I missing something and there is another way to supply parameters with a signature?
From what I read, x.509 allows the signer to specify the curve parameters along with the signature.
And yes, the bug here would be that Windows accepted parameters B without confirming they match A, it only checked that the public key was the same.
So you have official and trusted root / intermediate cert C1 which contains pubkey 1 and parameters A, which uses privkey 1 (secret obviously).
When signing it doesn't usually specify parameters (just gets it from the trusted cert), the leaf certificate just contain the reference to the trusted cert and its public key and of course also contains the actual signature.
In the attack you reuse pubkey 1 but create parameters B and associated privkey 2, and using that you create a leaf cert that contain both the same references that an official signature would contain - except you also specify parameters B, and then supply the signature that validates only under parameters B, and then Windows accepts both the parameters and the signature.
It seems the parameter block is all part of "Subject Public Key Info". The signature is just a binary blob at the bottom. But openssl doesn't really break that down, does this signature have its internal encoding that allows supplying additional parameters?
And if that's the case: How does that make any sense? It sounds like just asking for trouble. (I mean... there never can be a situation where the parameters of the signature do not match the parameters of the key.)
The parent comment is wondering about the structure of the signature and if different curve parameters can be specified for it. How can explicit curve parameters be specified in an ECDSA signature? ecdsaWithSHA256, at least, is simply two bigints. There's no spot for specifying explicit parameters.
Subject Public Key Info is just an Algorithm Identifier and the public key. The Algorithm Identifier is an OID and the parameters (ECParameters when using EC keys). It's these parameters that can contain the custom EC domain parameters.
The certificate signature is preceded by another Algorithm Identifier that specifies the signature algorithm (and the parameters), and so it seems that Microsoft is using this value instead of the parameters in the signer certificate Subject Public Key Info?
AIUI it's a root cert trust issue. You supply your own self-signed root cert, which obviously lets you specify your own parameters and build a fully valid chain of trust. Then the bug is that the library considers the root cert trusted if its public key hash and serial match that of a cert in the root trust store, even if the curve parameters don't.
Here is a sage script that implements the described attack. I have scripts that implement curve parameters separately (so I can load them into other scripts as needed) so this might look a little redundant in places:
#!/usr/bin/env sage
nistp256r1_order = 0xFFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551
nistp256r1_modulus = 2**224 * (2**32 - 1) + 2**192 + 2**96 - 1
nistp256r1_a = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC
nistp256r1_b = 0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B
nistp256r1_field = GF(nistp256r1_modulus)
nistp256r1 = EllipticCurve(nistp256r1_field, [0,0,0,nistp256r1_a,nistp256r1_b])
nistp256r1_base_x = 0x6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296
nistp256r1_base_y = 0x4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5
nistp256r1_gen = nistp256r1(nistp256r1_base_x, nistp256r1_base_y, 1)
curve = nistp256r1
curve_order = nistp256r1_order
curve_gen = nistp256r1_gen
CG = Zmod(curve_order)
### these are "inputs" to the system. Only pubkey is known to an attacker
privkey = CG.random_element()
Q = curve(ZZ(privkey) * curve_gen)
### The attacker generates the necessary malicious generator
kprime = CG.random_element()
kprimeinv = kprime.inverse_of_unit()
Gprime = ZZ(kprimeinv) * Q
### We can now verify that the attacker knows a private key corresponding
### to the public key under their generator
Qprime = curve(ZZ(kprime) * Gprime)
print("Q==Q'", Qprime == Q)
print(Qprime.xy())
print(Q.xy())
### So if the attacker believes Gprime is a correct generator,
### this is bad news.
### you can implement something relying on it, with Gprime as your generator, here.
This is using real secp256r1, i.e. NIST P256, parameters. You can try this in sagemath's online tools and see that it works very efficiently. inverse_of_unit is a nice function that computes the inverse of kprime in the multiplicative group modulo the prime order of the curve. You can do exactly the same thing with the XGCD algorithm from sage.arith.misc. ZZ is required simply for type conversion: sage doesn't understand how to multiply a point by a Zmod element. We help it out by converting to an integer. .xy() is not required, it simply prints affine, instead of projective, coordinates. I wrote this with sage 9, which is based on python 3. The 0,0,0 are not necessary for the elliptic curve constructor (two parameters = short weierstrass) but I'm in the habit...
As a corollary to Lagrange's theorem, any prime order group is cyclic, which means any randomly chosen point is a generator and since the group of curve points under elliptic curve point addition is of prime order, any randomly chosen point on the curve necessarily generates the whole group. However, we need to choose a random secret key to relate the old generator to the new, because solving G' = k'Q is a discrete logarithm problem and we can't solve those.
P256 is obviously quite difficult for humans to deal with in their minds, so if you want to play with a more human-sized curve, try:
E=EllipticCurve(GF(17),[3,5])
which is of prime order and has 23 points (and so cofactor 1 like P256).
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).