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)]在谷歌安全博客上發(fā)布了世界上*例公開(kāi)的SHA-1哈希碰撞實(shí)例!在經(jīng)過(guò)兩年的聯(lián)合研究和花費(fèi)了巨大的計(jì)算機(jī)時(shí)間之后，研究人員在他們的研究SHAttered上給出了兩個(gè)內(nèi)容不同，但是具有相同SHA-1消息摘要的PDF文件，這就意味著在理論研究長(zhǎng)期以來(lái)警示SHA-1算法存在風(fēng)險(xiǎn)之后，SHA-1算法的實(shí)際攻擊案例也浮出水面，同時(shí)也標(biāo)志著SHA-1算法終于走向了生命的末期。
、
相關(guān)背景
MD-SHA系列Hash函數(shù)家族是zui為的Hash函數(shù)家族，MD5，SHA-1和SHA-2都被廣泛的使用過(guò)。1990年MD4算法被提出，但是被很快發(fā)現(xiàn)了嚴(yán)重的安全問(wèn)題，在1992年被MD5算法取代。MD5算法在之后的十幾年內(nèi)被軟件行業(yè)廣泛使用，直到2004年我國(guó)密碼學(xué)家王小云在密碼討論年會(huì)(CRYPTO)上展示了MD5算法的碰撞并給出了*個(gè)實(shí)例(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)。該攻擊復(fù)雜度很低，在普通計(jì)算機(jī)上只需要幾秒鐘的時(shí)間。在2005年王小云教授與其同事又提出了對(duì)SHA-1算法的碰撞算法(Finding Collisions in the Full SHA-1， CRYPTO 2005)，不過(guò)計(jì)算復(fù)雜度為2的69次方，在實(shí)際情況下難以實(shí)現(xiàn)。
在現(xiàn)實(shí)世界中，利用Hash碰撞的真實(shí)案例確確實(shí)實(shí)發(fā)生在我們身邊：2008年的Chaos Communication Congress大會(huì)上，研究人員展示了利用MD5碰撞來(lái)偽造合法CA證書(shū)，從而攻破HTTPS的安全體系。 2012年在中東大范圍爆發(fā)的火焰(Flame)病毒，包含了一個(gè)偽造的數(shù)字簽名，就是利用MD5碰撞偽造了合法的微軟簽名來(lái)逃避殺毒軟件的查殺。
攻擊歷程
本次攻擊的關(guān)鍵是荷蘭阿姆斯特丹CWI研究所的Marc Stevens，他自2006年以來(lái)一直在Hash算法的研究領(lǐng)域發(fā)表了大量令人艷羨的成果，包括一系列關(guān)于MD5算法的攻擊。2009年他作為一作的論文Short chosen-prefix collisions for MD5 and the creation of a rogue CA certificate在當(dāng)年的CRYPTO上獲得了*論文獎(jiǎng)，在2013年的Eurocrypt上，他發(fā)表了一篇論文——New collision attacks on SHA-1 based on optimal joint local-collision analysis，提出了構(gòu)造SHA-1碰撞的一種新的攻擊方法(攻擊復(fù)雜度為2的61次方，隨后又提出了基于GPU的實(shí)現(xiàn)方法)，隨后數(shù)年不斷提出了新的改進(jìn)方法，在2016 年他給出了關(guān)于SHA-1算法的Freestart collision，也就是找到了SHA-1算法內(nèi)部的核心組件internal compression function的一個(gè)碰撞實(shí)例(64GPU集群，10天計(jì)算量)，這就已經(jīng)吹響了攻克SHA-1*實(shí)際碰撞攻擊的決戰(zhàn)號(hào)角。終于，在Google公司強(qiáng)有力的計(jì)算資源支持之下，在2017年2月23日，SHA-1算法的碰撞實(shí)例出現(xiàn)在我們面前!
此次攻擊到底使用了多強(qiáng)的計(jì)算資源，我們可以看一下Google Security Blog給出的原始數(shù)據(jù)：
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
可以看到，這樣如此強(qiáng)勁的計(jì)算能力幾乎是歷*zui大規(guī)模的一次計(jì)算Hash碰撞的實(shí)驗(yàn)。Google Security Blog還專(zhuān)門(mén)配了一幅圖來(lái)比較，如果使用暴力搜索，使用的計(jì)算資源即使是Google也無(wú)法承擔(dān)，而在人類(lèi)智慧的研究之下，改進(jìn)的Shattered算法只需要110個(gè)GPU年就可以完成第二階段的搜索任務(wù)
關(guān)于攻擊的更多細(xì)節(jié)，可以參考論文——The first collision for full SHA-1。關(guān)于這篇論文，還有很多幕后的八卦，LoCCS實(shí)驗(yàn)室理論密碼研究組長(zhǎng)期從事分組加密算法研究的王磊研究員曾與Marc Stevens合家聚餐，親切交談，并與本次工作的作者之一Pierre Karpman長(zhǎng)期合作交流，王磊老師告訴我們，他目睹了這個(gè)密碼學(xué)歷史性事件的諸多進(jìn)展，這個(gè)轟動(dòng)性結(jié)果甚至讓今年某*學(xué)術(shù)會(huì)議的Deadline為之延期!!!
安全建議
我們指出，SHA-1碰撞攻擊影響了大量現(xiàn)有的安全應(yīng)用，目前許多部署的SSL/TLS服務(wù)連接中均使用了SHA-1算法作為消息驗(yàn)證的基本密碼學(xué)原語(yǔ)，因此受到該攻擊的影響;流行的源代碼管理系統(tǒng)Git直到目前依然使用SHA-1作為文件的消息“指紋”;另外一個(gè)廣泛受到影響的場(chǎng)景是Android系統(tǒng)中應(yīng)用APP、升級(jí)包、Bootloader等模塊的簽名機(jī)制(RSA + SHA-1)，雖然Android 7.0給出的全新的簽名方案APK Signature Scheme v2中支持SHA-2家族的SHA-256和SHA-512，但經(jīng)過(guò)我們的驗(yàn)證，目前大量設(shè)備仍然在使用sha1withRSA的簽名驗(yàn)證。在碰撞攻擊的影響下，攻擊者能夠構(gòu)造出內(nèi)容篡改但是簽名一致的文件繞過(guò)驗(yàn)證。盡管計(jì)算量巨大且對(duì)內(nèi)容的控制存在一定的困難，但是我們認(rèn)為這類(lèi)安全機(jī)制已經(jīng)不再可信。
Google公司和諸多IT安全研究人員均在過(guò)去幾年呼喚盡快更換SHA-1算法，早在2014年，Chrome團(tuán)隊(duì)就已經(jīng)宣布了淘汰SHA-1算法的時(shí)間表，本次碰撞實(shí)例的發(fā)布，也給所有還在持觀(guān)望和猶豫態(tài)度的人敲響了警鐘：趕緊為安全的系統(tǒng)啟用新的Hash算法!
事實(shí)上，SHA-1算法的后繼算法早就已經(jīng)被研究人員設(shè)計(jì)和推廣，SHA-2算法家族(包括六種Hash函數(shù)：SHA-224， SHA-256， SHA-384， SHA-512， SHA-512/224， SHA-512/256)在2001年就已經(jīng)公布，而NIST在經(jīng)過(guò)多年的SHA-3設(shè)計(jì)競(jìng)賽后，在2015年正式推薦由的密碼學(xué)研究人員Guido Bertoni， Joan Daemen， Michaël Peeters和Gilles Van Assche共同設(shè)計(jì)的Keecak算法家族作為SHA-3的候選算法。更為值得注意的是，中國(guó)國(guó)家密碼管理局同樣在2010年底發(fā)布了我國(guó)自主的國(guó)密SM3消息摘要(密碼雜湊)算法。這些算法的安全性在目前經(jīng)受住了廣泛的測(cè)試和分析，是值得信賴(lài)的。所以，文章的zui后，GoSSIP小組建議大家：任何以SHA-1作為消息摘要算法的安全產(chǎn)品應(yīng)該盡快更換至這些更為安全的Hash算法。
上海交通大學(xué)密碼與計(jì)算機(jī)安全實(shí)驗(yàn)室(LoCCS)軟件安全小組(GoSSIP)翻譯。
