[11213] in cryptography@c2.net mail archive
Re: building a true RNG
daemon@ATHENA.MIT.EDU (David Honig)
Sat Jul 27 10:51:36 2002
Date: Sat, 27 Jul 2002 06:40:02 -0700
To: "John S. Denker" <jsd@monmouth.com>
From: David Honig <dahonig@cox.net>
Cc: amir@herzberg.name, "'Hannes R. Boehm'" <hannes@boehm.org>,
'Ian Hill' <Ian@Protonic.com>, cryptography@wasabisystems.com
In-Reply-To: <3D401D10.2C1051C9@monmouth.com>
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@wasabisystems.com
