November 18, 2005

在 VIA C3/x86 上作 MD5 Collision

昨天閱讀 DK 大神的 blog [MD4 與 MD5 Collision 的 Source Code] 後,突然覺得全身熱血沸騰。作者 Patrick Stach 在 [MD5 Collision Generation] 提到:
    Old (Wang, et al.) average run time on IBM P690 supercomputer - 1 hour New average run time on P4 1.6ghz PC - 45 minutes Note: some block #1's don't have block #2 solutions
在 [jserv's lab] 盯著 VIA 送的 EPIA 機器時,好奇的我,就拿這個程式來試試,首先是硬體資訊:
    jserv@epia:~$ cat /proc/cpuinfo 
    processor	: 0
    vendor_id	: CentaurHauls
    cpu family	: 6
    model		: 7
    model name	: VIA Samuel 2
    stepping	: 3
    cpu MHz		: 601.385
    cache size	: 64 KB
    fdiv_bug	: no
    hlt_bug		: no
    f00f_bug	: no
    coma_bug	: no
    fpu		: yes
    fpu_exception	: yes
    cpuid level	: 1
    wp		: yes
    flags		: fpu de tsc msr cx8 mtrr pge mmx 3dnow
    bogomips	: 1199.30
    
用 gcc-4.1 mainline 編譯:
    jserv@epia:~$ /opt/bin/gcc -v
    Using built-in specs.
    Target: i686-pc-linux-gnu
    gcc version 4.1.0 20051013 (experimental)
    jserv@epia:~$ /opt/bin/gcc -O7 -march=i686 -static -o md5coll md5coll.c
順手找 [新酷音] 計畫的 release file 來產生 MD5,並作為輸入:
    jserv@epia:~$ nohup /usr/bin/time ./md5coll ca4a4834 daf92475 82de9813 250e8466 &
經過一段時間後,輸出如下:
    block #1 done
    block #2 done
    unsigned int m0[32] = {
    0xb198b1de, 0xa45a609e, 0x7a7c3e52, 0xdab6df48,
    0x33b44275, 0x13c23c04, 0xd23508c7, 0xdf653e22,
    0x0532ed35, 0x0173e9f5, 0x7c7cae1f, 0x53103f39,
    0xd7e25ee3, 0x8ffa8737, 0x9446295f, 0x91f91ac9,
    0x7e361423, 0xcd501685, 0xfab819b8, 0xd82035e9,
    0x4712341b, 0x4e797c88, 0x46384d16, 0xff648e54,
    0x7cf37f61, 0x89c1b36c, 0x88f37442, 0xfcd5c871,
    0x91cf7ccf, 0x5607f8a9, 0x51c1d5e0, 0x67689096,
    };
    unsigned int m1[32] = {
    0xb198b1de, 0xa45a609e, 0x7a7c3e52, 0xdab6df48,
    0xb3b44275, 0x13c23c04, 0xd23508c7, 0xdf653e22,
    0x0532ed35, 0x0173e9f5, 0x7c7cae1f, 0x5310bf39,
    0xd7e25ee3, 0x8ffa8737, 0x1446295f, 0x91f91ac9,
    0x7e361423, 0xcd501685, 0xfab819b8, 0xd82035e9,
    0xc712341b, 0x4e797c88, 0x46384d16, 0xff648e54,
    0x7cf37f61, 0x89c1b36c, 0x88f37442, 0xfcd54871,
    0x91cf7ccf, 0x5607f8a9, 0xd1c1d5e0, 0x67689096,
    };
    36524.32 user 0.00 system 10:08:44
    elapsed 99%CPU (0avgtext+0avgdata 0maxresident)
    0inputs+0outputs (42 major + 7 minor) pagefaults 0 swaps
於是,我們找到 MD5 Collision 的組合,不過這時間也有點久,等一下複習 x86 MMX instructions,看看能否進一步最佳化。 由 jserv 發表於 November 18, 2005 08:49 PM
迴響

太過走火入魔? XD

Jouston Huang 發表於 November 21, 2005 05:20 PM