Re: [Cfrg] Re: [saag] Bad day at the hash function factory

[John Viega <viega at securesoftware.com>]

What Dan says is true in the case of modern MACs, but is not true for
the case of unkeyed hash functions built from a block cipher. There,
the best we have been able to do is prove security if the underlying
block cipher behaves like an ideal block cipher, much weaker than the
PRP assumption used in proving block cipher-based MACs secure.

As Eric mentioned, modern hash functions can be viewed as block
ciphers in Davies-Meyer mode. There's a proof of security for
Davies-Meyer mode in the ideal cipher model, and yet the recent
cryptanalytic results due to Joux et al. really take advantage of
Davies-Meyer mode. That is not to say that Davies-Meyer with a
stronger underlying block cipher wouldn't be better (e.g., Whirlpool),
but it does suggest that it might be good to move to one of the other
modes with similar security proofs, one that doesn't use the data
being hashed as the block cipher key, such as Matyas-Meyer-Oseas. 

This will slow down our hash functions, because the Davies-Meyer
approach essentially allows one to avoid key scheduling, and run fewer
iterations of the block cipher at the same time.  But it seems far
more conservative.

John

On Mon, Nov 01, 2004 at 06:28:04AM -0000, D. J. Bernstein wrote:
> Eric Rescorla writes:
> > You can then demonstrate that the MAC/Hash is secure if the
> > encryption algorithm has a bunch of (somewhat idealized) properties.
> 
> There's just one assumption needed for these proofs: namely, someone who
> doesn't know the key k can't distinguish AES_k from a uniform random
> permutation of the set of 16-byte strings. This was an explicit design
> criterion for AES.
> 
> ---D. J. Bernstein, Associate Professor, Department of Mathematics,
> Statistics, and Computer Science, University of Illinois at Chicago
> 
> _______________________________________________
> Cfrg mailing list
> Cfrg at ietf.org
> https://www1.ietf.org/mailman/listinfo/cfrg

_______________________________________________
Cfrg mailing list
Cfrg at ietf.org
https://www1.ietf.org/mailman/listinfo/cfrg