The Wayback Machine - http://web.archive.org/web/20141016051543/http://dualec.org/

On the Practical Exploitability of Dual EC in TLS Implementations

Link to the research paper (PDF)

Paper authors:

Stephen Checkoway, Johns Hopkins
Matt Fredrikson, U Wisconsin
Ruben Niederhagen, TU Eindhoven
Adam Everspaugh, U Wisconsin
Matt Green, Johns Hopkins
Tanja Lange, TU Eindhoven
Tom Ristenpart, U Wisconsin
Daniel J. Bernstein, UIC / TU Eindhoven
Jake Maskiewicz, UC San Diego
Hovav Shacham, UC San Diego

The paper represents the views of all coauthors; however, this website only represents the views of Checkoway, Fredrikson, Everspaugh, Green, Ristenpart, Maskiewicz, and Shacham.

For other information, see Dual EC DRBG.

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:

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.

LibraryDefault PRNGExtended RandomBytes per SessionAdditional EntropyTime (minutes)
BSAFE C31–600.04
BSAFE Java2863.96
SChannel I2862.97
SChannel II30182.64
OpenSSL-fixed I32200.02
OpenSSL-fixed II323583.32
OpenSSL-fixed III3235+k2k⋅83.32

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:

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.