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

[Zooko O'Whielacronx]

Here is the letter I wrote to the SHA-3 mailing list, followed by
replies from Jon Callas and John Kelsey.

-------
From: Zooko O'Whielacronx
	
Folks:

You might be interested in this discussion on the tor-dev mailing list
about a new crypto protocol for Tor:

https://lists.torproject.org/pipermail/tor-dev/2011-November/date.html

One of the issues brought up by Tor developer Nick Mathewson was
whether to switch from SHA-1 to SHA-2 or instead wait for SHA-3. I
argued that SHA-2 is better than SHA-3 (at least for a few years).

I feel slightly traitorous saying it, because I've enjoyed reading
this mailing list for years, and many of the SHA-3 candidates are
beautiful constructions, and I want them to be widely studied and
used, but there you have it: I can't think of good arguments for the
Tor developers to jump to SHA-3. Perhaps you can!

Regards,

Zooko
-------

-------
From: Jon Callas

Why do you feel traitorous saying it? In my opinion it's the right
decision (and frankly, having read the notes, some of the others are
sub-optimal), and I'm a co-author of a finalist.

Engineering is the art of applying science within constraints. Those
constraints include but are not limited to the laws of physics,
budgets, schedules, performance, and so on. The worst decision is no
decision.

If you are unhappy with SHA-1 for security reasons, then your first
choice should be using SHA-256. Your second choice should be SHA-512,
possibly in one of the narrow-width constructions that NIST recently
published. Those are the best-understood secure hash functions we
have.

SHA-3 candidates, no matter which ones they are are each and all
slightly less well-understood than SHA-2, for all the obvious reasons.

If you are unhappy with the above assessment for *performance*
reasons, well, that's a different kettle of fish entirely. Further
discussion is needed, but it's easier to find a performance metric and
select along it than there is to find a security metric. It can be
done, obviously, but the debate is a lot more entertaining.

The hardest thing of all, of course, is to try to minimax the two
considerations, security and performance. That debate would be really
entertaining.

All of this, however, presupposes that Tor can't reserve an algorithm
identifier for SHA-3 and design things so SHA-256 is used now and
SHA-3 when it's finally available. And yes, that's easier said than
done, but heck, that's what engineering is, too.

       Jon
-------

-------
From: John Kelsey

For whatever it's worth, if someone asked me the same question, I'd
give the same advice--go ahead and switch to SHA256 or SHA512, but
make sure you build algorithm identifiers and versioning into your
protocol, so that it's possible to change hash functions (and
everything else) when you need to.

SHA1 has a claimed collision attack (which looks like it should be
right, but has never been verified experimentally), and also has a
certain collision attack at 2^{80} work, so if you are worried about
collisions in your application, you should definitely switch, and I
think SHA2 is pretty much the only good choice right now.  Similarly,
if you're in a position to change hash functions now, but it will be a
big pain to do it in two or three years, switching to SHA2 makes good
sense.  On the other hand, if you're only using SHA1 with HMAC to do
MACing and key derivation and random number generation, there doesn't
appear to be any great urgency in switching over, as there are no
results I'm aware of that come anywhere close to really threatening
those applications.  There's no reason to keep SHA1 around in those
applications if you don't need to, but there is also no enormous
urgency switching over to SHA2 or SHA3 for HMAC.

Finally, if you're only worried about preimage and second preimage
resistance, SHA1 still seems okay.  But be careful assuming that you
don't care about collisions--there are a lot of weird and surprising
things you can do to hash functions if you can find intermediate
collisions.  For example, if a single colliding message is no big
deal, but a billion messages with the same hash is a disaster for your
application, it turns out you care very much about the difficulty of
finding one collision at a time in your Merkle-Damgaard hash function.
 It's much safer to just use hash functions whose cryptographic
strength and width makes collisions impractical to ever find--that is,
hash functions like SHA2 instead of SHA1.

--John
-------