從SHAttered事件談安全

大新聞？

在剛剛過去的2017年2月23日，Cryptology Group at Centrum Wiskunde & Informatica (CWI)和Google的研究人員公開了2個PDF文件，我也第一時間下載並按提示檢查了SHA-1的校驗值。文件內容和SHA1的結果如圖1所示。

圖1 重現大新聞

圖1說明了一個很簡單的事實：這是2個不同的PDF文檔，但是它們的SHA-1校驗值是一樣的。

這個簡單的事實（We have broken SHA-1 in practice.）轟動了安全界，因為這說明世界上首次實際意義上公開的SHA-1的碰撞試驗取得了成功。

SHA-1是啥？

一句話：SHA-1是Hash演算法的中廣泛使用的一種。

哈希（Hash）又稱為散列，或者雜湊，是一種演算法。這種演算法接受任意長度的數據輸入，然後給出一個固定長度的輸出。

圖2 Hash示意圖

如圖2所示，Hash函數的輸出反而沒有特別的意義，一個設計一個優良的Hash函數，需要（盡量）滿足如下條件：

• 通過輸入可以容易地計算出輸出

• 很難從給定的輸出反推出輸入，即不可逆性

• 不能修改輸入（哪怕是微小的修改）而使得輸出不變

• 不能找出2個不同的輸入，使得輸出一樣

Hash的輸出值（稱為散列值或者數據的摘要）通常可以作為數據的指紋，這在密碼學領域有重要的意義。

SHA（Secure Hash Algorithm）是由National Institute of Standards and Technology (NIST) 制定的作為U.S. Federal Information Processing Standard (FIPS)的散列函數家族。

圖3 SHA家族

這次被發現碰撞的是SHA-1散列演算法，是目前依然使用非常廣泛的一種演算法，它的輸出是160個bits，圖1中用了40個16進位數來表示。SHA-1被發現碰撞之所以能成為大新聞，和它的應用場景分不開。

大新聞做了啥？

雖然說在2005年文獻[2]已經提出了複雜度小於的理論碰撞，在2013年文獻[5]將這一數字優化到，但是他們都是理論分析，並沒有給出實證。在不見棺材不掉淚的情況下，給出一個實例才是最好的。所以，The first collision for full SHA-1一文創造了第一個碰撞的實例。

他們基於[5]的研究，使用一種名為相同前綴碰撞攻擊（identical-prefix collision attack）的方法：

即2條消息的前綴P是一樣的，主要尋找2個數據對

使得2個完整消息的SHA-1輸出相等，而後綴S可以是任意值。一旦這樣的數據對找到，就嚴重違背了「不能找出2個不同的輸入，使得輸出一樣」這一要求，也就宣布了SHA-1演算法已經變得不安全。

當然找到這樣一個碰撞的難度很大，得益於研究人員對演算法的不斷優化和GPU技術的發展，現在終於實現了在複雜度下的實際碰撞攻擊。如果認為圖1還是一個巧合的話（實際上這樣的巧合發生概率趨近於0），論文中還給出了另外一組實例，如圖4所示。

圖4 SHA-1碰撞實例

這次的實際攻擊是拿JPEG開刀，所以PDF中是2幅圖像不同，也算是比較有視覺說服力的實例。按照慣例，這次碰撞攻擊的細節（包括技術細節和源代碼）將會在以後條件成熟時公開。

以Git為例

Git的本質是一種內容定址的文件系統（Content-addressable filesystem），也就是說Git內部是通過鍵值對的方式存儲的，而檢索的本質是通過鍵來查找對應內容。因此向Git提交的任意內容，都會通過Hash演算法得到一個唯一的鍵，以後可以通過這個鍵唯一地檢索到存儲的內容。而Git使用的Hash演算法正是SHA-1。

接下來驗證這一點。

以一個文件為例，Git對於該文件取Hash的方法如下：

sha1(『blob 』 + filesize + 『0』 + filedata)

圖5 Git中的Hash

圖5中，3個紅框代表了3次hash操作。

第一次是使用openssl提供的sha1演算法計算hash

第二次是git提供的 hash-object方法計算hash

第三次是實際創建了一個倉庫並在commit後檢查hash

三次計算的結果完全一致，說明了Git在內部完全依賴SHA-1演算法作為其hash演算法。

實際上，Git並不關心文件或者處理的對象的名稱，而只通過Hash值來區分他們。在Git的世界裡，一個對象的Hash就是一個對象的唯一ID。如果ID可以偽造，那麼就沒有然後了。

接下來分析Git在遇到Hash碰撞的時候如何處理。

是不是很期待再來一發截圖玩壞Git，然而現在並不行。實際情況由於碰撞需要的計算量依然遠超過PC的能力，以及技術細節並沒有完全公開，真實的情況還有待驗證。而且Git並不是直接計算文件的Hash，所以圖1給出的樣例碰撞不會影響Git的運作。

要不「稍微」修改一下Git的實現，人為創造碰撞試試。文獻[1]通過修改源碼的方式，構造了一個簡化的4 –bit SHA1版本來探究了碰撞的情況。

實驗的結果是，在不少常見場景下，Git不報錯，而實際上倉庫已經出現了不同類型的損壞。

一種簡單的修復方法是報錯並提示用戶，雖然此時Git不能正常運作，但是可以及時止損。

