The OpenSSL software bug that saves you from surveillance!
Bugs in pseudorandom number generators (PRNGs) are usually cause for concern, at least in cryptographic circles.
There have been numerous examples over the years.
We had the Debian “code fix” that removed all but 15 bits’ worth of unpredictability from the random generator used to secure OpenSSH.
We had the CryptoCat bug that caused zeros to turn up about 0.4% too often.
And recently we had a cryptographic design flaw in Drupal that saw the wrong sort of random generator used in the wrong sort of way.
But this story is different.
It’s the curious case of the OpenSSL randomness bug with a happy ending!
The beginning
The story starts back in 2006, when the US National Institute of Standards and Standards and Technology, better known as NIST, first released its Special Publication SP800-90A.
This document presents four algorithms for generating cryptographically strong random numbers.
→ NIST doesn’t call the algorithms PRNGs, presumably to get rid of the rather unscientific term pseudo. It calls them DRBGs instead, short for for deterministic random bit generators.
Three of NIST’s DRBGs are conventional: two of them use cryptographic hashes internally to mash up a soup of pseudorandom bits, while the third uses a symmetric block cipher (Triple-DES or AES) with a similar result.
The fourth algorithm, which goes by the redolent name of the Dual Elliptic Curve Deterministic RBG (Dual EC DRBG), is a bit different.
Indeed, it is sufficiently different that it aroused the suspicion of cryptographers almost at once.
Here’s why.
Suspicions aroused
Imagine that you make your pseudorandom soup by repeatedly mixing up some starting data, not with a symmetric block cipher or a cryptograhpic hash, but with a randomly-generated public key for a public key encryption algorithm.
(This isn’t an accurate high-level description of how the Dual EC algorithm works, but it will do as a sort of analogy to explain why cryptographers were suspicious.)
You’d probably accept that the public key encryption aspect could serve as a one-way function, just like a cryptographic hash, provided that the associated private key had been destroyed.
Bear in mind that this is an inexact analogy and an imprecise explanation…
…but now ask yourself, “What if NIST kept something analogous to a private key up its sleeve?”
What if NIST surreptitiously retained algorithmic secrets that weakened the Dual EC DRBG, without telling anyone?
That would create a loophole that might make the DRBG not merely deterministic, but predictable, even to an attacker who could do no more than monitor the algorithm’s output.
Was there a backdoor?
That worrying question led to several well-known cryptographers, notably Dan Shumow and Niels Ferguson of Microsoft, openly wondering, back in 2007, whether this flaw was actually a deliberate back door in the NIST standard.
Fast forward five years, of course, and revelations by ueberwhistleblower Edward Snowden about surveillance shenanigans by the National Security Agency (NSA) have led to reports that as good as state the backdoor concern as a fact.
Other recent reports intriguingly claim that the NSA paid security company RSA $10,000,000 to prefer the use of the questionable Dual Elliptic Curve generator in its software.
→ Cryptographers have long wondered why anyone would used the Dual EC algorithm at all, even if its other shortcomings were ignored, because it is much less efficient than the others. According to Bruce Schneier, who also raised the question of a deliberate backdoor back in 2007, the Dual EC DRBG is about 1000 times slower than its more conventional cousins from SP800-90A.
Perhaps most tellingly of all, NIST itself recently and officially disowned Dual EC mode, recommending that you avoid it because:
recent community commentary has called into question the trustworthiness of [the] default elliptic curve points [used in the algorithm].
How big is the problem?
With this in mind, experts have been wondering how much software out there in the real world is using the Dual EC DRBG, and potentially vulnerable to cryptographic manipulation as a result.
OpenSSL, for example, one of the most widely-used encryption libraries, implements all four of the SP800-90A algorithms, ironically as part of achieving what is known as FIPS 140-2 certification.
And here is the happy ending.
Despite passing FIPS 140-2 tests many times over the years, the OpenSSL implementation of Dual EC DRBG is buggy.
Not just buggy, but totally broken and busted.
Simply put, it cannot be made to work in real-world software, and the fact that it has taken years for anyone to notice makes it reasonable to assume that no real-world software has ever even bothered to use it.
In the words of the OpenSSL Foundation itself, “We have no plans to fix this bug.”
Article source: http://feedproxy.google.com/~r/nakedsecurity/~3/dh64YNuXdhg/