Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Strange Story of Dual_EC_DRBG – suspected NSA backdoor (2007)

schneier.com

Post reply on HN
Print view View original

41–50 of 78 posts

Re: The Strange Story of Dual_EC_DRBG – suspected NSA backdoor (2007)

#41

Post by contingencies »

moonboots wrote: post #26
contingencies wrote: post #11

I'm no mathematician, so this is probably a dumb question that will serve as a great example for why random programmers shouldn't write cryptosystems. However, here goes anyway. Could a cryptographer please explain why it's not feasible to use multiple such PRNG algorithms in both series and parallel, perhaps even shuffling their order dynamically, at, err, random? Surely most attacks on PRNGs are based upon the assu…

Aggregating multiple sources of randomness has the potential to conceal bugs. In the Debian/OpenSSL bug from 2008 [1], randomness was sourced from multiple locations including the current process id. The idea was that more randomness, even the minimal amount from the pid, could only increase the total entropy. However, when the primary source of randomness was eliminated through an overzealous patch, the PRNG still e…

That's an interesting take and does seem logical for human testing. However, it seems to me the real culprit was a lack of decent automated testing.

More to the point, as well as the potential to conceal bugs it also offers the potential to mitigate the impact of bugs. This was the whole point of my question, which despite some interesting responses, basically remains unanswered.

Re: The Strange Story of Dual_EC_DRBG – suspected NSA backdoor (2007)

#42

Post by contingencies »

cdumler wrote: post #23
contingencies wrote: post #11

I'm no mathematician, so this is probably a dumb question that will serve as a great example for why random programmers shouldn't write cryptosystems. However, here goes anyway. Could a cryptographer please explain why it's not feasible to use multiple such PRNG algorithms in both series and parallel, perhaps even shuffling their order dynamically, at, err, random? Surely most attacks on PRNGs are based upon the assu…

Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin. - John von Neumann The very definition of a pseudo-random number generator is that it's deterministic, i.e. an algorithm. If you know in what the state of the algorithm is, you know what the next number will be. Attempting to add some ad hoc behavior on top of crypto has two common issues: First, adding of determin…

shouldn't be a need to do anything like what you're suggesting, ever, with a valid PRNG

OK, but the point was that if we approach PRNGs like any other element of a secure system, ie. without trust, as the article was suggesting, then combining them in some way may assist with QA on the overall output. (Example: I mean, we don't trust the NSA - but do we trust Schneier? He could be paid handsomely by the NSA as a false stooge and EFF board plant, who are we to know? And if you're an overseas government without a native cryptographic/cryptanalytic tradition, would you trust him? He's a US citizen connected to BT - that's UKUSA - two of the 'five eyes'!)

Similar to how multiple hashing algorithms are often used to preserve overall functional integrity in the case of individual hash function vulnerabilities that enable an attacker to propose collisions.

Re: The Strange Story of Dual_EC_DRBG – suspected NSA backdoor (2007)

#43

Post by contingencies »

malandrew wrote: post #38
cdumler wrote: post #23

Earlier quoted context omitted.

Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin. - John von Neumann The very definition of a pseudo-random number generator is that it's deterministic, i.e. an algorithm. If you know in what the state of the algorithm is, you know what the next number will be. Attempting to add some ad hoc behavior on top of crypto has two common issues: First, adding of determin…

How about using a stream of true random numbers and putting it through a set of deterministic functions that "multiply" the quantity of random numbers. e.g. make thousands upon thousands of functions, where the function names are sequential. Use the data itself to determine which of the functions will be called. Allow functions to call each other based on the random number values it calculates from its true random in…

Err, I think you'll find what you described is roughly the definition of a PRNG (though usually more mathematical in its verbiage). The problem is, we don't trust any particular PRNG. My question was, why not combine them so as to remove the need for absolute trust in any given PRNG.

Re: The Strange Story of Dual_EC_DRBG – suspected NSA backdoor (2007)

#45

Post by nknighthb »

contingencies wrote: post #40
nknighthb wrote: post #13

