[p2p-hackers] SHA1 broken?

[Zooko O'Whielacronx]

On 2005, Feb 17, at 19:23, Serguei Osokine wrote:

> For anyone *but* the original code author, however,
> achieving a malicious collision this way would be impossible.
>
> 	So the Bad Charlie Webmaster from Zooko is pretty much out of
> luck - he'd have to conspire with an honest programmer Bob to do any
> harm.

Maybe.

Executive summary:

If MD5 were collision resistant, Alice could be certain that the 
software she runs is the software that Bob intended.  Since MD5 isn't 
collision resistant, then whether Bad Charlie Webmaster can perform 
this attack depends on some subtler properties of MD5 -- properties 
which are not as well studied.  In any case it isn't necessary for Bad 
Charlie to break MD5's second-preimage resistance in order to perform 
this attack.

More detail:

Cryptographers have traditionally measured hash functions against two 
definitions: collision resistance and second-preimage resistance, see 
[1].

collision resistance: You can't find any x1 and x2 such that h(x1) == 
h(x2).
second-preimage resistance: Someone gives you a value x1.  Now you 
can't find any x2 such that h(x1) == h(x2).

Collision resistance is stronger than second-preimage resistance, in 
the sense that any hash function which is collision resistant must also 
be second-preimage resistant, but not vice versa.

collision resistance > second-preimage resistance

A lot of the discussion about the recent hash function weaknesses has 
been along the lines of people saying "Well, the attacks have shown 
that MD5 doesn't have collision resistance, but this doesn't matter 
because the property we require for our purposes is second-preimage 
resistance.".

My story about Bad Charlie Webmaster [2] was intended to illustrate 
that second-preimage resistance is not sufficient to protect Alice, 
although collision resistance would protect her.

Hal Finney has explained in detail [3] why he thinks the current 
attacks on hash functions don't enable Bad Charlie Webmaster to trick 
Alice.

But what are we to make of this?  If we believe Hal Finney's argument 
(I do), then MD5 doesn't have the property of collision-resistance, but 
it has some other property which makes it safe for Alice the User and 
Bob the Programmer to use.  This property is that any two messages that 
can be found to collide are constrainted to have only a few small 
differences from one another, and those differences close together.

I just want to emphasize that it isn't MD5's second-preimage resistance 
that is protecting Alice.  If less constrained collisions can be 
generated in MD5, then Alice is vulnerable to Bad Charlie Webmaster 
even if MD5 is second-preimage resistant.

Regards,

Zooko

[1] Menezes, van Oorschot, Vanstone "Handbook of Applied Cryptography"  
It's the best reference I know for this kind of thing, well worth the 
cover price, but it is also available free:
http://www.cacr.math.uwaterloo.ca/hac/about/chap9.pdf
[2] http://zgp.org/pipermail/p2p-hackers/2005-February/002403.html
[3] http://zgp.org/pipermail/p2p-hackers/2005-February/002408.html