ZenGo
Published in

ZenGo

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.

Previously in “Cheating in Elliptic Curve Billiards”

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.

A Schematic Elliptic Curve Plot (source: CloudFlare)

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.

Adding Two Points. A+B = C, C+A=D, A+D=E (source: CloudFlare)

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.

Doubling the Point P on Curve E: Shooting in the Tangent’s direction (Source: SlideShare)

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.

Google.com certificate specifies algorithm, parameters and public 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 !

The degenerate exploit: Q=G’ , d=1

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 potential impact of the vulnerability

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

The analysis of Microsoft patch: public key parameters checks are added

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

--

--

--

A blog on ZenGo, wallets, security, and cryptography

Recommended from Medium

MeowSwap Feature Release: Liquidity Pools

Net Deposit Competition — DEPOSIT and MAINTAIN ZIG into the Zignaly Vault & WIN up to 500,000 ZIG…

Why Capital Gains Tax does NOT work for Cryptocurrency

40 Tried And True Methods To Become “BAGHOLDER” In 2020

3rd November — $THOR uncapped launch on THORChain

The Ideal Digital Currency (Part 4 of 7): Digital Currencies Need to be Easier to Use

Weekly Market Report March 3rd

ENVELOP receives investment from Animoca Brands to build a protocol providing vault and oracle…

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Tal Be'ery

Tal Be'ery

All things CyberSecurity. Security Research Manager. Co-Founder @ZenGo (KZen). Formerly, VP of Research @ Aorato acquired by @Microsoft ( MicrosoftATA)

More from Medium

Homomorphic Encryption v Trusted Execution Environment for Privacy in Blockchain

Fixed income in DeFi

Signature Hash Flags

The Ones in the Arena: Maple Finance

A gigantic wolf stomps, Godzilla-like, through a city with surreal, pancake-stack buildings and mountains in the distance. The wolf is breathing fire and carries a carafe of syrup in one paw, and a fork spearing a slice of bacon in the other. Basquiat-style spikes run down its back, and line its mouth with pointy teeth.