上學期選修了一門信息安全討論，期末的時候是寫一個關(guān)于信息安全方面的報告，找本科畢設(shè)精簡一下交上去，被老師發(fā)現(xiàn)了，開學來了要重新寫，哭，于是遂有下文。

摘 要: Google對于SHA-1的破解是一個重大的突破，從應(yīng)用層上驗證了SHA-1的不安全 性。本文詳細的介紹了哈希函數(shù)及 SHA-1 的發(fā)展和應(yīng)用，其中著重介紹了針對 SHA-1 的攻 擊的歷史發(fā)展。最后我們介紹了在 SHA-1 之后的一些哈希函數(shù)的安全性和發(fā)展現(xiàn)狀。

關(guān)鍵詞:SHA-1，哈希函數(shù)，碰撞

1 引言

2017年2月23日，Google經(jīng)過兩年的研究，表示其已經(jīng)成功破解了SHA-1加密，具體的詳情在90天之后我們就能知道(根據(jù)Google的披露原則)。同時，還發(fā)布了兩份特制 PDF 文檔，它們擁有相同的SHA-1值，但是內(nèi)容卻不盡相同。谷歌公司多年來一直主張棄用SHA-1方案，特別是在TLS證書簽署等場景之下。早在2014年，Chrome小組就宣布將逐漸淘汰對SHA-1的使用。Google希望自己針對SHA-1完成的實際攻擊能夠進一步鞏固這一結(jié)論，讓更多人意識到其已經(jīng)不再安全可靠。

關(guān)于SHA-1的安全性，早在2005年，密碼學家就證明SHA-1的破解速度比預期提高了2000倍，雖然破解仍然是極其困難和昂貴的，但隨著計算機變得越來越快和越來越廉價， SHA-1 算法的安全性也逐年降低，已被密碼學家嚴重質(zhì)疑，希望由安全強度更高的 SHA-2 替代它。但是現(xiàn)在還是有好多領(lǐng)域在使用SHA-1。SHA-1 被業(yè)內(nèi)廣泛用于數(shù)字簽名、文件 完整性驗證、以及保護廣泛的數(shù)字資產(chǎn)(包括信用卡交易、電子文檔、開源軟件資源庫與 軟件更新等)的加密標準。

互聯(lián)網(wǎng)的出現(xiàn)給人們的生活或者工作帶來了極大的方便。但是隨著計算機被廣泛應(yīng)用的信息時代，面對越來越多的信息。如何保護信息的安全越來越顯得重要。特別是在網(wǎng)絡(luò)化的 今天，我們的很多信息暴露在網(wǎng)上，比如出生證明、身份信息、信用卡信息、學籍信息等。如果我們不對這些信息加以保護，那將給我們的生活帶來危害。哈希算法在我們?nèi)粘＞W(wǎng)絡(luò)安 全、代碼倉庫安全、甚至是確認文件的完整性方面都扮演著重要的角色。比如我們在登錄系統(tǒng)時，將我們的登錄密碼進行哈希后再保存起來，可以防止存放賬號密碼的數(shù)據(jù)庫被人入侵 時，破壞者仍然不知道我們的密碼。

2 哈希函數(shù)

哈希函數(shù)(Hash Function)又稱散列函數(shù)、散列算法。是一種將任意長度的數(shù)據(jù)映射到有限長度的域上。即對一串數(shù)據(jù)進行雜糅，輸出一段固定長度的數(shù)據(jù) h，這段固定長度的數(shù) 據(jù)稱為指紋。

哈希函數(shù)需要滿足一定的條件，首先是要滿足確定性，哈希函數(shù)算法是確定性的算法，算法執(zhí)行過程不引入任何隨機變量。即相同消息的哈希結(jié)果一定相同。如果相同消息產(chǎn)生的 結(jié)果不同，那這種算法也就不是哈希函數(shù)。高效性，給定任意一個消息，可以快速計算Hash(m)。哈希函數(shù)一個特點就是計算速度快，這樣就可以把長的消息轉(zhuǎn)為短的消息，然后供其他計算速度慢的算法去計算，用哈希函數(shù)做一個預處理。目標抗碰撞性，給定任意一個消息$m_0$ ，很難找到另一個消息$m_1$ ，使得 Hash($m_0$)=Hash($m_1$)。這也是在破解的時候，是基于目標抗碰撞性的。如果給定任意一個消息$m_0$ ，都能找到另外一個消息與它哈希值相同，
那么就可以稱完全破解了這種算法。廣義碰撞性，很難找到兩個消息$m_0=?m_1$，使得 Hash($m_0$)= Hash($m_1$)。如果第四個條件不滿足，則這個哈希函數(shù)是不安全的。如果第三個條件完全不滿足，那么此哈希函數(shù)已經(jīng)徹底不安全，應(yīng)該直接棄用。哈希函數(shù)要具有抗碰撞的能力以及抗篡改能力，對于一個數(shù)據(jù)塊，哪怕只是改動其一個比特位，其hash值的改動也會非常大。

