On 11/03/2011 05:10 PM, Jonathan Nieder wrote: > Why would that be? When someone dumps in 20 bits of data from a > strong, in-hardware, random number source, even if the PRNG is utterly > stupid, it can have an unguessable 20 bits of internal state. After > reading enough random numbers, I will have enough information to guess > the seed and learn what comes next.
If you want to attack a PRNG, you need very little of the output state--only enough to distinguish between the possible values of the generator seed. What you do need is for the generator seed to be partially guessable; otherwise, you will be trying to brute-force a 128-bit or 256-bit seed, which is impractical. If I somehow know the initial generator state, and you reseed your generator with only 20 unguessable bits, I will be able to determine those bits using 20 bits of output and 2^20 effort (which is easy), and then I will know all of the generator state again. However, if you reseed with enough unguessable bits that I can't brute-force them, it doesn't matter how much output I see; I will never again be able to determine the internal state. For the Fortuna generator, for instance, if I discover a way to determine the generator state solely by observing the output, then I will also have discovered a plaintext recovery attack against AES-256. For more, see chapter 9 of _Cryptography Engineering_. > A good PRNG helps mitigate that somewhat More than "somewhat". Any PRNG which doesn't have the above properties in its generator is insecure for any cryptographic purpose, and would be considered a security bug in the operating system. In another message, Peter Samuelson wrote: > apr_time_now() has microsecond resolution. It has microsecond precision but not necessarily microsecond accuracy. For instance, http://fixunix.com/kernel/378888-gettimeofday-resolution-linux.html suggests that two requests arriving within a 10ms window could get the same nonce.