Earlier quoted context omitted.

If you pull data from most OS-level RNGs (e.g. /dev/random on a Linux box), this is basically what you're getting. A bunch of hardware timing data, some of which may be at least partially predictable or observable, is passed through a hashing algorithm. If the hashing algorithm is good, and an attacker is missing some reasonable chunk of the data that went into it, you're getting secure random numbers.

Thanks, that's almost exactly what I was looking for. However, it doesn't answer the question which is "can't we avoid that one big assumption" (ie. if the hashing algorithm is good ) by combining them?

Ultimately the answer is no, because your question is predicated on a nonexistent distinction.

A combination of algorithms is simply a new, more complex algorithm. It may be an obvious and safe algorithm that enhances security, like Truecrypt's option of an AES/Twofish/Serpent cascade, or it may be a totally worthless algorithm -- like if you created a new "hashing" algorithm that consisted of CRC32 followed by SHA256.

As that second example demonstrates, the naïve way of combining hashing algorithms is obviously not safe. If you simply layer them, any one of them could destroy entropy by producing biased/predictable results. Your new algorithm is crippled.

If you try to "mix" them in some other way, all you've done is create a new hashing algorithm and fed it the output of other hashing algorithms. It's perhaps less likely that any one of those sub-algorithms will seriously cripple your system, but it's much more likely that you've made a mistake, and your new algorithm itself produces poor results.

Somewhere along the way, you end up trusting something, even if it's your own algorithm. But since trusting yourself to get crypto right is a bad idea, the next best thing is to trust a well-vetted hashing algorithm, of which there are several that are likely "good enough", and aren't even NSA designed.

If you're super-paranoid about backdoors, RIPEMD-160 might be your best bet -- it's a product of European academia. It gets some use, but not as much cryptanalysis as the SHA family has.

Re: The Strange Story of Dual_EC_DRBG – suspected NSA backdoor (2007)

#46

Post by contingencies »

nknighthb wrote: post #45
contingencies wrote: post #40

Earlier quoted context omitted.

Thanks, that's almost exactly what I was looking for. However, it doesn't answer the question which is "can't we avoid that one big assumption" (ie. if the hashing algorithm is good ) by combining them?

Ultimately the answer is no, because your question is predicated on a nonexistent distinction. A combination of algorithms is simply a new, more complex algorithm. It may be an obvious and safe algorithm that enhances security, like Truecrypt's option of an AES/Twofish/Serpent cascade, or it may be a totally worthless algorithm -- like if you created a new "hashing" algorithm that consisted of CRC32 followed by SHA25…

your question is predicated on a nonexistent distinction. A combination of algorithms is simply a new, more complex algorithm.

That's true if you combine multiple algorithms conventionally, for example by feeding inputs from one to the other or by passing the original entropy to the two algorithms in parallel.

However, if you run one algorithm independently of another - with completely different entropy sources - then flip between supplying the output of each in rapid succession, then on the face of it for ~50% overheads you have probably mostly mitigated exploitable vulnerabilities in either of the two single PRNGs for most applications. (Optionally add another for more security, and take it a step further...)

