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

[John Gilmore]

> So actually the "beacon" should be done differently.  Every existing
> system that already has access to randomness, will periodically
> multicast some "random bits".  A newly booted system is able to see
> this stuff (it will have to know where to look, of course).  The
> bits themselves aren't particularly useful, but the timing
> information should be.

This is sort of like "BOOTP for RNGs".  It sounds like an interesting
R&D project.  Deliberately relying on external inputs (even the timing
of external inputs) invites attackers, of course.  And spraying output
from your well-fed RNG out to the world invites a different class of
attackers.  Which is why this is more like a multi-year research
effort as opposed to an implement-it-and-forget-it service.

Multicast is a good technology for this.  Except that in IP multicasting,
the sender specifies how far the packets should spread through the net
(by setting the TTL and/or the multicast address).  In this case, a
randomness-starved receiving host might prefer to ask, "Could I have
some multicasts from several hops away, please?" -- but the existing
IP multicast protocols don't let it do that.

Let's do it another way.

Since all that a randomness-starved, unconfigured host can trust to be
"random" is the CPU tick counter when the packet arrives, the system
might as well ask for multicast "time updates" as "randomness
updates".  There are already protocols and deployed servers for that,
and indeed the unconfigured host is probably already using some
variant of them to set or tune up its clock!

There is a multicast group defined for time signals.  NTP can
multicast time packets.  The address is 224.0.1.1 in IPv4, FF0x::101
in IPv6 (typically FF02::101 for a link-local multicast or FF05::101
for a site-local multicast).  

One challenge is that NTP tries to severely limit the amount of
bandwidth that it uses (since it runs all the time).  The default
seems to be for a multicast server to send one multicast packet every
64 seconds.  That won't get a client much entropy very quickly, so the
client might have to send some multicast requests ("manycasts") asking
for time updates (which can provoke unicast responses that will reach
the client and tickle its CPU tick counter's entropy).  There is also
a "burst" mode in modern NTP clients, which will send eight packets
at multi-second intervals, trying to get a good characterization of
the delay and jitter between itself and its time servers, which will
increase the number of packets used quickly in initial synchronization.

Making the entropy service subtly depend on the time-sync service
seems like a recipe for some likely failure modes.  I wonder what we
can suggest to make them more obvious when occurring?  Maybe
/dev/random should spit out a kernel message "/dev/random blocking for
more entropy; is NTP and/or rngd running?" when it blocks.

	John