Re: Collision in SHA-0

From: Gregory G Rose (ggr_at_qualcomm.com)
Date: 08/17/04


Date: 16 Aug 2004 22:41:35 -0700

In article <cfrnsc$qt5$10@driftwood.ccs.carleton.ca>,
Jean-Luc Cooke <jlcooke@engsoc.org> wrote:
>Very interesting. but I have not been able to reproduce this.
>
>int m1[] = {
>0x313838dd, 0xfc2932c7, 0xc030b717, 0xbafc1bae, 0x6673a8d7, 0x9ddcf416, 0x85d70859, 0x99403db0,
>0x0634add1, 0xc0736004, 0x9558bd1f, 0x21e10982, 0xca94c90b, 0x6aae6e69, 0xcbf61bf1, 0x06b0e615,
>0x2e82d48b, 0x16bdf161, 0xce10bd62, 0xc3c6809d, 0xb6745639, 0xfc0e06c7, 0x6573a914, 0xbef0d753,
>0x537b8755, 0x497b92e8, 0x46f559c2, 0x7d7a347a, 0x0511d8b1, 0x98ebeb68, 0xc9ca4559, 0xeb10e037
>};
>int m2[] = {
>0x313838dd, 0xfc2932c7, 0xc030b717, 0xbafc1bae, 0xe673a8d7, 0x9ddcf416, 0x85d70859, 0x99403db0,
>0x0634add1, 0xc0736004, 0x9558bd1f, 0x21e18982, 0xca94c90b, 0x6aae6e69, 0x4bf61bf1, 0x06b0e615,
>0x2e82d48b, 0x16bdf161, 0xce10bd62, 0xc3c6809d, 0x36745639, 0xfc0e06c7, 0x6573a914, 0xbef0d753,
>0x537b8755, 0x497b92e8, 0x46f559c2, 0x7d79b47a, 0x0511d8b1, 0x98ebeb68, 0x49ca4559, 0xeb10e037
>};
>
>fwrite(m1, 1, sizeof(m1), fout1);
>fwrite(m2, 1, sizeof(m2), fout2);
>
>Any glaring mistakes?

No, the glaring mistake is not yours. But
apparently the team believed Applied
Cryptography's description of MD5, and got the
byte ordering wrong. Nevertheless, the result
apparently holds if you byte-swap all the words. I
met Xuejia Lai (who I know was him, I've met him
before) and (I think... it was dark, and I'm
inebriated) Ms Xiaoyun Wang tonight. If you take
their formula and apply it to the correct starting
vector you should have MD5 collisions soon.

It seems to me that one consequence of this is
that certificates with MD5 should be believed
*only* if they are dated before today.

Greg.

-- 
Greg Rose
232B EC8F 44C6 C853 D68F  E107 E6BF CD2F 1081 A37C
Qualcomm Australia: http://www.qualcomm.com.au
"Nothing beats a tinfoil hat." -- Phil Carmody.


Relevant Pages

  • Re: Is MD5 outdated ?
    ... >which means that two guys are posting a binary with the same MD5. ... binaries, so at 1e6 binaries/day you should be ... Greg Rose ...
    (sci.crypt)
  • Re: MD5CRK is now LIVE
    ... >I guess if you are able to find a collision in MD5 by assembling enough ... Greg Rose ...
    (sci.crypt)
  • Re: Crypto Mini-FAQ
    ... >Any informations about why that committee doesn't endorse ... thus avoid the users' having to consider many ... continued use of MD5. ... Greg Rose ...
    (sci.crypt)
  • Re: Hardening MD5 with multiplications -- use MD5.1
    ... Max Power wrote: ... >If my memory serves me correctly there is a slightly modified version of MD5 ... Greg Rose ...
    (sci.crypt)