密碼學大事件！研究人員公布第一例SHA-1哈希碰撞實例

上海交通大學密碼與計算機安全實驗室（LoCCS）軟體安全小組（GoSSIP）版權所有，轉載請與作者取得聯繫！

2017年2月23日，荷蘭阿姆斯特丹Centrum Wiskunde & Informatica (CWI) 研究所和Google公司的研究人員[Marc Stevens (CWI Amsterdam), Elie Bursztein (Google), Pierre Karpman (CWI Amsterdam), Ange Albertini (Google), Yarik Markov (Google), Alex Petit Bianco (Google), Clement Baisse (Google)]在谷歌安全博客上發布了世界上第一例公開的SHA-1哈希碰撞實例！在經過兩年的聯合研究和花費了巨大的計算機時間之後，研究人員在他們的研究網站SHAttered上給出了兩個內容不同，但是具有相同SHA-1消息摘要的PDF文件，這就意味著在理論研究長期以來警示SHA-1演算法存在風險之後，SHA-1演算法的實際攻擊案例也浮出水面，同時也標誌著SHA-1演算法終於走向了生命的末期。

相關背景

MD-SHA系列Hash函數家族是最為知名的Hash函數家族，MD5，SHA-1和SHA-2都被廣泛的使用過。1990年MD4演算法被提出，但是被很快發現了嚴重的安全問題，在1992年被MD5演算法取代。MD5演算法在之後的十幾年內被軟體行業廣泛使用，直到2004年我國密碼學家王小雲在國際密碼討論年會（CRYPTO）上展示了MD5演算法的碰撞並給出了第一個實例（Collisions for hash functions MD4, MD5,HAVAL-128 and RIPEMD，rump session of CRYPTO 2004，How to Break MD5 and Other Hash Functions，EuroCrypt 2005）。該攻擊複雜度很低，在普通計算機上只需要幾秒鐘的時間。在2005年王小雲教授與其同事又提出了對SHA-1演算法的碰撞演算法（Finding Collisions in the Full SHA-1， CRYPTO 2005），不過計算複雜度為2的69次方，在實際情況下難以實現。

在現實世界中，利用Hash碰撞的真實案例確確實實發生在我們身邊：2008年的Chaos Communication Congress大會上，研究人員展示了利用MD5碰撞來偽造合法CA證書，從而攻破HTTPS的安全體系。 2012年在中東大範圍爆發的火焰（Flame）病毒，包含了一個偽造的數字簽名，就是利用MD5碰撞偽造了合法的微軟簽名來逃避殺毒軟體的查殺。

攻擊歷程

本次攻擊的關鍵先生是荷蘭阿姆斯特丹CWI研究所的Marc Stevens，他自2006年以來一直在Hash演算法的研究領域發表了大量令人艷羨的成果，包括一系列關於MD5演算法的攻擊。2009年他作為一作的論文Short chosen-prefix collisions for MD5 and the creation of a rogue CA certificate在當年的CRYPTO上獲得了最佳論文獎，在2013年的Eurocrypt上，他發表了一篇論文——New collision attacks on SHA-1 based on optimal joint local-collision analysis，提出了構造SHA-1碰撞的一種新的攻擊方法（攻擊複雜度為2的61次方，隨後又提出了基於GPU的高效實現方法），隨後數年不斷提出了新的改進方法，在2016 年他給出了關於SHA-1演算法的Freestart collision，也就是找到了SHA-1演算法內部的核心組件internal compression function的一個碰撞實例（64GPU集群，10天計算量），這就已經吹響了攻克SHA-1完全實際碰撞攻擊的決戰號角。終於，在Google公司強有力的計算資源支持之下，在2017年2月23日，SHA-1演算法的碰撞實例出現在我們面前！

此次攻擊到底使用了多強的計算資源，我們可以看一下Google Security Blog給出的原始數據：

• Nine quintillion (9,223,372,036,854,775,808) SHA1 computations in total
• 6,500 years of CPU computation to complete the attack first phase
• 110 years of GPU computation to complete the second phase

可以看到，這樣如此強勁的計算能力幾乎是歷史上最大規模的一次計算Hash碰撞的實驗。Google Security Blog還專門配了一幅圖來比較，如果使用暴力搜索，使用的計算資源即使是Google也無法承擔，而在人類智慧的研究之下，改進的Shattered演算法只需要110個GPU年就可以完成第二階段的搜索任務

關於攻擊的更多細節，可以參考論文——The first collision for full SHA-1。關於這篇論文，還有很多幕後的八卦，LoCCS實驗室理論密碼研究組長期從事分組加密演算法研究的王磊研究員曾與Marc Stevens合家聚餐，親切交談，並與本次工作的作者之一Pierre Karpman長期合作交流，王磊老師告訴我們，他目睹了這個密碼學歷史性事件的諸多進展，這個轟動性結果甚至讓今年某頂級學術會議的Deadline為之延期！！！

安全建議

我們指出，SHA-1碰撞攻擊影響了大量現有的安全應用，目前許多部署的SSL/TLS服務連接中均使用了SHA-1演算法作為消息驗證的基本密碼學原語，因此受到該攻擊的影響；流行的源代碼管理系統Git直到目前依然使用SHA-1作為文件的消息「指紋」；另外一個廣泛受到影響的場景是Android系統中應用APP、升級包、Bootloader等模塊的簽名機制（RSA + SHA-1），雖然Android 7.0給出的全新的簽名方案APK Signature Scheme v2中支持SHA-2家族的SHA-256和SHA-512，但經過我們的驗證，目前大量設備仍然在使用sha1withRSA的簽名驗證。在碰撞攻擊的影響下，攻擊者能夠構造出內容篡改但是簽名一致的文件繞過驗證。儘管計算量巨大且對內容的控制存在一定的困難，但是我們認為這類安全機制已經不再可信。

Google公司和諸多IT安全研究人員均在過去幾年呼喚開發者儘快更換SHA-1演算法，早在2014年，Chrome團隊就已經宣布了淘汰SHA-1演算法的時間表，本次碰撞實例的發布，也給所有還在持觀望和猶豫態度的人敲響了警鐘：趕緊為安全的系統啟用新的Hash演算法！

事實上，SHA-1演算法的後繼演算法早就已經被研究人員設計和推廣，SHA-2演算法家族（包括六種Hash函數：SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224, SHA-512/256）在2001年就已經公布，而NIST在經過多年的SHA-3設計競賽後，在2015年正式推薦由著名的密碼學研究人員Guido Bertoni, Joan Daemen, Micha?l Peeters和Gilles Van Assche共同設計的Keecak演算法家族作為SHA-3的候選演算法。更為值得注意的是，中國國家密碼管理局同樣在2010年底發布了我國自主的國密SM3消息摘要（密碼雜湊）演算法。這些演算法的安全性在目前經受住了廣泛的測試和分析，是值得信賴的。所以，文章的最後，GoSSIP小組建議大家：任何以SHA-1作為消息摘要演算法的安全產品應該儘快更換至這些更為安全的Hash演算法。

推薦閱讀：