Author Topic: Hiding in plain sight: evidence that NSA isn’t wrecking internet security  (Read 2935 times)

0 Members and 1 Guest are viewing this topic.

Offline Elaine Davis

  • Administrator
  • *****
  • Posts: 1467
  • Gender: Female
  • To thine own self, be true.
By Stewart Baker April 3 at 9:26 pm

Hiding in plain sight: evidence that NSA isn’t wrecking internet security

An army of researchers recently published a short study of a weakness that NSA is alleged to have introduced into a public security standard.  Joseph Menn of Reuters gave the study lengthy and largely uncritical coverage; here’s the gist:

Security industry pioneer RSA adopted not just one but two encryption tools developed by the U.S. National Security Agency, greatly increasing the spy agency’s ability to eavesdrop on some Internet communications, according to a team of academic researchers. Reuters reported in December that the NSA had paid RSA $10 million to make a now-discredited cryptography system the default in software used by a wide range of Internet and computer security programs. The system, called Dual Elliptic Curve, was a random number generator, but it had a deliberate flaw – or “back door” – that allowed the NSA to crack the encryption. A group of professors from Johns Hopkins, the University of Wisconsin, the University of Illinois and elsewhere now say they have discovered that a second NSA tool exacerbated the RSA software’s vulnerability.

The allegation that NSA weakened the dual elliptic curve random number generator has been floating around for some time, and it has already had some policy impact. The President’s Review Group was reacting to the story when it declared that the US Government should “fully support and not undermine efforts to create encryption standards [and] not in any way subvert, undermine, weaken, or make vulnerable generally available commercial software.”

A careful reading of the actual study, though, suggests that there’s been more than a little hype in the claim that NSA has somehow made us all less safe by breaking internet security standards.  I recognize that this is a technical paper, and that I’m not a cryptographer. So I welcome technical commentary and corrections.

With that disclaimer, however, it seems to me that the paper makes two points that take a lot of the air out of the “NSA wrecks internet security” balloon:

1. If there’s a backdoor in the standard, no one has found it.

It’s an article of faith among academic cryptographers (and something the Reuters article just assumes) that there is a backdoor in the dual elliptic curve standard. In 2007, some Microsoft researchers explained how a backdoor might have been implanted in the standard. Researchers have been looking for ways to exploit the backdoor – and thus prove its existence – ever since.

Yet the paper concedes that the researchers can’t confirm the existence of a flaw. Instead, the researchers had to make up a different flawed protocol and show how quickly they could exploit that vulnerability. The artificiality of that exercise probably should have made Reuters a little more skeptical about the study’s results, but there’s a more important point in the researchers’ concession.



On the Practical Exploitability of Dual EC in TLS Implementations

Paper authors:

Stephen Checkoway, Johns Hopkins
Matt Fredrikson, U Wisconsin
Ruben Niederhagen, TU Eindhoven
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, Green, Maskiewicz, Ristenpart, and Shacham.

For other information, see Dual EC DRBG.

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.

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.

Library Default PRNG Extended Random Bytes per Session Additional Entropy Time (minutes)
BSAFE C ✓  31–60 — 0.04
BSAFE Java ✓ ✓ 28 — 63.96
SChannel I   28 — 62.97
SChannel II   30 — 182.64
OpenSSL-fixed I   32 220 0.02
OpenSSL-fixed III   32 235+k 2k⋅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 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.
Theme by orderedlist with minor changes; licensed CC BY-SA 3.0.
GOD FORBID THE LIGHTS GO OUT and a zillion brains have to be retrained to function in manual reality.

Does anyone else get the idea that the tweets on the WL account are starting to sound a little like someone is bathing in a bird bath, eating bird food & possibly smoking bird * in his own sphere??

Offline Elaine Davis

  • Administrator
  • *****
  • Posts: 1467
  • Gender: Female
  • To thine own self, be true.


Ecosystem vulnerability
DRBGs and back doors
Description of Dual EC
Dual EC origin
The basic back door
Dual EC news:
SP800-90 change
Extended Random
Exploitability in TLS
Attack cost
Downloads and links

Randomness is essential for secure cryptography. Random numbers are used for secret long-term keys, secret short-term keys, public "nonces" that must never repeat, secret nonces, and more. An attacker who can control these random numbers, or who can merely predict the secret random numbers, has the power to decrypt encrypted messages and forge authenticated messages.

Cryptographic users obtain random numbers from software and hardware devices called "random-number generators" (RNGs). This site collects new results on one RNG, Dual EC, and also provides detailed background on this RNG.

Dual EC was standardized by the American standardization bodies ANSI and NIST and by the International Organization for Standardization, ISO. Cryptographers raised alarms about undesirable properties of Dual EC, including a potential back door; these alarms began while the NIST standard was still a draft. In September 2013 the New York Times mentioned Dual EC as an example of NSA's Bullrun program. In response, NIST issued an official bulletin that "strongly recommends" against Dual EC. In February 2014, NIST issued a request for comments (due 18 April 2014) on the "principles, processes and procedures" behind NIST's "cryptographic standards development efforts".

Summaries of subpages with new content
For details on the research credit stated in these summaries see the individual pages.

Vulnerability of the RNG ecosystem
There is a large ecosystem that eventually gives random numbers to users. This ecosystem includes designing, evaluating, standardizing, selecting, implementing, and deploying RNGs. This page considers a high-level attack strategy against the ecosystem.
Modification in SP800-90 in March 2007
In March 2007 the SP800-90 Dual EC standard was changed. The June 2006 version of Dual EC had an error from the attacker's perspective: the back door was difficult to exploit if the user incorporated "additional input" for each output block, even if the additional input was guessable. The March 2007 change fixed this error, allowing exploitability whether or not the user incorporated "additional input". The same change appears in the current version of ISO 18031. Research credit (alphabetical order): Bernstein, Checkoway, Green, Lange.
Extended Random
The proposed "Extended Random" TLS extension improves the exploitability of the Dual EC back door. The published security motivation for Extended Random is incorrect. Research credit for exploitability (alphabetical order): Checkoway and Green. Research credit for security analysis of the motivation (alphabetical order): Bernstein and Lange.
Exploitability in TLS
The basic Dual EC attack turns out to be highly oversimplified: it ignores critical limitations and variations in the amount of the PRNG output actually exposed in TLS, additional inputs to the PRNG, PRNG reseeding, alignment of PRNG outputs, and outright bugs in Dual EC implementations. Dual EC has different levels of exploitability in RSA BSAFE, Microsoft SChannel, and OpenSSL. Research credit: Checkoway, Fredrikson, Niederhagen, Green, Lange, Ristenpart, Bernstein, Maskiewicz, and Shacham.
Performance of the attacks
Detailed cost analysis for Dual EC exploitation in TLS using BSAFE-C, BSAFE-Java, SChannel, and OpenSSL-fixed. The basic computations are considerably less expensive than indicated in the previous literature. Research credit: Checkoway, Fredrikson, Niederhagen, Green, Lange, Ristenpart, Bernstein, Maskiewicz, and Shacham.

Last modified: 2014.03.31
GOD FORBID THE LIGHTS GO OUT and a zillion brains have to be retrained to function in manual reality.

Does anyone else get the idea that the tweets on the WL account are starting to sound a little like someone is bathing in a bird bath, eating bird food & possibly smoking bird * in his own sphere??