Win10 Crypto Vulnerability: Cheating in Elliptic Curve Billiards 2
Yesterday, Microsoft has released a security update for Windows which includes a fix to a dangerous bug that would allow an attacker to spoof a certificate, making it look like it came from a trusted source. The vulnerability (CVE-2020–0601) was reported to Microsoft by the NSA.
The root cause of this vulnerability is a flawed implementation of the Elliptic Curve Cryptography (ECC) within Microsoft’s code.
As it often does, understanding this vulnerability is a perfect opportunity to learn how stuff really works. To do so, we would use the same “Load Bearing” Billiards analogy we used to explain another ECC vulnerability in the past.
Elliptic Curve Cryptography as a Billiards Game
Following Cloudflare’s Nick Sullivan blog’s terminology, Elliptic Curve Cryptography (ECC) can be described as a bizzaro Billiards game.
The Elliptic Curve described with the equation y² = x³+ ax + b is our Billiards table.
Adding two points on the curve, A and B, is our Billiards shot. To add A and B, place the ball at point A and shoot it towards point B. When it hits the curve, the ball bounces either straight up (if it’s below the x-axis) or straight down (if it’s above the x-axis) to the other side of the curve and this is the result C.
But what happens when you want to “double” a point, i.e. add a Point to itself (A+A). How can you shoot a ball from A towards A itself?
To do so, let’s choose point A’ very close to A and shot towards it. As we bring A’ closer and closer to A, the connecting line between them gets closer to the Tangent of A.
Now that we learned the basic moves, let’s define the rules of the game. The first player Alice plays alone in the room. The game begins when the ball is placed on a known point G (called generator or base point), and Alice can arbitrarily choose how many times (denoted as d) to successively shoot towards the same Point G. When Alice is done and the ball is on point Q, Eve enters the room and tries to guess how many times the ball was struck. It turns out that the only way for Eve to discover that number d is by replaying the game shot after shot until the table reaches the same state. However, Alice that knows in advance the number of times she intends to strike, can efficiently know the final state of the board without actually taking all these shots. Therefore this game achieves the desired cryptography “trapdoor” property: Easy to do, hard to undo.
Signing with ECC
Using some more formal and mathematical terms, d is called the private key, while Q is called the public key. Calculating Q = d×G over Elliptic Curves is easy. However, given Q and G it’s hard to determine d.
Using this “trapdoor” property of the game, a digital signature scheme can be implemented. A digital signature on a message can prove the message was indeed generated by the holder of the private key.
To do so, the signer Alice generates a private and public key pair (d, Q) as described above and sends only the public key to verifier Bob. When Alice wants to sign a message m (caution: way-over-simplified, apologies in advance to all crypto gods, for actual signatures, see below) she multiplies it with her private key, so the signature s is something like s=m×d and sends the signature and the message to Bob. Bob can now verify by multiplying s with G and making sure it is the same outcome as multiplying the message directly with the public key Q that he already knows, i.e. s×G = m×d×G = m×Q.
[The actual ECDSA (Elliptic Curve Digital Signing Algorithm) equations are R = k×G, s = (h(m)+r⋅d)/k where k is a random number and the full process is explained below
]
As a result, Bob was able to verify that the message was indeed generated by Alice based only on public data. This is how a browser verifies a HTTPS site. The site serves a certificate with a public key and digitally signs a part of the communications to prove it has access to the corresponding private key.
The Vulnerability
We had seen that it is hard for Eve that is only shown the final ball position Q, to know how many times (d) the ball was struck and this hardness enables us to securely digitally sign messages.
But this only true if the game referee verifies that the game begins with known base-point G. If Eve is allowed to choose any starting point, then it is almost intuitive that the ECC billiards game becomes very easy. Specifically, Eve can just arbitrarily strike the ball d’ times from an arbitrary point G’= Q/d’. Note, that with this new base-point, Eve now has a new private key d’ that corresponds to the original public key Q, i.e Q = d×G but also Q = d’×G’ = d’×Q/d’=Q. This means that if Bob doesn’t validate he is using the right base-point G, Eve can digitally sign on behalf of Alice!
In fact, if Eve is very audacious, she can claim the ball has not moved at all, and the final ball position Q is also the initial position G’, i.e. G’=Q and d’=1 such that Q = d’×G’ = 1×Q=Q !
According to Thomas Ptacek, this was exactly the problem within Microsoft code. The vulnerable code verified certificates even if they specified their own G’ and not just standard curves, for example, “Elliptic Curve secp256r1 (1.2.840.10045.3.1.7)”, as shown in Google’s certificate above. This may enable attackers to specify such parameters in their certificate and sign on behalf of others to masquerade as different sites over the web, distribute falsely signed software updates and other shenanigans.
The NSA advisory warns against such certificates: “Certificates containing explicitly-defined elliptic curve parameters which only partially match a standard curve are suspicious, especially if they include the public key for a trusted certificate, and may represent bona fide exploitation attempts.”
And indeed an analysis of the Microsoft fix revealed it added a check for the parameters
Final thoughts
Implementing cryptography is hard and even subtle mistakes might get heavily punished. Implementations need to be scrutinized to make sure they are indeed adhering to best practices. That is the main reason for us in ZenGo to open source our cryptography algorithms implementations and have them audited.
On the other hand, understanding attacks against implementation can help builders gain a better understanding not only of correct implementation but also of how stuff actually works.
Enjoy your ECC Billiards!
And please don’t forget to patch your vulnerable Windows machines!
Update January 20, 2020: published a follow up story shedding light on additional elements required for the attack
and added the degenerate case ( G’=Q and d’=1) example
Update February 3, 2020: published a follow up story on CurveBall exploits detection
