SHA—3計劃候選算法的安全策略剖析

程璐

摘 要：Hash函數是將任意長度的消息變換成為固定長度的摘要，在實現數據的消息認證、完整性檢驗、數字簽名等領域有著十分重要的應用。本文對美國標準技術研究所（NIST）征集哈希函數的SHA-3計劃進行了全面介紹，分析了SHA-3計劃中最終5個候選算法的設計思想與策略，并對5個算法的安全性分析結果與SHA-2算法進行了簡要比較。

關鍵詞：Hash函數；SHA-3；迭代結構

1 引言

隨著現代社會進入信息時代，戰爭的形式發生了根本性的變化。掌握信息的主動權就是獲取勝利的保證。在軍事領域，信息的爭奪稱為信息戰，在作戰時，戰斗的雙方都企圖通過控制信息和情報的流動來把握戰場的主動權，在情報的支持下，綜合運用軍事欺騙、作戰保密、電子戰和對敵信息系統的實體摧毀，阻斷敵方信息流，并制造虛假信息來影響和削弱敵情報控制能力，同時確保自己的指揮控制系統免遭敵方類似的破壞。由此可知，信息的傳輸、變換、壓縮和存儲等信息處理的有效性、可靠性和安全性已成為當今信息處理中急待解決的重要問題，而各種形式的編碼和密碼則是解決上述問題的基本理論與方法。就保密通信而言，信息在從采集、處理、傳輸到最終應用的整個過程中，面臨著被偷竊、截收、竄收、插入、刪除、中斷等多種安全威脅。信息安全技術是維護信息保密性、完整性和可靠性的重要手段，它包括保護信息免受非法修改、破壞和泄露的所有措施。密碼技術是信息安全技術的核心，而密碼技術中的數字簽名技術可以有效保護信息的完整性和可靠性。在數字簽名中，一個重要工具便是Hash函數。Hash函數被廣泛用于消息的完整性檢測和消息認證。

2 Hash函數的概念與SHA-3計劃

一個Hash函數：將任意長的消息映射到固定長的比特串。為簡便敘述，做如下定義：k比特長消息塊；表示消息與級聯，表示消息的比特長度；消息表示填充的消息（），壓縮函數：將定長消息塊壓縮到定長hash值。

近幾年來，Hash函數的密碼分析已經取得了突破性的進展.在通行的世界Hash函數標準MD5和SHA-1君臨天下很長的時間內，它曾被認為是非常安全的.然而，中國學者王小云找到了破解Hash函數的關鍵技術，成功地破解了MD5、SHA-1和其他幾個Hash函數，震驚了世界[1][2]。這些研究成果一方面使人震驚，另一方面也促進了人們對Hash函數的更深入的研究[3]。

基于王小云及其團隊對MD5和SHA系列函數的分析結果，美國NIST從2008年起開始在全世界范圍內征集新的Hash函數標準，這個計劃被稱為SHA-3計劃[4]，在新標準確立之前，由SHA-2作為代替算法。

SHA-3計劃中，候選算法需要滿足下列四個條件，否則將被淘汰：

算法容易實現，占用資源少；

算法能夠抵抗已知的攻擊，并且支持224bit、256bit、384bit和512bit四種長度的散列。

算法必須接受來自于密碼學界的分析，在分析過程中發現的任何缺陷要調整或者重新設計。

算法不能使用Merkle-Damgard結構。

2008 年10 月有64 個算法正式向SHA-3提交了方案。經過初步評價，共有51個算法進入第一輪評估，算法通過對安全、消耗、和算法實現特點，特別是對算法的分析，2009年7月，只有14個算法進入了第二輪評估，2010年11月，NIST公布了進入第三輪的5個算法：JH算法[5]、Grstl算法[6]、Blake算法[7]、Keccak算法[8]和Skein算法[9]。經過密碼學界的分析和測試，2012年10月，美國NIST選擇了Keccak算法作為SHA-3的標準算法。

3 SHA-3計劃候選算法的設計策略分析

Hash函數的設計通常采用迭代結構，其迭代函數的設計又借鑒了很多分組密碼的思想。JH算法采用了新的壓縮函數結構，其核心壓縮函數就是一個分組密碼，該分組密碼的設計與美國高級加密標準AES類似，通過固定密鑰對消息加密，并將部分消息反饋以達到消息壓縮的目的；Grstl算法壓縮函數通過兩個不同的分組密碼來構造，而這兩個分組密碼又采用了與AES算法相同的S盒，如果假設這兩個分組密碼是理想分組密碼，則可以給出Grstl算法的安全性證明；Blake算法采用了HAIFA迭代結構，只采用了模加、異或和循環移位等邏輯運算；Keccak算法Sponge結構，壓縮函數基于模加、異或和循環移位構造；Skein算法其核心壓縮函數為Threefish，也是只利用模加、異或和循環移位等邏輯運算來實現數據的混淆與擴散。

