RSA caught again in NSA subverting of Dual EC encryption

A team of researchers has discovered that RSA's "Extended Random" TLS extension decreases encryption cracking times by a factor of up to 65,000 times.

The collaboration between EMC-owned RSA Security and the US National Security Agency (NSA) had been revealed to be deeper than first thought, after a team of researchers found a gaping flaw in the "Extended Random" TLS extension found in RSA's BSAFE encryption libraries.

Rather than adding extra randomness to the encryption, the researchers found that the extension sped up an attack on the already flawed Dual Elliptic Curve Deterministic Random Bit Generator (Dual EC) by a maximum factor of 65,000.

"If using Dual Elliptic Curve is like playing with matches, then adding Extended Random is like dousing yourself with gasoline," one of the researchers told Reuters, who first reported the story.

RSA did not dispute the research, when contacted by Reuters.

The research team examined RSA BSAFE Share for C/C++, RSA BSAFE Share for Java, Microsoft SChannel, and OpenSSL for how each implemented Daul EC, and found that RSA's BSAFE was "particularly easy to exploit".

"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 researchers wrote. "The Java version of BSAFE includes fingerprints in connections, making it relatively easy to identify them in a stream of network traffic."

OpenSSL was found to have a bug, one that was previously unknown, that prevented the library from running when Dual EC was enabled. The team patched the library, and found that it had extra entropy on each library call that would make its version of Dual EC harder to attack.

Using a 16-CPU cluster to attack each implementation, the researchers said that all implementations were practical for a motivated attacker, even for a large number of targets.

"The BSAFE-C attack is practically instantaneous, even on an old laptop," the research paper (PDF) said. "The BSAFE-Java and SChannel attacks require more processing power to recover missing bits of Dual EC output. The OpenSSL-fixed attack cost depends fundamentally on how much information on the additional input is available."

Due to the ability to detect fingerprints of the various implementations, the researchers found only 720 servers have BSAFE-Java exposed in a ZMap scan of 21.8 million IPv4 addresses. SChannel was found on 2.7 million servers, but because Dual EC is not enabled by default for SChannel, the team could not say how many were vulnerable. Because BSAFE-C did not exhibit a fingerprint, it is not known how many servers are vulnerable to the quickest attack found.

"Our results demonstrate that otherwise innocuous implementation decisions greatly affect exploitability," the researchers said. "For example, RSA BSAFE-C is by far the easiest to exploit due to caching of unused bytes of Dual EC output."

"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."

"Our work further emphasizes the need to deprecate the [Dual EC] algorithm as soon as possible."