[svn.haxx.se] · SVN Dev · SVN Users · SVN Org · TSVN Dev · TSVN Users · Subclipse Dev · Subclipse Users · this month's index

Re: [RFC] ra_svn::make_nonce: how to cope with entropy shortages?

From: Greg Hudson <ghudson_at_MIT.EDU>
Date: Thu, 03 Nov 2011 18:30:45 -0400

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

This is an archived mail posted to the Subversion Dev mailing list.

This site is subject to the Apache Privacy Policy and the Apache Public Forum Archive Policy.