密碼雜湊算法綜述

王小云于紅波

1(清華大學高等研究院 北京 100084)2(密碼技術與信息安全教育部重點實驗室(山東大學) 濟南 250100)3 (清華大學計算機系 北京 100084)

?

密碼雜湊算法綜述

王小云1,2于紅波3

1(清華大學高等研究院 北京 100084)2(密碼技術與信息安全教育部重點實驗室(山東大學) 濟南 250100)3(清華大學計算機系 北京 100084)

(xiaoyunwang@mail.tsinghua.edu.cn)

密碼雜湊算法是現代密碼學中的基本工具，它能夠將任意長度的消息壓縮成固定長度的摘要.雜湊值又稱為雜湊碼、消息摘要或數字指紋.通常密碼雜湊算法被非正式地稱為雜湊算法.雜湊算法的重要性就是能夠賦予每個消息唯一的“數字指紋”，即使更改該消息的一個字母，對應的雜湊值也會變為截然不同的“指紋”.雜湊算法在現代密碼學中有著極其重要的作用，它最常用的用途是用在數字簽名和數據完整性保護中.雜湊算法是數字簽名的核心技術，通常用公鑰密碼算法如RSA進行數字簽名時，一般不是對消息直接簽名，而是對消息的雜湊值進行簽名，這樣既可以減少計算量，提高效率，也可以破壞數字簽名算法的某些代數結構，保障其安全性.雜湊算法還是許多密碼算法密碼系統安全的基本前提條件，它可以用來設計消息認證碼以及眾多可證明安全協議，還廣泛應用于口令保護協議、電子支付協議、廣播認證協議等密碼協議中.因此對雜湊算法進行研究在密碼學領域具有重要的意義.

密碼雜湊算法；碰撞攻擊；原像攻擊；MD5算法；SHA-1算法；SHA-3算法

密碼雜湊算法在現代密碼學中起著重要作用，它可以將任意長度的消息壓縮成固定長度的摘要.給定1個消息計算其雜湊值是容易的，但是找到具有相同雜湊值的2個不同消息則是困難的，許多密碼體制的安全性正是基于這一屬性.

最早的雜湊算法不用于密碼學，而源于1953年IBM的歷史性討論，其思想就是把消息的關鍵詞打亂，并且使用這部分信息作為查找的索引，通過構造雜湊表進行存儲和查找，Knuth[1]對這類雜湊算法進行了綜合描述.1979年，Merkle[2]第1次給出了單向雜湊算法的實質性定義，包含抗原像和第二原像的安全屬性，以提供安全可靠的認證服務.1980年，Davies和Price[3]將雜湊算法用于電子簽名，用于抵抗RSA等數字簽名中的存在性偽造攻擊，標志著密碼雜湊算法的開始.1987年，Damg?rd[4]首次給出抗碰撞的雜湊算法的正式定義，指出了抗碰撞性和抗第二原像性，并用于設計安全的電子簽名方案.由于雜湊算法的高效性和無代數結構特性，常被用作偽隨機數生成器，成為帶隨機諭示的可證明安全密碼體制的一項核心技術.

除了數據壓縮、易于計算這2個基本屬性之外，雜湊算法還應該滿足下面3個安全屬性：

1) 單向性(抗原像攻擊).給定輸出值y，計算輸入值x，使y=H(x)是困難的，其理想的計算復雜度是搜索攻擊的復雜度.

2) 抗第二原像攻擊(弱抗碰撞性).給定輸入值x，計算另一個輸入值x′，使H(x)=H(x′)是困難的，理想的計算復雜度是搜索攻擊的復雜度.

3) 抗碰撞攻擊(強抗碰撞性).尋找x≠x′，使H(x)=H(x′)是困難的.理想的復雜度為生日攻擊的復雜度.

隨著雜湊算法分析技術的進步，自2004年以來出現了一些新的理論分析結果，如長消息的第二原像攻擊[5]和集群攻擊[6]等.這些分析技術也可以用于其他密碼體制的分析，尤其在消息認證碼的理論分析方面，可以進行區分攻擊、偽造攻擊等.為了避開雜湊算法和基于雜湊算法的消息認證碼的上述攻擊，美國國家標準技術研究所(NIST)在全球范圍內征集新的雜湊算法安全屬性，經過一年的研究，補充了抗長度擴展攻擊的安全屬性：

4) 抗長度擴展攻擊.給定H(IV,M)，對于任意的消息M′，當僅知道M的長度時，直接利用H(IV,M)計算H′=H(IV,M‖padM‖M′)是困難的.

雜湊算法是密碼學的3類基礎算法之一(加密算法、數字簽名算法和雜湊算法)，主要用于數據的完整性校驗、基于口令的身份認證、提高數字簽名的有效性和安全性、密鑰推導、構造基于密碼雜湊算法的消息認證碼和構造確定性隨機比特生成器等，對雜湊算法進行研究對理論和實際是有重要意義的.

1 雜湊算法設計技術

雜湊算法在密碼學中具有重要的地位，如何設計出快速安全的雜湊算法一直是密碼學重要的研究問題.直接設計一個算法能夠將任意長度的消息壓縮成固定長度的雜湊值并不是一件容易的事情.已有的雜湊算法都是基于壓縮函數(或置換函數)的迭代結構設計的.每個壓縮函數的輸入為一固定長度的消息分組，而且每個消息分組采用相似的操作.

基于迭代壓縮函數的雜湊算法設計整體結構如下：

1) 對消息進行填充，使得成為消息分組長度的整數倍；填充方法有多種，可以參照文獻[7-8]；

2) 對填充后的消息按消息分組長度進行分組；

3) 使用壓縮函數對每個消息分組依次進行迭代壓縮；

4) 對最后一個消息分組的輸出進行變換得到雜湊算法的輸出.

雜湊算法的設計包括迭代結構的設計以及壓縮函數的設計.

1.1 雜湊算法的迭代結構設計

在CRYPTO 1989上，Merkle[9]和Damg?rd[10]獨立給出了構造雜湊算法的迭代結構，后被稱為MD結構(Merkle-Damg?rd structure).MD結構基于壓縮函數的迭代，任何抗碰撞性的壓縮函數在MD結構下都能拓展為抗碰撞的雜湊算法，將如何構造抗碰撞雜湊算法的問題轉化成如何構造抗碰撞壓縮函數的問題.MD結構是使用最廣泛的雜湊算法構造方法.在CRYPTO 1990上，Rivest[11]設計了第1個基于MD結構的專用的雜湊算法MD4算法.此后又出現了基于MD結構的MD5[12]、HAVAL[13]、SHA-1[7]、SHA-2系列[8]、RIPEMD系列[14]以及我國商用雜湊標準SM3[15]等.MD結構雜湊算法如圖1所示：

