SHA-0 Broken, MD5 Rumored Broken

[Jérôme ATHIAS]

MD5 Collision Nearly Found

Following up on yesterday's discussion about new attacks on cryptographic hashfunctions, Eric Rescorla points to a new paper (http://eprint.iacr.org/2004/199.pdf) from Chinese computer scientists, which claims to have found a collision in MD5. MD5 is a co
usin of the SHA-1 function discussed yesterday; MD5 is believed to be the weaker of the two.

The paper is odd, in that it includes two values that it claims have the same MD5 value, but it doesn't explain how the claimed collision was generated. And it turns out that the authors made an error, so that the two values don't in fact generate the sam
e MD5 value. Eric and the commenters on his site did some clever detective work to determine that the two published values generate a collision for a slightly different function, which Eric dubbed MD5'. MD5' is very similar to MD5 so it seems very likely
that the new attack can be extended to the real MD5.

Global link:
http://www.freedom-to-tinker.com/archives/2004_08.html

[Anthony Nemmer]

Looks like a MD5 collision HAS been found:

http://www.freedom-to-tinker.com/archives/000664.html

Jérôme ATHIAS wrote:
>
> MD5 Collision Nearly Found
>
> Following up on yesterday's discussion about new attacks on cryptographic hashfunctions, Eric Rescorla points to a new paper (http://eprint.iacr.org/2004/199.pdf) from Chinese computer scientists, which claims to have found a collision in MD5. MD5 is a
cousin of the SHA-1 function discussed yesterday; MD5 is believed to be the weaker of the two.
>
> The paper is odd, in that it includes two values that it claims have the same MD5 value, but it doesn't explain how the claimed collision was generated. And it turns out that the authors made an error, so that the two values don't in fact generate the s
ame MD5 value. Eric and the commenters on his site did some clever detective work to determine that the two published values generate a collision for a slightly different function, which Eric dubbed MD5'. MD5' is very similar to MD5 so it seems very likel
y that the new attack can be extended to the real MD5.
>
> Global link:
> http://www.freedom-to-tinker.com/archives/2004_08.html
>
>
>


--

SKYKING, SKYKING, DO NOT ANSWER.

[stanislav shalunov]

"Anthony Nemmer" <intertwingled@qwest.net> writes:

> Looks like a MD5 collision HAS been found:
> http://www.freedom-to-tinker.com/archives/000664.html

In case anyone is still wondering whether the collision in MD5 is
real, here are the two files.

$ cmp md5-1.bin md5-2.bin
md5-1.bin md5-2.bin differ: char 20, line 1
$ md5 md5-1.bin md5-2.bin
MD5 (md5-1.bin) = a4c0d35c95a63a805915367dcfe6b751
MD5 (md5-2.bin) = a4c0d35c95a63a805915367dcfe6b751

Note that as of now, there are no attacks that demonstrate that MD5 is
not preimage-resistant or 2nd-preimage-resistant. Perhaps more
importantly, it is also not clear (to me, at least), whether the
collisions that can be produced in MD5 are selective (i.e., the
attacker has some control over the colliding messages) or existential.

Collision resistance was a design goal for MD5. It does appear that
there exists a method for finding collisions in significantly less
than 2^64 operations. Thus, MD5 should not be used in any new
cryptographic systems that require collision resistance, preimage
resistance, or 2nd preimage resistance. Existing systems should be
evaluated individually. Some might require emergency patching.

--
Stanislav Shalunov http://www.internet2.edu/~shalunov/

A fanatic is one who can't change his mind and won't change the
subject. -- Winston Churchill


begin 644 md5.tar.gz
M'XL(`*N%)4$"`\M-,=4UU$O*S&.@'3`P-#`P,S-C,#`P,#0W-031(`"C#8R`
M;$,#0T,#,U,S<Q.@N*$1D,N@8,!`!U!:7))8I*#`4)R1F%.:EU^&2UUY1FIJ
M#L.P`Q<-[S(=??;N2*;M++89ZW_&Z)_:VB[D5K?:@27";L?O^L[0M29LG%\V
M,S4_Z6A6+72,X@A4??'][,GY-V7W?FHPMXF>QBU[\8YC]9PG-Z9_B4H-O6I:
M/.OXA]=_>0PT/Z9=Y-S87ZI>7VEP->:UTHNUNRK/B,:\+3E]-_[HY=R-L[EN
MF)Y9_IAA%`PHR`7F?Z/!D__-C8Q,(/G?8#3_#U#^9\>9_S^BY/\B'/G?'6?^
M]T')_Q&C^7\4C()1,`I&P2@8!:-@%(R"43`*1L$H&`6C8!2,@E$P"D;!*!@%
:HV`4C()1,`I&P2@8!:.`<@``VKRAJP`H````
`
end