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

[Theodore Ts'o]

On Sat, Nov 02, 2013 at 04:36:13PM -0700, John Denker wrote:
> 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.

You didn't say which Linux distribution you measured this on, but you
later on you mentioned, "upstart".  So I suspect you ran this on an
Ubuntu system.  On a Debian system, which still uses sysvinit (as God
intended :-), the ordering is quite different.  The urandom script is
run before networking is enabled, and in fact this is enforced by the
init script's dependencies:

### BEGIN INIT INFO
# Provides:          networking ifupdown
# Required-Start:    mountkernfs $local_fs urandom
# Required-Stop:     $local_fs
# Default-Start:     S
# Default-Stop:      0 6
# Short-Description: Raise network interfaces.
# Description:       Prepare /run/network directory, ifstate file and raise network interfaces, or take them down.
### END INIT INFO

So your observation the urandom init script is being late is
apparently configuration bug for Ubuntu.  Debian sysvinit's has a
dependency which requires that urandom be run before we bring up the
networking stack.  Clearly that dependency is missing for Ubuntu's
configuration.

The other thing to note about the "number of bits being extracted from
/dev/random", a large number of these bits are being used to support
the ASLR for the processes being executed out of the various init
scripts.  For example, the fact that the bits used to initialize the
ASLR for processes such as "mount" and "fsck" were before the RNG was
fully initialized is not as important compared to the ASLR for
processes such as inetd and sshd, which are (a) long-running, and (b)
listening to network connections, where they might be more likely to
encouter external inputs that might trigger a potential buffer-overrun
attack.

So the important here is to make sure that "/etc/init.d/urandom start"
is run before networking and the networking daemons are started up.
This is definitely true for Debian, and I suspect it's true for Red
Hat Enterprise Linux, since it also uses sysvinit.  I don't know about
Fedora systems using systemd; they might have a similar problem, but
this is fundamentally an boot services configuration problem.

Regards,

     		      	      	       		     - Ted