You are right that this would need to be done carefully .. perhaps the flip in which PRNG is used for the output stream occurs at hard-to-predict points in time (the range of periods for which, potentially, might be carefully chosen from a range that takes in to account some other cryptographically relevant factors ... from a complete non-cryptographer like me, this might include things like entropy draw size by typical applications (optimizing for multiple PRNGs over a typical application draw), the length of any feedback register or calibration cycle of individual cryptographic client algorithms, etc. Generally this would mean 'pretty frequently but not so frequently that it's predictably useful' - something of a paradox, true.)

In short, I still think this approach may have some merit.

Re: The Strange Story of Dual_EC_DRBG – suspected NSA backdoor (2007)

#47

Post by nknighthb »

contingencies wrote: post #46
nknighthb wrote: post #45

Earlier quoted context omitted.

Ultimately the answer is no, because your question is predicated on a nonexistent distinction. A combination of algorithms is simply a new, more complex algorithm. It may be an obvious and safe algorithm that enhances security, like Truecrypt's option of an AES/Twofish/Serpent cascade, or it may be a totally worthless algorithm -- like if you created a new "hashing" algorithm that consisted of CRC32 followed by SHA25…

your question is predicated on a nonexistent distinction. A combination of algorithms is simply a new, more complex algorithm. That's true if you combine multiple algorithms conventionally, for example by feeding inputs from one to the other or by passing the original entropy to the two algorithms in parallel. However, if you run one algorithm independently of another - with completely different entropy sources - the…

> That's true if you combine multiple algorithms conventionally

What I said is true no matter how you combine them, including in the manner you propose.

> flip between supplying the output of each in rapid succession

You've just exposed yourself to a possible related-key attack. Also, the effective entropy of your key could be halved simply by one of the PRNGs being compromised, so even absent a related-key attack, you'd better be using an encryption algorithm with a big key size.

(BTW, it's 100% overhead, not 50% overhead.)

(Oh, and if both algorithms happen to be compromised, the results are or might as well be 0-entropy. Yet again, somewhere along the way you end up trusting something.)

> perhaps the flip in which PRNG is used for the output stream occurs at hard-to-predict points in time

"Hard-to-predict" requires a secure random number generator. You've gone on to describe yet another ad-hoc random number generator that you would use in the construction of your random number generator.

Cryptography is hard.

Re: The Strange Story of Dual_EC_DRBG – suspected NSA backdoor (2007)

#48

Post by StavrosK »

contingencies wrote: post #46
nknighthb wrote: post #45

Earlier quoted context omitted.

Ultimately the answer is no, because your question is predicated on a nonexistent distinction. A combination of algorithms is simply a new, more complex algorithm. It may be an obvious and safe algorithm that enhances security, like Truecrypt's option of an AES/Twofish/Serpent cascade, or it may be a totally worthless algorithm -- like if you created a new "hashing" algorithm that consisted of CRC32 followed by SHA25…

your question is predicated on a nonexistent distinction. A combination of algorithms is simply a new, more complex algorithm. That's true if you combine multiple algorithms conventionally, for example by feeding inputs from one to the other or by passing the original entropy to the two algorithms in parallel. However, if you run one algorithm independently of another - with completely different entropy sources - the…

Basically, cryptography requires a PRNG whose output is provably indistinguishable from a true RNG. Your algorithm cannot be proven to have this property, and might even be susceptible to some attacks.

Basically, it's a band-aid, but cryptography is rigorous and averse to band-aids, requiring everything to be mathematically proven before use.

It's not enough for an algorithm to "seem reasonable", it must be mathematically proven to have certain properties. It's really an extremely interesting subject to study, I'd give it a go. Join the coursera class on cryptography.

Re: The Strange Story of Dual_EC_DRBG – suspected NSA backdoor (2007)

#49

Post by jokoon »

I'll always question any cryptographic standard adopted or advised by government.

I have an hard time even trusting AES.

http://crypto.stackexchange.com/questions/579/how-can-we-rea...

Honestly I think those issues (like cryptanalysis) are totally out of reach by the public to comprehend, it's hard to really know how to make strong assumptions.

Re: The Strange Story of Dual_EC_DRBG – suspected NSA backdoor (2007)

#50

Post by makomk »

damarquis wrote: post #6

So either the NSA wanted a backdoor, in which case we learn that even the NSA can't build a backdoor that academic cryptographers can't detect. Or, much more likely I think, it was just a project that some NSA employees had sitting around and they wanted to get something out of it. In that case we learn that the NSA isn't so far ahead of academic cryptographers that their designs will always be better. Either way I d…

They might be able to build backdoors that academic cryptographers can't detect, but this backdoor was special - even after the academics figured it out, the NSA are still the only ones that could use it because it requires a secret key whose public counterpart was baked into the Dual_EC_DRBG specification. Backdoors with that special property are going to be much harder to create.
Post reply on HN