這些Hash函數的壓縮函數都可以單獨作為分組密碼來使用，而在這些算法中，JH和Grstl采用了“寬軌跡策略”來設計分組密碼；Blake、Keccak和Skein都采用了模加、異或和循環移位來設計分組密碼。實際上，MD5、SHA系列函數的壓縮函數也可以看做是一個分組密碼，但是這些分組密碼沒有明顯的擴散層，因此密碼分析者可以很容易地控制單個比特或少數幾個比特的差分傳播，從而得到碰撞或近似碰撞；與MD5、SHA系列Hash函數不同，JH等SHA3候選算法都采用了明顯的擴散層，使得比特追蹤法很難適用于這類Hash函數的安全性分析。

對Hash函數的安全性分析主要包含兩個方面：一是抗碰撞攻擊的能力評估，二是抗原像攻擊的能力評估。

所謂碰撞攻擊是指找到兩個不同的消息，使得兩個Hash值相同。在實際研究某個Hash函數抗碰撞攻擊時，密碼學者們提出了一些適當變形和推廣，如偽碰撞攻擊、近似碰撞和多碰撞攻擊等。研究碰撞攻擊最有效的方法是差分密碼分析，通過研究算法的差分傳播特性，當輸出差分為0時，碰撞即可產生。早期對Hash函數的碰撞攻擊都屬于經典差分分析的范疇，如Biham等正是利用經典差分分析方法尋找到SHA0的碰撞和近似碰撞的；王小云教授對MD5等Hash函數的攻擊方法稱作“比特追蹤法”，屬于差分攻擊的范疇，通過在輸入明文出引入很少幾個比特的差分，研究這些差分傳播特性，結合“明文修改”技術，可以使得只有很少幾個比特不同的兩組消息具有相同的Hash值。與分組密碼一樣，能夠抵抗經典差分密碼分析并不能保證Hash函數能夠抵抗其他類型的差分密碼分析。

對 MD和SHA系列Hash函數的碰撞攻擊，更多地體現了如何在“消息差分”、“鏈變量差分特征”、“消息塊自由度”和“優化算法”取得一種有效的均衡，使得攻擊變得可行，見下圖。

由于新的Hash函數的設計采用了新的設計理念，擴散層的擴散能力明顯增強，因此“比特追蹤法”很難對SHA-3候選算法形成威脅。

對SHA-3計劃進入第三輪的5個算法的攻擊結果見下表所示。

4 總結

本文對美國NIST征集哈希函數的SHA-3計劃進行了全面介紹，分析了SHA-3計劃中最終5個候選算法的設計思想與策略，并對5個算法的安全性分析結果與SHA-2算法進行了簡要比較。

參考文獻

[1] Wang， X.， Yu， H.： How to break MD5 and other hash functions. EUROCRYPT 2005. LNCS， vol. 3494， pp. 19–35. Springer， Heidelberg （2005）

[2] Wang， X.， Yin， Y.L.， Yu， H.： Finding Collisions in the Full SHA-1. In： Shoup， V.（ed.） CRYPTO 2005. LNCS， vol. 3621， pp. 17–36. Springer， Heidelberg （2005）

[3] Yu Sasaki and Kazumaro Aoki， Finding Preimages in Full MD5 Faster Than Exhaustive Search， A. Joux （Ed.）： EUROCRYPT 2009， LNCS 5479， pp. 134–152， 2009.

[4] National Institute of Standards and Technology. Announcing Request for Candidate Algorithm Nominations for a New Cryptographic Hash Algorithm （SHA–3） Family 72（212） of Federal Register （November 2007）

[5] H. Wu， “The Hash Function JH，” Submission to NIST （Round 3）， 2011， http：//csrc.nist.gov/groups/ST/hash/sha-3/Round3/submissions_rnd3.html

[6] P. Gauravaram， L. R. Knudsen， K. Matusiewicz， F. Mendel， C. Rechberger， M. Schl?ffer， S. Thomsen， “Gr?stl A SHA-3 Candidate，” Submission to NIST （Round 3）， 2011， http：//csrc.nist.gov/groups/ST/hash/sha-3/Round3/submissions_rnd3.html

[7] J.-P. Aumasson， L. Henzen， W. Meier， R. C.-W. Phan， “SHA-3 proposal BLAKE，” Submission to NIST （Round 3）， 2011，

http：//csrc.nist.gov/groups/ST/hash/sha-3/Round3/submissions_rnd3.html

[8] G. Bertoni， J. Daemen， M. Peeters， G. V. Assche， “Keccak Specifications，” Submission to NIST （Round 3）， 2011， http：//csrc.nist.gov/groups/ST/hash/sha-3/Round3/submissions_rnd3.html

[9] N. Ferguson， S. Lucks， B. Schneier， D. Whiting， M. Bellare， T. Kohno， J. Callas， J. Walker， “The Skein Hash Function Family，” Submission to NIST （Round 3）， 2011， http：//csrc.nist.gov/groups/ST/hash/sha-3/Round3/submissions_rnd3.html