/dev/random is probably not

[John Kelsey]

>From: "Charles M. Hannum" <root at ihack.net>
>Sent: Jul 3, 2005 7:42 AM
>To: Don Davis <dtd at world.std.com>
>Cc: cryptography at metzdowd.com
>Subject: Re: /dev/random is probably not

...
>Also, I don't buy for a picosecond that you have to gather
>"all" timings in order to predict the output.  As we know
>from countless other attacks, anything that gives you some
>bits will reduce the search space and therefore weaken the
>system, even if it does not directly give you the result.

I think you're landing on the genuinely hard problem here.
Designing a PRNG intelligently is an exercise in design and
cryptanalysis, so long as you get to assume that you know
how much entropy you're getting.  But actually getting
reliably entropy estimates is:

a.  A data analysis problem, where you never really get a
final answer, you just get the best model you knew how to
test and don't find strong evidence to discard it, and 

b.  Enormously sensitive to implementation details that are
hard to deal with in software.  In a hardware RNG design,
you can at least analyze test-mode raw outputs of the ring
oscillator or whatever, build a statistical model, and know
that the same basic model will also describe the devices in
the field.  They may vary because of manufacturing defects,
changes in the field (like heating/cooling or component
failure), etc., but you at least know what kind of thing
you've got.  With software sources, there's pretty much no
limit to what changes the designer of the hardware is
allowed to make to your devices, so long as he keeps the
interface the same.  You do lots of analysis on a machine
with a spinning disk drive, and end up on one with one
networked drive and one flash drive, or some such horrible
thing.  

Additionally, building a probability model for stuff you
observe on a general purpose computer is *hard*, because
there's so much complicated deterministic stuff going on.
Even if you're using the same machine and setup to collect
entropy in production as you did to build your probability
model for entropy estimation, it's hard to have enormous
confidence in the correctness of your estimates.  How much
of that apparently random behavior you were getting when you
sampled the cycle counter in a tight loop was because of
genuine unpredictability, and how much was because of the
very patterned but complicated stuff going on behind the
scenes on your machine? 

--John

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com