<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
</head>
<body>
Entropy is important to RNGs but unfortunately RNG people are at
risk of devoutly worshiping at the alter of "Countable Entropy",
blinded to realities, ready with jeers for anyone who does not share
their extreme theology.
<p>These people are so in the thrall of the theoretical that they
are blinded to the practical and any other theories.<br>
</p>
<p>And for practical purposes, it is the unguessability of the RNG
that matters. Any source of unguessable data is a good thing to
use to drive an RNG. Even sources that are dismissed as "squish"
by the most devout and most blinded can be good. And there is a
great example that these disciples can't see.</p>
<p>And now I need to shift the subject for a moment. It is on topic,
honest.<br>
</p>
<p><br>
</p>
<h3>Time Distribution is Hard</h3>
<p>NTP is really great, I love it, so cool. It can set my computer's
clock with a precision measured in milliseconds. Very impressive
it can do this just by applying algorithms to hardware that is
already present. </p>
<p>If one wants better, the next option is to get time from GPS.
According to gps.gov a specialized receiver, at a fixed location,
can know the time within 40ns. This is pretty cool, too. It is
good enough to synchronize RF signals between CDMA cell sites so
phones can communicate with more than one site as the same time.</p>
<p>GPS also depends on billions of dollars of infrastructure with an
annual budget that must be in the millions. People think GPS is
about location, but at its core it is <i>really</i> about time
distribution. From end-to-end a design where every component is
doing its best to carefully keep and distribute precise time. If
one pays attention to details and has the money for good hardware
(far more than just a smartphone), to get 40ns is very cool.</p>
<p><br>
</p>
<h3>Guessing Time is Even Harder<br>
</h3>
<p>With all that money can constructive effort, one can do 40ns.
What are <i>you</i> going to do to do better? Get specific.
(Warning, it's not going to be easy.)<br>
</p>
<p><br>
</p>
<h3>Cheap Unguessability</h3>
<p>A 1 GHz clock has a cycle time of 1ns. (Is it even possible to
buy an Intel-based machine that runs slower than 1GHz these days?)
1ns is a lot smaller than 40ns. You don't know the value of my
clock.<br>
</p>
<p>Intel chips have a timestamp counter that increments with every
tick of the system clock. You don't know the value of my counter.</p>
<p>The system clock isn't fed to the CPU, the CPU is fed a much
lower frequency, that it then multiplies up using analog on-chip
PLL circuitry. That clock is then (carefully) distributed on-chip.
And even then, different parts of the chip are in different clock
domains, because clock distribution and synchronization is hard.</p>
<p>So the "system clock" doesn't exist outside the CPU, it is only a
"CPU clock", and not all parts of the CPU are even privy to it.</p>
<p>No one at any distance outside that chip knows the value of the
timestamp counter. A program might contain the instruction to read
the timestamp counter, but by the time anything is done with that
value, it will have changed.</p>
<p>Is there "entropy" in that system clock? Some, but only some. The
PLL will have some jitter, the precision of the lower frequency
input clock will have iffy precision and be subject to drift. </p>
<p>Is there "unguessability" in that system clock? Plenty! At least
to any observer at any distance (i.e., outside the computer).<br>
</p>
<p>Remember, it takes billions of dollars and lots of careful design
and cooperation to distribute 40ns. time. No such effort nor
expense has been made to tell the world the precise value of my
1ns period (or less) CPU clock.</p>
<p>No one outside my computer knows its precise value. </p>
<p><br>
</p>
<h3>Back on Topic</h3>
<p>Intel hardware has a great source of unguessability in its
timestamp counter. All you need is an uncorrelated sampling of
this clock. Say, a network interrupt. <br>
</p>
<p>I know the squish patrol is now <i>all</i> upset, because
external observers can be the one's sending these packets with
careful timing. So what? The timing can't be careful enough. The
value that is read from the timestamp counter in servicing that
interrupt depends on knowing edge timings far more closely than
1ns, for every time the observer guesses a value on the wrong side
of one of these edges, one bit of unguessability slips by.</p>
<p><br>
</p>
<h3>RNGs are Still Hard</h3>
<p>A (1) uncorrelated sampling of a (2) fast clock is, indeed, a
good source of unguessability. <br>
</p>
<p>But, make sure both those things be true.<br>
</p>
<p>Is virtualization messing with how these things work? Is variable
clock scaling messing with it? Have interrupts been virturalized
in some predictable way? Is the timestamp counter being messed
with in an attempt to have it not appear to be warped by clock
scaling and effectively running much slower? Is some OS scheduling
algorithm synchronizing interrupt servicing with timestamp values?
<br>
</p>
<p>Just because there is an underappreciated way to feed an RNG
doesn't mean there aren't plenty of ways to still mess it up.
("Um, it turns out the RNG isn't <i>in</i> production builds."
Who will notice?)</p>
<p>Implementation matters.</p>
<p><br>
</p>
<p>But the fact remains time distribution is hard, the period of a
gigahertz clock is small. No one at any distance knows its value.
An awful lot of computers out there can use this to drive their
RNGs.<br>
</p>
<p><br>
</p>
<p>-kb, the Kent who laments that Arm CPUs didn't have something
like a timestamp counter last he looked.<br>
</p>
</body>
</html>