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

31–40 of 78 posts

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

#31

Post by arkem »

efm wrote: post #27

The ANU Quantum Random Number generator http://qrng.anu.edu.au/ can be used as a source of additional randomness for your server's pseudo RNG, or directly. They monitor quantum fluctuation of a vacuum to generate the random numbers at a high rate.

While it's an interesting project (I had fun playing with it) you really shouldn't be relying on remote sources of entropy for security purposes.

Generally the entropy needs to be secret to be effective so sourcing remote entropy reduces your security to that of the transport security (if any). It's hard to imagine a situation where you have a secure transport mechanism but do not have enough entropy since most encryption schemes that you might use to secure the transmission require secure random number generation.

Disclaimer: I am not a cryptographer, cryptology frightens and confuses me.

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

#33

Post by Myrmornis »

OK I have a probably naive/nonsensical cryptography question. It seems that one good way of transmitting a secret would be to do so with everyone thinking it is encrypted one way (or possibly believing it has not been encrypted) when the truth is it has been encrypted some other way. I.e. it would be a difficult problem to know when the message has truly been decrypted. So basically there would be multiple decrypted versions which are plausible as the true decrypted message. Is there any parallel to that sort of thing in modern mathematical cryptography?

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

#34

Post by tptacek »

The most important thing to know about Dual_EC_DRBG is that practically nobody uses it (I'd say "nobody ever uses it", but who knows, maybe something did?). It's a CSPRNG that involves bignum elliptic curve point multiplication. It's not something that's maybe slower than an alternative; it's something noticeably, horrendously slower than its alternatives. Even systems that use number theoretic crypto use it sparingly; nobody uses it to generate random numbers.

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

#35

Post by rogerbinns »

Myrmornis wrote: post #33

OK I have a probably naive/nonsensical cryptography question. It seems that one good way of transmitting a secret would be to do so with everyone thinking it is encrypted one way (or possibly believing it has not been encrypted) when the truth is it has been encrypted some other way. I.e. it would be a difficult problem to know when the message has truly been decrypted. So basically there would be multiple decrypted…

Encrypted traffic should be indistinguishable from random numbers. A quick test is trying to compress it, as true randomness has no patterns and hence nothing to compress.

In general you can tell exactly what compression was used because protocols start out in the clear and include some sort of negotiation. https://en.wikipedia.org/wiki/Transport_Layer_Security#Proto...

However both ends can separately agree that if they select one cipher suite, they will be secretly using a different one.

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

#36

Post by malandrew »

croikle wrote: post #9
malandrew wrote: post #3

Out of curiosity, why can't we just use a series of sensors on the computer to generate random numbers? Between mouse movements, touch inputs, video camera input, microphone movements, the behavior of applications in your system and how they use resources like RAM, CPU, hard-disk, listening to all the wifi + bluetooth signals around you and munging them, etc. I would imagine that there is enough entropy coming in thr…

This sort of thing is used, e.g. [0]. It collects entropy at a limited rate, though, so for demanding applications (SSL servers, say) you want dedicated hardware: [1], [2]. [0]: https://en.wikipedia.org/wiki/Hardware_random_number_generat... [1]: https://en.wikipedia.org/wiki/RdRand [2]: http://www.entropykey.co.uk/

How do those Entropy Keys work? What sort of environmental random data does it rely on for creating random bits?

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

#38

Post by malandrew »

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…

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 input. To figure out how much random data to produce, simply add an extra bit that is passed along to all the functions that indicates depth (how much show the true random data be processed before returning it to the program that needs a random number). This approach would produce a lot more random data that could only be determined if you knew the original true random data input and the amount of entropy that was required at the time since you'd need to know the depth used to know when to exit the functions.

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

#39

Post by wiml »

malandrew wrote: post #36
croikle wrote: post #9

Earlier quoted context omitted.

This sort of thing is used, e.g. [0]. It collects entropy at a limited rate, though, so for demanding applications (SSL servers, say) you want dedicated hardware: [1], [2]. [0]: https://en.wikipedia.org/wiki/Hardware_random_number_generat... [1]: https://en.wikipedia.org/wiki/RdRand [2]: http://www.entropykey.co.uk/

How do those Entropy Keys work? What sort of environmental random data does it rely on for creating random bits?

Thermal noise of various kinds, usually.

(Edit: that is, the noise introduced in a circuit by the fact that it's not at absolute zero, e.g. Johnson noise. Not just gathering entropy from a temperature sensor reading or something like that.)

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

#40

Post by contingencies »

nknighthb wrote: post #13
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…

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?
Post reply on HN