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)

#51

Post by Sharlin » Sat, Jul 06, 2013, 10:27 AM UTC

conradev wrote: post #17

mikeash wrote: post #8

Earlier quoted context omitted.

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

Indeed, although as the man page describes, /dev/random is too slow for most practical purposes. The entropy pool drains rather quickly and then the device will block while the pool refills.

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

#52

Post by nhaehnle » Sat, Jul 06, 2013, 10:38 AM UTC

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?

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 of uniform and independent random bits if at least one of the source streams is a stream of uniform and independent random bits (this is an elementary argument in probability).

I'm not certain at the moment whether this generalizes to pseudo-random generators, but it seems plausible enough to expect that the XORed bit stream is at least as "good" in terms of pseudo-randomness as the best of the input streams.

Edit: Okay, I just realized that this is obviously false when the input streams themselves are correlated. For example, suppose that one of the input streams is PRNG A, and the other input stream is simply the negation of the output of PRNG A with the same seed. Then the output stream will consist of all 0s, which is not good. Perhaps some result can be salvaged when the seeds of the different PRNGs come from independent, truly random sources, but this means things get very tricky very quickly.

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

#53

Post by lloeki » Sat, Jul 06, 2013, 10:47 AM UTC

arkem wrote: post #31

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

> most encryption schemes that you might use to secure the transmission require secure random number generation.

If I understand this correctly, most channel securing schemes require RNG for key exchange (e.g "no prior knowledge" DH key exchange) or pair generation (RSA), then you can move on to a symmetric cipher (whose key is derived from the resulting DH shared secret, or exchanged encrypted via RSA), which requires no RNG (until you want to change the key for PFS).

So one can assume scenario where only a quantum of entropy is needed to establish a secure connection, then refuel the entropy bucket with random data transmitted over the now secure yet "non entropy consuming" channel.

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

#54

Post by w-m » Sat, Jul 06, 2013, 11:49 AM UTC

btipling wrote: post #37

This random generator is found in some versions of Windows: http://www.schneier.com/blog/archives/2007/12/dual_ec_drbg_a... I don't know if it's in Windows 8 or not.

The link to msdn in your post is still working.

> The dual elliptic curve random-number generator algorithm. Standard: SP800-90

> Windows 8: Beginning with Windows 8, the EC RNG algorithm supports FIPS 186-3. Keys less than or equal to 1024 bits adhere to FIPS 186-2 and keys greater than 1024 to FIPS 186-3.

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

#55

Post by nikcub » Sat, Jul 06, 2013, 12:26 PM UTC

Intercepting signals is only half of the NSA mandate, the other half is securing national communications against interception by foreign governments and organizations.

It is possible that the NSA want other nations to have the impression that NSA audited communications protocols are insecure or may contain backdoors. They have never expressly come out to deny any of these accusations.

The involvement of the NSA thus doesn't imply that they wish to weaken standards. Perhaps they want people like Schneier to question the security of these protocols and create a false aura of potential vulnerability so that their opponents don't make use of them.

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

#56

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

StavrosK wrote: post #48

contingencies wrote: post #46

Earlier quoted context omitted.

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

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. Perhaps sometimes mathematicians in general take a not wholly dissimilar bent in their reasoning; ie. 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.

The threat of someone else having or coming up with a faster physical or logical method of deduction does threaten these assumptions.

The broader goal, then, is not to trust a single PRNG algorithm, or, if possible, branch of mathematics (I am not skilled in that area but heard Pythagorean vs. Elliptic Curve mentioned). I am positing that this level of paranoia is, whilst computationally and resource-wise somewhat more costly, probably a good idea, and that the example of the present article is a good one that demonstrates the efficacy of this line of thinking.

The secondary route of side-channel attacks is also hampered by this strategy, since arbitrary entropy sources (potential side channels) may be (re)assigned to arbitrary PRNG algorithms running in parallel at any time.

In summary: hedge thy bets.

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

#57

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

nhaehnle wrote: post #52

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?

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 degree of feedback, or with large initial random seeds. But I'm not a cryptographer, so that's all baseless assertion. IMHO the notion stands, though.

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

#58

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

nknighthb wrote: post #47

contingencies wrote: post #46

Earlier quoted context omitted.

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, y…

You've just exposed yourself to a possible related-key attack

It's a tradeoff for mitigating other, perhaps more realistic attack vectors.

the effective entropy of your key could be halved simply by one of the PRNGs being compromised

Halved is a whole lot better than wholly negated, which was the point of the suggestion.

Cryptography is hard.

Yeah.

Architecturally, though, it seems that (dis-)trusting two supposedly PRNG sources is better than all eggs in one basket with one.

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

#59

Post by StavrosK » Sat, Jul 06, 2013, 2:17 PM UTC

contingencies wrote: post #56

StavrosK wrote: post #48

Earlier quoted context omitted.

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

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 trust a single PRNG algorithm, or, if possible, branch of mathematics.

No, if you don't trust something, use something you do trust. The change you're proposing has more potential to do harm than good, e.g. render nine perfectly good PRNGs broken just because you mixed them with one broken one. If you had only used one PRNG, your adversary had to break that PRNG, but, now that you used ten, he only has to break the weakest one, so you've made things much easier for him.

> whilst computationally and resource-wise somewhat more costly, probably a good idea.

Nope, it probably isn't.

> In summary: hedge thy bets.

In summary, the entire crypto community is smarter than you (or me), and any improvement you (or I) think might work has probably been proven hopelessly broken a thousand times over. There's a reason people use a single PRNG, 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)

#60

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

contingencies wrote: post #41

moonboots wrote: post #26

Earlier quoted context omitted.

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.

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