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

[John Denker]

On 10/31/2013 07:22 PM, Jerry Leichter wrote:

> Every time there's a discussion of RNG's, someone proposes using 
> network timing information, and someone else responds no, you can't 
> use that, an attacker can watch the network and learn or influence 
> enough to ruin your generator.  I'm suggesting that those who adhere
>  to one view of the other move away from abstractions and *prove
> it*,

I understand the question.  It's a perfectly fine question
... but it may not be answerable.  There is an important
category of stuff I call "squish" ... namely stuff that is
neither reliably predictable nor reliably unpredictable.
I suspect timing information is in this category.

Also note that good engineering -- and in particular engineering 
management -- requires looking not only at the strengths and
weaknesses of plan A, but also at the strengths and weaknesses
of all the plausible alternatives.

So, any analysis that artificially restricts attention to just 
network timing will never be a serious, professional-grade 
analysis.  If you ask the question too narrowly, the answer 
is guaranteed to be "no" ... for several reasons:
 -- Even if it works in a datacenter, network timing doesn't 
  work for a handheld device that powers up with no network 
  connectivity at all.
 -- In a datacenter or elsewhere, network timing will have a 
  very hard time competing with easier and better solutions, 
  such as a properly provisioned seed.  Let's be clear:  Even 
  if you could get it to work in some technical sense, it would 
  not be competitive.  It would not be worth bothering with, 
  because there are easier and better solutions.

Security generally requires a minimax approach, which is why
squish is not useful.  Squish would be great in a best-case
scenario, but there's no point in designing something on that
basis.

============================

> if I go out to build a datacenter from off-the-shelf parts today, my
> hardware won't include the (fairly minor) bits and pieces needed to
> implement Turbid on every physical machine

Really?  If you shop around you can find off-the-shelf server-class 
mainboards with built-in audio.  There are plenty that don't have
audio, but some that do ... and if the demand went up the supply
would go up pretty fast.  In the worst case, you can add a USB 
audio dongle for about $5.00.

> and my virtual machines will have no hope at all.

They're hopeless if they have to rely on network timing, but 
not hopeless in general.

There are lots of ways that a host machine can provide 
randomness to its guests.  virtio-rng among many others.  It 
takes a bit of engineering and a bit of fussing to get this 
set up (both host and guest) and it helps if the host has a
copious supply of randomly-distributed numbers to draw on ... 
but if you have thousands of VMs the incremental cost per VM 
is essentially zero.  Certainly it's small compared to the 
cost of cleaning up after a security breach, which is the 
all-too-likely alternative.