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

[David Mercer]

On Thu, Oct 31, 2013 at 11:09 PM, Jerry Leichter <leichter at lrw.com> wrote:

> 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.



> Whenever I've delivered more than (arbitrary number) 1/3 of the bits in
> the pool, I won't deliver any more until I've (a) done a cryptographically
> secure hash; (b) received at least N network packets; (c) received at least
> K updates from other machines.  If network packets aren't arriving fast
> enough, I'll start listening promiscuously.  If that doesn't give me
> enough, I can start sending "please send me a random update" requests to
> nodes I know about, which generates both those updates, and traffic.
>  (During the first boot the "wait long enough" logic actually isn't based
> on time but on number of packets received.)
>

Your datacenter description is a pretty good match for what I've seen in
the last 10+ years for decently high-end facilities. The main flaw I can
see is in using the network for entropy on boot up, especially on first
boot. As there are quite a few services starting up that need good random
numbers in most systems, you are as you say going to wait a while to grab
enough entropy. Your entropy collection is going to have to start so early
in the boot process that you aren't going to be sending out much, if any,
network traffic, and are not going to be getting much of it.

You need to wait to start up any services that use encryption of any kind,
and which use it you can't know about ahead of time, so you need to start
before pretty much anything else. Which means before all the things that
might send out network traffic.

Listening promiscuously is NOT going to help, as you're going to be on a
dedicated switch port. The only thing to listen to is the switch. Maybe
some arp packets or similar??

Sticking a transparent bridge machine between a system being measured and a
switch port and sniffing everything travelling between them would let you
see what network traffic you get in a real world install and first boot
scenario.

"First boot" really refers to "first post-install boot", and is one of the
lowest entropy points in a systems life-cycle. If you start collecting
entropy during the installation, when lots of network packets are likely to
be flying around, and save the RNG state so that it has a decent amount of
entropy saved on "first boot". If your install process sucks down your
entropy pool, you might not have much to save, and you'd have to save the
amount of entropy estimated remaining when you saved it's state.

-David Mercer
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20131101/7d2a8bd5/attachment.html>