building a true RNG

[David Honig]

At 11:45 AM 7/25/02 -0400, John S. Denker wrote:
>David Honig helped focus the discussion by advocating the 
>block diagram:
>
>> Source --> Digitizer --> Simple hash --> Whitener (e.g., DES)
>
>Let me slightly generalize this to:
>! Source --> Digitizer --> hash --> Whitener (e.g., DES)
>
>i.e. we defer the question of whether the hash is "simple" or not.
>
>I continue to claim that
> a) if the hash function happens to have a property I call "no 
>wasted entropy" then the whitening stage is superfluous (and
>you may decide to classify the hash as "non-simple");  

Not wasting entropy does not mean that a function's output 
is "white" ie uniformly distributed.  E.g., a function 
which doubles every bit: 0->00, 1->11 preserves total
entropy but does not produce uniformly distributed output.
(It also reduces entropy/symbol.)

The simple-hash's --lets call it a digest-- function is to increase the
entropy/symbol
by *reducing* the number of symbols while preserving *total* entropy.
A function like xor(bit N, bit N+1) which halves the number of bits
can do this.  While its output is whiter than its input, its output 
will not be perfectly white unless its input was.  

The crypto-whitener produces perfectly uniform output.  It also 
hides the analog source and digest's regularities.  


>Well, then, suppose that the raw data coming off my digitizer
>consists of an endless sequences of even-parity words.  The
>words have lots of variability, lots of entropy, but the parity
>is always even.  Then the output of the simple-hash is an endless 
>sequence of zeros.  I encrypt this with DES.  Maybe triple-DES.  
>It's not going to help.  The generator is defective and doesn't 
>even have satisfactory error-concealment.

Yes, your bit-reducing function (parity-over-N-bits) is particularly
ill-suited
for your raw source (constrained parity-over-M bits) for M=N.  Pick a
different
N.

>I like my design a lot better:
>
>+ Source --> Digitizer --> good hash
>
>where I have chosen SHA-1 as my hash function.  
>
>Finally, since SHA-1 is remarkably computationally efficient,
>I don't understand the motivation to look for "simpler" hash
>functions, especially if they are believed to require whitening
>or other post-processing.

This discussion has made things clearer on this end, too.
I better understand what SHA does in RNGs that use it.

Two scenarios where SHA is contraindicated came up: 
1. hardware
2. interrupt handlers

Sometimes a hardware RNG will feed raw data into a crypto-WEAK analogue of
SHA,
ie a LFSR which does the bit-reduction and mixing functions, 
but doesn't mix as well as SHA.  (LFSR are hardware-friendly)  Separating
the bit-reduction from the mixing can be useful for analyzing what's
really going on.

dh




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