再看HTTPS

相比Git的問題，HTTPS使用的證書，情況似乎好很多。

SHA-1的不安全性，王小雲教授早就在2005年就已經指出了[2]。

近幾年各大公司也正逐漸的淘汰SHA-1：

對於SSL證書，Windows已於2017年1月1日起停止支持SHA1證書。

對於代碼簽名證書，Windows早在2016年1月1日就停止接受沒有時間戳的SHA-1簽名的代碼和SHA-1證書。

Google的Chrome瀏覽器已經逐步地廢棄了SHA-1證書支持，現在最新版的Chrome已經徹底不支持了。

Mozilla自2017 年 1 月1 日後不再信任SHA-1證書。

……

可以看到，不再支持SHA-1隻是一個時間問題。或許這次的大新聞將加速這一進程。

So far so good。這是由於，對於大公司而言，更換新的證書很簡單，因為不涉及到客戶端的分發。

真正的挑戰還是客戶端：對於寫應用程序的工程師來說，困難在於老舊的客戶端不支持某些新特性，而在安全領域是倒過來的，困難的是老舊的客戶端支持了過時的特性。

所以並不是大公司更新了證書，用戶就可以高枕無憂。以HTTPS為例，只要瀏覽器還支持SHA-1，那麼攻擊者就可以偽造一個SHA-1簽名的證書來冒充，即便被攻擊的對象早已升級成了更安全的證書。因為瀏覽器會直接信任收到的SHA-1假證書，並不知道新證書的存在。這種方式的攻擊只能從各方面來緩解，真正要杜絕，只能讓瀏覽器徹底不支持SHA-1。

（以下以Windows為例，其它產品情況類似，或者更糟吧）

幸運的是，我們生活在一個科技快速更新的時代，Windows 10已經迭代了多個版本，大家覺得夠好用的Windows 7 ，實際上都是8年前的「老古董」了，好在老傢伙們都老當益壯，沒有問題。

不幸的是Windows XP！Windows XP在SP3之後才支持SHA-2，才能夠淘汰SHA-1。問題：國內還有多少Windows XP的用戶，幾百萬？他們打死不升級系統還會在乎是SP幾么。但是又不能徹底放棄XP，難道只有時間才能告訴我們答案……

歷史的行程和改進建議

這次大新聞還給出了攻擊的代價。相比MD5可以用手機秒算而言，SHA-1的代價是110個GPU一年。這個代價對於中小企業和個人還是很難接受，但是對於大公司而言是可以做到的。更別忘了摩爾定律還在垂死掙扎，擁有更加高效，更加廉價的計算資源，也是歷史的行程，不能不考慮。

圖6 代價對比

所以，在安全領域，一種演算法用到天荒地老是不太現實的。實際上每一種密碼學演算法都有其預估的生命周期，「道高一尺，魔高一丈」，不斷的更新迭代，才鑄就了密碼學今日的輝煌。

例如，文獻[3]給出了Hash的生命周期。

圖7 Hash的生命周期

簡言之，紅色已死，黃色有小病，綠色的活蹦亂跳。

這次的新聞，給SHA-1畫上了句號，目前依然存活的是SHA-2（例如SHA-256）和SHA-3（Keccak是最終勝出者）。

所以改進的思路倒是很簡單：新的項目全用SHA-2或者SHA-3就可以了。SHA-2已經非常成熟，直接拿來用即可。SHA-3的各種高效實現也層出不窮，這些都是依然安全的Hash演算法（Keccak真是一個年輕充滿活力的演算法，個人推薦）。

對於正在開發的項目，能換的趕緊換，不能換的也要創造條件換。畢竟以後攤子大了更加不好辦。

對於已有的項目，比如Git這種情況，想更換也就只能慢慢迭代更新了。這確實是有較大的工程量。如這裡[4]提到的，單單是替換硬編碼的unsigned char[20]，可能就需要不少精力。（SHA-256和SHA-3的輸出都不止160bits，20位元組的空間是不夠的）

此外對於一些安全不敏感的應用，也可以不用換。MD5理論上已經「死了」十多年了，但是還是有不少地方在使用它們。畢竟軟體工程上有牽一髮動全身的特點，如果僅僅為了替換一個演算法，而引入了更多不該有的bug，反而得不償失。

最後是對於普通用戶的建議：有條件就更新。消費電子產品買新不買舊在歷史的行程上看還是總體正確的。即便硬體不能更新，軟體也要及時更新，這能解決很多安全上的問題（雖然也可能帶來一些小的麻煩）。

參考文獻

[1] How would Git handle a SHA-1 collision on a blob? How would Git handle a SHA-1 collision on a blob?

[2] Wang X, Yin Y L, Yu H. Finding collisions in the full SHA-1[C]//Annual International Cryptology Conference. Springer Berlin Heidelberg, 2005: 17-36.

[3] Lifetimes of cryptographic hash functions Lifetimes of cryptographic hash functions

[4] Why doesnt Git use more modern SHA? http://stackoverflow.com/questions/28159071/why-doesnt-git-use-more-modern-sha

[5] Stevens M. New collision attacks on SHA-1 based on optimal joint local-collision analysis[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer Berlin Heidelberg, 2013: 245-261.

作者：cyxu，更多安全類文章，請持續關注阿里聚安全的安全專欄和官方博客

推薦閱讀：