圖1 MD結構雜湊算法圖

隨著雜湊算法分析方法的不斷成熟，MD結構算法暴露出了一些典型的問題，比如長度擴展攻擊、二次碰撞攻擊、多碰撞攻擊[16]和長消息第二原像攻擊等.為了克服MD結構帶來的問題，一些改進的MD結構隨之出現.比如，Liskov[17]在SAC 2006上提出了Zipper結構等.但這些改進通常比較復雜，實現效率低.同時，為了抵抗生日攻擊和多碰撞攻擊，Lucks[18]在ASIACRYPT 2005上提出了寬管道和雙管道的結構.該結構要求將壓縮函數的初始值加倍，來防止生日攻擊、多碰撞攻擊，但這可能導致壓縮函數擴散變慢.RIPEMD系列算法即為典型的雙管道算法，這些算法并聯使用2個尺寸相同的窄管道雜湊算法，對每個消息分組并行壓縮2次，對最終的壓縮結果再進行壓縮得到雜湊值.在EUROCRYPT 2015上，Leurent和Wang[19]證明了通過這種方法構造的雜湊算法抵抗原像攻擊的能力有所減弱.

寬管道和雙管道結構雜湊算法如圖2、圖3所示：

圖2 寬管道結構雜湊算法圖

圖3 雙管道結構雜湊算法圖

圖4 HAIFA結構雜湊算法圖

針對MD結構雜湊算法易受第二原像攻擊的弱點，Biham和Dunkelman[20]在2006年的雜湊算法研討會上提出了HAIFA結構，在壓縮函數的輸入中增加隨機鹽值(salt)和已雜湊比特(bh).SHA-3征集活動第3輪(最終輪)的候選算法之一的BLAKE[21]算法即是典型的HAIFA結構雜湊算法.HAIFA結構雜湊算法如圖4所示.

在ECRYPT 2007上，由Bertoni等人[22]提出了基于大狀態置換的海綿體結構(sponge structure)的雜湊算法，海綿體結構雜湊算法通常包含吸收(sbosbing)和壓縮(squeezing)2個過程，如圖5所示.

圖5 海綿體結構雜湊算法圖

目前，海綿體結構已經成為繼MD結構后被使用最廣泛的結構，如SHA-3標準KECCAK[23]使用海綿體結構，輕量級雜湊算法PHOTON[24]，QUARK[25]，SPONGENT[26]等都使用海綿體結構設計.

1.2 雜湊算法壓縮函數的設計

1.2.1 基于分組密碼的雜湊算法的設計

雜湊算法有2種基本的構造方法：基于分組密碼的構造方法和直接構造法(定制雜湊算法).最早的雜湊算法設計方式是基于成熟的分組密碼.最簡單的轉換方法是利用密碼分組鏈接(CBC)或密碼反饋(CFB)模式，將密鑰替換為初始值，對消息的分組逐次加密，最后的密文即是雜湊值.這種雜湊算法都是基于成熟的分組密碼，其安全性分析側重于結構的分析.

當雜湊值長度等于分組密碼的分組大小時，通常對雜湊算法的每個輸入分組Mi進行一次迭代加密，最后的密文就是雜湊值.這類迭代結構概括如下：H0=IH，IH是一個隨機的初始值.Hi=EA(B)⊕C，其中A,B,C∈{Mi,Hi,Mi⊕Hi,c}，c是一個常量.Preneel等人[27]對總共的64種情況給出了詳細的分析，其中12種結構是安全的，能夠抵抗直接攻擊(direct attack)、置換攻擊(permutation attack)、前向攻擊(forward attack)和后向攻擊(backward attack)這4種攻擊，僅有4種結構能夠抵抗除這4種攻擊以外的固定點攻擊(fixed point attack).最常用的幾種基于分組密碼的結構包括DM(Davies-Meyer)結構、MMO(Matyas-Meyer-Oseas)結構和Miyaguchi-Preneel結構等.如雜湊算法MDC-2、MDC-4、舊的俄羅斯標準GOST R34.11-94等都是基于分組密碼算法的DM結構；SHA-3候選算法Skein是基于分組密碼算法的MMO結構.

1.2.2 定制雜湊算法的設計

1990年，美國密碼學家Rivest[11]針對32位計算機系統，設計了雜湊算法MD4.該算法不基于分組密碼等任何的密碼學本原，稱為定制雜湊算法(dedicated hash function)，MD4具有高速的軟件實現效率.Rivest[12]又設計了MD4的加強算法MD5，2個算法的雜湊值長度均為128 b.HAVAL是1992年由Zheng(鄭玉良)等人[13]設計，主要利用高度非線性的輪函數代替MD4和MD5普遍采用的簡單的輪函數.基于MD4的設計技術，NIST[7]設計了安全雜湊算法SHA系列，包括SHA-0，SHA-1，其雜湊值的長度都是160 b.SHA系列算法繼承了MD4的設計特色，進一步使用了消息擴展算法來加強算法的安全性.2002年NIST又推出SHA-2系列雜湊算法[8]，其輸出長度可取224 b，256 b，384 b，512 b，分別對應SHA-224，SHA-256，SHA-384，SHA-512.SHA-2系列雜湊算法比之前的雜湊算法具有更強的安全強度和更靈活的輸出摘要長度.與此同時，著名的歐洲密碼工程RIPE(RACE integrity primitives evaluation)設計了RIPEMD[28]，該算法基于2條并行的MD4結構.隨后，Dobbertin等人[14]又設計了其強化變種版本RIPEMD-128和RIPEMD-160.這些雜湊算法都是在MD4設計思想的基礎上，介入了新的設計理念，以提高算法的安全性，統稱為MDx系列雜湊算法.

1.2.3 雜湊算法標準

現代密碼學的發展離不開各類國際密碼組織的推動.在這些密碼組織的推動下，雜湊算法的設計和分析得到了長足的發展.

RIPE工程是由歐洲1988年發起的，通過公開征集的方式開發一些基本的密碼算法，對歐盟寬帶通信信息進行完整性保護并提供認證服務.主要征集身份識別算法、雜湊算法、消息認證算法和數字簽名算法，由RIPE進行評估.第1次征集共有31個提交方案，經過2個階段的評估，最終有7個方案獲選.在此基礎上啟動了第2次征集，并于1992年結束，確定了雜湊算法RIPEMD.

NESSIE(new european schemes for signature, integrity, and encryption)工程是歐盟信息社會技術(IST)發展規劃所支持的項目之一，開始于2000年1月，歷時3年，2002年12月結束.該工程面向國際征集數字簽名、雜湊算法和分組密碼等各類密碼算法.與RIPE工程一樣，NESSIE工程的征集和篩選過程都是公開透明的，最終獲選的雜湊算法是Whirlpool和SHA-2系列.

