Wednesday, September 18, 2013
The Many Flaws of Dual_EC_DRBG
The Dual_EC_DRBG generator from NIST SP800-90A.
As a technical follow up to my previous post about the NSA’s war on crypto, I wanted to make a few specific points about standards. In particular I wanted to address the allegation that the NSA inserted a backdoor into the Dual-EC pseudorandom number generator.
For those not following the story, Dual-EC is a pseudorandom number generator that NIST proposed for international use back in 2006. Just a few months later, Shumow and Ferguson made cryptographic history by pointing out that there might be an NSA backdoor in the algorithm. This possibility — fairly remarkable for a pseudorandom number generator — looked bad and smelled worse. If true, it spelled almost certain doom for anyone relying on Dual-EC to keep their system safe from spying eyes.
Now I should point out that much of this is ancient history. What is news today is a recent leak of classified documents that points a very emphatic finger towards Dual_EC, or rather, an unnamed ’2006 NIST standard’. The evidence that Dual-EC is this standard has now become so hard to ignore that NIST recently took the unprecedented step of warning implementers to avoid it altogether.
Better late than never.
In this post I’m going to do my best to explain the curious story of Dual-EC. While I’ll do my best to keep this discussion at a high and non-mathematical level, be forewarned that I’m probably going to fail at a few points. So if you’re not the mood for all the details, here’s a short summary:
In 2005-2006 NIST and NSA released a pseudorandom number generator based on elliptic curve cryptography. They released this standard — with very little explanation — both in the US and abroad.
This RNG has some serious issues with just being a good RNG. The presence of such obvious bugs was mysterious to cryptographers.
In 2007 a pair of Microsoft researchers pointed out that these vulnerabilities combined to produce a perfect storm, which — combined with some knowledge that only NIST/NSA might have — opened a perfect backdoor into the random number generator itself.
This backdoor may allow the NSA to break nearly any cryptographic system that uses it.
For everyone else, here’s the long version.