back to article Kill dodgy RNG says NIST

NIST has said what we already knew: the Dual Elliptic Curve Deterministic Random Bit Generator, Dual_EC_DRBG, is a dead duck and should be abandoned by anyone still using it. In this document, the US standards-setter is seeking comment on the final version of its Recommendation for Random Number Generation Using Deterministic …

COMMENTS

This topic is closed for new posts.
  1. Bartholomew

    NIST may have done nothing wrong, but trust in them has been reduced worldwide. I can see a new non-US, non-UK based institution taking over from them over the next several years as more and more privacy guarding equipment is sold worldwide.

  2. Mikel

    Determinism is not random

    That word itself should have been your clue. Determinist is the antonym of random.

    1. John Smith 19 Gold badge
      Holmes

      Re: Determinism is not random

      Thank you for that blinding insight.

      Most people know understand that computer generated random numbers are Pseudo random.

      The challenge of creating software that generates good random number is tricky.*

      * By good I mean that after you've recorded a very long stream of its output your best guess about its next output is literally no better than 50/50 either way.

      1. Michael Wojcik Silver badge

        Re: Determinism is not random

        The challenge of creating software that generates good random number is tricky.*

        * By good I mean that after you've recorded a very long stream of its output your best guess about its next output is literally no better than 50/50 either way.

        That's only one possible criterion for a pseudo random-number generator. There are many applications for PRNGs, not all of them have maximum entropy as a goal, and maximum entropy is not the only criterion for those that do.

        An example of the former: For pseudorandom system testing, it's often more important that your PRNG offer good coverage of the test space and an internal state that's completely visible at any point so you can reconstruct a test sequence.

        An example of the latter: For a CPRNG, maximal entropy might not be very helpful if your generator is susceptible to side-channel attacks, or if its internal state can be revealed in other ways.

        In other words, what's "good" depends on the application and design criteria.

        Dual_EC_DRBG wasn't good from most people's point of view, but if your primary criteria are "having a back door that can let Certain Parties predict the output" and "getting implemented as the default in a popular product set", then it fits the bill nicely.

  3. John Smith 19 Gold badge
    WTF?

    And speaking of dodgy software who made name searches on El Reg case sensitive?

    Every wondered why most computer languages are not?

    Perhaps you should?

    1. Steve Todd

      Re: And speaking of dodgy software who made name searches on El Reg case sensitive?

      Except all the ones in major use are case sensitive (certainly anything with C as a root).

      1. John Smith 19 Gold badge
        Unhappy

        Re: And speaking of dodgy software who made name searches on El Reg case sensitive?

        "Except all the ones in major use are case sensitive (certainly anything with C as a root)."

        Probably the biggest mistake Dennis Richie ever made.

        So now instead of searching for members comments you have to remember their exact spelling as well.

        I am so impressed.

      2. Michael Wojcik Silver badge

        Re: And speaking of dodgy software who made name searches on El Reg case sensitive?

        Except all the ones in major use are case sensitive

        COBOL isn't, and if you think that's not "in major use" you're sadly misinformed.

        Fortran isn't, and it's still widely used as well.

        HTML (except XHTML) and CSS aren't, and they're now Turing-complete.

        I know, I know. All the World's a VAX, and it's still September.

  4. CaptainBanjax

    RNG at Camelot

    I suggest we consult the national lottery for advice. They have one of the most unpredictable random number generator im aware of.

    Id quite enjoy giving Eamon Holmes a call to have him generate numbers for me. Keeps him off the telly.

    On a serious note though why are we still using pure maths to calculate random numbers? Why cant we factor in variables that cant possibly be calculated or duplicated rather than trying to calculate something that is hard to calculate? There must be plenty of natural entropy all around us to tap into.

    1. Steve Todd

      Re: RNG at Camelot

      There's plenty of history over using hardware random number generators (ERNIE for premium bonds for example). One would have thought it's something that could be built in to a modern CPU.

      1. Lee D Silver badge

        Re: RNG at Camelot

        It was built into the prior generation of CPU's

        VIA chips have had them for years.

        Intel incorporated quantum effects into their hardware RNG's.

        Nobody really used them.

        They stopped making them chip features.

        If you missed this entire section of history, maybe you should keep up. It wasn't that long ago.

        1. Mr Flibble

          Re: RNG at Camelot

          I'd use hardware RNGs, but I'd not rely on or put significant trust in them. Essentially, they're just an extra source of randomness to be mixed in with the others.

      2. Paul Crawford Silver badge

        Re: RNG at Camelot

        "One would have thought it's something that could be built in to a modern CPU."

        Intel have that, but as it is a secret black box, who would trust it?

        http://www.theregister.co.uk/2013/09/10/torvalds_on_rrrand_nsa_gchq/

    2. Anonymous Coward
      Anonymous Coward

      Re: RNG at Camelot

      Peter Wright alleged in SpyCatcher that the UK security services required that ERNIE produced very deterministic 'random numbers' in order to pay off certain spooks, tax-free, untraceably to the Ministries.

      I bet that doesn't happen now!

      ;-)

    3. John Savard

      Re: RNG at Camelot

      Natural entropy is usually used to set starting values for pseudo-random number generators. But that's about all it can be used for, since it's much harder for computers to get hold of real randomness than to calculate even a cryptosecure hash function.

  5. John Savard

    Getting it Wrong?

    Since the only flaw in this elliptic curve random number generator is that it is possible that the NSA might have generated and retained a private key which lets them crack it, and it is otherwise fully secure, NIST may actually have overreacted.

    While it is appropriate to say that this potential flaw makes that algorithm not recommended depending on who you don't want to read your mail, the NSA isn't one of the bad guys that is a threat to the U.S. government. Thus, use of that algorithm should not make a crypto implementation non-compliant with the standard - at least for most uses.

    For some uses, like signatures, or financial transactions, the mere possibility that anyone can crack the underlying crypto, though, is unacceptable - it's not best practice to risk a dishonest NSA employee. So, since crypto is used for things like that, where the U.S. government shouldn't even trust itself, perhaps they didn't go too far.

    1. Michael Wojcik Silver badge

      Re: Getting it Wrong?

      Since the only flaw in this elliptic curve random number generator is that it is possible that the NSA might have generated and retained a private key which lets them crack it, and it is otherwise fully secure, NIST may actually have overreacted.

      Sorry, John, but that's not correct. It's a lousy CPRNG even without the alleged back door. It underperforms other believed-strong CPRNGs and doesn't have any benefits over them. It puts too much state in the output. Its construction is suspicious. See Matt Green's blog post on the matter for more information.

      Sure, you can generate your own points on the curve and use Dual_EC_DRBG without worrying about back doors - NIST even tells you how. But no one does that because it's a crap CPRNG.

      It might also be worth noting that RSA BSAFE implemented a non-standard, undocumented TLS extension which coincidentally greatly speeds up the process of extracting sufficient pseudorandom data to break TLS encryption.

  6. tom dial Silver badge

    This news is not only old, but very old. Enough has been known since 2007, more than 6 years ago, to guide users away from the dual_ec_drbg: Schneier noted in 2006 that it is slow and biased, and Shumow and Ferguson showed in 2007 that whoever generated the determining constants had the capability to do so in a way that would enable them to break the RNG. That ought to have been enough to steer potential users to other PRNGs.

    The last argument applies differently, if at all, to implementations using different constants produced as the standard document describes in an appendix. You still need to trust whoever generated them unless you have the facility to reproduce the generation and verify the result.

    The second argument might or might not apply. The bias in the generator specified in the NIST standard hints that it might be difficult to produce constants that lead to unbiased output. It is reasonable to suppose that NSA or NIST would have done so if if they were able; and that is equally true whether they did so honestly or not.

    The first argument, poor performance, still would apply, although various cryptographers have suggested improvements over the methods NIST suggested.

  7. John Smith 19 Gold badge
    Unhappy

    Theoretically a hardware RNG is best.

    It can be made truly random. ERNIE was (is?) the output signal from a noisy diode that's sampled into a bit stream.

    But the question is do you trust it is truly random, given most are black boxes?

This topic is closed for new posts.

Other stories you might like