基于局部碰撞算法的SHA—1改進(jìn)算法設(shè)計(jì)與研究

劉坤+楊正校

摘 要：SHA-1是一種哈希函數(shù)，它被廣泛使用在電子商務(wù)這樣的現(xiàn)代安全領(lǐng)域，特別是應(yīng)用于數(shù)據(jù)加密通信、數(shù)字簽名。很多的密碼協(xié)議、標(biāo)準(zhǔn)中都包括了SHA-1算法，如著名的SSL、IPsec和PKCS。本文通過(guò)深入分析SHA-1算法及碰撞算法原理，找出SHA-1算法內(nèi)部碰撞的原因，對(duì)算法中邏輯函數(shù)和壓縮函數(shù)進(jìn)行改進(jìn)設(shè)計(jì)，得到基于局部碰撞算法的SHA-1改進(jìn)算法。

關(guān)鍵詞：哈希函數(shù)；SHA-1算法；局部碰撞算法；壓縮函數(shù)

中圖分類號(hào)：TP309 文獻(xiàn)標(biāo)識(shí)碼：A

Abstract：As a hash function，SHA-1 is widely used in modern security fields such as electronic commerce，especially for data encrypted communication and digital signature.The SHA-1 algorithm is applied in many cryptographic protocols and standards，such as the famous SSL，IPsec and PKCS.Through the in-depth analysis of the SHA-1 algorithm and the collision algorithm principle，the paper identifies the causes of internal collision in the SHA-1 algorithm，improves the logical function and compression function in the algorithm，and achieves the improved SHA-1 algorithm based on the local collision algorithm.

Keywords：hash function；SHA-1 algorithm；Local collision algorithm；compression function

1 引言（Introduction）

Hash函數(shù)主要有兩個(gè)系列，分別是MDx系列和SHA系列，其中MDx系列包括MD4、MD5等，SHA系列主要包括SHA-1、SHA-2等。MD5、SHA-1和SHA-2算法在數(shù)據(jù)加密、數(shù)字簽名方面被廣泛應(yīng)用。1990年MD4算法被提出，但是很快發(fā)現(xiàn)MD4算法存在嚴(yán)重的安全問題，在1992年MD4算法被MD5算法取代。MD5算法在之后的十幾年內(nèi)被軟件行業(yè)廣泛使用，直到2004年我國(guó)密碼學(xué)家王小云在國(guó)際密碼討論年會(huì)（CRYPTO）上展示了MD5算法的碰撞，并給出了第一個(gè)實(shí)例[1]。該攻擊復(fù)雜度很低，在普通計(jì)算機(jī)上只需要幾秒鐘的時(shí)間。在2005年王小云教授與其同事又提出了對(duì)SHA-1算法的碰撞算法[2]，不過(guò)計(jì)算復(fù)雜度為2的69次方，在實(shí)際情況下難以實(shí)現(xiàn)。2008年的Chaos Communication Congress大會(huì)上，研究人員展示了利用MD5碰撞來(lái)偽造合法CA證書，從而攻破了HTTPS的安全體系。2012年在中東大范圍爆發(fā)的火焰（Flame）病毒，包含了一個(gè)偽造的數(shù)字簽名，就是利用MD5碰撞偽造了合法的微軟簽名來(lái)逃避殺毒軟件的查殺。

2017年2月23日，荷蘭阿姆斯特丹（CWI）研究所和Google公司的研究人員在谷歌安全博客上發(fā)布了世界上第一例公開的SHA-1哈希碰撞實(shí)例，在經(jīng)過(guò)兩年的聯(lián)合研究和花費(fèi)了巨大的計(jì)算機(jī)時(shí)間之后，研究人員在他們的研究網(wǎng)站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算法終于走向了生命的末期。從這些事件上可以看出，MD4、MD5和SHA-1已經(jīng)不安全。本文主要根據(jù)近幾年國(guó)內(nèi)外對(duì)SHA-1算法的碰撞算法進(jìn)行分析研究，給出算法中壓縮函數(shù)和邏輯函數(shù)的改進(jìn)描述，以提高SHA-1抗碰撞性。

2 SHA-1算法內(nèi)部碰撞原理（Internal collision

principle of SHA-1 algorithm）

