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

From: "D. J. Bernstein" <[email-masked]>
Date: 1 Nov 2004 06:28:04 -0000

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
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: John Viega <[email-masked]>
Date: Mon, 1 Nov 2004 09:45:17 -0500

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

---

From: Jack Lloyd <[email-masked]>
Date: Mon, 1 Nov 2004 12:18:19 -0500

> being hashed as the block cipher key, such as Matyas-Meyer-Oseas. 

Actually Whirlpool uses the Miyaguchi-Preneel scheme, where the key used is
(IIRC) the H_{n-1}, not a chunk of the input.

-Jack

---

From: "D. J. Bernstein" <[email-masked]>
Date: 2 Nov 2004 20:55:20 -0000

David A. McGrew writes:
> I suspect that the group preference would be towards hash functions
> that are portable (e.g. fast on a wide variety of CPUs) and that
> require minimal per-key state.

I've just posted http://cr.yp.to/papers.html#poly1305, introducing and
analyzing Poly1305-AES, a 128-bit MAC. Main features:

   * Guaranteed security, even for long-term keys, if AES is secure.
   * Cipher replaceability: can switch from AES if desired.
   * Extremely high speed: for example, 3.625 Athlon cycles per byte.
   * Low per-message overhead: 800 cycles total for a 64-byte message.
   * Key agility: the key is stored in memory as just 32 bytes.
   * Parallelizability, incrementality, low circuit depth, etc.
   * No intellectual-property claims.

Guaranteed security, cipher replaceability, and parallelizability are
provided by the standard polynomial-evaluation-Wegman-Carter-MAC
framework. Within that framework, hash127 achieved high speed at the
expense of a large table for each key. The added feature of Poly1305-AES
is key agility: high speed without any key expansion.