[Python-Dev] SHA-256 module

[Tim Peters]

[Tim Peters]
...
>> A number of hash functions got cracked since this thread started, by
>> some researchers in China:
>>
>>     http://eprint.iacr.org/2004/199.pdf
 
[Michael Hudson]
> Is there any resource that explains these guys results any more fully?

Not that I know of.  I've read that they're writing a paper on *how*
their approach works, but it will take time to finish it.  There's no
doubt that they're on to something.  Apparently the first version of
the paper provided collisions for a hash that wasn't actually MD5, due
(at least) to confusing endianness in places.  This was pointed out at
the conference, and by the next morning they produced two collisions
for "the real" MD5.

> The only examples I've seen only differ in a very few bits.

Probably due to the method, which apparently makes a sequence of
small, controlled changes, based more on analysis than on brute force.
 Given the uses of MD5 for verifying downloads, it doesn't take much
of a change to open "a security hole" in C code, so even if they can't
extend the method beyond a few bits' difference, that would be cold
comfort.  I note that they got to pick both msgs here, and haven't
claimed to be able to derive a collision for a given msg.  When more
about their method is known, it may or may not prove feasible to
extend.

>> MD5 is truly dead now for "secure" applications.

> I'd say it's resting :)

I based "truly dead" on press reaction.  MD5 had been falling out of
favor for years anyway (due to earlier cracks of various weakened
versions); this is just nail-in-the-coffin news.

> ...
> I'm hardly an expert, but I'd still like to know more about this
> attack.  If it's as limited as it could possibly be (i.e. it can only
> make very specific strings differing by a handful of bits hash the
> same) then it's only an issue for the paranoid.  If it's as wide as it
> could possibly be it seems that all hash functions we currently know
> could be doomed.

Security weenies are paranoid by necessity -- paranoia is part of
their field.  I'm not sure there's ever been a real-world attack based
on a "double free" bug, for example, but finding such a bug is
sufficient to kill a product release anyway.

They don't claim to have an attack against SHA-1, BTW.  Someone else
reported collisions using a grossly weakened SHA-1, with 42 rounds
instead of 80.