哈希函數(shù)在信息安全方面的一個作用就是進行文件校驗，相比于我們熟悉的奇偶校驗和CRC校驗，使用哈希函數(shù)的校驗具有抗數(shù)據(jù)篡改的能力，防止對數(shù)據(jù)的惡意破壞。在文件 傳送后，將得到的目標文件計算的哈希值和源文件的哈希值進行對比，由著兩者的一致性，可以保證兩個文件的每一個碼元都是相同的。可以校驗文件傳輸過程中是否出現(xiàn)錯誤，以及更重要的是可以保證文件在傳輸過程中未被惡意破壞。比如我們在上Oracle官網(wǎng)上下載JDK的時候，就會有checksum。供用戶下載后進行驗證，保證下載JDK的正確性。還有在Linux系統(tǒng)安裝軟件包的時候，也可以進行校驗，以保證安裝的軟件包是來自于官方的源，不被破壞者植入惡意代碼。

哈希函數(shù)的另一個作用就是數(shù)字簽名，由于非對稱算法的運算速度較慢，所以在數(shù)字簽名協(xié)議中也包含了哈希函數(shù)，在這種簽名協(xié)議中，雙發(fā)必須事先協(xié)商好雙方都支持的 Hash 函數(shù)和簽名算法。簽名方先對數(shù)據(jù)文件使用哈希函數(shù)計算散列值，然后對較短的哈希值結(jié)果用非對稱算法進行數(shù)字簽名操作，接受方先對數(shù)據(jù)文件進行計算哈希值，然后再用非對稱算法驗證數(shù)字簽名。具體過程如圖1所示，數(shù)字簽名進行身份認證，并保證完整性和不可否認性。

SHA-1

3 SHA-1

3.1 SHA-1簡介

SHA(Secure Hash Algorithm)安全散列算法是一個密碼散列家族，由美國國家安全局(NSA)所設(shè)計，也是一種哈希函數(shù)。是FIPS所認證的安全散列算法。能計算出一個數(shù)字消息所對應(yīng)到的，長度固定的字符串(又稱消息摘要)的算法。輸入的消息不同，它們對應(yīng)到不同字符串的概率很高。

SHA-1發(fā)布于1995年，與前身MD5相比，SHA-1的輸出長度更長，(MD5輸出長度為128bit，SHA-1輸出長度為160bit)，曾被視為是MD5(更早以前被廣泛使用的散列函數(shù))的后繼者。在許多安全協(xié)議中廣為使用，包括TLS和SSL，PGP、SSH、S/MIME和IPsec。但SHA-1的安全性在2000年以后已經(jīng)不被大多數(shù)的加密場景所接受。

3.2 SHA-1算法

SHA-1 可以對不超過$2^{64}$比特的消息進行計算，輸入以512位數(shù)據(jù)塊為單位處理，產(chǎn)生160比特的消息摘要作為輸出。該算法的處理流程主要分為5個步驟:

步驟 1:對輸入的數(shù)據(jù)進行填充，是的數(shù)據(jù)位長度對512求余的結(jié)果為448。填充比特 串的最高位補一個 1，其余位補0。附加填充總是要進行的，即使消息的長度滿足所要求的長度。

步驟 2:將64比特加在報文后表示報文的原始長度，是報文長度為512比特的倍數(shù)。

步驟 3:一個160位MD緩存用以保存中間和最終的散列函數(shù)的結(jié)果。它可以表示為32位寄存器(A，B，C，D，E)。初始化為 A=67452301，B=EFCDAB89，C=98BADCFE， D=10325476，E=C3D2E1F0。前四個是與MD5相同的，但存儲為big-endian format，即將高 序字節(jié)存儲在起始地址。

步驟 4: 以512比特(16個字)分組處理消息。此算法的核心就是稱為壓縮算法(compression function)的模塊。這個模塊包括4次循環(huán)，每次循環(huán)又包含20 個處理步驟。 4次循環(huán)具有相似的結(jié)構(gòu)，但每次循環(huán)使用不同的基本邏輯函數(shù)，稱為 f1，f2，f3，f4。

步驟 5:全部L個512位數(shù)據(jù)塊處理完畢后，輸出160位消息摘要。

3.3 SHA-1碰撞

1990 年 MD4 算法提出，但是很快發(fā)現(xiàn)了嚴重的安全問題，在1992年被MD5算法取代，MD5算法在之后的十幾年內(nèi)被軟件行業(yè)廣泛使用，但之后也被破解。隨后開始使用SHA-1。

關(guān)于尋找哈希函數(shù)碰撞的難度和一般方法，SHA-1輸出長度為160bit。如果SHA-1本身沒有漏洞，而攻擊者想要找到一組碰撞的話，最顯然的方法是選取$2^{160}$ 組不同的數(shù)據(jù)，依次計算它們的哈希結(jié)果。根據(jù)著名的抽屜原理，必然會出現(xiàn)一組數(shù)據(jù)，使得其哈希結(jié)果相同。 此攻擊方法需要調(diào)用$2^{160}$次 SHA-1，即計算量級大約為$2^{160}$。這樣的計算代價是巨大的，實際操作根本不可能。

