MD5 and SHA cracked/broken...

[Bengt Richter]

On Sun, 12 Sep 2004 12:29:06 -0400, Tim Peters <tim.peters at gmail.com> wrote:

>[Paul Rubin]
>>> MD5 and SHA-0 had collisions found.
>
>[GomoX Gonzalo Sainz-Tr=E1paga]
>> I don't think so. Would you mind posting a link?
>
>Here's an MD5 collision demonstrated in Python.  I derived this code
>from the paper at
>
>    http://eprint.iacr.org/2004/199.pdf
>
>import md5
>
>S =3D ('\xd11\xdd\x02\xc5\xe6\xee\xc4i=3D\x9a\x06\x98\xaf\xf9\\'
>    '/\xca\xb5\x87\x12F~\xab@\x04X>\xb8\xfb\x7f\x89U\xad4'
>    '\x06\t\xf4\xb3\x02\x83\xe4\x88\x83%qAZ\x08Q%\xe8\xf7'
>    '\xcd\xc9\x9f\xd9\x1d\xbd\xf2\x807<[\x96\x0b\x1d\xd1'
>    '\xdcA{\x9c\xe4\xd8\x97\xf4ZeU\xd55s\x9a\xc7\xf0\xeb'
>    '\xfd\x0c0)\xf1f\xd1\t\xb1\x8fu\'\x7fy0\xd5\\\xeb"'
>    '\xe8\xad\xbay\xcc\x15\\\xedt\xcb\xdd_\xc5\xd3m\xb1'
>    '\x9b\n\xd85\xcc\xa7\xe3')
>
>T =3D ('\xd11\xdd\x02\xc5\xe6\xee\xc4i=3D\x9a\x06\x98\xaf\xf9\\'
>    '/\xca\xb5\x07\x12F~\xab@\x04X>\xb8\xfb\x7f\x89U\xad4'
>    '\x06\t\xf4\xb3\x02\x83\xe4\x88\x83%\xf1AZ\x08Q%\xe8\xf7'
>    '\xcd\xc9\x9f\xd9\x1d\xbdr\x807<[\x96\x0b\x1d\xd1\xdcA{'
>    '\x9c\xe4\xd8\x97\xf4ZeU\xd55s\x9aG\xf0\xeb\xfd\x0c0)'
>    '\xf1f\xd1\t\xb1\x8fu\'\x7fy0\xd5\\\xeb"\xe8\xad\xbayL'
>    '\x15\\\xedt\xcb\xdd_\xc5\xd3m\xb1\x9b\nX5\xcc\xa7\xe3')
>
>assert S !=3D T
>print md5.new(S).hexdigest()
>print md5.new(T).hexdigest()
>print "oops"

Others may have received that correctly, but between some systems and mine
'=' seems to get re-encoded as '=3D' (including in S and T). After fixing that,
pasting into my console python session worked for me:

 >>> import md5
 >>>
 >>> S = ('\xd11\xdd\x02\xc5\xe6\xee\xc4i=\x9a\x06\x98\xaf\xf9\\'
 ...     '/\xca\xb5\x87\x12F~\xab@\x04X>\xb8\xfb\x7f\x89U\xad4'
 ...     '\x06\t\xf4\xb3\x02\x83\xe4\x88\x83%qAZ\x08Q%\xe8\xf7'
 ...     '\xcd\xc9\x9f\xd9\x1d\xbd\xf2\x807<[\x96\x0b\x1d\xd1'
 ...     '\xdcA{\x9c\xe4\xd8\x97\xf4ZeU\xd55s\x9a\xc7\xf0\xeb'
 ...     '\xfd\x0c0)\xf1f\xd1\t\xb1\x8fu\'\x7fy0\xd5\\\xeb"'
 ...     '\xe8\xad\xbay\xcc\x15\\\xedt\xcb\xdd_\xc5\xd3m\xb1'
 ...     '\x9b\n\xd85\xcc\xa7\xe3')
 >>>
 >>> T = ('\xd11\xdd\x02\xc5\xe6\xee\xc4i=\x9a\x06\x98\xaf\xf9\\'
 ...     '/\xca\xb5\x07\x12F~\xab@\x04X>\xb8\xfb\x7f\x89U\xad4'
 ...     '\x06\t\xf4\xb3\x02\x83\xe4\x88\x83%\xf1AZ\x08Q%\xe8\xf7'
 ...     '\xcd\xc9\x9f\xd9\x1d\xbdr\x807<[\x96\x0b\x1d\xd1\xdcA{'
 ...     '\x9c\xe4\xd8\x97\xf4ZeU\xd55s\x9aG\xf0\xeb\xfd\x0c0)'
 ...     '\xf1f\xd1\t\xb1\x8fu\'\x7fy0\xd5\\\xeb"\xe8\xad\xbayL'
 ...     '\x15\\\xedt\xcb\xdd_\xc5\xd3m\xb1\x9b\nX5\xcc\xa7\xe3')
 >>>
 >>> assert S != T
 >>> print md5.new(S).hexdigest()
 a4c0d35c95a63a805915367dcfe6b751
 >>> print md5.new(T).hexdigest()
 a4c0d35c95a63a805915367dcfe6b751
 >>> print "oops"
 oops

QED

Regards,
Bengt Richter