Follow Slashdot blog updates by subscribing to our blog RSS feed


Forgot your password?
Security Encryption United States Government News

New NSA-Approved Encryption Standard May Contain Backdoor 322

Hugh Pickens writes "Bruce Schneier has a story on Wired about the new official standard for random-number generators the NIST released this year that will likely be followed by software and hardware developers around the world. There are four different approved techniques (pdf), called DRBGs, or 'Deterministic Random Bit Generators' based on existing cryptographic primitives. One is based on hash functions, one on HMAC, one on block ciphers and one on elliptic curves. The generator based on elliptic curves called Dual_EC_DRBG has been championed by the NSA and contains a weakness that can only be described as a backdoor. In a presentation at the CRYPTO 2007 conference (pdf) in August, Dan Shumow and Niels Ferguson showed that there are constants in the standard used to define the algorithm's elliptic curve that have a relationship with a second, secret set of numbers that can act as a kind of skeleton key. If you know the secret numbers, you can completely break any instantiation of Dual_EC_DRBG."
This discussion has been archived. No new comments can be posted.

New NSA-Approved Encryption Standard May Contain Backdoor

Comments Filter:
  • umm (Score:5, Interesting)

    by superwiz ( 655733 ) on Thursday November 15, 2007 @02:23PM (#21367509) Journal

    Don't look for malice where incompetence will do.

    -- Napoleon
    • Re: (Score:2, Insightful)

      by Anonymous Coward
      This is the NSA, not the FBI.
    • Re:umm (Score:5, Insightful)

      by bhima ( 46039 ) <> on Thursday November 15, 2007 @02:27PM (#21367599) Journal
      But this is the NSA we're talking about... Not the Bush administration.
      • by iknownuttin ( 1099999 ) on Thursday November 15, 2007 @02:57PM (#21368165)
        But this is the NSA we're talking about... Not the Bush administration.

        I wish I could remember the show I saw. But the scientist (MIT, PhD scientist) was amazed at the intellect of the NSA folks who came to see him about his research. I can't remember who it was - it was a NOVA episode (but it stuck in my head because of his fear!). And after talking to friends who work with various internet security companies and defense contractors, I have to reiterate their opinion of these guys - they're really sharp. And as much as I like to disparage Government workers, these guys aren't to be trifled with.

        And, as I was previewing, I noticed that the parent was moderated "Offtopic".

        As an Offtopic note: 2 out of 3 down mods that I meta mod are unfair. Keep that in mind. It's really pissing me off.

        • Re: (Score:2, Insightful)

          by failedlogic ( 627314 )
          If you find out the episode, please reply to this thread. I'd be interested in watching it (and its likely on Youtube which will make it easy to watch or my public library will have it).
        • by non ( 130182 )
          perhaps you've heard of Robert Morris? []
        • by Bearhouse ( 1034238 ) on Thursday November 15, 2007 @03:50PM (#21369001)
          Agree with both.

          1. CIA=sharp, Academe=smart. The NSA boys are both smart and sharp. They've got the budget.
          Wonder when the 'super brains' from Google will get into crypto? They have the market cap now - thanks to the inexplicable hype over Android...
          2. Yup - I tend to metamod the -ve mods as 'unfair', because they seem to be driven by bigotry than than sense.

          So, inserting one trapdoor? Likely, but not probable. Insert an easy one to find, so we miss the that's smart 'n' sharp
        • by mveloso ( 325617 )
          Has anyone done an analysis of the other algorithms? Could be that this one is iffy enough that everyone will use the other ones...which have issues that are more difficult to find.
          • by aproposofwhat ( 1019098 ) on Thursday November 15, 2007 @08:46PM (#21372707)
            I think the point of Schneier's article is that everybody (i.e. everybody who means anybody in terms of cryptoanalysis) has crawled over each algorithm, and there's only one that has failed the peer review.

            It's somewhat surprising that an algorithm with a documented flaw made it through to the standard, but Schneier makes it clear that the NSA pressured NIST to let it through, so there are grounds for concern.

    • Re:umm (Score:4, Insightful)

      by niceone ( 992278 ) * on Thursday November 15, 2007 @02:27PM (#21367615) Journal
      Either way best not use Dual_EC_DRBG.

      And if it is incompetence, in this case the malice can come later if anyone ever figures out the 'secret numbers'.
      • Re: (Score:2, Insightful)

        by nuzak ( 959558 )
        > Either way best not use Dual_EC_DRBG.

        I'm pretty sure that if they backdoored one, they backdoored them all. Best to not use any of the new algorithms, period.
        • Re:umm (Score:5, Insightful)

          by bhima ( 46039 ) <> on Thursday November 15, 2007 @02:37PM (#21367799) Journal
          How do you back door an Open algorithm you didn't design and don't distribute?
      • Re: (Score:2, Funny)

        by Anonymous Coward
        1 2 3 4
    • Re:umm (Score:4, Interesting)

      by someone1234 ( 830754 ) on Thursday November 15, 2007 @02:47PM (#21367995)
      The weakness of the encryption is not incompetence.
      The incompetence is that they failed to hide it.
      • by Anonymous Coward on Thursday November 15, 2007 @03:43PM (#21368875)
        There is another explanation; difference of opinion between management and staff

        - Management wants a backdoor in public standard, orders their very smart math geeks to make it so
        - Math geeks say it can't be done
        - Management insists
        - Math geeks go away and come up with something out of left field that technically fulfils the request of management, knowing it's vulnerabilities. They probably tell management that their solution is the best they could do, but it still has all the following problems (slow, crypto-nerds will see through it sooner or later, etc)
        - Management hears the 'best' and 'done' part, discounts possibility of anyone outsmarting their 'uber-elite' NSA math geeks

        predictable results follow.
    • Why bother looking, when the NSA's malicious incompetence (at respecting the Constitution - they're excellent at invading privacy) is already proven beyond doubt?

      Don't look for excuses where criminal convictions will do much better.
    • When the backdoor has been exposed and they continue to promote it, I think the balance of probabilities begins to shift.
    • Re:umm (Score:5, Insightful)

      by sacrilicious ( 316896 ) on Thursday November 15, 2007 @03:46PM (#21368949) Homepage
      Don't look for malice where incompetence will do.

      Don't tolerate incompetence.

      Especially when the party involved should know better, and when there's a lot at stake.

      • Re: (Score:3, Informative)

        by Anonymous Coward
        And when there's a lot at stake, don't blame ignorance, but greed.
        USA has done these things before. Just google for Crypto AG.
    • Kudos to Bruce Schneier for being a respected voice of reason and (seen to be) a disinterested party to critically analyze the strengths and weaknesses of what will be a backbone of computing (and, indeed, our daily lives).

      If I were the NSA trying to work in a back door, instead of coming up with a subtle flaw in the algorithm, I'd get Bruce Schneier to publicly praise an algorithm known to have flaws, while simultaneously offering to pay him a gajillion bucks and threatening his family if he refuses. That
  • by Verteiron ( 224042 ) on Thursday November 15, 2007 @02:25PM (#21367567) Homepage
    Anyone else reminded of the little Black Box from Sneakers? The one that used a mathematical backdoor to break any encryption based on a certain algorithm that was only used in the USA?
    • by Shakrai ( 717556 ) * on Thursday November 15, 2007 @02:48PM (#21368007) Journal

      Anyone else reminded of the little Black Box from Sneakers? The one that used a mathematical backdoor to break any encryption based on a certain algorithm that was only used in the USA?

      More to the point, anyone else remember the premise of that movie? That said black box was utterly useless for doing anything other then spying on Americans, which (prior to Dubya anyway) was outside of the NSAs mandate.

    • Re: (Score:3, Interesting)

      Of course the truly paranoid individual would realize that the backdoor in Dual_ECD_RBG was merely an "obvious" decoy designed to herd us all onto the other three which also have backdoors. ;) (not to make light of what Mr. Schneier's point - the NSA has every reason to deny others effective cryptographic tools)
    • Anyone else reminded of the little Black Box from Sneakers?

      It's a movie. A movie. Ya know, fiction.

  • Is what is essentially a random number generator really an 'encryption' standard? And if it's really a backdoor, don't you still need to know rather quite a bit more than the random number seeds to break something like AES or RSA?
    • by orclevegam ( 940336 ) on Thursday November 15, 2007 @02:31PM (#21367691) Journal
      This seems to be more an issue with something like SSL in which the security of the system is reliant on not being able to guess the next number out of the PRNG.
    • by ioshhdflwuegfh ( 1067182 ) on Thursday November 15, 2007 @02:34PM (#21367745)
      What happens in the article is that one of the algorithms proposed by NSA for standardization contains possibly a major backdoor because the constants it uses to generate numbers are such that there might be other constants, unknown by looking at the algorithm itself but nevertheless possibly known to the authors at NSA that allow to get the whole generated sequence of numbers based on only 32 byte sequence of generated numbers. Maybe or maybe not, depending on whether there are such constants, which only NSA knows.
    • by starfishsystems ( 834319 ) on Thursday November 15, 2007 @02:48PM (#21368021) Homepage
      Randomness is absolutely at the heart of cryptography. So yes, to answer your question, it does matter.

      If I can predict the value of a symmetric key, or the value whose two factors constitute an asymmetric key pair, I have effectively broken the encryption. Even supposing that I can't do this deterministically, but merely somewhat better than random, I'm still that much further ahead.

      • Why not use the encryption as-is, but swap out the random number generator with something else?

        I've always wondered why random number generators don't pull values from an A/D converter hooked to a white noise generator or Lorenz attractor or some such.

    • by peacefinder ( 469349 ) <> on Thursday November 15, 2007 @04:13PM (#21369315) Journal
      starfishsystems gives a good answer, but I'll say it a bit differently in case it helps.

      The random number generator in question is a mathematical tool for generating randomness, not a cryptosystem of any kind. It has many potential applications. However, modern cryptography is absolutely dependent on high-quality randomness, so cryptosystems tend to use exactly this sort of tool. The thing is, if the "random" data stream one uses in a cryptosystem is actually predictable, then the whole cryptosystem is insecure right from the start no matter how good it otherwise appears.

      It's is very much analagous to building a house on sand: if the foundation is unstable, it pretty much doesn't matter how good the rest of the construction on top of it may be; the whole structure is in dire and immediate peril.

      The random number generator itself may be just fine for many applications. However, any cryptosystem built on this random number generator is presumed to be useless just because there exists a set of keys which can easily predict the whole random number stream given a tiny part of it. We don't actually know if anyone holds the keys, but if someone does then that person could undetectably open any cryptographic locks built on this random number generator, or release the keys so everyone could open the locks.

      That help?
  • From TFA: (Score:5, Informative)

    by Spy der Mann ( 805235 ) <spydermann.slash ... minus cat> on Thursday November 15, 2007 @02:31PM (#21367697) Homepage Journal

    NIST intentionally put a backdoor in this PRNG

    The prediction resistance for this PRNG (as presented in NIST-SP800-90) is dependent on solving one instance of the elliptic curve discrete log problem.
    (And we do not know if the algorithm designer knew this beforehand.)

    On the last slide, the researchers add some suggestions:

    Truncate off more than the top 16 bits of
    the output block.
    - Results on extractors from x coordinates of
    EC points of prime curves suggest truncating
    off the top bitlen/2 bits is reasonable.
    * Generate a random point Q for each
    instance of the PRNG.
    • Re:From TFA: (Score:5, Interesting)

      by Saint Aardvark ( 159009 ) * on Thursday November 15, 2007 @02:34PM (#21367753) Homepage Journal
      And this bit from Bruce's article:

      If this story leaves you confused, join the club. I don't understand why the NSA was so insistent about including Dual_EC_DRBG in the standard. It makes no sense as a trap door: It's public, and rather obvious. It makes no sense from an engineering perspective: It's too slow for anyone to willingly use it. And it makes no sense from a backwards-compatibility perspective: Swapping one random-number generator for another is easy.

      My recommendation, if you're in need of a random-number generator, is not to use Dual_EC_DRBG under any circumstances. If you have to use something in SP 800-90, use CTR_DRBG or Hash_DRBG.

      In the meantime, both NIST and the NSA have some explaining to do.

  • I wonder how long it'll be before that "skeleton key" becomes public knowledge and makes the entire encryption scheme more worthless than it already is.
    • by bhima ( 46039 )
      This is just one part of a well designed system and I'd say all of this part it is already useless.
  • T-shirts (Score:5, Funny)

    by hoggoth ( 414195 ) on Thursday November 15, 2007 @02:33PM (#21367733) Journal
    secret numbers appearing on T-shirts in Finland in 3.. 2.. 1..

  • They're in the business of national security. That's generally at odds with personal security and liberty. Those who would trust such a product from them are suckers.

    • That would explain why SELinux isn't widely used.
    • by kebes ( 861706 ) on Thursday November 15, 2007 @02:53PM (#21368107) Journal

      They're in the business of national security. That's generally at odds with personal security and liberty. Those who would trust such a product from them are suckers.
      The problem is that this flaw is a much bigger threat to national security than to personal security. These "official recommendations" from the NSA are used to form official policies and guidelines in just about every branch of government (FBI, CIA, DOD, etc.).

      So, if the NSA was indeed intentionally creating a backdoor, then they were doing a disservice to the "national security" they are supposedly protecting. By allowing (encouraging, in fact) top-secret government data to be encrypted in this way, they would be making the nation's secrets quite vulnerable. By comparison, private citizens and corporations can use whatever encryption they like, regardless of NSA recommendations.

      I suppose one could argue that the NSA thought that no one would figure it out, so that they (and they alone) would be able to break that encryption for all time (so that they can spy on other branches of the government?). I think a simpler explanation is that NSA just made a mistake in endorsing that algorithm, and never intended to threaten national security. Of course it will be interesting to see what position they take now that a flaw has been publicly identified.
  • Fix (Score:4, Informative)

    by daveschroeder ( 516195 ) * on Thursday November 15, 2007 @02:35PM (#21367761)
    "It's possible to implement Dual_EC_DRBG in such a way as to protect it against this backdoor, by generating new constants with another secure random-number generator and then publishing the seed. This method is even in the NIST document, in Appendix A. "
  • by SlipperHat ( 1185737 ) on Thursday November 15, 2007 @02:35PM (#21367773)
    Should use the one that is hardest to break. If the NSA thinks elliptic curves are the best, only the NSA should use it. Let's see how happy they are having their own "unbreakable" code just for them.

    Personally, I wish the NSA was a bit more chivalrous when it comes to these kind of things. If it is your **JOB** to break codes, why whine when people pick the one that is hardest to break. The rest of the world doesn't have the luxury to pick how hard their job gets to be, so why should you?

    The NSA is like an anti-virus / a pharmaceutical company where a cure is only good if it's in the company's best interests. Not to say that anti-virus / pharmaceutical companies are not ethical. But there is a saying along the lines of "If you can't come up with the solution, there is good money to be made in the problem."
  • Trust the Spies (Score:5, Insightful)

    by Doc Ruby ( 173196 ) on Thursday November 15, 2007 @02:45PM (#21367967) Homepage Journal
    The NSA is spying on all telecom signals passing through the US (including this message. Hi, Dick Cheney!). Despite the Constitution's prohibitions. Why would you trust them not to make your crypto crackable?

    This situation shows one of the strongest arguments for open source. Trust no one.
    • Re: (Score:3, Funny)

      by caluml ( 551744 )
      -----BEGIN PGP MESSAGE-----
      Version: GnuPG v1.4.6 (GNU/Linux)

      -----END PGP MESSAGE-----

      This is secure. The password is foo. Let's have a symmetrically encrypted discussion using GPG. All passwords are foo.
  • by FranTaylor ( 164577 ) on Thursday November 15, 2007 @02:46PM (#21367971)
    Sessions can be recorded and cracked later when cpu is even more plentiful.

    Encryption keys can be demanded by the government, they'll throw you in jail for not complying.

    Keep your dirty laundry out of your computer.

    The government doesn't think that your data is something that should be protected from unreasonable search, you shouldn't either.

  • All you need are more lava lamps. []
  • by rilister ( 316428 ) on Thursday November 15, 2007 @02:49PM (#21368037)
    I can't be the only one who clicked on the link and was astonished to see:
    "On the Possibility of a Back Door in the NIST SP800-90 Dual Ec Prng - by Dan Shumow, Niels Ferguson, Microsoft"

    Microsoft are exposing this? Are they funding the group making these kind of claims? If this was true, wouldn't this intensely annoy the NSA to have this exposed? Am I missing something here? .

    - I see the disclaimer ("What we are NOT saying") where they seem to be saying - "No way did the NSA intentionally make this broken - maybe it was an errant developer and maybe they knew what they were doing", but it amounts to the same thing, surely?
    • by jbf ( 30261 ) on Thursday November 15, 2007 @03:17PM (#21368485)
      Well I'm not surprised. Microsoft Research has tons of sharp security guys working there. Niels Ferguson is quite well-known in security circles. You don't get your company's name as an "author" unless your employees actually did the work; funding is not good enough. It might annoy the NSA, but academics don't care that much.
  • RNG problems in xp/2k? Isn't the POINT of encryption to defeat/make EXTREMELY difficult the work undertaken by snoops?

    Maybe they need to listen to Mylene Farmer's "Fuck them all"...

    "Fuck Them All" is better than any Madonna song...heheh []

    "Hey bitch, you're not on the list. You wish. You suck. You bitch. What's your name again? Hey bitch, you're not on the list. You bitch, you're not on the list. You wish. You suck, you bitch."

    Well, Pardon her French.
  • Just look what they did with the telcos. The administration knew that it couldn't just go and force the telcos to install their drag net hardware to sweep up each and every electronic communication of ordinary Americans.

    So what did they do? Instead of ordering the telcos to do it, we now know that they paid them to do it.

    Would it be at all surprising if we were to find that the Bush administration also plans to pay crypto hardware manufacturers to install backdoors to allow them to better snoop on ordinary
  • Does the term "NSA Key" ring a bell for anyone?

    It should come as no surprise that the NSA want to read your communications. The U.S.A. is the new oppressive state. Shredding the constitution at lightening speeds. Between spying, being labeled as an enemy combatant, gitmo, and rendition, could someone tell me why I should fear the terrorists more than my own government?

    Hell, they want prison time for copyright violation, and they haven't even ironed out an exact definition of copyright infringement. "Fair Us
    • Does the term "NSA Key" ring a bell for anyone?

      I'm not saying that there isn't/wasn't an NSA-requested backdoor in Windows, however I'm sure that they wouldn't make it obvious by calling it NSAKEY (most likely, it would have been sneaked in as an undocumented API).

      • I'm not saying that there isn't/wasn't an NSA-requested backdoor in Windows, however I'm sure that they wouldn't make it obvious by calling it NSAKEY (most likely, it would have been sneaked in as an undocumented API).

        If you remember clearly, you will recall that it was an accident that the information was released. Normally various symbol names are stripped from the SDK/DDK. By accident, one release had the symbols intact.

        Then all sorts of bizarre explanation came out of Microsoft, my favorite was that it
  • by ColaMan ( 37550 ) on Thursday November 15, 2007 @02:58PM (#21368199) Journal
    The NSA is a lot more competent than you think.
    Go google "NSA DES" sometime.

    "The NSA was embroiled in controversy concerning its involvement in the creation of the Data Encryption Standard (DES), a standard and public block cipher used by the US government. During development by IBM in the 1970s, the NSA recommended changes to the algorithm. There was suspicion the agency had deliberately weakened the algorithm sufficiently to enable it to eavesdrop if required. The suspicions were that a critical component -- the so-called S-boxes -- had been altered to insert a "backdoor"; and that the key length had been reduced, making it easier for the NSA to discover the key using massive computing power, although it has since been observed that the changes in fact strengthened the algorithm against differential cryptanalysis, which was not publicly discovered until the late 1980s."

    So they made some small changes to DES... then a *decade* later, the rest of the crypto world says, "Huh. We've just done the sums and that actually made it better."

    Not to say that in this case they're just screwing with the algorithm though :-P
  • Clipper Chip (Score:4, Informative)

    by starfishsystems ( 834319 ) on Thursday November 15, 2007 @02:59PM (#21368213) Homepage
    I'm getting a distinct feeling of déjà vu about this. Anyone remember the Clipper Chip []? Key escrow? Same basic idea, and that proposal came out of the NSA as well. Only then the backdoor was explicit.

    The crypto community spoke out strongly against it, and the proposal, despite having a great deal of political muscle behind it, did not fly very far. Another sensible reason for its failure to gain acceptance was that it would have had no chance of success on the international market. Even if domestic use could have been forced through legislation, let's say, no other nation with a clue would pick it up.

  •   I guessing the elliptical basis PRNG was only included to allow for a checkmark to be put on a list for the requirements - "ensure there is a simple method to bypass security for agencies that have clearance to do so" or similar. This smacks of a top-down request, mathematically, it's a ludicrous concept to rely on for practical considerations - if not because of its strength but for its speed in current implementations.

  • More likely it can already be easily cracked.

    Or maybe they know we know that and are using a double bluff? or that could be a bluff as they will know that we know what they know we will know.

  • by Sloppy ( 14984 ) on Thursday November 15, 2007 @03:09PM (#21368345) Homepage Journal

    I see how it could be a problem for embedded work. But on personal computers, which nowdays have tremendously abundant resources, why not use multiple algorithms and entropy sources to build your pool? (Yes, I know some systems already do this.) NSA may be able to predict one sequence, but they sure as hell can't predict a bunch of them, XORed. They'd need mathematicians to crack all the RNGs, have a camera on your lava lamp, a microphone listening to the room, a tap on your power line, etc. By the time they do all of that, they might as well have just asked you what your plaintext is.

  • This is why when Im communicating with my business associates in Columbia, or reporting to my controller in Moscow .. we choose to always stick with the good old one time pad.

    Tiny little yellow Post-it-notes still beats elliptical curves anyday.
  • They totally got the idea from Digital Fortress [].

    So does that mean the NSA really does have a 3 million processor supercomputer? I find the individually soldered in by hand part hard to believe (not to mention everything else in dan brown books).
  • N.S.A. already owns the patent to DES and the whole point of that was have a backdoor when Clipper failed to pass.

    You also know that N.I.S.T. [] is a front for N.S.A. too right? Of course there's a backdoor.

    This and other stories are available in the latest issue of DUH!
  • by The Real Nem ( 793299 ) on Thursday November 15, 2007 @03:49PM (#21368977) Homepage

    In my final year in CS, I wrote a lengthy paper researching various DRBGs. To my surprise, there were very few good candidates for cryptographic DRBGs, but of the 7 I looked at, Dual_EC_DRBG rated the worst. I was unable to find any theoretic proofs for Dual_EC_DRBG, but I did find a few papers exposing serious flaws in Dual_EC_DRBG including this one [] which describes a tractable distinguisher so efficient it can run on a modest desktop.

    The other three DRBGs recommended by NIST were all reliant on the security of various other cryptographic primitives such as SHA (Hash_DRBG), HMAC (HMAC_DRBG - which is often based on SHA) and AES or 3DES (CRT_DRBG). They were all reasonably obvious, and only really tried to set out some sort of standard for jumbling the output of their respective primitives enough that they would be resilient to any unknown vulnerabilities in said primitives (though certain paths also failed to do this). This was mostly accomplished by calling the primitives several times (HMAC_DRBG with the NIST HMAC implementation called for 6 SHA hashes per SHA sized output) which isn't very efficient.

    I suspect they only included Dual_EC_DRBG because it wouldn't have looked too good if they were unable to come up with a single number theoretic or otherwise novel DRBG. They shouldn't be too disappointed, however, as the only one I was able to find was Blum Blum Shub [] which is terribly inefficient. CryptMT [] (Cryptanalysis []) also deserves a mention as it looks like a promising pseudo-number theoretic DRBG, at least a better candidate than Dual_EC_DRBG.

  • by peacefinder ( 469349 ) <> on Thursday November 15, 2007 @03:57PM (#21369107) Journal
    I thought the article was saying something slightly different: The standard does have a backdoor, it's just not clear who - if anyone - holds the keys.

    The safe assumption is that someone does hold the keys and therefore the standard is useless for cryptography, even though it might be just fine for other applications.
  • Rule of thumb: If any agency of the government in any way, shape or form has even the remotest, most tangential, most tenuous link to it, assume it has a backdoor.
  • by guttentag ( 313541 ) on Friday November 16, 2007 @01:38AM (#21375121) Journal
    "Mr. Potato Head? Mr. Potato Head! Back doors are not secrets!"

10.0 times 0.1 is hardly ever 1.0.