On Tuesday, the NSA announced they had found a critical vulnerability in the certificate validation functionality on Windows 10 and Windows Server 2016/2019. This bug allows attackers to break the validation of trust in a wide variety of contexts, such as HTTPS and code signing. Concerned? Get the important details and see if you’re vulnerable at https://whosecurve.com/. Then come back to this tab and keep reading to see exactly what this bug is and how it works.

At a high level, this vulnerability takes advantage of the fact that Crypt32.dll fails to properly check that the elliptic curve parameters specified in a provided root certificate match those known to Microsoft. Interestingly, the vulnerability doesn’t exploit any mathematical properties unique to elliptic curves – the same exact bug could have manifested itself in a normal DSA signature verification library. So let’s first review how this bug would have worked if Crypto32.dll used normal DSA.

A toy version of the attack

The security of DSA relies on the fact that the discrete log problem is hard when dealing with the group of integers mod a prime. Consider the following equation:

b = g^x mod p

It’s hard to find x if all you know is p, g, and b. To set up DSA, users need to specify a prime p and a generator g. Using these two parameters, they can then create a private key x and public key pk = g^x mod p. These keys allow for signatures that can only be created by the private key, but can be verified with the public key. Signature forgery is then as hard as the discrete log problem (very hard).

Digital signatures algorithms such as DSA aren’t very useful on their own, though, since they don’t provide a mechanism by which users can trust a given public key associated with a specific entity. This is where X.509 certificates come into play. An X.509 cert is a file that explicitly says “this public key belongs to this person,” signed by someone else (possibly the owner of the public key in question). These certificates can be chained together, starting at a “root” certificate, attesting to the identity of a root certificate authority (CA). The root CA signs intermediate certificates to attesting the identity of intermediate CAs, the intermediate CAs sign other intermediate certificates; and so on, down to the “leaf” certificate at the end.

Each certificate contains information about the signature algorithm and parameters used. Microsoft’s certificate might look like the following (heavily simplified) example:

• Certificate authority: Microsoft
• Name: Trail of Bits
• Public key info
  • Algorithm: DSA
  • Generator: g
  • Prime: p
  • Public key: pk

When Windows users receive a X.509 certificate chain, they check to make sure the CA at its root is one that Microsoft trusts. But what happens if Windows only checks to make sure the public key of the certificate in question matches a trusted entity, not the associated system parameters? In other words, what happens when an attacker can change the value of p or g associated with a given public key pk without Windows noticing? In fact, omitting this check completely breaks the security of DSA.

One potential way to exploit this vulnerability is to simply set g = p and make the private key x = 1. This allows the attacker to sign any message as if they were the legitimate owner of pk, since they now know the private key (it’s 1). Things can get even more interesting, though: Instead of simply setting the new generator to the target’s public key, we can choose a new private key y and set the malicious generator to be g’ = y^–1 * pk. This means the certificate still effectively has a secret key, but it is known only to the attacker, not the original issuer.

Importantly, this attack works without anyone solving the discrete log problem. Essentially, if the authenticity of parameters associated with a given public key is not established, the attacker can choose any private key they want. This exploit scenario was originally outlined in 2004 by Vaudenay and referred to as a domain parameter shifting attack, but wasn’t seen in the wild until now.

The actual vulnerability

Exploiting the vulnerability in Crypt32.dll involves adapting the previous attack so that instead of using DSA, the signer is using the elliptic curve variant ECDSA. In fact, you don’t really need to know much about elliptic curves at all to understand how this works. You need only know elliptic curves are more or less mathematically equivalent to the integers mod p, except instead of multiplying numbers, you geometrically manipulate points lying on a curve. In this post, curve points are bold upper case letters and adding a point P to itself n times is written as n * P

Elliptic curves, along with point addition, create another structure in which the discrete log problem is hard. Also, like the normal DSA case, ECDSA requires choosing a set of public parameters before generating a private/public key-pair, including a generator. Usually these parameters are specified by naming a curve, such as Elliptic Curve secp256r1 (1.2.840.10045.3.1.7), but users can manually specify them instead. In that case, users must supply constants that define the elliptic curve (A,B), the prime over which arithmetic is done p, the generator of the group G, and information about that group’s size (order, cofactor). For the purposes of this attack we only care about G.

Now that we have some background on elliptic curves, it’s not hard to see that the attack works basically the same as with DSA: Change the parameters specifying ECDSA to have a generator corresponding to a private key you know, but with the same public key as the certificate authority you’re trying to spoof. By editing the parameters, we can control the effective secret key for the certificate, and use it to attest to whatever identities we’d like.

In real life, the parameter validation bypass is also slightly more involved. Microsoft does check that the parameters used in most certificates are valid, but when it is presented a root certificate it has cached, it will skip parameter validation if the certificate uses elliptic curve cryptography and the public key matches what’s cached. This means that for common root CAs, which most users will have seen, our attack is viable. In practice, this means we can generate valid TLS certificates for almost any website, bypass code signing restrictions, or forge signatures for files and emails. For explanatory purposes, let’s look at how we might man-in-the-middle https traffic to some website.

Building a fake certificate

First we need to pick a trusted root certificate. Microsoft maintains a list here. For our purposes, we picked the Microsoft EV ECC Root Certificate Authority 2017. This is a secp384r1 cert, so the public key is a point on the curve defined by the parameters given by the secp384r1 curve.

Next we need to generate a new private key for our malicious certificate, defined over a different curve, using explicit parameters. This object has a specific ASN.1 key encoding, which we generate with OpenSSL. Remember from the previous section, we want to hold the public key the same as the private one to bypass validation. Once we have the public and private keys for our new certificate, we can use them to calculate a generator such that they correspond. More precisely, we need to calculate G’ = x^-1 * P where x is our private scalar and P is the public key point from the MS certificate (this corresponds to the second attack scenario in the previous section).

Now that we have a new mutated key, we can use this to generate a CA certificate:

Once we’ve generated that certificate we can use it to sign a leaf certificate for whatever we want. This key/cert is just signed by the “bad” root – it doesn’t need custom parameters or any magic.

Finally, we ensure that we send the “full chain” as part of a TLS connection. In normal TLS you send the leaf certificate along with any intermediates, but you don’t send the root itself. In this case we need to send that root to trigger the cache bug. Voila!

Fixing the vulnerability and lessons learned

Fortunately for Microsoft, fixing this bug simply required adding a couple of checks during signature verification to make sure ECDSA parameters are authentic. Unfortunately for everyone else, this vulnerability is absolutely devastating and requires all systems running Windows 10 to be patched immediately. Until it is, attackers can forge signatures for TLS, code, files, or email.

Cryptographically, this bug is a great example of how increasing the number of parameter choices increases system fragility. We’ve known for years that explicitly specified curves (as opposed to named curves) are a bad idea, and this is yet another piece of evidence to that point. It also is a great reminder that all cryptographic information needs to be verified when handling digital signatures.

While we have not provided a PoC for this we strongly encourage people to patch since public exploit code has become available today! And we have put up a website demonstrating the flaw for anyone interested in checking whether they have an unpatched system: Go find out Whose Curve Is It Anyway?

References:

• HN speculation
• Scott’s CT bypass suggestion
• Saleem Rashid’s PoC