Jserv's blog

在 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