NIST[7]于1993年推出了SHA-0和SHA-1算法.SHA-1于1995年被確定為NIST標準.2002年，NIST[8]推出了強度更高、輸出雜湊值長度224 b,256 b，384 b，512 b這4種長度可選的SHA-2系列算法.2004年至2005年我國密碼學家王小云等人破解了國際通用系列雜湊算法，包括MD5[29]，SHA-1[30]，RIPEMD[31]，HAVAL[31]等，引起國際密碼社會的強烈反響.為了應對MD5與SHA-1的破解，NIST于2007年至2012年開展了公開征集新一代雜湊算法標準SHA-3[32].SHA-3競賽征集到了64個算法，這些候選算法各具特色，體現了很多新的設計理念.進入SHA-3最終輪的5個候選算法都采用了不同于MD結構的新型結構，KECCAK采用了海綿體結構，BLAKE采用HAIFA結構，Skein采用基于密文的唯一分組迭代(unique block iteration)鏈接模式，Gr?stl和JH基于寬管道的MD改進結構.在內部變換中，KECCAK采用基于3維數組的比特級邏輯運算；BLAKE和Skein基于ARX運算；Gr?stl采用AES類的設計；JH使用了擴展的多維AES結構.經過5年的遴選，KECCAK憑借其優美的設計、足量的安全冗余、出色的整體表現、高效的硬件效率和適當的靈活性最終勝出，成為SHA-3標準.

在雜湊函數的設計方面，2010年12月國家密碼管理局公布了由王小云等人設計的我國商用密碼雜湊算法SM3[15]，該算法結構簡潔、軟硬件實現效率高、安全強度高，其總體性能優于國際上廣泛使用的雜湊函數標準SHA-256.目前SM3算法作為我國雜湊算法密碼行業標準和國家標準已經被廣泛推廣使用.

1.2.4 輕量級雜湊算法的設計

近年來輕量級雜湊算法的設計已經成為雜湊算法設計以及密碼學領域研究的熱點.2008年，Shamir[33]設計了第1個能應用于RFID協議的輕量級MAC算法SQUASH，該算法只要求抵抗64b的原像攻擊，而不需要抵抗碰撞攻擊.同年Bogdanov等人[34]利用分組密碼Present和雙塊模式構造了H-PRESENT-128算法.2010年，Aumasson等人[25]基于流密碼的設計理念設計了QUARK算法；Guo等人[24]利用AES類操作與廣義海綿結構設計了PHOTON算法；Bogdanov等人[26]基于分組密碼Present和海綿結構設計了SPONGENT算法.2014年我國學者Wu(吳文玲)等人[35]設計了輕量級雜湊算法LHash.這些輕量級雜湊算法都采用了海綿體結構，安全冗余度很高.

2 雜湊算法分析技術

一個安全的雜湊算法需要滿足3個性質：抗原像性、抗第二原象性和抗碰撞性.而近幾年人們在評估雜湊算法安全性時，不僅考慮這3個經典的安全要求，同時還會考慮其在近似碰撞、差分區分器、反彈攻擊及飛去來器(boomerang)區分器等攻擊方面的抵抗性能，并認為若給定雜湊算法表現不同于期望的隨機函數，則就被視為該雜湊函數的一個安全弱點.

對雜湊算法的攻擊分為通用的雜湊算法攻擊方法(該攻擊方法不依賴于具體的雜湊算法)，以及針對一類或者是某個具體雜湊算法的攻擊方法.

2.1 雜湊算法通用攻擊方法

雜湊算法的用途之一就是口令認證，它是基于雜湊算法抗第二原像攻擊的屬性.破解口令最有效的辦法就是遍歷搜索.但由于其解空間太大，要么需要時間太長，要么空間要求過高.在這種情況下時間-存儲折中攻擊(TMTO)[33]被提出并廣泛用于在可接受時間內破解密碼.時間-存儲折中攻擊(TMTO)是1980年由Hellman[36]提出的，該方法分為預計算過程和在線密鑰檢索2個階段.在預計算階段，通過迭代系列起始點建立密鑰的鏈表，構建TMTO表來存儲鏈表的頭結點和尾結點，供在線檢索使用，如圖6所示.在線密鑰檢索階段是對給定的口令的雜湊值，通過檢索TMTO表來尋找對應的密鑰.TMTO方法通過預計算來達到在查找過程時間和存儲的折中.這種時間-存儲折中的方法是一種概率模型，無法確保100%成功率，成功率的大小將取決于分配的時間和內存的大小.為了降低同一表中出現雜湊值的合并和碰撞的概率，通常TMTO方法采用多個小的表進行存儲和搜索，每張小表采用不同的約減函數.

圖6 TMTO表建立過程

為了避免同一個表中可能存在合并和碰撞，且這些合并和碰撞仍然是檢索表時額外計算開銷的主要原因.2003年，Oechslin[37]提出的彩虹表法成功解決了這一問題，提升了時間-存儲折中攻擊的效率.在彩虹表法中，針對同1條密鑰鏈，彩虹表使用1組約減函數而非1個約減函數，當2條鏈發生碰撞時，它們只有在碰撞發生在2條鏈的同一個位置時才會合并.如果碰撞并不在同一個位置發生，那么2條鏈的下一次生成將會使用不同的約減函數，因此它們不會合并.

LM-Hash(LAN manager hash)[38]是微軟用于保存網絡操作系統以及Windows操作系統口令而設計的雜湊算法.這個函數基于DES算法[39]，但設計上存在一定的缺陷，微軟在Windows Vista及之后的版本不再使用該雜湊算法作為默認的口令存儲函數，然而該算法在研究時間-存儲折中攻擊時仍然具有典型的意義.NTLM-Hash[40](簡稱NT-Hash)主要應用于Windows的網絡環境中，它基于雜湊算法MD4，該雜湊算法最早在Windows NT 4.0 SP4中被廣泛使用，隨后又被應用于Windows 2000中，雖然已經被Kerberos[41]取代不再作為默認的認證協議，但仍然在很多沒有采用Kerberos協議的服務器和客戶端通信中被使用.應用時間-存儲折中攻擊，可以有效地攻擊基于分組密碼DES實現的LM-Hash和基于雜湊算法MD4實現的NT-Hash.

時間-存儲折中攻擊的實施并不依賴于具體的雜湊算法，因此基于彩虹表的時間-存儲折中攻擊改進算法對當前通用的雜湊算法如MD5，SHA-1，SHA-2等均適用，是一種通用的雜湊算法的攻擊方法.

