This post presents results from our paper “Pseudorandom Black Swans: Cache Attacks on CTR_DRBG”. We illustrate how omissions in the threat model of a U.S government’s standard lead to a practical, end-to-end attack on the most popular generator contained within. It is based on work by Andrew Kwong, Shahar Paz, Daniel Genkin, Nadia Heninger, Eyal Ronen, Yuval Yarom and myself.
Pseudo-random number generators (PRGs) are super important for cryptography. They are algorithms that take a small amount of unpredictable data (entropy) and mix it with an internal secret state to produce a longer stream of random bits. Cryptographers use PRGs to generate cryptographic keys and other secret values. These algorithms are therefore critically important to many cryptosystems.
The primary criterion for PRG security is that an attacker should not be able to tell the difference between output from the PRG and truly random bytes. A prediction resistant PRG also ensures that if the secret state is compromised, an attacker should not be able to distinguish later outputs from random (after the PRG has had time to recover). This guarantees that an attacker can’t predict outputs and potentially recover cryptographic secrets. For a PRG to be prediction resistant, it is necessary (but not sufficient) for it to ingest additional entropy to refresh its state, allowing it to recover from compromise.
One of the most commonly used PRGs is CTR_DRBG, a design standardized in NIST Special Publication (SP) 800 90A. SP 800 90A is the standard that sets out how a product must generate pseudorandom bits if it is to be sold to or used in U.S government systems. Given the importance of sales to the U.S government, and widespread respect for NIST, standards like this are broadly adopted by implementers.
At the core of CTR_DRBG is AES in counter mode. The PRG encrypts the counter and uses the result as its pseduorandom output. While making a theoretically secure PRG out of a block-cipher is a typical exercise presented in Cryptography 101, the invertibility of such ciphers can cause trouble in practice. An attacker may be able to compromise prediction resistance if they can figure out the key to the cipher and brute force any entropy that the PRG uses to update its state.
A trivial example of the problem with block cipher constructions is the DUHK attack, in which a number of ANSI X9.31 PRG implementations relied on a single hard-coded key, and added insufficient entropy during the state update process. This allowed myself, Nadia Heninger and Matthew Green to break the design and passively decrypt VPN traffic secured by keys generated from the PRG.
CTR_DRBG’s problems are more subtle. Joanne Woodage and Dan Shumow noticed that under certain circumstances, CTR_DRBG may generate a lot of output before it updates the AES key. If with each iteration of AES a small bit of the key leaks via a side channel, an attacker may be able to monitor the channel and recover the key.
SP 800 90A (and the Federal Information Standards program to which it belongs) omit side channel attacks from their threat model. As a result, manufacturers are compliant even if they use a non-side-channel-secure AES implementation. As we discovered, this left a number of implementations open to the state recovery attack described above.
Further, the standard does not require implementers to continuously add entropy to the PRG. Without sufficient additional entropy, CTR_DRBG can’t recover from state compromise. Therefore if an attacker can induce their victim to generate a large amount of output between state updates, they may be able to recover the AES key and leverage it to guess subsequent outputs from the PRG.
In our paper, posted online today, we instantiate this side-channel attack against CTR_DRBG and show how it can be used to recover secret keys from TLS sessions. We found a protocol flow within TLS that forces a client to generate enough PRG output to run the attack, and allows us to calculate the private key used by the client to authenticate to the server. Our attacker can now masquerade as the client!
Turning to actual implementations, we found that NetBSD, FortiOS (a network device operating system) and OpenSSL FIPS implement CTR_DRBG in a fashion that is not side-channel resistant. Of these implementations, FortiOS also did not add any additional entropy to the PRG, breaking prediction resistance. This shows that the design choices we’re concerned about are more than merely theoretical.
Though we think it’s unlikely that anyone is actively exploiting this vulnerability, it’s always a good idea to patch your software. For NetBSD users, a patch is already available. Similarly, Fortigate will shortly issue CVE-2019-15703 and advisory FG-IR-19-186 which can be referenced for more information.
Implementing the attack demonstrates our main point: standards bodies and practitioners need to take theoretical flaws seriously. What may seem like a minor oversight or exclusion from the threat model may be theory one day, but a weapon the next.