SHA-1算法通過(guò)一系列的迭代計(jì)算把任意長(zhǎng)度的比特串壓縮成長(zhǎng)度160位的位串，而且一般認(rèn)為它的計(jì)算過(guò)程在密碼學(xué)意義上是單向的，也就是很難找到兩個(gè)不同的位串可以壓縮成相同的160位串[3]。正因?yàn)镾HA-1算法具有良好的特性，它被廣泛使用在電子商務(wù)這樣的現(xiàn)代安全領(lǐng)域，特別是應(yīng)用于公鑰密碼系統(tǒng)的數(shù)字簽名中，很多的密碼協(xié)議、標(biāo)準(zhǔn)中都包括了SHA-1算法，如著名的SSL、IPsec和PKCS。當(dāng)今社會(huì)移動(dòng)終端技術(shù)快速發(fā)展，推動(dòng)了電子商務(wù)的發(fā)展，因此SHA-1算法的安全性直接影響了使用它作為協(xié)議的密碼系統(tǒng)安全性，也將影響到電子商務(wù)活動(dòng)中數(shù)字證書的安全性。

針對(duì)哈希函數(shù)的攻擊方式很多，具體分類如圖1所示，其中最常用的是碰撞攻擊。所謂碰撞攻擊也就是假設(shè)哈希函數(shù)為H，攻擊者嘗試找到兩個(gè)信息M和M'，假設(shè)M≠M(fèi)'，但H（M）=H（M'）[4]。根據(jù)Hash函數(shù)的值域與定義域相比規(guī)模要小得多，是“多對(duì)一”映射，找出兩個(gè)不同的消息，使其產(chǎn)生相同的Hash結(jié)果，這稱為碰撞攻擊。一個(gè)具有n比特輸出長(zhǎng)度的Hash函數(shù)共有2n個(gè)可能的輸出值，用窮舉法只要計(jì)算2n/2個(gè)消息，就能期望找到一對(duì)碰撞。因此，值2n/2決定了Hash函數(shù)抗強(qiáng)行攻擊的強(qiáng)度[5]。如果一個(gè)輸出長(zhǎng)度為n比特的Hash函數(shù)可以用小于2n/2的計(jì)算找到一對(duì)碰撞，則該Hash函數(shù)理論上被認(rèn)為是可破解的。對(duì)于SHA-1來(lái)說(shuō)，利用窮舉法尋找它的碰撞至少需要進(jìn)行280次運(yùn)算，而最新的研究已經(jīng)將碰撞次數(shù)減低到了257.5，也就是大大提高了SHA-1碰撞可能性，并且已經(jīng)找到具體碰撞實(shí)例[6]，這說(shuō)明SHA-1碰撞處理方面有嚴(yán)重的安全缺陷。

在明文空間中隨機(jī)選取一段明文求出其Hash值，并以單字節(jié)字符的方式來(lái)表示，然后隨機(jī)地選擇并改變明文中任意1比特的值得到另一新的Hash結(jié)果。定義兩個(gè)Hash值之間的距離為：

其中，ei和ei'分別是最初和新的Hash值的第i個(gè)字符，S為Hash值對(duì)應(yīng)字符的個(gè)數(shù)，函數(shù)t（）將ei和ei′轉(zhuǎn)換成對(duì)應(yīng)的十進(jìn)制數(shù)。若兩個(gè)Hash分別由兩個(gè)獨(dú)立的均勻分布的隨機(jī)序列所組成，則理論上Hash值的單位字符的平均距離為85.33。取輸入長(zhǎng)度n=512比特，隨機(jī)選擇輸入樣本，測(cè)試其輸出的單位字符的平均距離。有關(guān)實(shí)驗(yàn)數(shù)據(jù)表明SHA-1算法在迭代在30步之后，其輸出的單位字符的平均距離才趨于穩(wěn)定[6]。

