Slashdot Mirror

← Back to Stories (view on slashdot.org)

NIST Removes Dual_EC_DRBG From Random Number Generator Recommendations

Posted by Soulskill on from the cryptic-announcement dept.

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."

86 comments

  1. Trust... by Anonymous Coward · · Score: 3, Insightful

    ... So much more easily lost than won. How is anyone supposed to take these new recommendations seriously?

  2. Random by sexconker · · Score: 1

    I really wish people would stop using the word "random" for things that are anything but.

    1. Re:Random by Anonymous Coward · · Score: 0

      Nothing is random. Nothing. And yet, you understand what it means.

    2. Re:Random by PRMan · · Score: 1

      That comment was random...

      --
      Peter predicted that you would "deliberately forget" creation 2000 years ago...
    3. Re:Random by Anonymous Coward · · 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.

    4. Re:Random by Bite+The+Pillow · · Score: 1

      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.

    5. Re:Random by sexconker · · Score: 1

      "Pseudorandom" isn't correct either. There is nothing random about the numbers.
      They're just statistically flat.

  3. Obligatory XKCD by Russ1642 · · Score: 3, Funny

    http://xkcd.com/221/

    1. Re:Obligatory XKCD by Anonymous Coward · · Score: 0

      Damn you! I wanted to post the same incredibly insightful and witty link!

    2. Re:Obligatory XKCD by Anonymous Coward · · Score: 0

      Then pick another comic at random.

      http://xkcd.com/1210/

  4. Cut off your nose to spite your face by Anonymous Coward · · 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.

    1. Re:Cut off your nose to spite your face by erikkemperman · · 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?

      --
      Gosh, thanks. That must be why the other ships call me Meatfucker -- GCU Grey Area (Eccentric)
    2. Re:Cut off your nose to spite your face by cold+fjord · · 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 person or group that created the values used in curve would know it and how to exploit it. If a backdoor exists for a particular set of curve values identifying it isn't easier than the original problem. It looks the same either way with or without a backdoor. People have been making exaggerated claims based on this ambiguity.

      --
      much of left-wing thought is a kind of playing with fire by people who don't even know that fire is hot - George Orwell
    3. Re:Cut off your nose to spite your face by kasperd · · Score: 1

      The weakness in Dual_EC_DRBG is publicly known.

      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.

      --

      Do you care about the security of your wireless mouse?
    4. Re:Cut off your nose to spite your face by cold+fjord · · Score: 0

      There is no evidence that a backdoor actually exists, only that one is possible with the technology. You can't tell if one exists or not just from the published specification. The only people that would know if one exists are the people that created the curve values.

      --
      much of left-wing thought is a kind of playing with fire by people who don't even know that fire is hot - George Orwell
    5. Re:Cut off your nose to spite your face by fustakrakich · · Score: 2

      With any state authority these days, as their true nature slowly becomes exposed, you have to assume the worst.

      --
      “He’s not deformed, he’s just drunk!”
    6. Re:Cut off your nose to spite your face by erikkemperman · · Score: 4, 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 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.

      --
      Gosh, thanks. That must be why the other ships call me Meatfucker -- GCU Grey Area (Eccentric)
    7. Re:Cut off your nose to spite your face by cold+fjord · · 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.

      --
      much of left-wing thought is a kind of playing with fire by people who don't even know that fire is hot - George Orwell
    8. Re:Cut off your nose to spite your face by kasperd · · Score: 1

      There is no evidence that a backdoor actually exists, only that one is possible with the technology.

      • Using asymmetrical primitives to build a PRNG is suspicious, since a PRNG can be build from symmetrical primitives, but placing a backdoor which can be used by yourself but not by others requires asymmetrical primitives.
      • Long before DECDRBG was published it was well established among cryptographers, that you document where your constants came from, and that any constant which is not justified is by default assumed to be a backdoor.
      • It is fully documented how the constants in DECDRBG could have been obtained with a backdoor, and to this date this date no other explanation for the exact value of the constant has been given.
      • Leaked documents suggest that NSA has been actively working on planting backdoors in cryptographic standards.

      To me that is more than sufficient evidence to assume DECDRBG to have a backdoor. A deliberately placed backdoor definitely is the most likely explanation for the structure of DECDRBG. By now there is really only one additional piece of information, which could change that picture, and that would be the actual calculations that were used to produce the constants.

      --

      Do you care about the security of your wireless mouse?
    9. Re:Cut off your nose to spite your face by fustakrakich · · Score: 0

      Sorry man, trust is gone. You can't regain your virginity.

      --
      “He’s not deformed, he’s just drunk!”
    10. Re:Cut off your nose to spite your face by erikkemperman · · Score: 4, 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.

      --
      Gosh, thanks. That must be why the other ships call me Meatfucker -- GCU Grey Area (Eccentric)
    11. Re:Cut off your nose to spite your face by cold+fjord · · 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!"

      --
      much of left-wing thought is a kind of playing with fire by people who don't even know that fire is hot - George Orwell
    12. Re:Cut off your nose to spite your face by cold+fjord · · 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 or not. And that is where the controversy comes in.

      --
      much of left-wing thought is a kind of playing with fire by people who don't even know that fire is hot - George Orwell
    13. Re:Cut off your nose to spite your face by cold+fjord · · 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 that cracked other methods. The people that refused to use DES and used those other methods were unknowingly using weaker encryption due simply to their suspicions. Operating by suspicion can be hazardous when it comes to encryption. Of course the flip side is true too, as the Ultra cracks of Enigma showed.

      --
      much of left-wing thought is a kind of playing with fire by people who don't even know that fire is hot - George Orwell
    14. Re:Cut off your nose to spite your face by erikkemperman · · Score: 4, 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.

      --
      Gosh, thanks. That must be why the other ships call me Meatfucker -- GCU Grey Area (Eccentric)
    15. Re:Cut off your nose to spite your face by cold+fjord · · 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.

      --
      much of left-wing thought is a kind of playing with fire by people who don't even know that fire is hot - George Orwell
    16. Re:Cut off your nose to spite your face by gweihir · · Score: 1

      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.

      --
      Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.
    17. Re:Cut off your nose to spite your face by David+Jao · · Score: 2

      I'm a crypto researcher specializing in elliptic curves. I don't think you understand the math behind Dual_EC_DRBG. The evidence that a backdoor exists is incontrovertible. The only question is who, if anyone, knows what the backdoor is.

    18. Re:Cut off your nose to spite your face by cold+fjord · · 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?

      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 techniques. Choosing a new set of known good constants for the standard would resolves all the issues other than performance. Of course that would mean you would need to verify the new configuration was still good and generated proper numbers. (And no matter what you do there will be people that mistrust it, just as this thread started.)

      Paranoia can be a useful factor in dealing with security, but it should be moderated and harnessed in a positive manner. If not you end up making mistakes due to poor judgment as I discussed in my other post on DES. You assume the worst case, flop around and make an ever worse choice.

      --
      much of left-wing thought is a kind of playing with fire by people who don't even know that fire is hot - George Orwell
    19. Re:Cut off your nose to spite your face by cold+fjord · · 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 don't do it from the start. An unknown "backdoor" that is as hard or harder to solve than the original math problem isn't really what you could call a backdoor in conventional terms, is it?

      Conclusions about Dual_EC_DRBG

      The bias in the output mentioned earlier is concerning, but there are no known attacks against Dual_EC_DRBG unless you have pre-existing knowledge of the relationship between P and Q. In other words, this backdoor (if true as alleged) allows the NSA to break Dual_EC_DRBG but does not make it much vulnerable to anyone else. This is much different than a backdoor password which would be immediately usable by any adversary who discovered it (e.g. by reverse engineering the code).

      On the Possibility of a Back Door in the NIST SP800-90 Dual Ec Prng

      --
      much of left-wing thought is a kind of playing with fire by people who don't even know that fire is hot - George Orwell
    20. Re:Cut off your nose to spite your face by David+Jao · · Score: 2

      A deterministic random bit generator has no need for even a possiblility of a backdoor. Ever. We're not talking about encryption where there needs to be a backdoor so that one person (the legitimate recipient) can decrypt the communication. Also, most experts in the field, including myself, hold the subjective opinion that it is very unlikely there could be any innocent explanation for the existence of the possibility of a backdoor. There are many other much more straightforward designs for deterministic random bit generators that provably contain no possibility of a backdoor under standard number-theoretic assumptions. You cannot reasonably compare this situation to DES. Symmetric key cryptography doesn't come with security proofs. Public-key cryptography primitives are a completely different ballgame.

    21. Re:Cut off your nose to spite your face by cold+fjord · · 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 to DES because the issue in question is the same in both cases: trust in the body creating the standard. The fact that they are different types of encryption is meaningless. Either NSA did or didn't backdoor DES. Either NSA did or didn't backdoor Dual_EC_DRBG. There is now enough accumulated knowledge and evidence to say that they didn't backdoor DES. We may never know about Dual_EC_DRBG. Suspicion is reasonable, claims of knowledge aren't unless you worked at NSA on that standards effort unless you want to say you "just know."

      --
      much of left-wing thought is a kind of playing with fire by people who don't even know that fire is hot - George Orwell
    22. Re:Cut off your nose to spite your face by Anonymous Coward · · Score: 0

      The problem isn't the algorithm. The "problem" is specifically a question of trust in how the constants for the curve were developed.

      The problem is the algorithm. The simple fact the constants can be generated in such a way as to provide a backdoor makes the algorithm problematic. The fact that it is impossible to check whether those constants were generated in such a way makes the algorithm even more problematic.

      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.

      There was no such open process. The constants were provided by the NSA with no explanation as to how they were obtained.

      The fact that they are different types of encryption is meaningless.

      Translation: facts don't matter.

      Either NSA did or didn't backdoor DES. Either NSA did or didn't backdoor Dual_EC_DRBG.

      In the absence of any probability estimates ascribed each event, these sentences are tautologies and carry no meaningful information.

    23. Re:Cut off your nose to spite your face by Anonymous Coward · · Score: 0

      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.

      Great words from someone who think saying "it doesn't pass the smell test." is the same as providing evidence.

    24. Re:Cut off your nose to spite your face by cold+fjord · · Score: 1

      You should have read the next line. Apparently you aren't there yet.

      Once you understand that you can apply your suspicions.

      --
      much of left-wing thought is a kind of playing with fire by people who don't even know that fire is hot - George Orwell
    25. Re:Cut off your nose to spite your face by kasperd · · Score: 1

      You may recall that elliptic curve encryption was thought to be a highly promising encryption technology at the time.

      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.

      --

      Do you care about the security of your wireless mouse?
    26. Re:Cut off your nose to spite your face by sjames · · Score: 2

      No, but it does leave you wondering about the other things they recommended.

    27. Re:Cut off your nose to spite your face by Anonymous Coward · · Score: 0

      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 person or group that created the values used in curve would know it and how to exploit it. If a backdoor exists for a particular set of curve values identifying it isn't easier than the original problem. It looks the same either way with or without a backdoor. People have been making exaggerated claims based on this ambiguity.

      This is why most cryptographic systems base their constants on fundamental mathematical constants (e.g. sequences of digits from near the start of pi or e, or that are easily derived from such constants), because then it would be extremely difficult to select constants that are a back door. It is unfortunate that this wasn't done in this case, but my understanding (based on only a small amount of reading on the subject) is that this is difficult or impossible for elliptical curve cryptography, where there are quite complex constraints on what constants are possible to use in the system design.

      (captcha: "guaranty" ... wtf?)

    28. Re:Cut off your nose to spite your face by Anonymous Coward · · Score: 0

      The simplest encryption, one time pad, has been proven to be absolutely secure and anyone with a bit of a brain can prove themselves it to be secure.

      Your only issue is how to generate the pad and how to give the pad to your counter party.

      Dice will work pretty well for generating small pads (in fact it is a pretty good way of generating high quality public/private key pairs). Small pads can be written down on a piece of paper.

      A quantum random number generator (one photon led/50% mirror/two one photon sensors) is a pretty good way of generating a large amount of random numbers. You could store them on a hard drive or flashcard depending on the size of data you are going to send to the counter party and the ease with which you can pass it physically and securely to your counter party.

      Quantum Cryptography can be used to create the same one time pad in both locations, each bit is separately randomly generated and randomly selected and then negotiated. Quantum Cryptography is actually pretty slow. It is probably just as secure to just drive a station wagon full of hard drives with one time pads to the other location.

    29. Re:Cut off your nose to spite your face by Anonymous Coward · · 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.

    30. Re:Cut off your nose to spite your face by Captain_Chaos · · Score: 1

      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 again...

    31. Re:Cut off your nose to spite your face by cold+fjord · · 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.

      --
      much of left-wing thought is a kind of playing with fire by people who don't even know that fire is hot - George Orwell
    32. Re:Cut off your nose to spite your face by cheesybagel · · Score: 1

      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.

    33. Re:Cut off your nose to spite your face by jittles · · Score: 1

      Sorry man, trust is gone. You can't regain your virginity.

      I'm a born again virgin, you insensitive clod!

    34. Re:Cut off your nose to spite your face by fustakrakich · · 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.

      --
      “He’s not deformed, he’s just drunk!”
    35. Re:Cut off your nose to spite your face by GuB-42 · · Score: 1

      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...

    36. Re:Cut off your nose to spite your face by Anonymous Coward · · Score: 0

      You are pretty much the opposite of a trusted source on the subject.

      Given just the number of words you have written I am pretty much willing to assume that the Dual_EC_DRBG option contains a backdoor.

    37. Re:Cut off your nose to spite your face by Anonymous Coward · · Score: 0

      When it comes to encryption you're either going to trust somebody

      Nope. The two major threats we have are script-kiddies and governments agencies.
      Both of them relies on automatic processes.

      By rolling you own security and encryption it doesn't matter how weak it is or what backdoors it has. It becomes very hard to break through with automations. This means that you get a situation where you have to be specifically targeted by someone who understands cryptography/security to be at risk.

    38. Re:Cut off your nose to spite your face by David+Jao · · Score: 1

      You seem to be suggesting to "keep the standard but change the constants." But there's no way to do that. The standard requires the use of the particular constants specified in the standard. Contrary to what you seem to believe, these constants were not created via an open process. We actually have no idea where these constants came from, but the likeliest candidate is the NSA, simply because if it had come from any other source we would have found out by now. There's no question that using the required values for the constants is just suicidally insane. On the other hand, you can't keep the standard and change the constants, because by using different constants, you are by definition violating the standard. It's like trying to use DES with different constants; well, sure, you can do that, but it's no longer DES.

    39. Re:Cut off your nose to spite your face by cold+fjord · · 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.

      --
      much of left-wing thought is a kind of playing with fire by people who don't even know that fire is hot - George Orwell
    40. Re:Cut off your nose to spite your face by cold+fjord · · 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

      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.

      --
      much of left-wing thought is a kind of playing with fire by people who don't even know that fire is hot - George Orwell
    41. Re:Cut off your nose to spite your face by David+Jao · · Score: 1

      But then you run into the problem that Dual_EC_DRBG is orders of magnitude slower than the other three algorithms contained in the standard. As far as we know, the only good reason to include Dual_EC_DRBG in the first place was because the NSA wanted a backdoor in the standard.

    42. Re:Cut off your nose to spite your face by cold+fjord · · Score: 1

      That doesn't seem to be true.

      The Many Flaws of Dual_EC_DRBG

      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.

      --
      much of left-wing thought is a kind of playing with fire by people who don't even know that fire is hot - George Orwell
    43. Re:Cut off your nose to spite your face by David+Jao · · Score: 1

      It's really not that hard to design a provably secure random number generator without a backdoor. My colleagues at Waterloo did it. Here's another construction. And another. For that matter, you could even backdoor-proof Dual-EC-DRBG itself, by reducing the output rate by 16 to 33%, depending on the curve size (so that it's 5/6th to 2/3rds as fast as before). Any of these choices would be more appropriate than simply keeping the algorithm as-is.

  5. OpenBSD has already removed it by Anonymous Coward · · Score: 2, Interesting

    OpenBSD has already removed that nonsensical algorithm from LibreSSL, has OpenSSL yet??? NOPE!!!!

  6. Not the only change by TechyImmigrant · · Score: 2, 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 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.

    --
    I should use this sig to advertise my book ISBN-13 : 978-1501515132.
    1. Re:Not the only change by TechyImmigrant · · Score: 2

      Oops. I missed the link for the announcement.. here

      --
      I should use this sig to advertise my book ISBN-13 : 978-1501515132.
  7. What's the cost to use a real rng vs psudo by medv4380 · · Score: 2

    I know they can be a bit cost prohibited, but psudo RNG's always look like you're just waiting for them to eventually become broken. Are the real RNG's out there so cost prohibitive?

    1. Re:What's the cost to use a real rng vs psudo by ArcadeMan · · Score: 1

      Not sure if their implementation is better, but VIA seems to have something different and hardware-based.

      If it's truly good, maybe it could be licensed and added to all future Intel, AMD and ARM CPUs?

      --
      Get free satoshi (Bitcoin) and Dogecoins
    2. Re:What's the cost to use a real rng vs psudo by Anonymous Coward · · Score: 0

      Nobody trusts them to not have deliberate weaknesses built into them at the behest of law enforcement or intelligence agencies. At least with software RNG's you can have experts pour over the algorithm and the source code.

    3. Re:What's the cost to use a real rng vs psudo by Anonymous Coward · · Score: 0

      Real hardware RNG was added to Intel Ivy Bridge processors.

      However, the chip is proprietary, which means it cannot be reviewed and therefore, no one can know if Intel could have a backdoor into it.

    4. Re:What's the cost to use a real rng vs psudo by gman003 · · Score: 1

      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.

    5. Re:What's the cost to use a real rng vs psudo by Anonymous Coward · · Score: 0

      An obvious case for an open source hardware project?

    6. Re:What's the cost to use a real rng vs psudo by Anonymous Coward · · Score: 0

      time dd if=/dev/urandom of=/dev/null bs=4096 count=10
      time dd if=/dev/random of=/dev/null bs=4096 count=10

      The first is almost instant, the second, well at 1-2bytes/second you'll be waiting a while unless it's backed by hardware. And - well, can you REALLY trust that hardware.

    7. Re:What's the cost to use a real rng vs psudo by Anonymous Coward · · Score: 0

      I know they can be a bit cost prohibited, but psudo RNG's always look like you're just waiting for them to eventually become broken. Are the real RNG's out there so cost prohibitive?

      Posting as AC to avoid undoing mods... I'm not an expert by any means, but here's what I've heard on the subject:

      My understanding is that real hardware-based random numbers are available, but it's harder to rely on that hardware being available on all platforms. There's also an issue with the speed at which numbers can be generated, which is always going to be slower than a software algorithm. It's also a bad idea to rely exclusively on a single source of randomness, even if it is hardware-based, because of possible hardware defects/biases, software bugs (since the hardware output has to be processed before it's used), or even backdoors (which is considered less tinfoil-hat-ish than it used to be). It's a good idea to mix entropy from as many different sources as possible so as to ensure maximum randomness. This also prevents any one contaminated source from becoming an issue, since xor'ing random + not_so_random = still_random. However, many of these alternatively sources are relatively slow. These sources are often mixed into a general "entropy pool", and libraries can then request true random numbers in limited quantities.

      Often, true random numbers from the entropy pool are used to seed high quality pseudo random numbers. If done properly (that is, the pseudo random algorithm isn't used too long that it's period is exceeded), the end result is just as secure as using all true random numbers, only it scales much more effectively. So, pseudo-random number generators are still very useful, even if hardware-based generators are available.

    8. Re:What's the cost to use a real rng vs psudo by TechyImmigrant · · Score: 2, 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 and personal data security. So if there was a back door, you would find out about it because you could pretty much guarantee that someone would bleat, and justly so.

      --
      I should use this sig to advertise my book ISBN-13 : 978-1501515132.
    9. Re:What's the cost to use a real rng vs psudo by TechyImmigrant · · Score: 1

      >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.

      --
      I should use this sig to advertise my book ISBN-13 : 978-1501515132.
    10. Re:What's the cost to use a real rng vs psudo by belmolis · · Score: 1

      A technique I've seen used for scientific purposes is to run a Zener diode in the high slope region and subtract DC, leaving a residue of quantum noise. I would think that with current technology such a package could be very small and cheap, though I don't know what is involved in reshaping the spectrum from 1/f in hardware.

    11. Re:What's the cost to use a real rng vs psudo by Anonymous Coward · · Score: 1

      It has been suggested that by tampering with the masks late in the process, you could sabotage functionality with very few people being in on it.

    12. Re:What's the cost to use a real rng vs psudo by twistedcubic · · Score: 1

      There is no such thing as a "real" RNG.

    13. Re:What's the cost to use a real rng vs psudo by Bite+The+Pillow · · Score: 1

      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.

    14. Re:What's the cost to use a real rng vs psudo by Anonymous Coward · · 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.

    15. Re:What's the cost to use a real rng vs psudo by Anonymous Coward · · Score: 0

      " There's also an issue with the speed at which numbers can be generated, which is always going to be slower than a software algorithm."

      How come taking one sample takes longer than doing a whole series of manipulations?

    16. Re:What's the cost to use a real rng vs psudo by sjames · · Score: 1

      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?

    17. Re:What's the cost to use a real rng vs psudo by Anonymous Coward · · Score: 0

      There is no such thing as a "real" RNG.

      That depends on your definition of "random". For most of us, the generally accepted definition of "produced or obtained by a random process (and therefore completely unpredictable in detail)" (OED 4th ed, and yes I'm aware the definition is self-referential, but contains enough information to resolve itself) is adequate, and there are several hardware RNGs available that are effectively "completely unpredictable in detail" -- they rely on thermal junction noise, for which there is no known model that predicts it in more detail than a frequency distribution.

      Yes, there are definitions of "random" that cannot be realised within the constraints of a physical universe bounded by actual physical laws, but such definitions don't seem especially useful to me.

      Even most mathematical definitions can be met by hardware RNGs. See, for example, the definition at mathworld.

    18. Re:What's the cost to use a real rng vs psudo by Anonymous Coward · · Score: 0

      Another way is:
      - Single photon pulsing led. Simply a led with lots of filters so it is extremely unlikely that multiple photons can escape at around the same time.
      - 50% mirror angled 45 degrees (beam splitter)
      - Two sensitive photo sensors.

      Some photons will disappear, but you don't care about those. You only care about the ones that are registered by the sensors. You do need to scrub the random numbers to remove bias.

      A really cheap random number generator (but more slower than the one described above) is a webcam pointing at a radio active source that you pull out of a fire alarm. Simply time the distance between to white pixels appearing.

    19. Re:What's the cost to use a real rng vs psudo by petermgreen · · Score: 1

      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 that much.

      --
      note: i'm known as plugwash most places but i screwd up registering that here somehow in the past and now can't register
    20. Re:What's the cost to use a real rng vs psudo by AmiMoJo · · Score: 1

      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 others should help reduce their effectiveness. The on-CPU RNG would need to be combined with other RNGs and PRGNs to be useful.

      --
      const int one = 65536; (Silvermoon, Texture.cs)
      SJW, n: "Someone I don't like, and by the way I'm a fuckwit" - AC
    21. Re:What's the cost to use a real rng vs psudo by AmiMoJo · · Score: 1

      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".

      --
      const int one = 65536; (Silvermoon, Texture.cs)
      SJW, n: "Someone I don't like, and by the way I'm a fuckwit" - AC
    22. Re:What's the cost to use a real rng vs psudo by TechyImmigrant · · Score: 1

      "Anonymous Coward tells people not the use the secure RNG available to them". What could possibly go wrong?

      --
      I should use this sig to advertise my book ISBN-13 : 978-1501515132.
    23. Re:What's the cost to use a real rng vs psudo by mrchaotica · · Score: 1

      See LavaRnd.

      --

      "[Regarding the 'cloud,'] ownership was what made America different than Russia." -- Woz

  8. We locked the door and threw away the passkey by WillAffleckUW · · Score: 0

    Of course we don't have any more passkeys to the other doors, or to the service entrances to the hallway, or the crawlspace for the ventilation.

    That's safe.

    Trust us.

    Oh, and don't you love those shiny new chips that are proprietary?

    --
    -- Tigger warning: This post may contain tiggers! --
  9. It's broken and disabled by Anonymous Coward · · Score: 1

    The implementation didn't work anyway and it looks like they disabled it. Announcement on their mailing list.

  10. Random numbers are so random by Celarent+Darii · · Score: 1

    Best random number generators are impervious to statistics

  11. There is a german word for it by Anonymous Coward · · Score: 0

    Schnellmerker

  12. NIH too removed a recommendation by Anonymous Coward · · Score: 0

    NIH removing cigarettes as a recommended cure for throat and lung cancer