NIST Removes Dual_EC_DRBG From Random Number Generator Recommendations 86
hypnosec writes: "National Institute of Standards and Technology (NIST) has removed the much-criticized Dual_EC_DRBG (Dual Elliptic Curve Deterministic Random Bit Generator) from its draft guidance on random number generators following a period of public comment and review. The revised document retains three of the four previously available options for generating pseudorandom bits required to create secure cryptographic keys for encrypting data. NIST recommends that people using Dual_EC_DRBG should transition to one of the other three recommended algorithms as quickly as possible."
Trust... (Score:3, Insightful)
... So much more easily lost than won. How is anyone supposed to take these new recommendations seriously?
Cut off your nose to spite your face (Score:1)
What do you mean? The weakness in Dual_EC_DRBG is publicly known. Just because you don't trust the organization recommending you not use it, doesn't mean you should use it.
Re:Cut off your nose to spite your face (Score:5, Insightful)
NIST recommends that people using Dual_EC_DRBG should transition to one of the other three recommended algorithms as quickly as possible.
Presumably GP worries that if one out of four options selected by this body is not just flawed but apparently deliberately subverted, what does that say about how well the other three were vetted?
Re: (Score:1, Informative)
Presumably GP worries that if one out of four options selected by this body is not just flawed but apparently deliberately subverted, what does that say about how well the other three were vetted?
That isn't quite the issue. All of the options in the standard were vetted. The Dual_EC_DRBG option is controversial for performance, the correction to it, and one other reason. Some people claim that it has a backdoor, but that isn't what has been proven. What has been proven is that a backdoor is possible with the technology and you wouldn't know either way. You can generate values for the curve without creating a backdoor, and that would be less work. If there was a backdoor created, only the perso
Re: (Score:2)
With any state authority these days, as their true nature slowly becomes exposed, you have to assume the worst.
Re:Cut off your nose to spite your face (Score:5, Insightful)
The problem is that by assuming the worst you can go down the wrong path is the situation isn't in fact worst case. Consider the example of DES encryption. The NSA tweaked the S-box values before the standard was approved. Nobody outside of NSA knew why. Many people suspected some sort of backdoor, but nobody could find one. As a result of the suspicion there were people that refused to use DES. Eventually it emerged that NSA had strengthened DES against secret cryptanalysis techniques that weren't generally known at the time. Many of the people that refused to use DES ended up using encryption schemes that were vulnerable to the secret techniques because they assumed the worst and were wrong. DES held up remarkably well against attacks over time, including attacks that were either invented or reinvented long after DES was approved.
Re: (Score:1)
When it comes to encryption you're either going to trust somebody, who may end up having a hidden agenda and the ability to hide it from you, or you won't be exchanging encrypted messaged. Even public review is no guarantee: "Opps! Looks like we didn't cover that obscure corner case, "glad" you spotted it!"
Re: (Score:1)
When it comes to encryption you're either going to trust somebody...
Yes, but the state, never again. Its soul is permanently blacken by its corruption. The only way they can get any trust now is if it is dissolved and is completely replaced with entirely new people, and those people should know they only get one chance. Never give the state the benefit of a doubt. They will invariably abuse it.
Re: (Score:2)
Sorry man, trust is gone. You can't regain your virginity.
I'm a born again virgin, you insensitive clod!
Re: (Score:2)
Eventually it emerged that NSA had strengthened DES against secret cryptanalysis techniques that weren't generally known at the time. Many of the people that refused to use DES ended up using encryption schemes that were vulnerable to the secret techniques because they assumed the worst and were wrong.
An excellent illustration of the downfalls of security through obscurity. The NSA could have known that would happen and that their secrecy might decrease the average security situation due to people not using the actually more secure crypto. They should have been transparent about why they tweaked the S-box values. People shouldn't have to assume anything, best or worst.
And now of course the NSA have demonstrated that they cannot be trusted at all and nobody should ever accept magic numbers from them ever
Re: (Score:2)
That was back when people still trusted the NSA to do its job properly i.e. secure US communications and decipher those of US opponents.
Today they seem to think everyone is an opponent which needs to have its communications deciphered.
Re:Cut off your nose to spite your face (Score:5, Insightful)
Some people claim that it has a backdoor, but that isn't what has been proven. What has been proven is that a backdoor is possible with the technology and you wouldn't know either way.
The difference is academic, but I suppose you mean as in this [slashdot.org] story about the proof of concept?
An algorithm for which a backdoor is possible should be considered backdoored. Especially for crypto PRNGs. Anyway, taken in context, which is to say the RSA connection and those unexplained constants P and Q which you couldn't change in certified implementations.. Guess I'm inclined to being just slightly more paranoid these days.
Re: (Score:1)
So, what are these algorithms that are impossible to backdoor either through design or implementation? No chance of another something like heartbleed, or Reflections on Trusting Trust [bell-labs.com]?
There is actually nothing wrong with the algorithm for Dual_EC_DRBG, the issue is with people's trust of the constants that define the curve for it in the standard. The only issue there is that people don't trust them just like they didn't trust the NSA generated S-boxes that strengthened DES against secret cryptanalysis tech
Re: (Score:2)
There *is* something wrong with Dual_EC_DRBG, the possibility of a backdoor is the most serious flaw but it isn't the only one : http://blog.cryptographyengine... [cryptograp...eering.com]
Re: (Score:1)
I don't remember if I've seen that link before, but thanks for sharing it. That is a great explanation, and reinforces the point I've been making.
The Many Flaws of Dual_EC_DRBG [cryptograp...eering.com]
The 'back door' in Dual-EC comes exclusively from the relationship between P and Q -- the latter of which is published only in the Dual-EC specification.
Re: (Score:2)
It is basically a compromised design, i.e. a design that makes an implementation compromise intentionally hard or impossible to spot. That does not actually mean the implementation is necessarily compromised.
People have real trouble understanding the distinction or why this is a compelling reason not to use it.
Re: (Score:2)
Sometimes it may be difficult to tell the difference between a weakness and a backdoor. But in the case of dual EC DRBG there is so much evidence indicating that it is an actual backdoor, and not (just) a weakness, that I think it is no longer fair to label it as a weakness. Who placed the backdoor is not officially confirmed, but we all know who the prime suspect is.
Re: (Score:2)
Re: (Score:1)
As I understand it that is the nature of elliptic curve technology, so I don't think that is quite right. You may recall that elliptic curve encryption was thought to be a highly promising encryption technology at the time. I'm not sure that the calculations would really help you since you could probably generate the same points with or without a backdoor, although I could be mistaken on that point. But as far as I know there is no way to tell just by examining a set of constants if there is a backdoor o
Re: (Score:2)
Yes, compared to other asymmetrical primitives. I have seen no research suggesting that it would be a good idea to replace symmetrical cryptography with elliptic curves. Quite the contrary, since symmetrical cryptography is more resistant to cryptoanalysis using quantum computers, than asymmetrical cryptography is.
Re:Cut off your nose to spite your face (Score:5, Insightful)
You go ahead and keep on using it. Meanwhile, for the rest if us, no proof is needed -- not in the sense that you insist is relevant. The theoretical possibility is enough to ditch this generator. That, and as kasperd and others point out, all those circumstantial bits of evidence... It must take real effort not to see it.
Re: (Score:1)
Clear thinking generally takes some effort. You should always be clear about what the evidence proves and what it doesn't prove or you are likely to make mistakes. Once you understand that you can apply your suspicions. There were plenty of people that assumed that DES was backdoored due to the changes made in the DES S-boxes prior to the standard being approved. They refused to use DES and used other technologies. It was later revealed that DES had been hardened against secret cryptanalysis techniques
Re:Cut off your nose to spite your face (Score:5, Interesting)
Operating by suspicion can be hazardous when it comes to encryption.
I would argue that operating by suspicion should be the default when it comes to encryption.
Re: (Score:1)
That may be at some level, but keep it mind that operating only on suspicion makes it easy to end up in the "didn't use DES, got data read by differential cryptanalysis (or method X)" bin. Your choice. It is easy to have suspicions that aren't well founded, as well as false confidence.
Math majors get heavily recruited for those jobs for a reason. Sound encryption doesn't tend to emerge from whimsy.
Re: (Score:1)
You should have read the next line. Apparently you aren't there yet.
Once you understand that you can apply your suspicions.
Re: (Score:1)
I did read that line. I didn't quote it out of pity because it makes your post even more ironic. Anyone that think "gut feeling", smell test" or "women intuition" means anything when it comes to fact checking is clearly a lousy thinker and hasn't understood anything about what evidence is.
Re: (Score:1)
Oh dear, did something I wrote bruise your feelings at some point? That's too bad. What is worse is that you don't understand that establishing the facts is a different question than making an assessment. You don't seem to be up to judging my thought process at the moment.
Re: (Score:3)
Re: (Score:1)
That really isn't right, is it? You're abusing the notion of "backdoor." The evidence that a backdoor is possible is incontrovertible. But practically speaking to have access to that backdoor you have to develop the backdoor values as part of defining the curve for the standard / implementation. If you don't develop the backdoor values as part of defining the curve then you are essentially back to solving the original problem in order to get your "shortcut". In other words, it is no help at all if you d
Re: (Score:3)
Re: (Score:1)
The problem isn't the algorithm. The "problem" is specifically a question of trust in how the constants for the curve were developed. There is no backdoor if you don't create one from the start. The possibility of there being one is gone if you have an open process to create the curve values in which a backdoor isn't created. At that point the remaining issue is performance. Up till now there have been three other RNGs in the standard if you don't like Dual_EC_DRBG. Yes you can compare the situation t
Re: (Score:2)
Re: (Score:1)
You could keep Dual_EC_DRBG by updating the standard to have a new set of constants just like you can update the standard to remove Dual_EC_DRBG entirely. It isn't that hard.
I never claimed that the existing constants were created via an open process. What I pointed out is that a new set of constants could be created by an open process and that addresses the trust issue.
Re: (Score:2)
Re: (Score:1)
That doesn't seem to be true.
The Many Flaws of Dual_EC_DRBG [cryptograp...eering.com]
Back in 2004-5, NIST decided to address a longstanding weakness of the FIPS standards, namely, the limited number of approved pseudorandom bit generator algorithms (PRGs, or 'DRBGs' in NIST parlance) available to implementers. This was actually a bit of an issue for FIPS developers, since the existing random number generators had some known design weaknesses.*
NIST's answer to this problem was Special Publication 800-90, parts of which were later wrapped up into the international standard ISO 18031. The NIST pub added four new generators to the FIPS canon. None these algorithms is a true random number generator in the sense that they collect physical entropy. Instead, what they do is process the (short) output of a true random number generator -- like the one in Linux -- conditioning and stretching this 'seed' into a large number of random-looking bits you can use to get things done.** This is particularly important for FIPS-certified cryptographic modules, since the FIPS 140-2 standards typically require you to use a DRBG as a kind of 'post-processing' -- even when you have a decent hardware generator.
The first three SP800-90 proposals used standard symmetric components like hash functions and block ciphers. Dual_EC_DRBG was the odd one out, since it employed mathematics more that are typically used to construct public-key cryptosystems. This had some immediate consequences for the generator: Dual-EC is slow in a way that its cousins aren't. Up to a thousand times slower.
Now before you panic about this, the inefficiency of Dual_EC is not necessarily one of its flaws! Indeed, the inclusion of an algebraic generator actually makes a certain amount of sense. The academic literature includes a distinguished history of provably secure PRGs based on on number theoretic assumptions, and it certainly didn't hurt to consider one such construction for standardization. Most developers would probably use the faster symmetric alternatives, but perhaps a small number would prefer the added confidence of a provably-secure construction.
Re: (Score:2)
Re: (Score:3)
No, but it does leave you wondering about the other things they recommended.
Random (Score:1)
I really wish people would stop using the word "random" for things that are anything but.
Re: (Score:2)
Re: (Score:2)
Pseudo random, as it could be predicted based on the headline alone.
When we say rng we mean prng unless otherwise noted. That is the common usage, and it is hard to correct the common.
Re: (Score:1)
"Pseudorandom" isn't correct either. There is nothing random about the numbers.
They're just statistically flat.
Re: (Score:1)
I really wish people would stop using the word "random" for things that are anything but.
Ah, to be fair, I did see the word pseudorandom used at least once here...which would be accurate.
Obligatory XKCD (Score:4, Funny)
http://xkcd.com/221/ [xkcd.com]
OpenBSD has already removed it (Score:2, Interesting)
OpenBSD has already removed that nonsensical algorithm from LibreSSL, has OpenSSL yet??? NOPE!!!!
It's broken and disabled (Score:1)
The implementation didn't work anyway and it looks like they disabled it. Announcement on their mailing list [marc.info].
Not the only change (Score:3, Interesting)
They also made many other changes. See appendix F of draft 1. I'm in the middle of reviewing them
The announcement and RFC is here.
The comments from the previous round addressed far more than just the Dual_EC_DRBG.
There are structural issues in the spec. My comments on the previous draft address them:
1) Flow control: ES pushing, vs conditioner pulling. Reseeding on demand vs when entropy is available.
2) A purely software centric API, when all nondeterministic random number generators need a hardware component.
3) Online testing that is too onerous for resource constrained solutions, when effective technical solution exists that have been ignored.
4) Conditioners (really an SP800-90B thing, but A, B and C go hand in hand) are all single source conditioners based on large crypto functions. The current state of math [ias.edu] tells us multiple input conditioners can be implemented with non cryptographic methods in fewer gates with higher lower-bounds for min entropy out.
There's more. See the comments [nist.gov].
Re: (Score:3)
Oops. I missed the link for the announcement.. here [nist.gov]
What's the cost to use a real rng vs psudo (Score:3)
Re: (Score:2)
Not sure if their implementation is better, but VIA seems to have something different and hardware-based [via.com.tw].
If it's truly good, maybe it could be licensed and added to all future Intel, AMD and ARM CPUs?
Re: (Score:2)
Intel has a hardware RNG (RdRand) as well, although I don't think AMD does (and I'm sure there are ARM implementations that have something similar). There was a spat a while back over it - because neither Intel nor VIA's microcode for it is public, they can't be trusted as a sole source of randomness. AFAIK nobody uses them as the sole source of randomness - they're either ignored, or mixed into the entropy pool with other PRNGs.
Re: (Score:2)
See LavaRnd.
Re: (Score:3, Interesting)
>no one can know if Intel could have a backdoor into it.
Except me and my colleagues, who have full visibility of it and know if a back door was put in it and no, a back door was not put in it.
If there was a back door, it would only take one person out of several hundred of those people who would know, to tell the world about a backdoor. If there isn't a backdoor (which there isn't), then there's no back door to tell the world about.
We are a company full of techies most of whom like open source principles
Re: (Score:1)
It has been suggested that by tampering with the masks [schneier.com] late in the process, you could sabotage functionality with very few people being in on it.
Re: (Score:2)
I hate to be on this side of the argument, but adding a single word changes your post completely, and that word is "yet".
It is unlikely at this point, but still possible. I repeat, unlikely.
Re: (Score:1)
So, out of the hundreds of people, how many actually check what the real, post production contents of the masks are?
I can imagine a backdoor could be made with a handfull of transistors. Does anyone check the individual transistors for functionality?
I thought not.
I think you need to admit that these hundreds of people don't each have complete control over every bit of real estate of the component.
Re: (Score:2)
"Anonymous Coward tells people not the use the secure RNG available to them". What could possibly go wrong?
Re: (Score:2)
No offence, but I'm not convinced you or anyone else would notice, or publicize it if you did.
Detecting such a back door could be hard. Maybe there is something the NSA knows about RNGs that you don't. Maybe what the fab produces isn't exactly what you drew in your CAD package. Maybe you are just lying, like the people working for RSA did. It's impossible for the rest of us to know either way.
That's why it is always a good idea to use multiple sources of entropy. Even if some of them do have backdoors the o
Re: (Score:2)
Re: (Score:2)
>Are the real RNG's out there so cost prohibitive?
No a real RNG on a modern silicon process takes only a tiny sliver of silicon and a few very smart designers and at least one very smart cryptographer.
Re: (Score:2)
Re: (Score:2)
Hardware RNGs are in the same boat. Was it subverted by the manufacturer? Does it have a subtle bias we haven't discovered yet? Can it be biased by external conditions?
Re: (Score:2)
There are a couple of issues with hardware RNGs
1: Pretty much every hardware RNG will have biases in the output. So you still tend to end up needing a prng-like layer to clean things up.
2: If the RNG is integrated into a processor or similar (which is the only way it will gain mass deployment) then it raises the question of whether you trust the processor vendor to implement it properly and without the influence of the spooks. The more paranoid members of the crypto community don't trust hardware vendors th
Re: (Score:2)
They are pretty cheap, and there are a number of projects on the web if you fancy building your own. The problem is that you need more than one, because relying on a single source of randomness is a bad idea. They need to be different types too, in case the non-randomness is systemic.
I suppose that's why there are so few commercial solutions. For them to be used seriously in encryption they would have to be sold as "you need this and a couple of our competitors' products too".
Random numbers are so random (Score:2)
Best random number generators are impervious to statistics [dilbert.com]