The Strange Story of Dual_EC_DRBG – suspected NSA backdoor (2007) • Hacker News Board

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

#61

Post by eru » Sat, Jul 06, 2013, 2:55 PM UTC

contingencies wrote: post #57

nhaehnle wrote: post #52

Earlier quoted context omitted.

Running different pseudo-random generators in parallel and then XORing their results should have the property that if at least one of the input algorithms is "good", then the output algorithm is "good". My intuition is based on the fact that this statement is correct for true random sources: If you take a bunch of random sources that generate streams of bits, then XORing those streams together will result in a stream…

Right, I came to the same realization. You'd need to make sure the input stream(s) (ie. entropy source(s)) to the PRNGs in question were not shared. Even if that was impractical, and this is pure conjecture from someone who is not a mathematician or cryptographer, then at the very least they should be well obfuscated, eg. unpredictably delayed throughout a large enough temporal keyspace with a not insignificant degre…

XORing multiple sources throws away lots of useful entropy. There are better approaches available, and they are used.

Edit: nhaehnle, I can't reply to your comment (yet) because it's too deeply nested. I don't know the direct answer, but if you want to do some research yourself, you could do worse then reading this relevant Wikipedia article (https://en.wikipedia.org/wiki/Randomness_extractor) and following the links. They don't talk about provable extractors in the article itself, but you can probably identify at least the right terms you need to search for on arxive or so.

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

#62

Post by cdumler » Sat, Jul 06, 2013, 3:37 PM UTC

contingencies wrote: post #43

malandrew wrote: post #38

Earlier quoted context omitted.

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.

When part of your system becomes flawed (part or whole), the whole can be attacked. Thus, adding more deterministic behavior doesn't add more randomness (i.e. more safety). Generally, when crypto falls down, it falls somewhat gracefully (i.e. there are a class of known attacks under certain particular situations.) As Crypto is an on-going war between those creating the security and those trying to break it, expect to have to change your crypto over time.

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

#63

Post by nhaehnle » Sat, Jul 06, 2013, 3:52 PM UTC

eru wrote: post #61

contingencies wrote: post #57

Earlier quoted context omitted.

Right, I came to the same realization. You'd need to make sure the input stream(s) (ie. entropy source(s)) to the PRNGs in question were not shared. Even if that was impractical, and this is pure conjecture from someone who is not a mathematician or cryptographer, then at the very least they should be well obfuscated, eg. unpredictably delayed throughout a large enough temporal keyspace with a not insignificant degre…

XORing multiple sources throws away lots of useful entropy. There are better approaches available, and they are used. Edit: nhaehnle, I can't reply to your comment (yet) because it's too deeply nested. I don't know the direct answer, but if you want to do some research yourself, you could do worse then reading this relevant Wikipedia article ( https://en.wikipedia.org/wiki/Randomness_extractor ) and following the lin…

Is there a provably better way, though? I think this was basically the premise of the original question: Given that there is doubt about the safety of some PRNG scheme, is there a proven way to combine multiple PRNG scheme with the property that the resulting PRNG is at least as secure as the most secure "input" PRNG?

If there is such a better way, then please provide more information - links and such.

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

#64

Post by geophile » Sat, Jul 06, 2013, 4:07 PM UTC

Much of the discussion in previous comments has to do with the generation of true random numbers. Does this need to happen on a client or on a server? If it's on a client, then isn't a cell phone an ideal source of randomness, due to all of the sensors on board?

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

#65

Post by contingencies » Sat, Jul 06, 2013, 5:06 PM UTC

StavrosK wrote: post #59

contingencies wrote: post #56

Earlier quoted context omitted.

Basically, it's a band-aid, but cryptography is rigorous and averse to band-aids, requiring everything to be mathematically proven before use. To be honest, I am quite partial to the description of modern economics given by George Soros, namely: the entire thing is based on a false analogy with Newtonian physics . This is the proverbial 'false sense of security', lent credence by its ... ubiquity ... in the field. Pe…

> they think that because something is proven in a mathematical sense using their current knowledge of viable routes of deducation that it remains 'true' and unassailable. That's because it does. > The threat of someone else having or coming up with a faster physical or logical method of deduction does threaten these assumptions. No, it doesn't, because there are no assumptions. > The broader goal, then, is not to tr…

> There's a reason people use a single PRNG

I just want to know what it is.

