[11239] in cryptography@c2.net mail archive
Re: building a true RNG
daemon@ATHENA.MIT.EDU (David Wagner)
Mon Jul 29 14:36:02 2002
From: David Wagner <daw@cs.berkeley.edu>
To: jsd@monmouth.com (John S. Denker)
Date: Mon, 29 Jul 2002 10:45:39 -0700 (PDT)
Cc: daw@mozart.cs.berkeley.edu (David Wagner),
cryptography@wasabisystems.com, barney@tp.databus.com (Barney Wolff)
In-Reply-To: <3D457D6D.E414C051@monmouth.com> from "John S. Denker" at Jul 29, 2002 01:37:49 PM
> 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@wasabisystems.com
