Hacker News Reader

Comment by dododo | Hacker News Reader

what are these guarantees you refer to? most pass a battery of tests e.g., diehard: http://www.stat.fsu.edu/pub/diehard/ but if you give a PRNG x bits of entropy, then it can produce at most x bits of entropy over its entire output.

all PRNGs have cycles: that is, they'll produce random numbers x[1], x[2], ... , x[n], then random number x[n+1] = x[1], x[n+2] = x[2], .... often n isn't as big as you'd like, and sometimes there are correlations among x[i] and x[i+k] you really don't want (linear congruent generators have this problem).

View on HN

Run the output through a hash function, and also get another 80 bits of entropy before you get to the critical n where your generator repeats.

are you sure?

the PRNG is a deterministic function of its seed. the hash is a deterministic function of the output. if you do the math and calculate the entropy (this isn't hard) you'll see that the total entropy is still 80 bits because the distributions of the PRNG output given the seed, and of the hash given the output have no entropy. the marginal entropy of the PRNG is 80 bits if you don't observe the seed.

another way of seeing this is via the data processing inequality: http://www.neng.usu.edu/classes/ece/7680/lecture3/node2.html

Did you misread my statement as saying hashing the output will magically give another 80 bits of entropy? No, I'm saying to get another 80 bits before your PRNG repeats. I know you can infer things like linear congruential generators. I implemented such an inference program in grad school from someone else's thesis, then demoed it on a crypto USENET newsgroup. The hash is going to make inferring the seed much harder. Using a cryptographic PRNG will make even the unhashed output hard to infer. Using both is going to be way beyond the ability of most attackers.

why hash the output then? this is introducing a dependence in the PRNG that you seem not to need (nor want).

if you're going to generate another 80 bits of entropy, then simply use this as the seed for another PRNG. this, sure, i agree, will get you more entropy, because you're adding more entropy to the system from an external source (such as the advertised device).

Hashing the output makes the seed harder to infer from the output and also tends to make the output look better on randomness tests.

Reply on news.ycombinator.com