(Edit as can't reply to child: Sure, but this gets back to the mathematical analysis does not equal real world proof, since we do not know all possible computational (or side channel!) vectors. Assertion otherwise is reminiscent of Socrates: οὖτος μὲν οἴεταί τι εἰδέναι οὐκ εἰδώς, ἐγὼ δέ, ὥσπερ οὖν οὐκ οἶδα, οὐδὲ οἴμαι This man, on one hand, believes that he knows something, while not knowing [anything]. On the other hand, I – equally ignorant – do not believe [that I know anything]. https://en.wikipedia.org/wiki/I_know_that_I_know_nothing ... OK that's weak, but honestly that's how I tend to think (ie. with great cynicism about any assertion) and it serves me alright in general security / non-cryptographic discourse. Basically this approach is treating the PRNG algorithm as a black box, refusing to trust it, and attempting to design a system incorporating the black box along with others claiming the same functionality, based upon that assumption. If this works for any other algorithm - and it seems to - then why not PRNGs? It's not like cryptography has a monopoly as an arbiter of risk. Cryptography is not a silver bullet.)

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

#66

Post by contingencies » Sat, Jul 06, 2013, 5:16 PM UTC

eru wrote: post #60

contingencies wrote: post #41

Earlier quoted context omitted.

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.

It is pretty hard to automatically test cryptography. (I do agree however, that C is a rather bad language for implementing cryptography.)

It seems like there is an established test suite in the PRNG space, by NIST. http://csrc.nist.gov/groups/ST/toolkit/rng/documentation_sof...

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

#67

Post by StavrosK » Sat, Jul 06, 2013, 5:21 PM UTC

contingencies wrote: post #65

StavrosK wrote: post #59

Earlier quoted context omitted.

> they think that because something is proven in a mathematical sense using their current knowledge of viable routes of deducation that it remains 'true' and unassailable. That's because it does. > The threat of someone else having or coming up with a faster physical or logical method of deduction does threaten these assumptions. No, it doesn't, because there are no assumptions. > The broader goal, then, is not to tr…

> There's a reason people use a single PRNG I just want to know what it is. (Edit as can't reply to child: Sure, but this gets back to the mathematical analysis does not equal real world proof, since we do not know all possible computational (or side channel!) vectors. Assertion otherwise is reminiscent of Socrates: οὖτος μὲν οἴεταί τι εἰδέναι οὐκ εἰδώς, ἐγὼ δέ, ὥσπερ οὖν οὐκ οἶδα, οὐδὲ οἴμαι This man, on one hand, b…

It's in the next sentence:

> and the reason is that, when your PRNG's output is provably indistinguishable from true randomness, messing with it will certainly not improve it, and will probably ruin it.

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

#68

Post by contingencies » Sat, Jul 06, 2013, 5:22 PM UTC

cdumler wrote: post #62

contingencies wrote: post #43

Earlier quoted context omitted.

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.

When part of your system becomes flawed (part or whole), the whole can be attacked. Thus, adding more deterministic behavior doesn't add more randomness (i.e. more safety). Generally, when crypto falls down, it falls somewhat gracefully (i.e. there are a class of known attacks under certain particular situations.) As Crypto is an on-going war between those creating the security and those trying to break it, expect to…

> When part of your system becomes flawed (part or whole), the whole can be attacked.

This is the most concise and meaningful argument against the proposed approach thus far. Hats off.

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

#69

Post by cdumler » Sat, Jul 06, 2013, 5:41 PM UTC

contingencies wrote: post #42

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…

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 fals…

The difference is between a PRNG and encryption. Encryption's design is to obscure the data stream; thus, if there is a failure in an encryption it is masked by another encryption. Personally, I do not think this is a particularly useful activity. Public vetted encryption rarely spontaneously falls over. A modern encryption, like AES256, is well beyond the far future in computing requirements to brute force. It's better to be aware of changes over time and switch to a current crypto if things change, like how 3DES died. PRNG, on the other hand, is a string of numbers. They don't obscure anything. Either A) you don't try to obscure, and part of your numbers are weak anyways and need to be replaced or B) you're attempting to write your own crypto and you're going to do it badly. Using PRNG to obscure another one is a sin, you're trying to write encryption. (Sin being "to miss the mark" or point.)

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

#70

Post by malandrew » Sat, Jul 06, 2013, 7:32 PM UTC

contingencies wrote: post #43

malandrew wrote: post #38

Earlier quoted context omitted.

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.

I really need to get up to speed on cryptography. I've been a software developer for a while but haven't had a chance to get into it. Part of the reason is time, the other reason is that I haven't a clue where to start. I've heard about the books Security Engineering and Cryptography Engineering. Are they good books for someone new to all this?