SHA-1算法的關(guān)鍵是壓縮函數(shù)。在SHA-1的內(nèi)部結(jié)構(gòu)中，鏈接變量A、B、C、D、E經(jīng)過(guò)6個(gè)操作步的傳遞、混合后，又回到A、B、C、D、E，過(guò)程如圖2所示。這樣就容易出現(xiàn)局部碰撞。例如若在SHA-1算法第i步存在1比特消息差分，這1比特差分將在隨后的5操作步中依次影響5個(gè)鏈接變量。由于存在這樣的規(guī)律性，若能阻止差分傳播，則可構(gòu)造一個(gè)局部碰撞差分鏈，進(jìn)而產(chǎn)生6操作步的局部碰撞。

3 SHA-1算法壓縮函數(shù)和邏輯函數(shù)分析（Analysis

of SHA-1 algorithm's compression function and＼

logical function）

3.1 SHA-1算法邏輯函數(shù)分析

在SHA-1算法中邏輯函數(shù)ft具有良好的混淆性，但是自身的抗碰撞性較弱。SHA-1壓縮函數(shù)邏輯結(jié)構(gòu)有四輪循環(huán)模塊，每一輪使用一個(gè)函數(shù)如f1、f2、f3、f4來(lái)表示四輪循環(huán)對(duì)應(yīng)的邏輯函數(shù)，函數(shù)如下式所示[7]：

從中可以知道這四個(gè)函數(shù)中f2和f4是相同的，這樣會(huì)造成防御風(fēng)險(xiǎn)。

3.2 SHA-1算法壓縮函數(shù)分析

SHA-1算法能夠?qū)⑷我忾L(zhǎng)的輸入壓縮成160bit的輸出，但SHA-1算法中的基本迭代只能處理512bit的數(shù)據(jù)塊。因此首先需要將輸入的消息每512bit分成一塊，并將最后一塊不足的消息按一定規(guī)則補(bǔ)齊。SHA-1算法的核心部分是壓縮函數(shù)。SHA-1算法壓縮函數(shù)的功能結(jié)構(gòu)，是將字符串以512位分組為單位進(jìn)行處理，主循環(huán)由四輪循環(huán)模塊構(gòu)成，每輪20個(gè)步驟的運(yùn)算，輸入當(dāng)前分組q的16個(gè)字，和由前一個(gè)分組輸出的160位緩存值[8]。

SHA-1壓縮函數(shù)的工作過(guò)程是首先5個(gè)中間變量a，b，c，d，e中置入特定初值，壓縮函數(shù)的輸入值為IHVin=（a，b，c，d，e）。然后512位信息塊B被分割成16個(gè)連續(xù)的32位字，如W0，W1，…，W15，利用擴(kuò)展函數(shù)公式（1），將字從16個(gè)擴(kuò)展到80個(gè)。

4 基于局部碰撞的SHA-1改進(jìn)算法研究（Research

on improved SHA-1 algorithm based on local

collision）

通過(guò)對(duì)SHA-1算法和碰撞攻擊原理分析，找到SHA-1算法產(chǎn)生內(nèi)部碰撞的原因，這里主要從兩個(gè)方面即SHA-1算法的邏輯函數(shù)和壓縮函數(shù)進(jìn)行算法改進(jìn)，以提高SHA-1抗碰撞攻擊能力。

4.1 SHA-1邏輯函數(shù)改進(jìn)研究

SHA-1每輪循環(huán)實(shí)際上只使用了三個(gè)函數(shù)。這樣隨著現(xiàn)在攻擊者技術(shù)和計(jì)算能力的不斷提高，SHA-1的安全性受到了很大的影響。本文采用變換其中一個(gè)函數(shù)，也就是使f2和f4不一樣，加強(qiáng)SHA-1算法的完備性，以及增加整體算法的抗差分分析能力。這里針對(duì)函數(shù)f4的表達(dá)式進(jìn)行修改，見表1。這樣改進(jìn)后，對(duì)其運(yùn)算速度幾乎沒有影響，同時(shí)大大提高了SHA-1的安全性和抵抗SHA-1算法局部碰撞攻擊的能力。

4.2 SHA-1壓縮函數(shù)邏輯結(jié)構(gòu)改進(jìn)研究

