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

程璐

摘 要：Hash函數(shù)是將任意長度的消息變換成為固定長度的摘要，在實(shí)現(xiàn)數(shù)據(jù)的消息認(rèn)證、完整性檢驗(yàn)、數(shù)字簽名等領(lǐng)域有著十分重要的應(yīng)用。本文對(duì)美國標(biāo)準(zhǔn)技術(shù)研究所（NIST）征集哈希函數(shù)的SHA-3計(jì)劃進(jìn)行了全面介紹，分析了SHA-3計(jì)劃中最終5個(gè)候選算法的設(shè)計(jì)思想與策略，并對(duì)5個(gè)算法的安全性分析結(jié)果與SHA-2算法進(jìn)行了簡(jiǎn)要比較。

關(guān)鍵詞：Hash函數(shù)；SHA-3；迭代結(jié)構(gòu)

1 引言

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

2 Hash函數(shù)的概念與SHA-3計(jì)劃

一個(gè)Hash函數(shù)：將任意長的消息映射到固定長的比特串。為簡(jiǎn)便敘述，做如下定義：k比特長消息塊；表示消息與級(jí)聯(lián)，表示消息的比特長度；消息表示填充的消息（），壓縮函數(shù)：將定長消息塊壓縮到定長hash值。

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

基于王小云及其團(tuán)隊(duì)對(duì)MD5和SHA系列函數(shù)的分析結(jié)果，美國NIST從2008年起開始在全世界范圍內(nèi)征集新的Hash函數(shù)標(biāo)準(zhǔn)，這個(gè)計(jì)劃被稱為SHA-3計(jì)劃[4]，在新標(biāo)準(zhǔn)確立之前，由SHA-2作為代替算法。

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

算法容易實(shí)現(xiàn)，占用資源少；

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

算法必須接受來自于密碼學(xué)界的分析，在分析過程中發(fā)現(xiàn)的任何缺陷要調(diào)整或者重新設(shè)計(jì)。

算法不能使用Merkle-Damgard結(jié)構(gòu)。

2008 年10 月有64 個(gè)算法正式向SHA-3提交了方案。經(jīng)過初步評(píng)價(jià)，共有51個(gè)算法進(jìn)入第一輪評(píng)估，算法通過對(duì)安全、消耗、和算法實(shí)現(xiàn)特點(diǎn)，特別是對(duì)算法的分析，2009年7月，只有14個(gè)算法進(jìn)入了第二輪評(píng)估，2010年11月，NIST公布了進(jìn)入第三輪的5個(gè)算法：JH算法[5]、Grstl算法[6]、Blake算法[7]、Keccak算法[8]和Skein算法[9]。經(jīng)過密碼學(xué)界的分析和測(cè)試，2012年10月，美國NIST選擇了Keccak算法作為SHA-3的標(biāo)準(zhǔn)算法。

3 SHA-3計(jì)劃候選算法的設(shè)計(jì)策略分析

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

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

對(duì)Hash函數(shù)的安全性分析主要包含兩個(gè)方面：一是抗碰撞攻擊的能力評(píng)估，二是抗原像攻擊的能力評(píng)估。

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

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

由于新的Hash函數(shù)的設(shè)計(jì)采用了新的設(shè)計(jì)理念，擴(kuò)散層的擴(kuò)散能力明顯增強(qiáng)，因此“比特追蹤法”很難對(duì)SHA-3候選算法形成威脅。

對(duì)SHA-3計(jì)劃進(jìn)入第三輪的5個(gè)算法的攻擊結(jié)果見下表所示。

4 總結(jié)

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

參考文獻(xiàn)

[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