為避免彩虹表攻擊，密碼系統應該對雜湊值采用加鹽值機制，即在密碼之后追加隨機數使密碼的雜湊值無法被反查.鹽值需要額外存儲，并且最好是根據每個密碼隨機生成不同的鹽值.

2.2 針對具體算法的攻擊

2.2.1 雜湊算法的碰撞攻擊

由于碰撞攻擊能夠深入到壓縮函數的內部，很多縮減輪的分析具有實際的攻擊復雜度，能夠更好地反映雜湊算法的安全強度.

最早對雜湊算法MD4和MD5進行分析的有den Boer，Bosselaers[42-43]，Vaudenay[44].隨后Dobbertin[45]提出了一種新的分析方法，并于1996年成功破解了MD4；1998年，證明了MD4前2輪不是單向的(共3輪)[46]；在MD5攻擊方面，1996年給出了自由初始值下的MD5的碰撞實例[47]，也就是說在初始值可以自由選擇的情況下，能夠找到2個不同的消息具有相同的雜湊值.1998年，Chabaud和Joux[48]給出了SHA-0全算法的理論分析結果.

在2004年美密會上，我國密碼學家Wang(王小云)等人[31]首次公布了MD4，MD5，HAVAL-128，RIPEMD的碰撞實例.他們提出的模差分分析方法又稱比特追蹤法，建立了現有雜湊算法碰撞攻擊的理論與技術，破解了包括MD5和SHA-1在內的系列國際通用雜湊算法，動搖了雜湊算法及相關密碼應用的理論根基，引發了雜湊算法研究的熱潮，有力推動了雜湊算法分析與設計技術的進一步發展.

模差分是一種精確差分，它不同于一般差分攻擊里面使用的異或差分，它能夠準確地表達整數模減差分和異或差分這2種信息.利用模差分方法對雜湊算法進行分析有4個步驟：第1步是選擇合適的消息差分，它決定了攻擊成功的概率；第2步是針對選擇的消息差分尋找可行的差分路線，這是模差分分析關鍵一步，也是最難的一步，它需要聰明的分析、熟練的技術、持久的耐心；第3步是推導出保證差分路線可行的充分條件，在尋找差分路線的過程中，鏈接變量的條件被確定下來，一個可行的差分路線就意味著從路線上推導出來的所有鏈接變量的條件相互之間沒有沖突；最后1步就是使用消息修改技術，使得被修改的消息滿足盡可能多的充分條件.

使用模差分方法，通過提煉MD4和RIPEMD的輪函數的特征建立統一的數學分析模型，Wang(王小云)等人[49]在2005年首次給出了RIPEMD的實際攻擊以及改進的MD4的實際攻擊.同年，Wang(王小云)等人[50]又提出了首個針對雜湊算法MD4的新的第二原像攻擊方法，該方法直接導致國際密碼領域開展基于MD4，HAVAL，SHA-0的消息認證碼的分析.

由于MD5具有強雪崩效應，Wang(王小云)等人[29]使用更復雜的比特進位控制和高級的消息修改技術來控制雪崩，找到MD5的1個明文分組的高概率的幾乎碰撞.進一步，結合MD迭代結構的特點，提出利用多個明文分組構造碰撞的理論，從而給出了MD5的實際的碰撞攻擊.而國際密碼學家Biham等人[51]在同一時間獨立提出多明文分組碰撞理論，提高了SHA-0的攻擊效率.基于Wang(王小云)等人[29]對MD5的碰撞攻擊方法，Stevens[52]于2007年給出了對MD5算法在選擇前綴下的實際碰撞攻擊結果.2009年，Stevens等人[53]又將選擇前綴的MD5碰撞攻擊結果用于偽造X.509數字證書，該偽造的中間結點證書能夠通過合法服務器的認證，這對實際應用安全造成了直接的威脅.2012年5月，被俄羅斯專家發現的火焰病毒就是基于Wang(王小云)等人[29]的MD5的碰撞差分路線偽造的數字證書.該病毒能夠通過鍵盤輸入、記錄音頻對話和獲取截屏畫面等收集數據，數據收集完畢后自行銷毀，不會留下任何痕跡.

1997年，Wang(王小云)等人[54]通過建立SHA-0的代數分析模型，首次破解了SHA-0.但2005年Wang(王小云)等人[30]分析SHA-1時發現，已有的對MD5和SHA-0的碰撞攻擊方法還不足以用來破解SHA-1，主要是由于SHA-1的所有可能的碰撞路線中均存在不可能差分現象.Wang(王小云)等人[30]通過先擴散雪崩然后再控制雪崩的技術，將不可能差分轉化成了可能差分，從而首次給出SHA-1全算法的理論碰撞攻擊結果，復雜度為269次運算.后來，Wang(王小云)等人[55]又找到了一條新的差分路線，將碰撞攻擊的復雜度提高到263次運算.該結果被很多密碼學進一步改進，其中Stevens等人[56]給出的碰撞攻擊結果復雜度為261次運算.但到目前為止，沒有SHA-1的實際碰撞攻擊出現.對縮減輪SHA-1的實際碰撞攻擊結果中最好的是76輪(共80輪)的SHA-1的偽碰撞攻擊結果[57].

模差分方法已經成為雜湊算法分析的最重要、最通用的方法，該方法也成為針對基于MD系列雜湊算法的消息認證碼攻擊的主流方法[58].近幾年，模差分方法還成功用于對分組密碼和流密碼算法的安全性分析[59-60].Wang(王小云)等人[29-30]對雜湊算法MD5和SHA-1的破解導致NIST專門舉辦2次研討會并宣布系列政策應對雜湊算法破解的威脅，啟動了新一代雜湊算法SHA-3標準的設計工程.

SHA-2是目前廣泛使用的雜湊算法標準，近5年對縮減輪SHA-2的碰撞類攻擊取得了重要研究進展，文獻[61-62]結合比特追蹤法與自動化搜索技術，給出了SHA-256512縮減到38輪的偽碰撞理論分析.在對SHA-3的公開分析中，Dinur等人[63]給出了可實現復雜度的KECCAK-224和KECCAK-256的4輪碰撞攻擊和5輪的近似碰撞攻擊.Duc等人[64]給出了KECCAK的反彈攻擊結果.但是SHA-3共有24輪，這些分析結果均不能對SHA-3算法構成威脅.在區分器方面，Duan等人[65]給出了SHA-3置換函數的24輪的零和區分攻擊，復雜度為21579.

2.2.2 雜湊算法原像攻擊

