A team of academics released a study on the maligned Dual EC DRBG algorithm used in RSA Security’s BSafe and other cryptographic libraries that includes new evidence that the National Security Agency used a second cryptographic tool alongside Dual EC DRBG in Bsafe to facilitate spying.
Allegations in top secret documents leaked by Edward Snowden say the NSA subverted the NIST standards process years ago in order to contribute weaknesses to the Dual EC DRBG algorithm. Reuters then reported in December that RSA Security was paid $10 million to make it the default random number generator in Bsafe. Those libraries are not only in RSA products, but in a good number of commercial and open source software packages.
The paper, “On the Practical Exploitability of Dual EC in TLS Implementations,” concludes that Dual EC can be cracked in short order given its inherent predictability weaknesses in generating random numbers. The inclusion of the Extended Random extension in Bsafe reduced the time required to crack the algorithm exponentially, from three hours on Microsoft Windows SChannel II down to four seconds in Bsafe for C. The researchers also tested OpenSSL’s implementation of Dual EC and found it the most difficult to crack.
A report this morning by Reuters outed the presence of Extended Random in Dual EC DRBG; the extension works contrary to its mission of enhancing the randomness of numbers generated by the algorithm.
Reuters said today that, while use of Extended Random isn’t pervasive, RSA built support for Extended Random in BSafe for Java in 2009. The paper explains how the researchers used $40,000 worth of servers in their experiment and that cracking BSafe for C and BSafe for Java were the most straightforward attacks.
“The BSAFE implementations of TLS make the Dual EC back door particularly easy to exploit in two ways,” the researchers wrote. “The Java version of BSAFE includes fingerprints in connections, making them easy to identify. The C version of BSAFE allows a drastic speedup in the attack by broadcasting longer strings of random bits than one would at first imagine to be possible given the TLS standards.”
Stephen Checkoway, assistant research professor at Johns Hopkins, told Reuters it would have been 65,000 times faster with Extended Random.
RSA Security said it had removed Extended Random within the last six months, but its CTO Sam Curry would not comment on whether the government had paid RSA to include the protocol in BSafe as well.
RSA advised developers in September to move off Dual EC DRBG, one week after NIST made a similar recommendation. But experts were skeptical about the algorithm long before Edward Snowden and surveillance were part of the day-to-day lexicon. In 2007, cryptography experts Dan Shumow and Niels Ferguson gave a landmark presentation on weaknesses in the algorithm, and Bruce Schneier wrote a seminal essay in which is he said the weaknesses in Dual EC DRBG “can only be described as a backdoor.”
Schneier wrote that the algorithm was slow and had a bias, meaning that the random numbers it generates aren’t so random. According to the new paper, assuming the attacker generated the constants in Dual EC—as the NSA would have if it inserted a backdoor into the RNG—would be able to predict future outputs.
“What Shumow and Ferguson showed is that these numbers have a relationship with a second, secret set of numbers that can act as a kind of skeleton key. If you know the secret numbers, you can predict the output of the random-number generator after collecting just 32 bytes of its output,” Schneier wrote in essay. “To put that in real terms, you only need to monitor one TLS Internet encryption connection in order to crack the security of that protocol. If you know the secret numbers, you can completely break any instantiation of Dual_EC_DRBG.
“The researchers don’t know what the secret numbers are,” Schneier said. “But because of the way the algorithm works, the person who produced the constants might know; he had the mathematical opportunity to produce the constants and the secret numbers in tandem.”
Over the weekend, Steve Marquess, founding partner at the OpenSSL Software Foundation, slammed FIPS 140-2 validation testing and speculated that the weaknesses in Dual EC DRBG were carefully planned and executed, likening them to an advanced persistent threat in a post on his personal website. FIPS 140-2 is the government standard against which cryptographic modules are certified.
“That, I think, perhaps even more than rigged standards like Dual EC DRBG, is the real impact of the cryptographic module validation program,” he wrote. “It severely inhibits the naturally occurring process of evolutionary improvement that would otherwise limit the utility of consciously exploited vulnerabilities.”
He offered up the OpenSSL FIPS module as an example where vulnerabilities live on, including Lucky 13 and CVE-2014-0076.
“That’s why I’ve long been on record as saying that ‘a validated module is necessarily less secure than its unvalidated equivalent’, e.g. the OpenSSL FIPS module versus stock OpenSSL,” he said.
Dual EC DRBG, however, is not enabled by default in the OpenSSL FIPS Object Module, but its presence offers an attacker who is on a server by another means the chance to enable it silently.
“As an APT agent you already have access to many target systems via multiple means such as ‘QUANTUM INTERCEPT’ style remote compromises and access to products at multiple points in the supply chain. You don’t want to install ransomware or steal credit card numbers, you want unobtrusive and persistent visibility into all electronic communications,” Marquess wrote. “You want to leave as little trace of that as possible, and the latent Dual EC DRBG implementation in the OpenSSL FIPS module aids discrete compromise. By only overwriting a few words of object code you can silently enable use of Dual EC, whether FIPS mode is actually enabled or not. Do it in live memory and you have an essentially undetectable hack.”
Marquess said the best defense is not to have the code present at all and that the OSF is trying to have it removed from its FIPS Module.
