building a true RNG

[David Wagner]

> 3) For a one-way hash function should not expect a _constructive_ 
> proof that it generates all possible codes;  such a construction
> would violate the one-way property.

Nitpick: the last statement does not seem quite right to me.  I'm thinking
of the notion of a one-way permutation.  For instance, the RSA function
f(x) = x^3 mod n is conjectured to be a one-way permutation, assuming n
is a RSA modulus with unknown factorization and the RSA assumption holds.
(I'm being a little fast and loose with the formal details, but I hope
this conveys the idea.)

That said, I'm not claiming that the RSA function would make a good
cryptographic hash function.  Cryptographic hash functions are expected
to be a lot more than just one-way and collision-free.

I don't know of any good cryptographic hash function that comes with
a proof that all outputs are possible.  However, it might not be too
hard to come up with plausible examples.  For example, if we apply the
Luby-Rackoff construction (i.e., 3 rounds of a Feistel cipher), with
ideal hash functions in each round, does this have the desired properties?
It might.

On the gripping hand, I don't think this is a real issue in practice.
SHA1 is probably good enough for all practical purposes that I can
think of.

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