是否抗原像攻擊是評估密碼雜湊算法安全性的3個主要屬性之一.在SAC 2008上，Aoki和Sasaki[66]首次將中間相遇攻擊[67]應用到密碼雜湊算法的原像攻擊中，給出了單個消息分組的完整MD4算法和63輪MD5算法的原像攻擊，同時改進了窮舉搜索完整MD5算法原像的復雜度.提出了分段-鏈接技術(splice-and-cut technique)，將反饋運算看成特殊的輪操作，這樣壓縮函數在結構上形成一個環，從環的任何位置斷開都是相似的，從而構造出壓縮函數的偽原像攻擊，再結合偽原像轉化為原像的方法[68]，將單個消息分組的偽原像攻擊轉化成多個消息分組的原像攻擊.

此后，中間相遇攻擊成為雜湊算法原像攻擊最重要的方法，同時也出現了很多技術對其進行改進，比如初始化結構體技術(initial structure technique)[69]、完全二分結構體技術(biclique technique)[70]、局部碰撞技術(local-collision approach)[71]、部分固定技術(partial-fixing technique)[66]、間接匹配技術(indirect-partial-matching technique)[72]和概率匹配技術等.帶完全二分結構體的中間相遇攻擊如圖7所示，其中IWⅠ，IWⅡ表示獨立消息字(initial words).

圖7 帶完全二分結構體的中間相遇攻擊圖示

基于中間相遇攻擊的原像攻擊在結構上可分為起始部分、相互獨立部分和匹配部分.為了增加原像攻擊的輪數，可以從增加這3部分的輪數入手.

為了增加起始部分的輪數，主要采用初始化結構體技術和完全二分結構體技術，完全二分結構體技術是初始化結構體技術的推廣.首先在壓縮函數中尋找一個預計算部分，預計算部分被稱為初始化結構體或者完全二分結構體.初始化結構體技術和完全二分結構體技術使本身相互交錯的獨立消息字在預計算部分2端交換位置,以滿足基本中間相遇攻擊的獨立性要求(如圖7所示).

為了增加匹配部分的輪數，主要采用部分固定技術、間接匹配技術和概率匹配技術.這些技術依賴于對獨立消息字中自由比特位置的選取和匹配部分壓縮函數的性質.部分固定技術在選取獨立消息字自由比特位置時結合匹配起始位置的壓縮函數特性，使不確定的比特在匹配起始位置具有某些特性，從而使2個方向可計算的比特位置能匹配.間接匹配技術則是通過壓縮函數的性質等，將直接的匹配轉化成另外一種等價形式的匹配.概率匹配技術則是使匹配以小于1的概率成立，這樣一方面可以增加攻擊的輪數，另一方面會增加攻擊的復雜度.

在CRYPTO 2012上，Knellwolf和Khovratovich[73]從差分的角度看待中間相遇攻擊，提出了差分中間相遇攻擊，將SHA-1的原像攻擊由48輪提高到60輪(偽原像攻擊).差分中間相遇攻擊將對鏈接變量的匹配轉化成對差分的匹配，能與已有的技術相融合，對消息線性拓展和輪函數較弱的雜湊算法具有良好的攻擊效果.

在CRYPTO 2015上，Espitau等人[74]將差分中間相遇攻擊推廣到高階差分中間相遇攻擊，將SHA-1的原像攻擊提高到64輪(偽原像攻擊).高階差分中間相遇攻擊將差分中間相遇攻擊中差分的匹配形式進行擴充，以達到高階的形式，從而增加了原像攻擊的輪數.高階差分中間相遇攻擊的消息劃分更多，攻擊中需要搜索一些劃分的組合，相同自由度的情況下較差分中間相遇攻擊需要的鏈接變量的列表數多，空間占用大，但攻擊復雜度相同.例如，在與差分中間相遇攻擊的自由度相同時，二階差分中間相遇攻擊需要在2個獨立部分分別創建3個列表，并且需要窮搜6個列表中的4個，差分的匹配條件也更復雜.

2.2.3 其他新型的攻擊

自2009年以來，出現了多種針對雜湊算法攻擊的方法.如對SHA-3候選算法的分析和評估過程中，有很多創新性的分析技術出現，其中包括反彈攻擊(rebound attack)[75]、循環移位攻擊(rotational attack)[76]、零和區分攻擊(zero-sum attack)[77]、飛去來器區分攻擊[78]等.反彈攻擊由Mendel等人[75]在FSE 2009上提出，對基于AES類的雜湊算法如Whirlpool，Gr?stl，ECHO，JH等攻擊非常有效；循環移位攻擊則用來對部分基于ARX類雜湊算法進行區分攻擊，如縮減輪的Skein和SIMD等，這種攻擊方法與算法中使用的常數有關；零和區分攻擊由Aumasson等人[77]提出，主要用來分析Luffa和KECCAK等代數次數比較低的雜湊算法.

在所有新的分析方法中，反彈攻擊是最具有代表性的分析方法.反彈攻擊被提出的目的是為了高效地尋找雜湊算法的碰撞.對基于分組密碼或置換的雜湊算法的安全性影響較大，特別是AES類算法，比如ISOIEC標準算法中的Whirlpool和SHA-3候選算法Gr?stl等.反彈攻擊通常從被分析算法的中間狀態差分開始向前和向后拓展，該攻擊又被稱為中間起始(start from middle)攻擊.

在亞密2009上，Lamberger等人[79]利用Whirpool在密鑰上的信息量冗余對反彈攻擊進行了改進，提出了9.5輪Whirpool的幾乎碰撞和距今為止唯一的全輪Whirpool壓縮函數的區分器攻擊.在FSE 2010上，Gilbert等人[80]針對AES類置換提出大S盒技術(super-sbox)，推動了反彈攻擊技術的發展.隨后，反彈攻擊技術又被用于其他結構的雜湊算法中，比如MD結構的Skein[76]和海綿體結構的KECCAK[81]等.

同時，反彈攻擊技術和其他分析技術相結合，推動了分組密碼分析技術的發展.比如，Bouillaguet等人[82]利用反彈攻擊技術改進了Dunkelman等人[83]提出的AES的中間相遇區分器，給出了AES-128，AES-192，AES-256的新結果.隨后，Li(李雷波)等人[84]又改進了AES-192和AES-256的分析結果.目前，結合反彈攻擊技術和中間相遇攻擊是AES在單密鑰模式下的最有效的攻擊技術.

3 結束語

