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

11–20 of 78 posts

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

#11

Post by contingencies »

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 assumption that their state can be modelled to expose weaknesses. By viewing an entire, shifting, 'topology' of PRNGs as a single polymorphic source for pseudorandom data, surely this class of attack becomes much more difficult and we avoid either placing absolute trust in a single PRNG author, input entropy source, or a single mathematical approach.

I suppose this has already been done to the extent reasonable and that tradeoffs versus performance and available entropy input rates are probably responsible. But I'd still be keen to hear someone thrash this out in understandable prose.

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

#12

Post by jahewson »

derefr wrote: post #5
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…

I believe that, at least in Linux, ACPI thermal sensor readings are used for this purpose.

It has probably been done, but there is not much entropy in those low-precision temp readings. Linux support for ACPI is not great anyway.

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

#13

Post by nknighthb »

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.

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

#14

Post by lvs »

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…

you're right, my friend. look up entropy. it's used in linux and windows kernels, and some processors have it implemented at a hardware level.

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

#15

Post by anigbrowl »

trotsky wrote: post #7

_NSAKEY discovered two years before patriot act is passed? coincidence? i think not!!1 said another way, what relates the two events in the editorialized title? Just an end of the innocence type vibe? Trusting the sigint guys to design your crypto has always been a well acknowledged double edged sword.

The Patriot Act was passed in late 2001. It was renewed in 2009.

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

#16

Post by marshray »

This is one of my favorite examples showing the need for 'Nothing up my sleeve' numbers. https://en.wikipedia.org/wiki/Nothing_up_my_sleeve_number

I believe NIST learned their lesson, and it was applied in the design of SHA-3: http://crypto.stackexchange.com/questions/6444/why-are-the-c...

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

#17

Post by conradev »

mikeash wrote: post #8
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…

I don't think that application behavior would be a good source of entropy, since it is, at least in theory, predictable. The others are probably good, although you need to be sure to only use the least significant bits, and make sure that the sensor doesn't have some weird behavior which makes the least significant bits predictable somehow. If I had to hazard a guess, I'd say that this isn't often done simply because…

> I'd say that this isn't often done simply because computers didn't typically have a lot of sensors until recently

I thought it was done a lot, for example, in the Linux kernel: "The random number generator gathers environmental noise from device drivers and other sources into an entropy pool." [1]

[1] http://man7.org/linux/man-pages/man4/random.4.html

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

#19

Post by dhx »

There was significant discussion and concern in the academic community[1][2][3] during the early 90's in response to NIST's draft standard for digital signatures (DSS). The academic community was concerned that field parameters could have been carefully selected such that they contained hidden properties (weak primes, etc). This is why "nothing up my sleeve numbers"[4] must be used in cryptography. The same issue impacts the selection of prime field parameters for use in ECDSA/ECDH (TLS, S/MIME, etc). Worth noting is that NIST P-256 and NIST P-384 elliptic curves were selected from "verifiable random numbers" generated in accordance with ANSI X9.62. This standard is not freely available so I am not sure which PRNG was used to generate the curve parameters and why the PRNG seed is considered a "nothing up my sleeve number".

[1] Daniel M Gordon. Designing and detecting trapdoors for discrete log cryptosystems (1993). http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.97.3...

[2] Yvo Desmedt, Peter Landrock, Arjen K. Lenstra, Kevin S. McCurley, Andrew M. Odlyzko, Rainer A. Rueppel, Miles E. Smid: The Eurocrypt '92 Controversial Issue: Trapdoor Primes and Moduli (Panel). 194-199. http://link.springer.com/content/pdf/10.1007%2F3-540-47555-9...

[3] Miles E. Smid, Dennis K. Branstad. Response to Comments on the NIST Proposed Digital Signature Standard. http://link.springer.com/content/pdf/10.1007%2F3-540-48071-4...

[4] https://en.wikipedia.org/wiki/Nothing_up_my_sleeve_number

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

#20

Post by trotsky »

anigbrowl wrote: post #15
trotsky wrote: post #7

_NSAKEY discovered two years before patriot act is passed? coincidence? i think not!!1 said another way, what relates the two events in the editorialized title? Just an end of the innocence type vibe? Trusting the sigint guys to design your crypto has always been a well acknowledged double edged sword.

The Patriot Act was passed in late 2001. It was renewed in 2009.

http://en.wikipedia.org/wiki/NSAKEY
Post reply on HN