密碼雜湊算法綜述

王小云于紅波

1(清華大學(xué)高等研究院 北京 100084)2(密碼技術(shù)與信息安全教育部重點(diǎn)實(shí)驗(yàn)室(山東大學(xué)) 濟(jì)南 250100)3 (清華大學(xué)計(jì)算機(jī)系 北京 100084)

?

密碼雜湊算法綜述

王小云1,2于紅波3

1(清華大學(xué)高等研究院 北京 100084)2(密碼技術(shù)與信息安全教育部重點(diǎn)實(shí)驗(yàn)室(山東大學(xué)) 濟(jì)南 250100)3(清華大學(xué)計(jì)算機(jī)系 北京 100084)

(xiaoyunwang@mail.tsinghua.edu.cn)

密碼雜湊算法是現(xiàn)代密碼學(xué)中的基本工具，它能夠?qū)⑷我忾L度的消息壓縮成固定長度的摘要.雜湊值又稱為雜湊碼、消息摘要或數(shù)字指紋.通常密碼雜湊算法被非正式地稱為雜湊算法.雜湊算法的重要性就是能夠賦予每個(gè)消息唯一的“數(shù)字指紋”，即使更改該消息的一個(gè)字母，對應(yīng)的雜湊值也會(huì)變?yōu)榻厝徊煌摹爸讣y”.雜湊算法在現(xiàn)代密碼學(xué)中有著極其重要的作用，它最常用的用途是用在數(shù)字簽名和數(shù)據(jù)完整性保護(hù)中.雜湊算法是數(shù)字簽名的核心技術(shù)，通常用公鑰密碼算法如RSA進(jìn)行數(shù)字簽名時(shí)，一般不是對消息直接簽名，而是對消息的雜湊值進(jìn)行簽名，這樣既可以減少計(jì)算量，提高效率，也可以破壞數(shù)字簽名算法的某些代數(shù)結(jié)構(gòu)，保障其安全性.雜湊算法還是許多密碼算法密碼系統(tǒng)安全的基本前提條件，它可以用來設(shè)計(jì)消息認(rèn)證碼以及眾多可證明安全協(xié)議，還廣泛應(yīng)用于口令保護(hù)協(xié)議、電子支付協(xié)議、廣播認(rèn)證協(xié)議等密碼協(xié)議中.因此對雜湊算法進(jìn)行研究在密碼學(xué)領(lǐng)域具有重要的意義.

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

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

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

除了數(shù)據(jù)壓縮、易于計(jì)算這2個(gè)基本屬性之外，雜湊算法還應(yīng)該滿足下面3個(gè)安全屬性：

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

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

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

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

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

雜湊算法是密碼學(xué)的3類基礎(chǔ)算法之一(加密算法、數(shù)字簽名算法和雜湊算法)，主要用于數(shù)據(jù)的完整性校驗(yàn)、基于口令的身份認(rèn)證、提高數(shù)字簽名的有效性和安全性、密鑰推導(dǎo)、構(gòu)造基于密碼雜湊算法的消息認(rèn)證碼和構(gòu)造確定性隨機(jī)比特生成器等，對雜湊算法進(jìn)行研究對理論和實(shí)際是有重要意義的.

1 雜湊算法設(shè)計(jì)技術(shù)

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

基于迭代壓縮函數(shù)的雜湊算法設(shè)計(jì)整體結(jié)構(gòu)如下：

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

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

3) 使用壓縮函數(shù)對每個(gè)消息分組依次進(jìn)行迭代壓縮；

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

雜湊算法的設(shè)計(jì)包括迭代結(jié)構(gòu)的設(shè)計(jì)以及壓縮函數(shù)的設(shè)計(jì).

1.1 雜湊算法的迭代結(jié)構(gòu)設(shè)計(jì)

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

圖1 MD結(jié)構(gòu)雜湊算法圖

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

寬管道和雙管道結(jié)構(gòu)雜湊算法如圖2、圖3所示：

圖2 寬管道結(jié)構(gòu)雜湊算法圖

圖3 雙管道結(jié)構(gòu)雜湊算法圖

圖4 HAIFA結(jié)構(gòu)雜湊算法圖

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

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

圖5 海綿體結(jié)構(gòu)雜湊算法圖

目前，海綿體結(jié)構(gòu)已經(jīng)成為繼MD結(jié)構(gòu)后被使用最廣泛的結(jié)構(gòu)，如SHA-3標(biāo)準(zhǔn)KECCAK[23]使用海綿體結(jié)構(gòu)，輕量級(jí)雜湊算法PHOTON[24]，QUARK[25]，SPONGENT[26]等都使用海綿體結(jié)構(gòu)設(shè)計(jì).

1.2 雜湊算法壓縮函數(shù)的設(shè)計(jì)

1.2.1 基于分組密碼的雜湊算法的設(shè)計(jì)

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

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

1.2.2 定制雜湊算法的設(shè)計(jì)

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

1.2.3 雜湊算法標(biāo)準(zhǔn)

現(xiàn)代密碼學(xué)的發(fā)展離不開各類國際密碼組織的推動(dòng).在這些密碼組織的推動(dòng)下，雜湊算法的設(shè)計(jì)和分析得到了長足的發(fā)展.

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

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

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

在雜湊函數(shù)的設(shè)計(jì)方面，2010年12月國家密碼管理局公布了由王小云等人設(shè)計(jì)的我國商用密碼雜湊算法SM3[15]，該算法結(jié)構(gòu)簡潔、軟硬件實(shí)現(xiàn)效率高、安全強(qiáng)度高，其總體性能優(yōu)于國際上廣泛使用的雜湊函數(shù)標(biāo)準(zhǔn)SHA-256.目前SM3算法作為我國雜湊算法密碼行業(yè)標(biāo)準(zhǔn)和國家標(biāo)準(zhǔn)已經(jīng)被廣泛推廣使用.

1.2.4 輕量級(jí)雜湊算法的設(shè)計(jì)

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

2 雜湊算法分析技術(shù)

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

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

2.1 雜湊算法通用攻擊方法

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

圖6 TMTO表建立過程

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

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

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

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

2.2 針對具體算法的攻擊

2.2.1 雜湊算法的碰撞攻擊

由于碰撞攻擊能夠深入到壓縮函數(shù)的內(nèi)部，很多縮減輪的分析具有實(shí)際的攻擊復(fù)雜度，能夠更好地反映雜湊算法的安全強(qiáng)度.

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

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

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

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

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

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

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

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

2.2.2 雜湊算法原像攻擊

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

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

圖7 帶完全二分結(jié)構(gòu)體的中間相遇攻擊圖示

基于中間相遇攻擊的原像攻擊在結(jié)構(gòu)上可分為起始部分、相互獨(dú)立部分和匹配部分.為了增加原像攻擊的輪數(shù)，可以從增加這3部分的輪數(shù)入手.

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

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

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

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

2.2.3 其他新型的攻擊

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

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

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

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

3 結(jié)束語

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

[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

王小云

教授，博士生導(dǎo)師，主要研究方向?yàn)槊艽a理論與技術(shù).

xiaoyunwang@mail.tsinghua.edu.cn

于紅波

博士，副教授，主要研究方向?yàn)槊艽a學(xué).

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

國家“九七三”重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃基金項(xiàng)目(2013CB834205)；國家自然科學(xué)基金項(xiàng)目(61133013,61373142)

TP309