基于局部碰撞算法的SHA—1改進算法設計與研究

劉坤+楊正校

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

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

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

2017年2月23日，荷蘭阿姆斯特丹（CWI）研究所和Google公司的研究人員在谷歌安全博客上發(fā)布了世界上第一例公開的SHA-1哈希碰撞實例，在經(jīng)過兩年的聯(lián)合研究和花費了巨大的計算機時間之后，研究人員在他們的研究網(wǎng)站SHAttered上給出了兩個內(nèi)容不同，但是具有相同SHA-1消息摘要的PDF文件，這就意味著在理論研究長期以來警示SHA-1算法存在風險之后，SHA-1算法的實際攻擊案例也浮出水面，同時也標志著SHA-1算法終于走向了生命的末期。從這些事件上可以看出，MD4、MD5和SHA-1已經(jīng)不安全。本文主要根據(jù)近幾年國內(nèi)外對SHA-1算法的碰撞算法進行分析研究，給出算法中壓縮函數(shù)和邏輯函數(shù)的改進描述，以提高SHA-1抗碰撞性。

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

principle of SHA-1 algorithm）

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

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

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

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

SHA-1算法的關鍵是壓縮函數(shù)。在SHA-1的內(nèi)部結構中，鏈接變量A、B、C、D、E經(jīng)過6個操作步的傳遞、混合后，又回到A、B、C、D、E，過程如圖2所示。這樣就容易出現(xiàn)局部碰撞。例如若在SHA-1算法第i步存在1比特消息差分，這1比特差分將在隨后的5操作步中依次影響5個鏈接變量。由于存在這樣的規(guī)律性，若能阻止差分傳播，則可構造一個局部碰撞差分鏈，進而產(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ù)邏輯結構有四輪循環(huán)模塊，每一輪使用一個函數(shù)如f1、f2、f3、f4來表示四輪循環(huán)對應的邏輯函數(shù)，函數(shù)如下式所示[7]：

從中可以知道這四個函數(shù)中f2和f4是相同的，這樣會造成防御風險。

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

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

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

4 基于局部碰撞的SHA-1改進算法研究（Research

on improved SHA-1 algorithm based on local

collision）

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

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

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

4.2 SHA-1壓縮函數(shù)邏輯結構改進研究

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

5 結論（Conclusion）

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

本文根據(jù)SHA-1算法內(nèi)部缺陷找到碰撞原因，對SHA-1算法中邏輯函數(shù)和壓縮函數(shù)進行改進描述，以提高SHA-1算法抗碰撞性。下一步可以將改進算法在硬件電路上進行設計實現(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] 黃諄，白國強，陳弘毅.快速實現(xiàn)SHA-1算法的硬件結構[J].清華大學學報（自然科學版），2005，45（1）：123-125.

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

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

[6] 劉建東，余有明，江慧娜.單向Hash函數(shù)SHA-1的統(tǒng)計分析與算法改進[J].計算機科學，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.

作者簡介：

劉 坤（1979-），女，碩士，講師.研究領域：計算機網(wǎng)絡技術，網(wǎng)絡安全技術.

楊正校（1963-），男，碩士，教授.研究領域：軟件技術.