UPDATE: Known theoretical attacks against TLS using the troubled Dual EC random number generator— something an intelligence agency might try its hand at—are in reality a bit more challenging than we’ve been led to believe.
The addition of the Extended Random extension to RSA Security’s BSAFE cryptographic libraries, for example, where Dual EC is the default random number generator, makes those challenges a moot point for the National Security Agency.
“By adding the extension, cracking Dual EC is trivial for TLS,” said Matt Fredrikson, one of the researchers who yesterday published a paper called “On the Practical Exploitability of Dual EC in TLS Implementations,” which explained the results of a study determining the costs of exploiting the Dual EC RNG where TLS is deployed.
The presence of Extended Random in BSAFE means the incursion into RSA Security by the NSA went beyond the inclusion of a subverted NIST-approved technology, as is alleged in the documents leaked by Edward Snowden, and an alleged $10 million payout by the government. Its presence solidifies that the NSA will leave no stone unturned to ensure its surveillance efforts are successful.
BSAFE was a prime target since it was used by developers not only in commercial and FIPS-approved software, but also in a number of open source packages. An attacker with a presence on the wire, say at an ISP or a key switching point on the Internet, could just passively sit and watch client or server handshake messages and be able to decrypt traffic at a relatively low cost.
Ironically, Extended Random is not turned on by default in BSAFE, and RSA says it is present only in BSAFE Java versions. Fredrikson confirmed the researchers did not see support for the extension compiled into the C/C++ version they studied despite the fact that the BSAFE documentation says it is supported.
By attacking Dual EC minus Extended Random, the researchers were able to crack the C/C++ version of BSAFE in seconds, whereas Microsoft Windows SChannel and OpenSSL took anywhere from 90 minutes to three hours to crack. In SChannel, for example, less of Dual EC’s output is sent making it more difficult to crack.
“Dual EC, as NIST printed it, allows for additional entropy to be mixed into the computation,” Fredrikson said. “OpenSSL utilizes that alternative, where BSAFE did not. That’s significant because the attacker would have to guess what randomness is given by OpenSSL.”
Dual EC, written by the NSA, was a questionable choice from the start for inclusion in such an important encryption tool as BSAFE. Experts such as Bruce Schneier said it was slower than available alternatives and contained a bias that led many, Schneier included, to believe it was a backdoor.
Extended Random, meanwhile, was an IETF draft proposed by the Department of Defense for acceptance as a standard. Written by Eric Rescorla, an expert involved in the design of HTTPS and currently with Mozilla, Extended Random was never approved as an IETF standard and its window as a draft for consideration has long expired.
Yet, it found its way into BSAFE. In a Reuters article yesterday that broke the story, RSA Security CTO Sam Curry declined to say whether RSA was paid by the NSA to include the extension in BSAFE; he added that it has been removed from BSAFE within the last six months. In September, NIST and RSA recommended that developers move away from using Dual EC in products because it was no longer trustworthy.
The researchers tested Dual EC in BSAFE C, BSAFE Java, Microsoft Windows SChannel I and II and OpenSSL. BSAFE C fell in fewer than four seconds while BSAFE Java took close to 64 minutes; and while Extended Random was not enabled for their experiments, it was simple to extrapolate its impact, the researchers said. They concluded the extension makes Dual EC much less expensive to exploit in BSAFE Java, for example, by a factor of more than 65,000.
The DOD’s reasoning for Extended Random was a claim that the nonces used should be twice as long as the security level, e.g., 256-bit nonces for 128-bit security, the researchers said in the study. Instead, Dual EC’s bias, which already makes it easier for an attacker to guess the randomness of the numbers it generates, is exacerbated by the Extended Random extension which does not enhance the randomness of numbers generated by Dual EC.
“When transmitting more randomness, that translates to faster attacks on session keys,” Fredrikson said. “That’s pretty bad. I haven’t seen anything quite like this.”
This article was updated on April 2 with clarifications throughout.
