Forgot your password?
typodupeerror
Encryption

Dual_EC_DRBG Backdoor: a Proof of Concept 201

Posted by Soulskill
from the this-is-how-we-do-it dept.
New submitter Reliable Windmill sends this followup to the report that RSA took money from the NSA to use backdoored tech for random number generation in encryption software. From the article: "Dual_EC_DRBG is an pseudo-random number generator promoted by NIST in NIST SP 800-90A and created by NSA. This algorithm is problematic because it has been made mandatory by the FIPS norm (and should be implemented in every FIPS approved software) and some vendors even promoted this algorithm as first source of randomness in their applications. If you still believe Dual_EC_DRBG was not backdoored on purpose, please keep reading. ... It is quite obvious in light of the recent revelations from Snowden that this weakness was introduced by purpose by the NSA. It is very elegant and leaks its complete internal state in only 32 bytes of output, which is very impressive knowing it takes 32 bytes of input as a seed. It is obviously complete madness to use the reference implementation from NIST"
This discussion has been archived. No new comments can be posted.

Dual_EC_DRBG Backdoor: a Proof of Concept

Comments Filter:
  • Bah (Score:3, Interesting)

    by colinrichardday (768814) <colin.day.6@hotmail.com> on Wednesday January 01, 2014 @03:17PM (#45838767)

    Who can you trust?

    • Amish (Score:5, Funny)

      by Anonymous Coward on Wednesday January 01, 2014 @03:34PM (#45838915)

      shun anything electronic, or electric for that matter. Substinance farm and read dead-tree books for leasure.

    • Whom?
    • Re: (Score:3, Funny)

      by Anonymous Coward

      Ghostbusters!

    • by HalAtWork (926717)
      Not Bob and Alice I guess!
    • Re:Bah (Score:4, Interesting)

      by 1s44c (552956) on Thursday January 02, 2014 @02:47AM (#45843497)

      Theo de Raadt.

      OpenBSD is trustworthy but you have to be suspicious of the BIOS it runs under and every network it connects to.

  • by QuietLagoon (813062) on Wednesday January 01, 2014 @03:20PM (#45838799)
    RSA doesn’t quite deny undermining customers’ crypto [freedom-to-tinker.com]

    Reuters reported on Saturday that the NSA had secretly paid RSA Data Security $10 million to make a certain flawed algorithm the default in RSA’s BSAFE crypto toolkit, which many companies relied on. RSA issued a vehement but artfully worded quasi-denial. Let’s look at the story, and RSA’s denial....

    • by WaywardGeek (1480513) on Wednesday January 01, 2014 @11:12PM (#45842439) Journal

      The crypto email list [metzdowd.com] discussed this at length. People chimed in who remember when this happened. Here's my take away: EMC had just bought RSA, and was looking for profits, and many of the best and brightest at RSA had left. The NSA offered $10M to make their RNG the default in BSAFE, and no one at RSA could offer EMC management any compelling argument as to why they should not take the money. RSA issued a press release about it. There was no secrecy. Competitors thought it was foolish to take money from the NSA, and at the same time wondered how they could get onto this gravy train.

      This is a case of typical incompetence. The response RSA published is slimy lawyer crapola. The lawyer sucks as bad as the incompetent EMC management. The good news is that there was no secret deal that RSA agreed to with the NSA to compromise all our security. The NSA did their job well. RSA didn't. I'll just point out that only crypto ignoramuses would accept closed-source un-auditable stuff from anyone when it comes to encryption, IMO. Money corrupts this industry.

  • by Anonymous Coward
    Can you still read the linked article? Or am I not allowed? I can't tell anymore what is allowed under the law and what isn't, since the US Gov feels free to interpret the law as it chooses.
  • by Anonymous Coward

    xorshift64 is a simple random number generator with a period of 2**64 - 1 (you cannot use 0).
    The 64 bit random number that it produces is the same as its complete state.

    • by thue (121682)

      I think the backdoored Dual_EC_DRBG still as forward security [wikipedia.org]. xorshift64 doesn't have forward security, if nothing else then because the period is small enough that you can brute force search it.

  • by koan (80826)

    Meaning what? That encryption was good enough to keep likes of the NSA out even with their resources, and so they compromised it?
    Or something even more insidious.

    • or they just wanted to make it easier/faster to break.

    • by mikael (484)

      With certain file encryption algorithms, they asked that the salt and/or hashed password were tacked on at the end of the file. That sped up decryption enough that their resources could decrypt the file, but not so much that anyone else could figure out it was compromised.

    • by fatphil (181876)
      From the patent linked to from article:
      """
      [0047] Escrow keys are known to have advantages in some contexts. They can provide a backup functionality. If a cryptographic key is lost, then data encrypted under that key is also lost. However, encryption keys are generally the output of random number generators. Therefore, if the ECRNG is used to generate the encryption key K, then it may be possible that the escrow key e can be used to recover the encryption key K. Escrow keys can provide other functionality, s
  • Good article (Score:5, Informative)

    by Okian Warrior (537106) on Wednesday January 01, 2014 @03:38PM (#45838947) Homepage Journal

    The link above [0xbadc0de.be] is a very good introductory article on EC cryptography. If you know a little math but have no background in elliptic curves, this is a good introduction. Well worth reading.

    Clearly explained at an introductory level, with Wikipedia links for the assumed terms.

    Topical, singular (ie - it's the first one currently, a news "scoop" if you like), technical, and important.

    Lots to like here - Slashdot needs more articles like this.

  • Does this mean that OpenBSD has suffered a 3rd remote hole in its default installation? (http://it.slashdot.org/story/07/03/15/0045207/remote-exploit-discovered-for-openbsd)

    (I don't understand the implications of Aris' blog above, so I'm hoping someone can explain it to me & other OpenBSD users.)

  • FIPS (Score:5, Informative)

    by sunderland56 (621843) on Wednesday January 01, 2014 @03:58PM (#45839123)

    FIPS is a large group of standards - literally, the Federal Information Processing Standards. Any requirement is not "mandated by FIPS", it is mandated by one particular standard - which may or may not apply to any contract.

    FIPS 140-2 Annex C, for one, lists quite a few acceptable random number generators; for that standard, I see no requirement for Dual EC DRBG.

    • Re:FIPS (Score:5, Informative)

      by Anonymous Coward on Wednesday January 01, 2014 @04:10PM (#45839211)

      FIPS is a large group of standards - literally, the Federal Information Processing Standards. Any requirement is not "mandated by FIPS", it is mandated by one particular standard - which may or may not apply to any contract.

      FIPS 140-2 Annex C, for one, lists quite a few acceptable random number generators; for that standard, I see no requirement for Dual EC DRBG.

      There's still no requirement for Dual EC DRBG (so the summary is misleading) but Annex C is also somewhat misleading.

      FIPS 140-2 is modified by SP 800-131A which describes algorithm transitions (see FIPS 140-2 Implementation Guidance G.14) and therefore any new FIPS 140-2 module submitted after Dec 31, 2013 can only use an RNG from the SP 800-90A standard; not any of the other RNGs listed in Annex C.

      However SP 800-90A specifies four different DRBG algorithms, only one of them being the suspect Dual EC DRBG. So even today new modules aren't forced to use it. (And if fact I believe NIST posted a warning on their 140-2 website strongly recommending that people not use the Dual EC DRBG)

  • by gman003 (1693318) on Wednesday January 01, 2014 @04:01PM (#45839131)

    Actually read TFA, enough flew over my head that I can't personally verify the math, but if true, well holy fucking shit. Once someone brute-forces the backdoor "key" used by the NSA, it looks like the entire system is cracked. Even if it takes a while to brute-force, once you have that you can open any encryption using that curve.

    Given that cracking this open would be so useful to both other monitoring agencies, and to criminal hackers, it's sure to happen eventually, if it hasn't already. I'm sure China could throw one of their supercomputers at it.

    I'd be curious to know just how hard it would be to brute-force the backdoor key itself. There didn't seem to be anything in TFA about that, and I can't figure out the math myself.

    • by gnasher719 (869701) on Wednesday January 01, 2014 @04:20PM (#45839267)

      Actually read TFA, enough flew over my head that I can't personally verify the math, but if true, well holy fucking shit. Once someone brute-forces the backdoor "key" used by the NSA, it looks like the entire system is cracked. Even if it takes a while to brute-force, once you have that you can open any encryption using that curve.

      It's quite possible that this cannot be brute forced. The only way is to create the back door at the time that the random number generator is created. In the end, that is the _first_ requirement: That an arbitrary attacker, given a complete description of the algorithm, cannot brute force it.

      • by jader3rd (2222716) on Wednesday January 01, 2014 @04:50PM (#45839449)

        It's quite possible that this cannot be brute forced. The only way is to create the back door at the time that the random number generator is created. In the end, that is the _first_ requirement: That an arbitrary attacker, given a complete description of the algorithm, cannot brute force it.

        From what I understand the whole point of algorithms like this is that brute force is the only option (without knowing the key). If there was some other mathematical way of determining the key the hackers would use that; so the goal is to create an algorithm where the secret key has to either be known, or brute forced. The only way to find the secret key is to literally try every possible number and hope that the computer stumbles across the right one eventually.

    • by thue (121682)

      According to Dan Shumow and Niels Ferguson's 2007 presentation [cr.yp.to], finding the private key e corresponds to solving one instance of the elliptic curve discrete log problem [washington.edu], which is believed to be a very hard problem indeed, and probably not even doable for a any current supercomputer.

      • If its not doable how then did NSA supposed to have done it? Its not like they came up with the key at random then invented this algorithm to fit it, the fact that there is a backdoor key is a quirk of the mathematics.

        • by gman003 (1693318) on Wednesday January 01, 2014 @06:08PM (#45839951)

          From my understanding, the ability to have *a* backdoor is a quirk of the math, but the "key" depends on the parameters of the elliptic curve. Those parameters for this specific implementation were written by the NSA (under the guise of their mandate to secure American communications) and standardized by NIST. TFA had a full proof of concept using parameters he had generated, which worked.

        • by thue (121682)

          If you can choose P and e, then you can easily calculate Q=eP. It it only if you start with P and Q given that you can't find e.

        • by Dr. Blue (63477) on Wednesday January 01, 2014 @06:55PM (#45840421)

          If its not doable how then did NSA supposed to have done it? Its not like they came up with the key at random then invented this algorithm to fit it, the fact that there is a backdoor key is a quirk of the mathematics.

          It's basically public-key crypto: you can create a keypair and publish the public key - that's essentially what this is, where the point Q in the Dual_CD_DRBG spec is really just a public key. There's a private key as well - it's far to expensive to compute it from the public key (basically 2^128 time), but they didn't have to do that since they generated the private key first.

          And it's really not a "quirk of the mathematics" - it's really pretty straightforward if you understand elliptic curves, and it has been well-known how to do this since 2007 or earlier. I think a lot of academic cryptographers didn't really worry about it when Shumow and Ferguson pointed out the potential backdoor, because it's really a pretty crappy technique anyway - academic cryptographers, who quite frankly often don't know what is used in practice, assumed no one would use this. Then it turns out that RSA used it as the default tehnique in BSAFE. Oops.

    • by Anonymous Coward on Wednesday January 01, 2014 @04:34PM (#45839331)

      (Hi. I'm the one Dan was replying to, from another thread. Proof on request, but /. mangles PGP signatures, amongst many other things.)

      No, it'd take a Rho attack of 2^127.8 complexity to break that key. Not happening. Way more likely is that someone simply steals the key from the NSA - a daunting prospect - but not particularly useful if all you wanted to know is that there is a backdoor, not to actually use it. There is, and people have been pointing that out since 2006.

      I was... surprised at Dan's response. I did not actually expect a response to noting that the backdoor in Dual_EC_DRBG was, and I'll quote myself here, "a backdoor that couldn't have been more obvious if you'd erected a flashing neon sign and driven a mounted parade with a marching band through it", because I didn't think anybody was in disagreement about that. Apparently I was wrong.

      My own reply to him, pointing out that even if you mind your Ps & Qs (in the way that he patented, mind you), Dual_EC_DRBG still sucks: http://www.ietf.org/mail-archive/web/cfrg/current/msg03689.html [ietf.org]

      I don't have a reply to that yet. In all fairness, it has been the Christmas and New Year period, and it's been kind of a busy one this year, and there's some procedural things to sort out that are probably going to take some time (and input from the crowd here would probably only make things worse, right now). Meanwhile, we have recommendations to make about TLS - in short, use it, but for God's sake, turn off RC4 because it's shit and probably worse than the BEAST attack people tended to use it to avoid - and some new things to roll out with that before the big work on TLS 1.3; with encrypted ClientHellos and pinned certificates to stop random CAs impersonating sites high on the wishlist.

      An update, by the way: after re-opening the comments period, having been openly informed of the Snowden disclosures (albeit years after cryptographers warned them), NIST have agreed to remove Dual_EC_DRBG from SP 800-90A. So that's something, at least.

      /akr

  • by Anonymous Coward

    Please, people who understand EC properly, verify & reproduce this ASAP. If so this is yet another thing (one the BIGGEST things) the NSA has denied about the content of the Snowden leaks.

    Plus RSA needs to really step up and be honest about just what occurred inside their walls wrt. FIPS and this algorithm.

    At this point, I think the longstanding rule that 'only a fool writes his own crypto' is getting weaker.. I would amend it to "only a fool writes his own crypto, or uses ones supplied by anyone withou

  • by thue (121682) on Wednesday January 01, 2014 @04:43PM (#45839401) Homepage

    I have been adding various facts to the Wikipedia article on Dual_EC_DRBG [wikipedia.org]. A good deal of the most interesting points have not been reported in mainstream media.

    * The ANSI group which standardize Dual_EC_DRBG were aware of the potential for a backdoor.
    * Three RSA Security employees were listed as being in that ANSI group, making RSA Security's claim innocence claim shaky, since it is less likely that RSA Security didn't know about the back door when NSA paid them $10 million to use Dual_EC_DRBG as default.
    * Two Certicom members of the ANSI group wrote a patent which describes the backdoor in detail, and two ways to prevent it.
    * Somehow the ways to prevent the backdoor only make it into the standard as non-default options.
    * Somehow the people on the ANSI group forget to publicize the potential for a backdoor. Especially Daniel brown of Certicom (co-author of the patent), who also wrote an attempt at a mathematical security reduction for Dual_EC_DRBG, but somehow forgets to explicitly mention the backdoor. The conclusion in Brown's paper also seems very determined to hype Dual_EC_DRBG, whereas the other papers about Dual_EC_DRBG seem excited to hype the errors they find.
    * The potential backdoor only becomes public knowledge in 2007.
    * Daniel Brown writes in December 2013 [ietf.org] that "I'm not sure if this was obvious." and "All considered, I don't see how the ANSI and NIST standards for Dual_EC_DRBG can be viewed as a subverted standard, per se.".

    Certicom is the main inventor and patent-holder for elliptic curve cryptography. The two Certicom employees failing to warn or prevent the backdoor they clearly know was possible doesn't reflect well on Certicom.

  • by LazLong (757) on Wednesday January 01, 2014 @06:01PM (#45839907) Homepage

    So, they introduced a backdoor into software that can be/is used to secure US nuclear secrets, in the hopes only they would be able to take advantage of it? This is just another variant of "security through obscurity." Really, really fucking stupid!

    • by Darinbob (1142669)

      I don't think they're that stupid. Which is why I doubt the Snowden revelations about this, either it's misinterpreted or misrepresented.

    • by fatphil (181876)
      The US nuclear secret is "00000000".
    • The backdoor is only useful if you have the "secret" key, i.e. the e such that Q^e=P . Working out e from P and Q is hard (discrete log problem). However, if you are in a position to pick the P and Q that will make it into the standard, you just pick up any Q and e of your liking, keep e secret to yourself, and hand out Q and the P derived from Q and e.

      So, only the NSA, and maybe people having managed to steal e from the NSA would be able to take advantage of this back door.

  • If you use more than 1 sequence of randomness while using the required standard, is that code viewed as compliant?
  • It is quite obvious in light of the recent revelations from Snowden that this weakness was introduced by purpose by the NSA. It is very elegant and leaks its complete internal state in only 32 bytes of output, which is very impressive knowing it takes 32 bytes of input as a seed.

    I'll stick with twofish,or AES256 for my openssl and gpg stuff.

  • The silver lining seems to be that there's evidence no one has ever actually used Dual EC_DRBG in release versions of the OpenSSL module (though that in turn raises the question of why RSA's BSAFE crypto tool used the RNG by default). ...

    The takeaway from Thursday's advisory is that Dual EC_DRBG has been formally banished from yet another widely used crypto platform (with RSA's BSAFE being the other one). Before bidding a formal farewell to the algorithm, it's worth mentioning that Dual EC_DRBG was suspicio

  • There are two distinct random generators available:

    The Continuously Seeded Pseudo Random Number Generator (CSPRNG), which is based on the classic GnuPG derived big pool implementation. Implemented in random/random-csprng.c and used by default.
    A FIPS approved ANSI X9.31 PRNG using AES with a 128 bit key. Implemented in random/random-fips.c and used if Libgcrypt is in FIPS mode.

    http://www.gnupg.org/documentation/manuals/gcrypt/Random_002dNumber-Subsyst [gnupg.org]

  • If they aren't already, now would be the time to start putting the masses to work hunting down the NSA's special key. This is a nasty one, and the sooner we can use it to bludgeon the guilty parties the better.

If you are good, you will be assigned all the work. If you are real good, you will get out of it.

Working...