Patch Critical Cryptographic Vulnerability in Microsoft Windows [pdf]
From a conversation with Thomas Pornin, a plausible explanation given the details provided in the DoD advisory:<p>Given an ECDSA signature and control over the curve domain parameters, it&#x27;s straightforward to create a second private key that matches the original public key, without knowledge of the original signing private key. Here&#x27;s how:<p>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<p><pre><code>    y^2 = x^3 + ax + b mod p
</code></pre>
The &quot;curve&quot; 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.<p>To use that curve for cryptography, we standardize a base point G, which generates all the points we&#x27;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&#x27;s part of the standard.<p>Assume that we have a signature validator in CryptoAPI that allows us to specify our own nonstandard base point. We&#x27;re ready to specify the attack; it&#x27;s just algebra:<p>Let&#x27;s call Q the public key corresponding to the signature; for instance, Q could be the ECC public key corresponding to an intermediate CA.<p>Q is a point on a named curve (like P-256). Q = xG for some private key x; we don&#x27;t, and won&#x27;t ever, know x. G is the standard generator point for (say) P-256.<p>What we&#x27;ll do is define a &quot;new curve&quot;, which is exactly P-256, but with a new generator point. We&#x27;ll generate our own random private key --- call it x&#x27; --- and then from that random private key compute a malicious generator G&#x27; = (1&#x2F;x&#x27;)*Q.<p>On our &quot;new curve&quot;, 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&#x27; = x&#x27;G&#x27;, and we know x&#x27;.<p>Now we sign a fake EE certificate with our evil private key x&#x27;. 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&#x27;ve tricked Windows into believing the private key corresponding to Q is x&#x27;, a key we know, and not x, the key we don&#x27;t know.<p>I&#x27;m paraphrasing a shorter writeup Pornin provided, and the basic curve explanation is mine and not his, so if I&#x27;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&#x27;d hope that the actual details of the attack are subtle and clever, and not as simple as &quot;anyone could have specified their own base point straightforwardly at any time&quot;.<p>See also this related exercise in Sean Devlin&#x27;s Cryptopals Set 8:<p><a href="https:&#x2F;&#x2F;toadstyle.org&#x2F;cryptopals&#x2F;61.txt" rel="nofollow">https:&#x2F;&#x2F;toadstyle.org&#x2F;cryptopals&#x2F;61.txt</a><p>This attack --- related but not identical to what we suspect today&#x27;s announcement is --- broke an earlier version of ACME (the LetsEncrypt protocol).