[Cryptography] Finding Entropy Isn't That Hard

[Kent Borg]

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


[* 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.]


-kb