[Cryptography] Finding Entropy Isn't That Hard
kentborg at borg.org
Thu Sep 12 10:41:46 EDT 2013
On 09/11/2013 07:18 PM, Perry E. Metzger wrote:
> the world's routers, servers, etc. do not have good sources,
> especially at first boot time, and for customer NAT boxes and the like
> the price points are vicious.
I agree that things like consumer NAT boxes have a tricky problem, and
anything that needs high bandwidth random data, but otherwise routers
and servers are not as bad off as people say. At least in the case of
modern servers that are running enough of an OS to include a good
entropy-pool RGN (like Linux's urandom*).
These boxes have GHz-plus clocks, so fast that the "box" doesn't have
that clock, it only exists on-chip. It is multiplied up from a lower
frequency external crystal oscillator by an analog PLL which is also
on-chip. This fastest clock is commonly used to drive an on-chip
counter. These chips also have interrupts from the outside world.
There is real entropy in the interaction between the two.
What is that value of that counter when the interrupt is serviced? I
assert there is entropy in the LSB of that value. A GHz-plus clock is
running just too fast for someone meters (or kilometers) away to know
its exact value. And every time the observer might get the LSB wrong, a
bit of entropy got by: Use that data to stir an entropy pool.
How do we know it is hard to know the value of a GHz-plus counter?
Because of the engineering problems suffered by people trying to build
fast systems. Clock distribution is difficult--there is a reason that
high speed clock doesn't exist off-chip, the skew becomes great. Even
on-chip clock distribution is tricky and requires careful layout rules
when designing the chip. And even on this fast chip, the uses of the
fastest clock are limited and any functions that will work on a slower
clock will get a slower clock. Clock distribution is hard. Hard within
a large IC, hard on a circuit board, hard between circuit boards, hard
between boxes, hard between equipment racks, hard between
buildings...how far away is this nefarious observer, the one who you
worry might be able to infer the LSB? I think more than a few cm is too
far away and if you don't have security at that radius, you don't have
[* Until Linux kernel 3.6 the person maintaining urandom was busily
turning off interrupts as a source of entropy, I think because he didn't
know how much entropy he was getting so better not to get it at all
(huh?). In 3.6 this was changed to use all interrupts as entropy
sources, which is good. This means earlier kernels aren't so
good--though I notice that Ubuntu's kernel has the 3.6 improvement in
their version of 3.2, so individual distributions will vary.]
More information about the cryptography