[tor-dev] prop224: Deprecating SHA1 circuit digests

[Taylor R Campbell]

> Date: Sun, 23 Jul 2017 12:08:25 +1000
> From: teor <teor2345 at gmail.com>
> 
> We still need to think about how we migrate hashes, because all hashes
> break eventually:
> https://valerieaurora.org/hash.html

As a counterpoint, here is an updated history of collision *and* preimage
attacks, and some commentary on them:

https://z.cash/technology/history-of-hash-function-attacks.html

No hash functions widely accepted as preimage-resistant have ever had
their preimage resistance broken, with the lone exception of Snefru.
(Wikipedia claims a preimage attack on MD5 with complexity 2^123.4,
but if you follow the reference, you'll see that's the time estimate;
the memory estimate is 2^45, raising the area*time product well above
the advertised security level.)

No hash functions widely accepted as collision-resistant have had
their collision resistance broken since Panama: not Whirlpool, not
SHA-2, not SHA-3, none of the SHA-3 finalists, not BLAKE2.  This is
not to say it won't happen, but the extrapolation in
<https://valerieaurora.org/hash.html> does not seem as well supported
by the (admittedly quite heuristic) evidence as the page suggests.

I don't know how hash functions are used in every case in Tor.
Probably not all uses rely on collision resistance at all; perhaps
some that do can be adapted to rely instead only on target collision
resistance, which even MD5 is still conjectured to exhibit.

> And I am concerned that we might be hard-coding either SHA1 or SHA3-256
> in the v3 hidden service protocol.

Maybe so, but are you hard-coding it in the v4 hidden serice protocol?

There's a serious complexity cost in implementing fine-grained
algorithm agility: a combinatorial explosion of possible compositions
and a wider attack surface for decisions by autonomous agents (or,
worse, by inexpert users not competent to make crypto decisions).

I'm not saying don't make it easy to swap out SHA-3 if the time comes,
just cautioning against wiring complexity into the protocol to have
all the agents involved automatically make decisions on the fly about
algorithm choices, without a clear benefit that can't be had in some
simpler way.