從上面的SHA-1壓縮過(guò)程中得知，壓縮函數(shù)邏輯結(jié)構(gòu)對(duì)其進(jìn)行四輪、每輪20個(gè)步驟的運(yùn)算存在一個(gè)規(guī)律性的安全隱患，這里通過(guò)改變壓縮函數(shù)邏輯運(yùn)算來(lái)抵抗強(qiáng)碰撞攻擊，同時(shí)對(duì)計(jì)算量幾乎沒有影響。針對(duì)上面所述SHA-1碰撞出現(xiàn)的原因，這里將SHA-1壓縮函數(shù)進(jìn)行改進(jìn)的算法是在第一輪的壓縮函數(shù)中，用簡(jiǎn)單的邏輯判斷、邏輯取反、移位操作引入到混合函數(shù)，目的在于加速首輪的差分?jǐn)U散，并且打破原來(lái)固定的鏈接變量傳遞方式帶來(lái)的規(guī)律性，使傳遞過(guò)程具有很強(qiáng)的隨機(jī)性，從而消除局部碰撞的依從條件。

5 結(jié)論（Conclusion）

針對(duì)SHA-1碰撞算法研究必將導(dǎo)致不久的將來(lái)SHA-1算法被破解，攻擊者可以通過(guò)偽造數(shù)字證書等手段破壞密碼系統(tǒng)、數(shù)字證書系統(tǒng)的電子商務(wù)領(lǐng)域的安全性、可靠性，嚴(yán)重可導(dǎo)致經(jīng)濟(jì)損失或有政治攻擊目的。因此對(duì)SHA-1算法的研究和改進(jìn)具有重大意義。SHA-1算法的改進(jìn)可以有效提高利用SHA-1算法進(jìn)行加密、數(shù)字簽名的信息安全性、可靠性。

本文根據(jù)SHA-1算法內(nèi)部缺陷找到碰撞原因，對(duì)SHA-1算法中邏輯函數(shù)和壓縮函數(shù)進(jìn)行改進(jìn)描述，以提高SHA-1算法抗碰撞性。下一步可以將改進(jìn)算法在硬件電路上進(jìn)行設(shè)計(jì)實(shí)現(xiàn)，測(cè)試改進(jìn)算法的抗碰撞性和運(yùn)算速度。

參考文獻(xiàn)（References）

[1] Xiaoyun Wang，Hongbo Yu.How to Break MD5 and Other Hash Functions，EUROCRYPT（Ronald Cramer，ed.）[M].Lecture Notes in Computer Science，2005，3494：19-35.

[2] Xiaoyun Wang，Yiqun Lisa Yin，Hongbo Yu.Finding Collisions in the Full SHA-1，CRYPTO（Victor Shoup，ed.）[？？].Lecture Notes in Computer Science，2005，3621：17-36.

[3] 黃諄，白國(guó)強(qiáng)，陳弘毅.快速實(shí)現(xiàn)SHA-1算法的硬件結(jié)構(gòu)[J].清華大學(xué)學(xué)報(bào)（自然科學(xué)版），2005，45（1）：123-125.

[4] 張斌，徐名揚(yáng).SHA-1算法及其在FPGA加密認(rèn)證系統(tǒng)中的應(yīng)用[J].中國(guó)集成電路，2011，145（6）：57-61.

[5] 林雅榕，侯整風(fēng).對(duì)哈希算法SHA-1的分析和改進(jìn)[J].計(jì)算機(jī)技術(shù)與發(fā)展，2006，16（3）：124-126.

[6] 劉建東，余有明，江慧娜.單向Hash函數(shù)SHA-1的統(tǒng)計(jì)分析與算法改進(jìn)[J].計(jì)算機(jī)科學(xué)，2009，10（15）：141-145.

[7] Christophe De Canni`ere，F(xiàn)lorian Mendel，Christian Rechberger.Collisions for 70-Step SHA-1：On the Full Cost of Collision Search，SelectedAreas in Cryptography（Carlisle M.Adams，

Ali Miri，and Michael J.Wiener，eds.），Lecture Notes in Computer

Science，Springer，2007，4876：56-73.

[8] Stevens M.New collision attacks on SHA-1 based on optimaljoint local-collision analysis.In EUROCRYPT，2013.

作者簡(jiǎn)介：

劉 坤（1979-），女，碩士，講師.研究領(lǐng)域：計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)，網(wǎng)絡(luò)安全技術(shù).

楊正校（1963-），男，碩士，教授.研究領(lǐng)域：軟件技術(shù).