[討論] MD5 被破解了！

swbai

還是被對岸學者破的，短短四頁的論文，攻破大家原先認為牢不可破的堡壘！
請參閱：http://www.md5crk.com/
這可是件大事，有懂密碼學的朋友談一談將來可能的因應對策嗎？

zard

CNET這邊有比較白話的新聞,大家可以看看.

演算法露破綻 密碼學界譁然
http://taiwan.cnet.com/enterpris ... 938,20091786,00.htm




另外有對岸的新聞
http://www.stdaily.com/big5/stdaily/2004-09/04/content_296123.htm
我科學家成功破解指紋密碼  
--------------------------------------------------------------------------------
　本報訊（記者 孫明河） 在8月17日美國聖塔芭芭拉市舉行的2004國際密碼學大會上，中國科學家王小雲關于成功破解MD5的報告引起國際密碼界轟動。因為，目前我國和國際上廣泛使用的保障電子簽名安全的雜湊函數MD5存在嚴重安全隱患———被認為是十分安全的“數字手印”完全可能出現假冒。

　　全世界沒有兩個完全相同的指紋，手印因此成為人們身份唯一和安全的標志。在國際網絡安全協議中，計算機科學家使用雜湊函數來處理電子簽名，以便產生理論上獨一無二的“指紋”，形成“數字手印”。MD5就是目前最常用的一種雜湊函數。經過MD5處理，原始信息即使只更動一個字母，被改動的信息所產生的“指紋”也會截然不同。正是這個“指紋”的獨一無二，才保證了電子簽名的“絕對安全”。

　　然而，王小雲研究發現，MD5存在“雜湊碰撞”，就是兩個文件可以產生相同的“指紋”。這意味著，當你在網絡上使用電子簽名簽署一份合同后，還可以存在另外一份具有相同簽名但內容迥异的合同。這一發現使目前電子簽名的法律效率和技術體系受到挑戰。王小雲教授現為山東大學數學與系統科學學院博士生導師，多年來在國家自然科學基金資助下開展密碼算法分析的研究。

[ Last edited by zard on 2004-9-8 at 23:57 ]

HUANGLIFU

其實本來就有可能啦，只是要發現這樣的可能性，除非有非常大的資源，不然很難達成，加密方式也不只MD5而已。

allex

MD5存在“雜湊碰撞”，就是兩個文件可以產生相同的“指紋

哇勒....
雜湊碰撞這跟破解無關啊.....
任何雜湊演算法對一群夠多的輸入資料
其中兩個不同的資料算出相同的結果的機率從來就不是0啊.....

另外 數位簽章也不必然跟MD5相關....

mtgold

應該是說要花多少時間精力去破解，並不是可不可能吧！
就可能性來說一定是有的，但是如果要算個幾個月或幾年，那就沒啥意義了嘛！

ychao

MD5雜湊值比原始資料短的多，自然是有可能會有不同的內容出現相同的雜湊值啊！重點是這兩份具相同雜湊值的文件內容差異有多大？
再來，這世界上根本就沒有說有哪種加密是牢不可破的，在數學上只能證明在一定的極限下，破解的『機率』很低。運氣好的話，也可能一次就猜出來了。不然用暴力解法，也是一定可以的，只是要花多少的運算時間，合不合經濟效益的問題。
這個結果出來，應該可以減少一些對這類加密的『迷信』吧。像是自然人憑證真的萬無一失？健保卡，甚至是國民身份證晶片化，資料不會洩漏？(其實問題最大的應該是『人』吧)

chrispinyang

也許日後的超級電腦可以在很短的時間運算出來

infax

其實不用用到超級電腦....
如果原文大小為1MB用MD5加密出來的密文
有很大的可能可以用極小的文字算出跟原文加密出來的密文一模一樣....
運氣大於所有一切可能~ :p

另外MD5目前最大量使用是用在於資料比對或是登入系統
跟目前常用的簽章沒什麼太大的關係

破解？只要會寫程式，會寫Loop..要完成一支破解程式並不難

allex

Originally posted by ychao at 2004-9-9 02:28 AM:
像是自然人憑證真的萬無一失？健保卡，甚至是國民身份證晶片化，資料不會洩漏？(其實問題最大的應該是『人』吧)

憑證本身基本上可以說是萬無一失的
不過經過國內政府機關或是一些民間企業的亂搞後
保證缺失多多..... XD

記得自然人憑證竟然用身份證字號當主key
cn值竟然放中文字
更不用說憑證的使用了....

在台灣還真的是什麼都有可能耶.... B)

Dragoon

請先看看 cnet 那篇文章

雜湊碰撞最大的問題不是破解 MD5 沒啥好破解的~
問題在於, 刻意製造雜湊碰撞的能力.

目前程式碼或壓縮文件交換有很大比例是用 檔案大小 與 MD5 做比對的,
如果這兩項相同, 則視內容可信任, 發送者與接收者的內容一致.

假設我要發佈 Apache 2.1.1 好了, 如果有人能夠刻意計算出一段加了後門的程式碼, 天衣無縫的取代了我原先發佈的內容, 而原來的程式碼與駭客加工過後的程式碼在某一個程度上與我的檔案大小與 MD5 一致(該修改過的原始碼 或 原始碼的壓縮檔 或 binary 檔 或 binary 壓縮檔), 下載的使用者就與平常一般地安裝了該程式碼, 則後門就已經進入廣大的 server 了.

製造雜湊碰撞的能力越強, 這種情況發生的機率就越高.

所以以往採行的檔案大小與 MD5 比對, 可能該研究修改成安全性更高的方式了.

N710C

這次是 collision attack 不是 Preimage attack, 不過雖然如此, md5 大楖也不能用了