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.
Received on 2011-11-03 23:31:23 CET