Summary

The results indicate that a sufficiently motivated attacker with knowledge of the trapdoor is able to decrypt traffic in a targeted manner in all of the cases studied. For BSAFE-C, it seems likely that dragnet surveillance of all encrypted communication is possible. For other libraries, dragnet surveillance depends on the attackers computational abilities, the amount of communication, and, in some cases, additional knowledge about the server using the library.

Background

In September 2013, the New York Times, the Guardian and ProPublica reported on a secret National Security Agency SIGINT Enabling Project with the mission to “actively [engage] the US and foreign IT industries to covertly influence and/or overtly leverage their commercial products’ designs.” The project aims to influence commercial encryption products to make the encrypted connections vulnerable to electronic surveillance. Named targets include protocols for “TLS/SSL, https (e.g., webmail), SSH, encrypted chat, VPNs and encrypted VOIP.”

In particular, leaked NSA documents indicate that particular NIST and ISO cryptography standards may have been influenced by the NSA in order to weaken the security of U.S. and non-US cryptography products. These standards include NIST Special Publication 800-90A and ISO 18031, both of which contain algorithms for generating the random numbers used, for example, to generate keys for cryptographic systems.

One of the algorithms contained within these documents is a pseudorandom number generator called the Dual Elliptic Curve Deterministic Random Bit Generator (Dual EC DRBG) that has long been known to admit a serious potential back door in the event that an attacker generates the standard algorithm parameters. While no one is claiming that NIST or NSA designed the generator to facilitate such attacks, the September 2013 news appears to provide evidence for this possibility.

Use of Dual EC in TLS Libraries

Despite Shumow and Ferguson's warning in 2007, several cryptographic software vendors have implemented Dual EC in their products. For example, both Microsoft’s SChannel (used in Microsoft Internet Explorer and IIS) and OpenSSL’s FIPS module include Dual EC as an optional random number generator. Moreover, RSA’s BSAFE crypto libraries use Dual EC as the default random number generator.

A primary use-case for each of the aforementioned software libraries is to establish encrypted SSL/TLS connections, which are used for secure web browsing, email transfer, VPNs and many other applications. The authors study to what extent TLS/SSL connections established by these software libraries are vulnerable to attacks using the Dual EC back door, assuming that an attacker knows a trapdoor for the Dual EC parameters.

To conduct this research, the authors reverse-engineered several libraries, including RSA BSAFE Share for C/C++, RSA BSAFE Share for Java, Microsoft SChannel, and OpenSSL, in order to replace the existing Dual EC parameters with those of their own devising. In the case of Share for C/C++, Share for Java and SChannel, identifying the Dual EC parameters and disabling relevant diagnostics required substantial reverse engineering effort. They then determined to what extent TLS connections made by these libraries were vulnerable to attacks on Dual EC DRBG.

Surprisingly, the previously known attacks do not tell the entire story. They do not consider many important implementation-specific decisions, in particular the amount of generator output revealed, the alignment of outputs, the use of additional entropy, and even critical bugs in Dual EC implementations.

Summary of the results

The researchers analyzed the use of Dual EC in four recent TLS/SSL library implementations: RSA BSAFE Share for C/C++, RSA BSAFE Share for Java, Microsoft SChannel, and OpenSSL. The major findings are as follows:

• The RSA BSAFE implementations of TLS make the Dual EC back door particularly easy to exploit compared to the other libraries analyzed. The C version of BSAFE makes a drastic speedup in the attack possible by broadcasting long contiguous strings of random bytes and by caching the output from each generator call. The Java version of BSAFE includes fingerprints in connections, making it relatively easy to identify them in a stream of network traffic.
• SChannel does not implement the current Dual EC standard: it omits one step of the Dual EC algorithm. This omission does not prevent attacks; in fact, it makes them slightly faster.
• A previously unknown bug was discovered in OpenSSL that prevented the library from running when Dual EC is enabled. It is still conceivable that someone is using Dual EC in OpenSSL, since the bug has an obvious and very easy fix which was applied in order to evaluate the resulting version of OpenSSL, which the paper calls “OpenSSL-fixed.” OpenSSL-fixed turns out to provide additional entropy (“additional input”) with each call to the library. In practice, this additional input can make attacks significantly more expensive than for the other libraries.

Evidence of an implementation of a non-standard TLS extension called “Extended Random” was discovered in the RSA BSAFE products. This extension, co-written at the request of the National Security Agency, allows a client to request longer TLS random nonces from the server, a feature that, if it enabled, would speed up the Dual EC attack by a factor of up to 65,000. In addition, the use of this extension allows for for attacks on Dual EC instances configured with P-384 and P-521 elliptic curves, something that is not apparently possible in standard TLS. While the code implementing Extended Random was not compiled into the build of Share for C/C++ examined, it was available (though deactivated) in the build of Share for Java that was analyzed. In the latter case, the researchers were able to re-enable it and verify the functionality. Note that the attack times reported below do not take advantage of extended random.

The results are summarized in the following table.

Each of the rows above describes a TLS library in a particular attack scenario. The rightmost column indicates the time required to achieve full decryption of a TLS connection on the small 16-CPU computer cluster used in the experiments. The “Default PRNG” column indicates whether the Dual EC algorithm is specified as the default random number generator, or must be activated by the calling application. “Extended Random” indicates whether code for the Extended Random extension was present in the library analyzed. The “Additional Entropy” column indicates how much “additional input” entropy is provided to the generator on each call to the generator. In the case of OpenSSL-fixed III it is assumed that an additional input entropy of 35+k bits is used.

As illustrated above, TLS connections made by RSA Share for C/C++ could be decrypted in several seconds on the cluster and in under a minute on an old laptop. Other libraries, such as Share for Java, Microsoft SChannel, and OpenSSL (with the bug repaired) also proved feasible to attack, but were in some cases significantly more costly. Indeed, depending on the design choices in the implementations, an attacker can recover TLS session keys within seconds on a single CPU or may require a cluster of more than 100,000 CPUs for the same task if a different library is used. Note that the speed results are due to custom, highly-optimized attack implementations. Less efficient implementations may take significantly more time.

Measurement Study

Finally, the prevalence of these libraries on the Internet was studied. Initiating a ZMap scan over the entire IPv4 address space, TLS handshake data from 21.8 million servers responding to public https requests was collected. Using the known handshake fingerprint exhibited by BSAFE, as well as a pattern discovered in the session identifiers produced by SChannel servers, the researchers were able to identify the presence of these implementations from handshake data alone. They found that:

• The Java version of BSAFE is not prevalent on public-facing https servers—only 720 servers were found (much less than 1%) that exhibit the fingerprint. Closer examination revealed that one third of these correspond to one particular software package (Apache Coyote/1.1).
• SChannel is far more prevalent, comprising approximately 2.7 million servers (12%) of those scanned.

There are two important points to make regarding these results. First, the number of BSAFE servers found is a lower bound for the true number of running BSAFE implementations—because the C++ version does not exhibit a handshake fingerprint by default and there does not appear to be a reliable way to identify it remotely. Second, the SChannel fingerprint does not indicate whether Dual EC is in use on the server. It is not enabled by default on Windows, so the servers observed are not all vulnerable to Dual EC attacks.