building a true RNG

[David Wagner]

Oh dear.  On re-reading your message I now suspect that what you asked
is not what I originally thought you asked.  I see two questions here:
  Q1: If we cycle through all N-bit messages, are all
      2^N output values possible?
  Q2: If we cycle through all messages (possibly very long
      or very short), are all 2^N output values possible?
On first reading I thought you were asking Q1, but it now occurs to me
you were probably asking Q2.  I apologize profusely for any confusion
I may have caused.

Anyway, the answer to Q1 is likely to be "No".  I'd guess that the answer
to Q2 is probably "Yes", or close to it.

For the first scenario, if the hash behaves like a random oracle,
then one would expect only 2^N * (1 - 1/e) of the possible outputs to
be attainable.  Of course, the forbidden outputs are not easy to find;
the best way I know is by exhaustive search over all 2^N N-bit messages.
For the second scenario, if the hash behaves like a random oracle, then
one would expect all outputs to be attainable.  No significant deviation
from the random oracle model is known for SHA1 (well, with one exception
that doesn't appear to be relevant here).  That said, this is not a proof,
and my answers just represent my best guesses.

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