Is there a backdoor in NIST’s SP800-90 Dual Ec pseudorandom number generator?
According to a presentation by Dan Shumow and Niels Ferguson from Microsoft given at CRYPTO 2007, there is a backdoor in this pseudorandom number generator. While the authors don’t know how to use the backdoor, they point out that it is possible that the creators of the algorithm specified in the NIST standard could have access to numbers which would render the pseudorandom number generator insecure.
O brave new quantum world!
Wow, that’s just appalling. It looks like the NSA not only tried to screw everyone over, but did so in a really incompetent fashion. Are they trying to lose all credibility?
This way of presenting it isn’t really fair to NSA, and I don’t think it’s likely that there’s a backdoor in the system. The issue is that there are several strange constants appearing in the algorithm, with no explanation as to why those values were chosen. Probably they were chosen to defeat certain attacks, but NSA won’t reveal what those attacks were. This is not unrealistic. In the 1970’s people were very concerned about the design of the “S-boxes” in the US Data Encryption Standard, and in particular whether their mysterious values encoded a backdoor. In the 90’s it was revealed that they were chosen to defeat differential cryptanalysis, which was known to NSA in the 70’s but not discovered publicly until the early 90’s.
What Ferguson and Shumow realized is that it is possible to choose these constants to create a backdoor, and they gave a method for doing so. However, they cannot give any evidence that this was actually done. There’s no way of knowing (unless the design criteria for these constants is revealed, which just isn’t going to happen).
NSA ought to be embarrassed for having created a system with the appearance of a possible backdoor. However, I very much doubt there is one. It’s just too obvious, since the Ferguson-Shumow method is not very difficult or subtle (if they hadn’t noticed it, someone else would have). My guess is that the NSA employees who designed the system just weren’t worrying about appearances, and they didn’t think hard enough about whether it might look like there’s a backdoor.
Exercise for reader: determine the backdoor that the current choice of the point on an eliptic curve is designed to thwart.
Randall: I don’t quite understand why it couldn’t also be that the NSA knows that the other PRNGs are not secure…
Ah, I see Randall. Thanks for the comment. I was wondering why you were confident in the security of the SHA hash functions…
What makes a backdoor especially plausible here is that this is is such a lame algorithm otherwise; it’s so much slower than the other generators that used symmetric algorithms. It’s not clear what reason there could be for the algorithm to be part of the standard other than to have a backdoor.
(If all the other generators had security problems, that would probably mean NSA’s SHA-2 hash functions are flawed. In that case, they could just fix SHA-2 like they fixed SHA-0; they seem to have no policy against giving the world strong hash functions, or correcting their mistakes.)
Aside: there’s a somewhat relevant academic random number generator called Blum-Blum-Shub. BBS also relies on a hard problem for its security (factoring), and is slow. If you wanted a slow algorithm based on a known-hard problem, BBS is arguably a better choice than Dual_EC_DRBG, because BBS is *provably* secure if factoring is hard, and BBS has been publicly studied. And, AFAIK, it specifies no Mysterious Constants.
But the more important point is that random number generators based on hash functions should be fine for everyone.
Dave: given a secure block cipher, or a secure hash function, you can build a secure random number generator. A break in the CTR_DRBG generator is a break in the underlying block cipher.
There’s some evidence NSA is confident in the underlying algorithms. NSA itself designed the SHA hash functions. The government allows the use of the AES block cipher with 192+-bit keys for information classified as top secret.
If NSA knows their SHA algorithm is insecure, my theory is they’d fix it (they did fix flaws in SHA-0). If NSA knows AES is insecure, my theory is they’d recommend a different algorithm for data classified as top secret.
I don’t know any of that for a fact; I don’t know what goes on in the minds of NSA bureaucrats, or what their principles are for interfacing with the outside cryptographic world. But it does support the notion that Dual_EC_DRBG wasn’t necessary for security, even though it doesn’t prove it.
In that case, they could just fix SHA-2 like they fixed SHA-0; they seem to have no policy against giving the world strong hash functions, or correcting their mistakes.
My interpretation of the evidence is just the opposite: NSA has gone to great lengths to avoid giving the world a strong hash function. SHA-0, 1, and 2 are all based on Ron Rivest’s publicly available ideas from MD4 and MD5, with only minimal modifications. MD4 and MD5 were the first to fall, and now SHA-0 and SHA-1 as well. SHA-2 will hold out longer (because of greater hash lengths) but it is based on the same flawed design principles. Basically, NSA didn’t want to reveal how they would design a hash function from scratch, so they made the smallest modifications to MD4/5 that they could get away with. SHA-0 was a blunder (they didn’t modify it carefully enough), so they patched it to SHA-1.
SHA-3 is being designed in a NIST-sponsored contest (like AES), so we won’t see any NSA technology there either. It’s possible that NSA has no idea how to make a better hash function, but I think it’s more likely that they just have a lot to lose by revealing their secrets.
In general, NSA is extremely conservative in what is revealed. Skipjack is the only NSA-designed crypto primitive we have ever seen in the unclassified world (except for ones like SHA that are variants of previous public systems). It’s a pretty unimaginative design, which suggests that it was chosen to avoid revealing much. Shortly after it was made public, researchers broke 31 of the 32 rounds in Skipjack, and everyone figured the whole thing was busted. Ten years later, after extensive work, nobody has beaten all 32 rounds. The upshot seems to be that NSA wants to release only unimaginative methods that are just barely secure. My guess is that they intended SHA-1 to be barely secure as well, but misjudged how far Xiaoyun Wang would go in hash function cryptanalysis. SHA-2 is just a patch meant to keep the US from having to go without any decent hash standard (which is why the SHA-3 contest is being held).
P.S. The fact that AES, SHA-2 etc. are used for top secret data is not a definitive argument in favor of their security. There’s actually a surprisingly large amount of top secret data out there, not all of which is so critical. Plus some of it doesn’t have to remain secure for such a long time. (If you need to protect data for a year, AES is almost certainly fine. If you want to keep anyone from decrypting it in the next 50 years, it’s not so clear.) There’s a whole family of NSA-designed algorithms for particularly sensitive top secret data; search for “Suite A” on the web, although you won’t get any information beyond a few supposed cipher names. You can turn the argument around: if Suite B (AES, SHA-2, etc.) is so great, why have a Suite A? It could be just that NSA won’t admit that their job is over, but it’s probably because Suite A is intrinsically superior to Suite B.
Anonymous:
I agree with most of what you’re saying factually, although not with the interpretation. SHA and Skipjack were definitely both meant for public consumption, so they don’t include NSA’s best tricks. I know about Suite A (or rather, I know some cipher names, like you said), and I don’t doubt that they’re more secure. Good point calling me out about Suite A and about SHA being an MDx derivative.
Still, for three reasons, I don’t think NSA introduced Dual_EC_DRBG to fix security flaws in the other DRBGs.
First reason is the use of AES in TOP SECRET systems. That authorization didn’t seem to be just for data that needs to be secret for a year, or stuff that’s no more secret than, say, a bank transaction. The most super-secret stuff will still be protected by BATON, but the remainder probably includes some stuff that Uncle Sam would not trust to a bad cipher. (Put another way: if NSA has a practical AES break, the security of lots of top secret information would depend on their ability to keep that break secret.)
Second is how profoundly broken AES/SHA would have to be for DRBGs based on them to be in need of replacement. Real attackers probably won’t get megabytes of DRBG output to analyze; you’d need something that worked with a handful of outputs.
If AES/SHA are that weak, you’d hope we’d have discovered some more substantial attacks on them. The public world isn’t all that far behind the folks who made SHA and Skipjack (acknowledging that Skipjack != Baton); academics found problems in SHA-0 and the limitations of Skipjack. I could be engaging in wishful thinking here — NSA could have some truly huge breakthroughs in block cipher cryptanalysis behind those walls.
Third, if NSA actually doesn’t want to give the public secure algorithms, they probably wouldn’t propose Dual_EC_DRBG as a security fix. Despite the possible backdoor, someone can probably just choose another starting point on the elliptic curve and use it safely. (Unless only NSA knows how to choose good starting points.) And Dual_EC_DRBG can be turned into a (slow) stream cipher, so proposing it as a security fix could be as bad as revealing a secure hash function.
In conclusion, we still don’t really know why Dual_EC_DRBG was included because we don’t know what goes on in NSA folks’ heads. Despite all I said, maybe there *is* some calculus in which NSA thinks that AES and SHA are insecure and that adding this PRNG is a proper response.
But my best guess is that Dual_EC_DRBG is there either (1) because of random bureaucratic nonsense — someone at NSA has a thing for elliptic curves — or (2) for the backdoor.
> If Suite B (AES, SHA-2, etc.) is so great, why have a Suite A? It could be just that NSA won’t admit that their job is over, but it’s probably because Suite A is intrinsically superior to Suite B.
More directly replying to this: Suite A is better, but that doesn’t mean AES, SHA, etc. systems are practical to break. Suite A algorithms probably have been built on well-tested principles, vetted to death, and found to have a strong security margin (i.e., only academic breaks at a greatly reduced number of rounds). They may also have awesome performance, and the secrecy of the algorithm can’t hurt. Conversely, NSA probably knows some academic attacks against AES/SHA that we don’t know about. That doesn’t mean they can actually see through AES in practice, though. Suite A may be to AES/SHA as SHA-2 is to MD5, say.