building a true RNG

[Joseph Ashwood]

----- Original Message -----
From: "John S. Denker" <jsd at monmouth.com>
To: "David Honig" <dahonig at cox.net>
Cc: <amir at herzberg.name>; "'Hannes R. Boehm'" <hannes at boehm.org>; "'Ian
Hill'" <Ian at Protonic.com>; <cryptography at wasabisystems.com>
Sent: Saturday, July 27, 2002 10:52 AM
Subject: Re: building a true RNG


> I wrote:
> > > 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");

I disagree. The whitening stage can perform a very important step of
allowing for stretching of the entropy. Ideally a true RNG would be fast
enough to supply all our needs, but that typically doesn't happen. Instead
we have to depend on stretching tricks, basically using a primitive in
counter mode, to stretch the bits we have as far as is needed. This can be
combined with the distillation stage itself by inserting a fixed string,
copying the state, and finishing the calculation, but can conceptually be
thought of as a seperate stage.

> David Honig responded:
> > 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.)
>
> That's a red-herring tangent.  I'm not talking about any old
> function that doesn't waste entropy;  I'm talking about a
> !!hash!! function that doesn't waste entropy.

A construct that simply does not exist, more on this later.

> And remember:  in addition to having a non-entropy-wasting hash
> function, we are also required to saturate its input.  Then we can
> conclude that the output is white to a very high degree, as
> quantitatively discussed in the paper.
>



> > 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.

I seperated this because I agree with teh statement completely, that is the
one and only function of the distilling function, whether it is a hash, a
cipher, or a miracle construct.

>
> Total entropy is preserved in the non-saturated regime.  This is
> documented in upper rows of the table:
>   http://www.monmouth.com/~jsd/turbid/paper/turbid.htm#tab-saturation

I disagree. There are several ways of viewing the problem. Modelling the
distillation function as a perfect entropy smoother over k bits (other than
that I will be assuming a worst case). We see the following happen:
When the first bit is inserted, each of the k bits receives 1/k entropy
When the second bit of entropy is inserted one of those bits received 1 bit
of entropy, the entire system now has 1 + (k-1)/k bits of entropy, already
there is a small but measurable discrepancy
Each bit now has (2k-1)/k bits of entropy
The third bit results in 1 of the k bits having entropy 1 giving 1+
((2k-1)/k)(k-1)/k bits of entropy in total

While the system slowly loses entropy, it does lose entropy. It's also worth
noting that this agrees with the presented analysis at 3 points, 0 has 0
entropy, 1 has 1-bit of entropy, and inf has k bits, but that for all useful
lengths having k bits of entropy can never occur.

> In the saturated regime, some entropy is necessarily lost.  This is
> documented in the lower rows of the table.  This is only a small
> percentage, but it is mandatory.  I don't consider this to be "wasted"
> entropy;  I consider it entropy well spent.  That is, these are
> necessary hash collisions, as opposed to unnecessary ones.

These don't even have to be hash collisions, it is possible for the hash
function to discard entropy simply through its behavior, as in my example
where entropy starts being discarded beginning with the second bit. From a
theoretic standpoint, it is entirely possible that a function exists that
discards entropy beginning with the first bit.

> > 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.

This statement is true of all deterministic algorithms. In fact it it one of
the points where all presented models agree, you cannot reach a completely
entropic state until you reach infinite lengths for the input. If the input
if purely entropic there is some grey area surrounding this, but for a hash
function to be secure the grey area disappears.

> > 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.
>
> Well, I tend to agree that systems that separate the bit-reduction
> from the mixing are easier to analyze, in the sense that it is
> easier to find flaws in them.  But that's because they're so flawed!

Not necessarily. Take a two phase system, in hardware you have a hardware
random bit generator feeding a perfect hash function, in software you have
something collecting several of these inputs, and mixing them using a strong
cipher (no stretching is occurring). This system is no easier to analyze
than the bit generator->hash, but also no weaker. It is certainly the case
that certain designs are more likely to be weak when encountered in the
wild, but in general this is due simply to the frequency with which
under-educated people design/implement them versus the rate at which
properly educated people design/implement.
                        Joe


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