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

[Hannes Frederic Sowa]

On Thu, Oct 31, 2013 at 11:09:38AM -0400, Jerry Leichter wrote:
> It's become very difficult to know where sound engineering practice ends and tin-hat paranoia begins.  I'd like to propose one way to get at what reasonable boundaries are:  I'll lay out a particular, I hope realistic, proposal, and then ask the group to play attacker.  After all, the best way to understand what's needed for defense is to try to attack.  To that end:
> 
> I am the owner of a data center.  I have some hundreds of physical machines, with old ones being decommissioned and new ones being added periodically.  These run thousands of VM's that are created and destroyed much more frequently.  The machines are interconnected by a number of high-speed (say 10GigE or better) networks, further partitioned for security purposes into multiple VLAN's.  None of these networks are visible outside the boundaries of my data center.  Connection to the Internet is via bastion routers.  There's a DMZ, all the usual stuff.  I have excellent physical security, and I regularly "patrol the perimeter", as well as the internal physical plant, so I assume that any attempt to run additional network links into my data center, plant significant hardware, etc., will be noticed fairly quickly.  I'm actually paranoid enough that I've spec'ed conductive mesh throughout the outer structure, so the data center is effectively inside a Faraday cage (i.e., no magic r
>  adio connections to the outside), and of course I check this periodically as well.  As a result of all this, I choose not to consider physical threats; nor, because ultimately there's nothing I can do about them, on-going sophisticated insider attacks.
> 
> I use a very simple random number generator:  There's a "random pool" of a few thousand bits.  At first boot, it's initially populated using whatever I can get my hands on principally the MAC address, any serial numbers available, etc.  At shutdown, the state is stored locally; at restart, it's restored to the previous state.  The first boot logic will wait for a significant period of time to gather entropy as I'll describe in a moment before allowing any processes that use random numbers to proceed.  (Reboot may also wait a bit, but not nearly as long.)
> 
> There is *exactly two* sources of entropy.  The primary one is watching the network:  Each time a network packet arrives, mix into my pool the full contents of the packet, the value of the real-time clock, and the value of the CPU cycle counter.  The secondary source is other machines in the datacenter:  Each machine will periodically get from some fraction of other machines scattered through the network some number of random bits, delivered in an encrypted packet using a key agreed upon between the two (based on their own randomness), and also mix that in.  The mixing function is like that in the Linux RNG - "good enough but fast enough" - but not cryptographically secure as that's too expensive.  To make up for that, periodically (say every millisecond or so) I also scramble the pool using a cryptographically secure 1-way hash.

Are we talking about real world operating systems? Most of them
already need good random data to bring up the kernel and especially the
network. So maybe you already drunk from the non-fully-seeded entropy
pool (in your case only mac address and serial numbers) to install
long-lived secrets before you could apply the old state. Most of these
secret keys protect you from DoS attacks (randomized hash tables) but
some could be more exposed (e.g. tcp syncookie secrets).

So only depending on the network to gather entropy from the network
does not sound that good (given you only used static data to initialize
the entropy pool). I guess you need a bootstrap procedure for the DC to
make sure the application on the first machine powered on does not have
weaker random keys.

Hopefully Linux 3.13 will initialize some of these secrets (socket
hashes, syncookie key, tcpfastopen key) as late as possible, e.g.
when the secret is needed for the first time (next step is to have no
long-lived secrets at all because it may still be too early).

Greetings,

  Hannes