MD4 & MD5 Collision Generation

超強者發paper，次強者實作，我們這種弱者在旁邊搖旗吶喊就好了XD

昨天下班前在看Sony偷放rootkit在CD裡的新聞（Darkkiller的blog有事件說明），網頁連一連突然看到這個東西，大驚。

去年的CRYPTO 2004，來自中國的王小雲女士和她的研究團隊發表了SHA-0和MD5的攻擊法，可以快速製造出collision。當時這個團隊賣關子，沒有把整個理論的paper公開出來，但發表的結果仍是衝擊全世界啊！（這種才算是真正中國人的光榮吧？結果國內親共的媒體反而沒報(…) ）

Paper推出後，現在有人把這套理論實作出來，且號稱執行速度更快，用他的P4 1.6找MD4的collision是瞬殺，MD5的話也只要45分鐘。

MD4和MD5是一種hash algorithm，丟給它一堆字串它可以生出另一串字串出來，主要是用來做數位簽章。數位簽章的使用，就是把一份文件做簽章後生出來的字串當簽名，只要比對這一部份是否相同就知道文件內容有沒有被動過了。如果能被人輕易找出兩組不同的輸入卻能產生一樣的輸出，就是這裡說的collision，那使用這個algorithm防偽的簽章就有可靠性的暇疵（別人有機會製造出內容不同的文件卻產生一樣的簽名）。

我還在看paper而已（功力不足，看很慢-_- ），就出現實作品了，網路發達的世界真是恐怖啊。

Darkkiller也有篇文章寫到這件事。