自20世紀90年代，Rivest[11-12]設計了雜湊算法MD4，MD5以來，雜湊算法的分析與設計一直是密碼領域關注的熱點.2004年Wang(王小云)等人[29-30]破解MD5和SHA-1，引發了雜湊算法研究的熱潮，雜湊算法的分析和設計技術近10年來取得了突破性的進展.在雜湊算法分析方面，Wang(王小云)等人[29-30]提出的模差分分析方法是分析MDx系列雜湊算法碰撞攻擊的通用方法.基于對模差分方法的廣泛研究，Mendel等人[75]提出的反彈攻擊是分析AES類雜湊算法碰撞的有效工具.而在雜湊算法的設計方面，最具有代表性的就是SHA-3標準的設計.SHA-3具有優秀的設計、高效的軟硬件實現效率以及靈活的適應性，標志著國際雜湊算法的設計技術達到了一個新的高度.SHA-3基于大狀態的置換函數設計，已有的雜湊算法的分析方法如模差分方法和反彈攻擊等對SHA-3算法不能提供有效的攻擊方法，目前對SHA-3最好的分析只有5輪(共24輪)的理論碰撞攻擊結果，SHA-3安全冗余度很高.我國發布的雜湊算法標準SM3安全性冗余高、實現效率與國際雜湊算法標準SHA-256相當，標志著我國雜湊算法的設計技術也走在了國際的前列.尋找新的針對SHA-3類雜湊算法的分析方法，設計一個在軟硬件效率和靈活性方面能夠超越SHA-3的雜湊算法是未來在雜湊算法分析和設計領域研究的方向.

[1]Knuth D E. Sorting and searching[M]The Art of Computer Programming, volume 3. Massachusetts: Addison-Wesley, 1973

[2]Merkle R C. Secrecy, authentication, and public key systems[D]. Stanford , CA: Stanford University, 1979

[3]Davies D W, Price W L. The application of digital signatures based on public key cryptosystems[R]. Atlanta Ga: National Physical Lab, 1980

[4]Damg?rd I B. Collision free hash functions and public key signature schemes[G]LNCS 304: Proc of Workshop on the Theory and Application of Cryptographic Techniques. Berlin: Springer, 1987: 203-216

[5]Kelsey J, Schneier B. Second preimages on n-bit hash functions for much less than 2nwork[G]LNCS 3494: Proc of the 24th Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2005: 474-490

[6]Kelsey J, Kohno T. Herding hash functions and the nostradamus attack[G]LNCS 4004: Proc of the 24th Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2006: 183-200

[7]National Institute of Standards and Technology. FIPS 180-2 Secure Hash Standard[SOL]. 2002[2015-08-10].http:csrc.nist.govpublicationsfipsfips180-2fips180-2.pdf

[8]National Institute of Standards and Technology. FIPS 180-3 Secure Hash Standard[SOL]. 2008[2015-08-10]. http:csrc.nist.govpublicationsfipsfips180-3fips180-3_final.pdf

[9]Merkle R C. One way hash functions and DES[G]LNCS 435: Proc of Advances in Cryptology—CRYPTO’89. Berlin: Springer, 1990: 428-446

[10]Damg?rd I B. A design principle for hash functions[G]LNCS 435: Advances in Cryptology—CRYPTO’89. New York: Springer, 1990: 416-427

[11]Rivest R L. The MD4 message digest algorithm[G]LNCS 537: Advances in Cryptology—CRYPT0’90. Berlin: Springer, 1991: 303-311

[12]Rivest R L. The MD5 message digest algorithm[SOL]. RFC 1321, 1992[2015-08-10].https:www.ietf.orgrfcrfc1321.txt

[13]Zheng Yuliang, Pieprzyk J, Seberry J. HAVAL—A one-way hashing algorithm with variable length of output[G]LNCS 718:Proc of the Workshop on the Theory and Application of Cryptographic Techniques. Berlin: Springer, 1992: 81-104

[14]Dobbertin H, Bosselaers A, Preneel B. RIPEMD-160: A strengthened version of RIPEMD[G]LNCS 1039: Proc of the 3rd Int Workshop on Fast Software Encryption. Berlin: Springer, 1996: 71-82

[15]國家密碼管理局. SM3密碼雜湊算法[EBOL]. 2010 [2015-08-10]. http:www.oscca.gov.cnUpFile20101222141857786.pdf

[16]Joux A. Multicollisions in iterated hash functions. Application to cascaded constructions[G]LNCS 3152: Proc of the 24th Annual Int Cryptology Conf. Berlin: Springer, 2004: 306-316

[17]Liskov M. Constructing an ideal hash function from weak ideal compression functions[G]LNCS 4356: Revised Selected Papers of the 13th Int Workshop on Selected Areas in Cryptography. Berlin: Springer, 2007: 358-375

[18]Lucks S. A failure-friendly design principle for hash functions[G]LNCS 3788: Proc of the 11th Int Conf on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2005: 474-494

[19]Leurent G, Wang Lei. The sum can be weaker than each part[G]LNCS 9056: Proc of the 34th Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2015: 345-367

[20]Biham E, Dunkelman O. A framework for iterative hash functions: HAIFA[OL]. (2006-08-25) [2015-08-10]. http:csrc.nist.govgroupsSThashdocumentsDUNKELMAN_talk.pdf

[21]Aumasson J P, Henzen L, Meier W, et al. SHA-3 proposal BLAKE, Version 1.3[EBOL]. (2010-12-16) [2015-08-10]. https:131002.netblakeblake.pdf

[22]Bertoni G, Daemen J, Peeters M, et al. Sponge functions[OL]. 2007[2015-08-10]. http:events.iaik.tugraz.atHashWorkshop07slidesVanAssche_Sponge.pdf

[23]Bertoni G, Daemen J, Peeters M, et al. The KECCAK SHA-3 submission[EBOL]. (2011-01-14) [2015-09-22]. http:keccak.noekeon.orgKeccak-submission-3.pdf

[24]Guo Jian, Peyrin T, Poschmann A: The PHOTON family of lightweight hash functions[G]LNCS 6841: Proc of the 31st Annual Cryptology Conf. Berlin: Springer, 2011: 222-239

[25]Aumasson J P, Henzen L, Meier W, et al. QUARK: A lightweight hash[G]LNCS 6225: Proc of the 12th Int Workshop on Cryptographic Hardware and Embedded Systems. Berlin: Springer, 2010: 1-15

[27]Preneel B, Govaerts R, Vandewalle J. Hash functions based on block ciphers: A synthetic approach[G]LNCS 773: Proc of the 13th Annual Int Cryptology Conf. Berlin: Springer, 1994: 368-378

[28]RACE integrity primitives evaluation. Integrity primitives for secure information systems: Final report of RACE integrity primitives evaluation RIPE-RACE, 1040[R]. Berlin: Springer, 1992

[29]Wang Xiaoyun, Yu Hongbo. How to break MD5 and Other hash functions[G]LNCS 3494: Proc of the 24th Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2005: 19-35

[30]Wang Xiaoyun, Yin Y L, Yu Hongbo. Finding collisions in the full SHA-1[G]LNCS 3621: Proc of the 25th Annual Int Cryptology Conf. Berlin: Springer, 2005: 17-36

