Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

Due to a potential NSA backdoor, the NIST is now recommending that implementor no longer use ECC-based PRNG Dual EC DRBG.

(As described in Wired.com) this PRNG has certain features such as:

  • continuous testing of output
  • prediction resistance
  • re-seeding
  • ... possibly others

Question

  1. Now that other PRNGs will be used, not all of them will offer the same feature set. What are the features we'll be missing, or be "weaker" in any sense of the word?

  2. What do these features mean? Why are they useful? (continuous testing for example)

You can assume for my question / threat model that the NSA is not my adversary, however I do want to prevent other capable attackers from compromising the integrity or effectiveness of my encryption.

share|improve this question
add comment

4 Answers

A PRNG which lacks reseeding, prediction resistance, or whatever these people mean by "continuous testing", is not a PRNG. Not in cryptographic terms.

Conversely, a good PRNG, like HMAC_DRBG, will be as good as Dual_EC_DRBG, actually better since Dual_EC_DRBG exhibits measurable biases, and is awfully slow. The only good point of Dual_EC_DRBG is the potential for a security proof which would demonstrate that the output is as random as a given number-theoretic problem is hard; but no such proof is known yet...

Here, by Dual_EC_DRBG, I mean a fixed Dual_EC_DRBG, with the two "random" points replaced by two points really generated randomly, not with the probable backdoor of the two standard points. But even "fixed", it would still be slow and biased.

The article you link to quotes the chief technical officer from RSA Security, who lists some advantages of Dual_EC_DRBG over "other algorithms". Without stating which algorithms Dual_EC_DRBG is compared with, these statements are vacuous. NIST themselves would feel quite offended at the suggestion that Hash_DRBG and HMAC_DRBG don't have the same features.

share|improve this answer
add comment

(Note: I am not a cryptographer, I might be completely off-based with this answer. :P)

I would take anything Sam Curry said with a bucket of salt. He has proven that he knows absolutely nothing about cryptopgrahy. Here is the full quote.

The length of time that Dual_EC_DRBG takes can be seen as a virtue: it also slows down an attacker trying to guess the seed. Plenty of other crypto functions (PBKDF2, bcrypt, scrypt) will iterate a hash 1000 times specifically to make it slower. At the time, elliptic curves were in vogue and hash-based RNG was under scrutiny. The hope was that elliptic curve techniques—based as they are on number theory—would not suffer many of the same weaknesses as other techniques (like the FIPS 186 SHA-1 generator) that were seen as negative, and Dual_EC_DRBG was an accepted and publicly scrutinized standard. SP800-90 (which defines Dual EC DRBG) requires new features like continuous testing of the output, mandatory re-seeding, optional prediction resistance, and the ability to configure for different strengths.

continuous testing of output

Here is a quote from FIPS-140-2.

Continuous random number generator test. If a cryptographic module employs Approved or nonApproved RNGs in an Approved mode of operation, the module shall perform the following continuous random number generator test on each RNG that tests for failure to a constant value.

  1. If each call to a RNG produces blocks of n bits (where n > 15), the first n-bit block generated after power-up, initialization, or reset shall not be used, but shall be saved for comparison with the next n-bit block to be generated. Each subsequent generation of an n-bit block shall be compared with the previously generated block. The test shall fail if any two compared n-bit blocks are equal.
  2. If each call to a RNG produces fewer than 16 bits, the first n bits generated after power-up, initialization, or reset (for some n > 15) shall not be used, but shall be saved for comparison with the next n generated bits. Each subsequent generation of n bits shall be compared with the previously generated n bits. The test fails if any two compared n-bit sequences are equal.

I'm not sure if this is what he was referring to, but it's the only application of continous testing with regards to PRNG that I can think of or find.

As you can see, this is a very simple test that any decent PRNG can pass.

prediction resistance

I suppose he is referring to an attacker being unable to predict the next n-bits of output of a PRNG given the first n-bits. This is the only thing that makes sense to me. I'm not sure why he considers this an advantage of Dual-EC-DRBG since any CSPRNG must possess this property to be useful.

re-seeding

Again, I'm not sure why he considers this a special property of Dual-EC-DRBG. The other algorithms defined in SP800-90A all define methods to reseed the PRNG.

As many people have pointed out on the Internet recently, PRNGs are easily substituted. You will not lose anything by switching from Dual-EC-DRBG.

share|improve this answer
1  
I don't think Sam Curry is stupid. His stupid "explanation" may be the consequence of being compelled to justify the unjustifiable. –  Jeffrey Goldberg Sep 24 '13 at 4:56
add comment

What you miss by switching away from Dual_EC_DBRG for a deterministic random bit generator are

  • Bias. The actual output is biased so there is an extra layer added to debias it. (Bias is a bad thing)
  • Inefficiency. Dual_EC_DBRG is slow compared to alternatives. There are some very specific cases where you want something to be slow, but a DBRG is not one of them. (The analogy given to PBKDF2 as justification for slowness is laughable.)
  • Implementational complexity. Implementing Dual_EC_DBRG is trickier than implementing any of the alternatives that were offered at the same time. (You guessed it. This is also a bad thing)

So those are three big strikes against Dual_EC_DBRG relative to alternatives at the time. These were known.

There is only one reason why anyone should have ever preferred Dual_EC_DRBG to the alternatives it was published with: Elliptic curves are cool. I'm actually sympathetic to that reason, and would consider it legitimate had other things been equal, but given that Dual_EC_DBRG was visibly inferior to other DBRGs available at the time, there is no reason for anyone to pick it.

As a reminder, the possibility of a back door was proven in 2007. So any decision after that 2007 presentation had to add that possibility of a back door to the reasons against it.

Sam Curry, whose peculiar "explanation" for the choice is probably what is behind this question, is not stupid. But if he was barred from telling the truth, then providing a response that reads like, "we picked it because unicorns are a nice pretty shade of blue" is informative. If you are compelled to justify the unjustifiable, gibberish is to be expected.

share|improve this answer
add comment

Now that other PRNGs will be used...

It's worth noting that with the exception of a few niche products, Dual EC DRBG wasn't previously used by anyone. At it's inception, independent researchers pointed out that this was a horrifically inefficient algorithm which produced an output that could be poisoned by a malicious actor. But for some hefty insistence from the NSA during the standards-making process, this algorithm would have simply gone down in history as a bad idea from a misguided designer.

So, now that other PRNGs will be used.... nothing will change, because other PRNGs have always been in use.

Also, with modern technology, if you're still using a simple mathematical PRNG, you're doing it wrong. Algorithms that can manage pools a externally-sourced true entropy, in combination with simple effective sources of real randomness are resistant to every known attack.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.