Re: [Cfrg] updating RFC 1750

[Don Davis <dtd at world.std.com>]

At 4:45 PM -0400 9/1/04, John Kelsey wrote:
> 5.2.4
> It sure is hard to see where someone is actually going to use
> the FFT or LZH to deskew data that they're then going to process
> with SHA1 or AES to get a seed for their cryptographic PRNG. 

hi --

i completely agree that the RFC shouldn't recommend
using the FFT for de-skewing.  as an author of the
paper that mentioned FFT for deskewing, i guess i
ought to explain that my coauthor ross ihaka suggested
using the FFT to whiten the disk noise for theoretical
reasons, not for practical reasons.  our point was
to show that one _could_ get true, mathematical random-
ness from disk noise, as a way of proving that there
is true entropy in the disk timings.  now, having
established that true entropy is present in disk timings,
it's sufficient to use a hash function for de-skewing
in normal use.

> 5.3.2
> This is a nice reference, but it doesn't seem like you see
> many people using it in practice, at least not directly.

actually, everyone who uses /dev/random uses disk
randomness.  but anyway, the RFC's purpose isn't only
to document the standard practices of the moment.

> It's very hard in software to know how many layers of cache
> memory are between you and your hard drive, and sometimes,
> the drive is virtual, or is a network drive, or is a flash drive.

these concerns are actually easy to address:  a 
disk rng just has to discard all sub-millisecond
access times, in order to keep cache hits and
memory-disk accesses out of the timing-stream.
also, it's not hard for the kernel to tell the
difference between a local drive and a remote
drive, and the kernel is where a disk RNG belongs,
anyway. 

finally, caching controllers don't impair a disk RNG's
productivity, because a caching disk-controller just
allows a hard drive to service more I/O requests.  
the disk RNG discards the cache-hit timings, but
because the disk is still busy with other requests,
there's no shortage of usably noisy timings.

from RFC 1750:
>> 5.3.2 Using Existing Disk Drives
>> ...most disk drives easily produce 100 bits a
>> minute or more of excellent random data.

our '94 paper's figure of 100 bits per minute is
obsolete.  modern computers afford higher-precision
timings, and modern disks' speed regulation is much
_less_ accurate than the disk i used in my experimental
setup, so much better entropy-rates are now possible.

it turns out that for every doubling of the CPU's
timing accuracy, one gets an additional bit of
entropy from every access-timing.  for example,
with a normal disk-speed of 5400 RPM +/- 5%, the
disk's rotational period is 11 msec +/- 500 usec.
so:
  * if the CPU's clock affords 1 usec I/O timing
    accuracy, each access-time has roughly
       log2(1000usec/1usec) = 10 bits
    of variability.
  * if instead the CPU can give 10 nsec accuracy,
    we get log2(1000usec/10nsec) = 16.6 bits per
    access.

assuming the disk performs 1000 accesses per minute,
these disk RNGs would afford 10000 to 17000 bits per
minute.

in the setup i used for the '94 paper, i had a
3600 +/- 0.03% RPM disk, so that disk's period
variation was only +/- 5 usec.  further, my CPU 
afforded only 1 msec timing accuracy.  so, i was
forced to measure a small variation with a coarse-
grained clock, and it was this disparity that kept
our entropy rate down to 100 bits per minute.

				- don davis, boston







-

_______________________________________________
Cfrg mailing list
Cfrg at ietf.org
https://www1.ietf.org/mailman/listinfo/cfrg