上面的方法可以通過放寬條件，用概率的方法尋找，能降低一定的計算量。 一個屋子里必須有366個人(一年有365天，不考慮閏年的情況)才能保證有兩個人的生日是同一天。
但假設(shè)現(xiàn)在有23個人，根據(jù)概率論:第2個人和第1個人生日不同概率為1-$\frac{1}{365}$，第3個人和前兩個人生日不同的概率為$(1?\frac{1}{365})(1?\frac{1}{364})$ ，第4個人和前三個人生日都不相同的概率為$(1?\frac{1}{365})(1?\frac{1}{364})(1?\frac{1}{363})$，依次類推，第23個人和前22個人生日都不相同的概率為$$\prod_{i=1}^{23}(1-\frac{1}{365-i+1})$$，上述事件同時發(fā)生時，23個人生日才會各不相同。因此23個人中存在2個人生日相同的概率為:
$$1?\frac{365!}{(365-23)!365^{23}} ≈ 50% $$。所以在尋找哈希碰撞時，選擇大約$\sqrt{2^{160}}=2{80}$組不同的數(shù)據(jù)并計算哈希結(jié)果，則有50%的概率有2個哈希結(jié)果相同。此方法的數(shù)量級遠優(yōu)于前一種方法，但是引入的代價是成功率變?yōu)?0%。密碼學上認為，如果能找到一種方法，能在計算時間小于$2^{80}的情況下，有超過生日攻擊概率下找到一組碰撞，則認為這個哈希函數(shù)就不安全了。

SHA-1自提出后，學者們一直認為它是安全的，并沒有找到計算時間小于$2^{80}$攻擊方法。 我國著名密碼學家王小云教授所在的團隊提出了一種尋找SHA-1碰撞的，相對快速的攻擊方法。此攻擊方法的計算量級為269，這標志著SHA-1存在漏洞。NIST不得不選擇新的哈希函數(shù)，因此才有了SHA-256、SHA-384、SHA-512等。

王小云教授的開創(chuàng)性工作讓進一步破解SHA-1成為了可能。然而，王小云教授的方法 僅可破解SHA-1的廣義抗碰撞性，且計算時間相對較長。在計算發(fā)雜度上也很高，具體操 作上可行度并不是很高。這表明SHA-1在一段時間內(nèi)還是可以使用的。后來Stevens提出了 一種攻擊方法，可以在$2^{61}$計算量級內(nèi)找到一組哈希碰撞。

上述方法都是使用純CPU計算的方法。Stevens等人在2016年提出了新的攻擊方法， 把顯卡(即GPU)引入破解工作，使用大規(guī)模并行處理，進行并行計算，則計算量級會進一步降低到$2^{57.5}$。這樣使得具體的破解成為了可能，本次Google的破解工作也使用了類似的方法。

3.4 Google 的破解工作

Google 發(fā)布了兩個 PDF 文件，第一個 PDF 文件打開打開如圖 2 所示，

SHAttered1

SHAttered2

upload

4 一些其他的SHA

在SHA-0和 SHA-1 之后，NSA 又設(shè)計發(fā)布了 SHA-2 和 SHA-3，其中 SHA-2 包括SHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224和SHA-512/256。后面跟的數(shù)字是哈希后的 bit 位數(shù)。至今尚未出現(xiàn)對 SHA-2 有效的攻擊，但是由于其算法與 SHA-1 相似。 需要一個其他替代的散列算法，于是 SHA-3 出現(xiàn)了，SHA-3 并不是要替換 SHA-2，而是算 法不同，更加的安全。
現(xiàn)在很多網(wǎng)絡(luò)上很多地方還在使用SHA-1，比如我們現(xiàn)在我們打開網(wǎng)站好多都是https。 但是一些一些網(wǎng)站使用的 https 證書是用 SHA-1 進行哈希計算的，這樣是很不安全的?，F(xiàn)在 很有必須更換為 SHA-2 等安全性算法，當然國內(nèi)還有好多網(wǎng)站沒有實現(xiàn) https，這也需要盡 快加上 https，使用戶訪問網(wǎng)站更加安全。

5 結(jié)論

本文根據(jù)最近Google對SHA-1的破解，了解了關(guān)于哈希函數(shù)的定義以及它的一些應(yīng)用發(fā)展。之后著重討論了SHA-1的算法及破解的歷程，以及Google這次破解對信息安全一些 領(lǐng)域的影響。最后介紹了其他的哈希函數(shù) SHA-2 和 SHA-3 這些現(xiàn)在安全的的哈希函數(shù)。
當然本文只是一個簡單的探究，還有好多關(guān)于哈希函數(shù)的其他知識尚未涉及到。