[31]Wang Xiaoyun, Feng Dengguo, Lai Xuejia, et al. Collisions for hash functions MD4, MD5, HAVAL-128 and RIPEMD[OL]. 2004 [2015-08-10]. https:eprint.iacr.org2004199.pdf

[32]National Institute of Standards and Technology. SHA-3 competition[EBOL]. (2005-04-15) [2015-08-10]. http:csrc.nist.govgroupsSThashdocumentsFR_Notice_Nov07.pdf

[33]Shamir A. SQUASH—A new MAC with provable security properties for highly constrained devices such as RFID tags[G]LNCS 2086: Proc of the 15th Int Workshop on Fast Software Encryption. Berlin: Springer, 2008: 144-157

[34]Bogdanov A, Leander G, Paar C, et al. Hash functions and RFID tags: Mind the gap[G]LNCS 5154: Proc of the 10th Int Workshop on Cryptographic Hardware and Embedded Systems. Berlin: Springer, 2008: 283-299

[35]Wu Wenling, Wu Shuang, Zhang Lei, et al. LHash: A lightweight hash function[G]LNCS 8567: Proc of the 9th Int Conf on Information Security and Cryptology. Berlin: Springer, 2013: 867

[36]Hellman M E. A cryptanalytic time-memory trade-off[J]. IEEE Trans on Information Theory, 1980, 26(4): 401-406

[37]Oechslin P. Making a faster cryptanalytic time-memory trade-off[G]LNCS 2729: Proc of the 23rd Annual Int Cryptology Conf. Berlin: Springer, 2003: 617-630

[38]Microsoft TechNet. Operating system installation: The LMHash[OL]. (2015-05-12) [2015-08-10]. https:technet.microsoft.comen-uslibrarydd277300.aspx#ECAA

[39]National Bureau of Standards. FIPS 46-3: Data Encryption Standard[SOL]. 1999[2015-08-10].http:csrc.nist.govpublicationsfipsfips46-3fips46-3.pdf

[40]Schneier B. Cryptanalysis of microsoft’s point-to-point tunneling protocol (PPTP)[C]Proc of the 5th ACM Conf on Computer and Communications Security. New York: ACM, 1998: 132-141

[41]Neuman B C, Ts’O T. Kerberos: An authentication service for computer networks[J]. IEEE Communications Magazine, 1994, 32(9): 33-38

[42]den Boer B, Bosselaers A. An attack on the last two rounds of MD4[G]LNCS 576: Advances in Cryptology—CRYPTO’91. Berlin: Springer, 1992: 194-203

[43]den Boer B, Bosselaers A. Collisions for the compression function of MD5[G]LNCS 765: Proc of Workshop on the Theory and Application of Cryptographic Techniques. Berlin: Springer, 1994: 293-304

[44]Vaudenay S. On the need for multipermutations: Cryptanalysis of MD4 and SAFER[G]LNCS 1008: Proc of the 2nd Int Workshop on Fast Software Encryption. Berlin: Springer, 1995: 286-297

[45]Dobbertin H. Cryptanalysis of MD4[G]LNCS 1039: Proc of the 3rd Int Workshop on Fast Software Encryption. Berlin: Springer, 1996: 53-69

[46]Dobbertin H. The first two rounds of MD4 are not one-way[G]LNCS 1372: Proc of the 5th Int Workshop on Fast Software Encryption. Berlin: Springer, 1998: 284-292

[47]Dobbertin H. Cryptanalysis of MD5 compress[OL]. (1996-05-02) [2015-08-10]. http:cseweb.ucsd.edu～bsydobbertin.ps

[48]Chabaud F, Joux A. Differential collisions in SHA-0[G]LNCS 1462: Proc of the 18th Annual Int Cryptology Conf. Berlin: Springer, 1998: 56-71

[49]Wang Xiaoyun, Lai Xuejia, Feng Dengguo, et al. Cryptanalysis of the hash functions MD4 and RIPEMD[G]LNCS 3494: Proc of the 24th Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer,2005: 1-18

[50]Yu Hongbo, Wang Gaoli, Zhang Guoyan, et al. The second-preimage attack on MD4[G]LNCS 3810: Proc of the 4th Int Conf on Cryptology and Network Security. Berlin: Springer, 2005: 1-12

[51]Biham E, Chen R, Joux A, et al. Collisions of SHA-0 and reduced SHA-1[G]LNCS 3494: Proc of the 24th Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2005: 36-57

[52]Stevens M, Lenstra A, De Weger B. Chosen-Prefix collisions for MD5 and colliding X.509 certificates for different identities[G]LNCS 4515: Proc of the 26th Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2007: 1-22

[53]Stevens M, Sotirov A, Appelbaum J, et al. Proc of short chosen-prefix collisions for MD5 and the creation of rogue CA certificate[G]LNCS 5677: Proc of the 29th Annual Int Cryptology Conf. Berlin: Springer, 2009: 55-69

[54]Wang Xiaoyun, The collision attack on SHA-0[OL]. 1997[2015-08-10]. http:www.infosec.sdu.edu.cnperson_wangxiaoyun2.htm

[55]Wang Xiaoyun, Yao A C, Yao F. Cryptanalysis on SHA-1[OL]. 2005 [2015-08-10]. http:csrc.nist.govgroupsSThashdocumentsWang_SHA1-New-Result.pdf

[56]Stevens M. New collision attacks on SHA-1 based on optimal joint local-collision analysis[G]LNCS 7881: Proc of the 32nd Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2013: 245-261

[57]Karpman P, Peyrin T, Stevens M. Practical free-start collision attacks on 76-step SHA-1[G]LNCS 9215: Proc of the 35th Annual Cryptology Conf. Berlin: Springer, 2015: 623-642

[58]Fouque P, Leurent G, Nguyen P Q. Full key-recovery attacks on HMACNMAC-MD4 and NMAC-MD5[G]LNCS 4622: Proc of the 27th Annual Int Cryptology Conf. Berlin: Springer, 2007:13-30

[59]Raddum H. Algebraic analysis of the Simon block cipher family[G]LNCS 9230: Proc of the 4th Int Conf on Cryptology and Information Security. Berlin: Springer, 2015: 157-169

[60]Knellwolf S, Meier W, Naya-Plasencia M. Conditional differential cryptanalysis of NLFSR-based cryptosystems[G]LNCS 6477: Proc of the 16th Int Conf on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2010: 130-145

[61]Mendel F, Nad T, Schl?ffer M. Improving local collisions: New attacks on reduced SHA-256[G]LNCS 7881: Proc of the 32nd Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2013: 262-278

