[Cryptography] What's a Plausible Attack On Random Number Generation?

[John Denker]

As one possible answer to the question in the Subject: line 
of this thread:  The #1 all-time most-plausible method for
attacking a PRNG starts by finding out how badly initialized 
the thing is.

Some actual observed facts:
                                   prior
     startup script                #bits
   ---------------------           -----
   (mountall)                      18816
   (mounted-run)                   21888
   (sshd server)                   35616
   (network-interface : lo)        55968
   (network-interface : eth0)      68832
   (urandom)                       79168

In the left column, we have the description of a startup script,
as observed on an ordinary Linux system.  In the rightmost column 
we have the number of bits extracted from the kernel PRNG before 
said script gets invoked.

These are "typical" numbers, as discussed below.

1) The script that claims to be in charge of initializing the 
kernel PRNG is getting called late in the game.  This definitely 
a problem.

2) In general, it is not sufficient to initialize the PRNG from a 
external web server, DHCP server, or anything like that. That’s 
because network connections are likely to become available too 
late in the boot-up process. As you can see from the numbers 
tabulated above, a *lot* of water has flowed under the bridge 
before the network devices come up, and IMHO it would be a Bad 
Idea to assume (or require) that nobody can do anything random 
until this-or-that network device come up, let alone completed 
the DHCP process.

 -- The device might have a fixed address, or some other reason
  for not doing DHCP at all.
 -- The device might be a USB dongle that gets hotplugged long
  after the system has come up, if at all.
 -- etc. etc. etc.

It could be argued that it is "sometimes" OK for everybody to wait,
but that argument doesn't cut it.  The shoe is on the other foot.
Security requires evidence that it is /always/ OK, but this
remains unproven and IMHO implausible.

The upstart process is asynchronous, for good reason.  As a
consequence, the numbers tabulated above will exhibit some
variation.  Indeed, even the order in which things come up is 
not 100% reproducible.  However, it is not necessary for me to 
prove that the DHCP idea always fails.  That shoe is still on 
the other foot.  If anybody wants to "implement it, standardize 
it and forget it" they should please provide evidence that it 
always works.  The tabulated numbers suffice to prove that unless 
sweeping changes are made, it doesn't always work.

Of course the stuff deployed in the current Linux distros is also
several sandwiches short of a picnic.

The problem is entirely fixable, but it's a lot harder than most
people think.  There are a thousand ideas that look like quick
fixes at first glance, but do not withstand serious scrutiny.

I still think that proper care and feeding of a /seed file/ is
the way to go.  As you can see from the tabulated numbers, it
will be a challenge to get the file loaded early enough.