[tor-dev] SHA-3 isn't looking so hot to me

[Markku-Juhani O. Saarinen]

Watson Ladd:

> (HMAC is a bad idea anyway: quadratic security bounds are not the best
> possible, we have to use nonces anyway to prevent replay attacks, so 
> Wegman-Carter is a better idea for better in{faster, more secure}. GCM
> would be an example of this.)

GCM has quadratic security bounds, not only in the proof but in practice
too. Furthermore a 128-bit GCM MAC offers much less than 128-bit
security; in this sense it is certainly weaker than, say, MD5-HMAC ! And
there are the implementation caveats mentioned already mentioned in the
list, including Joux's "forbidden attack" which may indeed be very real
in many implementations. 

GCM also tends to be slow on software. I've been told that GCM was
pushed through the NIST standardization process mainly by CISCO who were
concerned about the performance of their hardware crypto accelerators
(many hash functions are tricky to implement on hardware).

There's also the issue of weak keys etc. See

http://eprint.iacr.org/2011/202.pdf

This came out in ECRYPT II Hash Workshop 2011, 19-20 May 2011, Tallinn,
Estonia. The current ECRYPT recommendations take this into account, see
section 8.5.5 of "ECRYPT II Yearly Report on Algorithms and
Keysizes (2010-2011)" for a brief discussion:

http://www.ecrypt.eu.org/documents/D.SPA.17.pdf

I should be expanding this work as Niels Ferguson noted in the Redmond
Crypto Retreat workshop last August that there's a trivial extension of
this attack that allows arbitrary message modification. Also a
significantly faster method for identifying weak AES-GCM keys has been
discovered.

As a hash function researcher I would personally select SHA-512 with
digest truncated to required number of bits as an interim solution.
SHA-512/256 tends to be faster than SHA-256 in software. Also it makes
sense to implement a single hash core rather than two (SHA-256 and
SHA-512 are fundamentally different). This is also in the standards,
see:

http://csrc.nist.gov/publications/drafts/fips180-4/Draft-FIPS180-4_Feb2011.pdf

Cheers,
- markku

Dr. Markku-Juhani O. Saarinen <mjos at reveresecurity.com>