[62]Eichlseder M, Mendel F, Schl?ffer M. Branching heuristics in differential collision search with applications to SHA-512[C]LNCS 8540: Revised Selected Papers of the 21st Int Workshop on Fast Software Encryption. Berlin: Springer, 2014: 473-488

[63]Dinur I, Dunkelman O, Shamir A. New attacks on Keccak-224 and Keccak-256[G]LNCS 7549: Revised Selected Papers of the 19th Int Workshop on Fast Software Encryption. Berlin: Springer, 2012: 442-461

[64]Duc A, Guo Jian, Peyrin T, et al. Unaligned rebound attack: Application to Keccak[G]LNCS 7549: Revised Selected Papers of the 19th Int Workshop on Fast Software Encryption. Berlin: Springer, 2012: 402-421

[65]Duan Ming, Lai Xuejia. Improved zero-sum distinguisher for full round Keccak-f permutation[J]. Chinese Science Bulletin, 2012, 57(6): 694-697

[66]Aoki K, Sasaki Y. Preimage attacks on one-block MD4, 63-step MD5 and more[G]LNCS 5381: Proc of the 15th Int Workshop on Selected Areas in Cryptography (SAC 2008). Berlin: Springer, 2009: 103-119

[67]Diffie W, Hellman M E. Special feature exhaustive cryptanalysis of the NBS data encryption standard[J]. Computer, 1977, 10(6): 74-84

[68]Menezes A J, Van Oorschot P C, Vanstone S A. Handbook of Applied Cryptography[M]. Boca Raton: CRC Press, 1996

[69]Sasaki Y, Aoki K. Finding preimages in Full MD5 faster than exhaustive search[G]LNCS 5479: Proc of the 28th Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2009: 134-152

[70]Khovratovich D, Rechberger C, Savelieva A. Bicliques for preimages: Attacks on Skein-512 and the SHA-2 family[G]LNCS 7549: Proc of the 19th Int Workshop on Fast Software Encryption. Berlin: Springer, 2012: 244-263

[71]Sasaki Y, Aoki K. Preimage attacks on 3, 4, and 5-pass HAVAL[G]LNCS 5350: Proc of the 14th Int Conf on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2008: 253-271

[72]Aoki K, Guo J, Matusiewicz K, et al. Preimages for step-reduced SHA-2[G]LNCS 5912: Proc of the 15th Int Conf on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2009: 578-597

[73]Knellwolf S, Khovratovich D. New preimage attacks against reduced SHA-1[G]LNCS 7417: Proc of the 32nd Annual Cryptology Conf. Berlin: Springer, 2012: 367-383

[74]Espitau T, Fouque P A, Karpman P. Higher-order differential meet-in-the-niddle preimage attacks on SHA-1 and BLAKE[G]LNCS 9215: Proc of the 35th Annual Cryptology Conf. Berlin: Springer, 2015: 683-701

[75]Mendel F, Rechberger C, Schl?ffer M, et al. The rebound attack: Cryptanalysis of reduced Whirlpool and Gr?stl[G]LNCS 5665: Proc of the 16th Int Workshop on Fast Software Encryption. Berlin:Springer, 2009: 260-276

[77]Aumasson J P, Meier W. Zero-sum distinguishers for reduced Keccak-f and for the core functions of Luffa and Hamsi[OL]. 2009[2015-08-10]. https:131002.netdatapapersAM09.pdf

[78]Wagner D. The boomerang attack[C]Proc of the 6th Int Workshop on Fast Software Encryption. Berlin: Springer, 1999: 156-170

[79]Lamberger M, Mendel F, Rechberger C, et al. Rebound distinguishers: Results on the full Whirlpool compression function[G]LNCS 5912: Proc of the 15th Int Conf on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2009: 126-143

[80]Gilbert H, Peyrin T. Super-Sbox cryptanalysis: Improved attacks for AES-like permutations[G]LNCS 6147: Revised Selected Papers of the 17th Int Workshop on Fast Software Encryption. Berlin: Springer, 2010: 365-383

[81]Duc A, Guo Jian, Peyrin T, et al. Unaligned rebound attack: Application to Keccak[G]LNCS 7549: Revised Selected Papers of the 19th Int Workshop on Fast Software Encryption. Berlin: Springer, 2012: 402-421

[82]Bouillaguet C, Derbez P, Dunkelman O, et al. Low-data complexity attacks on AES[J]. IEEE Trans on Information Theory, 2012, 58(11): 7002-7017

[83]Biryukov A, Dunkelman O, Keller N, et al. Key recovery attacks of practical complexity on AES-256 variants with up to 10 rounds[G]LNCS 6110: Proc of the 29th Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2010: 299-319

[84]Li Leibo, Jia Keting, Wang Xiaoyun. Improved single-key attacks on 9-Round AES-192256[G]LNCS 8540: Revised Selected Papers of the 21st Int Workshop on Fast Software Encryption. Berlin: Springer, 2014: 127-146

王小云

教授，博士生導師，主要研究方向為密碼理論與技術.

xiaoyunwang@mail.tsinghua.edu.cn

于紅波

博士，副教授，主要研究方向為密碼學.

yuhongbo@mail.tsinghua.edu.cn

Survey of Hash Functions

Wang Xiaoyun1,2and Yu Hongbo3

1(InstituteforAdvancedStudy,TsinghuaUniversity,Beijing100084)2(KeyLaboatoryofCryptologicTechnologyandInofrmationSecurity(ShandongUniversity),MinistryofEducation,Jinan250100)3(DepartmentofComputerScienceandTechnology,TsinghuaUniversity,Beijing100084)

One of the fundamental primitives in modern cryptography is the cryptographic hash functions, often informally called hash functions. They are used to compress messages of arbitrary length to fixed length hash values which are also called hash codes, message digests or digital fingerprints. A primary motivation for cryptographic hash functions is that they serve as compact representative images of input messages, which they can uniquely identify. Changing a single letter will change most of the digits in the hash code. The most common cryptographic uses of hash functions are with digital signature and for data integrity. Hash functions are frequently used in digital signature schemes to compress large messages for processing by public-key cryptosystems such as RSA. They are also used to design message authentication codes (MACs) and many secure cryptographic protocols. Hash functions occur as components in various cryptographic applications (e.g. protection of pass-phrases, protocols for payment, broadcast authentication etc.), where usually their property as a computational one-way function is used. So the study of the hash functions is of great significance in the cryptanalysis field.

cryptographic hash function; collision attack; preimage attack; MD5 algorithm; SHA-1 algorithm; SHA-3 algorithm

2015-09-20

國家“九七三”重點基礎研究發展計劃基金項目(2013CB834205)；國家自然科學基金項目(61133013,61373142)

TP309