Exploiting the Windows CryptoAPI Vulnerability

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. If you want to stop reading here, get the important details, and see if you’re vulnerable, check out  https://whosecurve.com/. Once you’ve done that, come back to this tab and keep reading for an explainer of exactly what this bug is and how it works.

Why even patch if it doesn’t have a logo? https://whosecurve.com

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. Therefore, to avoid getting into the weeds of elliptic curve cryptography, let’s first go over how this bug would have worked if Crypto32.dll used normal DSA.

A toy version of the attack

Recall that 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. In other words, if we have 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 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 do not provide a mechanism by which users can trust a given public key is associated with a specific entity. This is where X.509 certificates come into play. An X.509 cert is basically 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 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. An example Microsoft certificate might look something like the following (N.B.: this is heavily simplified):

• 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? It turns out omitting this check completely breaks the security of DSA.

One potential way to exploit this vulnerability is to simply set g = p and have the private key be x = 1 . This allows the attacker to sign any message as if they were the legitimate owner of  pk , since they know now 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 choose a new private key  y and set the malicious generator to be g’ = y ^{– 1} * pk . This means the certificate still has what is effectively a secret key, but it is known only to the attacker, not the original issuer.

Importantly, this attack works without anyone being able to solve the discrete log problem, it really just boils down to the fact that not establishing the authenticity of parameters associated with a given public key lets the attacker choose any private key they want. This exploit scenario was originally outlined in 2004 by Vaudenay , 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 to the case where instead of 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 – the only relevant details are that 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 n * P

Fig 1. The diagram you’ve seen a million times showing elliptic curve addition

Elliptic curves, along with point addition, create another structure where the discrete log problem is hard. Also similar to 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 specified by naming a curve, such as Elliptic Curve secp256r1 (1.2.840.10045.3.1.7), but users can alternatively manually specify them. 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 really 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 at some point before, 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, let’s pick 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.

Fig 2. A trusted certificate with public key

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 to bypass validation. Once we have the public and private key for our new certificate, we can use these 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:

Fig 3: A parsed view of our bad root

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.

Fig 4: A cert for whosecurve.com

Now the final step is to 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!

Fig 5. Not a real TLS certificate

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) were 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 as public exploit code has become available today! We have, however, put up a website demonstrating the flaw for anyone interested in checking to see if 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

*** This is a Security Bloggers Network syndicated blog from Trail of Bits Blog authored byBen Perez. Read the original post at: https://blog.trailofbits.com/2020/01/16/exploiting-the-windows-cryptoapi-vulnerability/