改進(jìn)的Keccak算法4輪區(qū)分器

劉景美，薛 寧，趙林森

（1. 西安電子科技大學(xué)綜合業(yè)務(wù)網(wǎng)國家重點(diǎn)實(shí)驗(yàn)室 西安 710071；2. 西安郵電大學(xué)電子工程學(xué)院 西安 710061）

改進(jìn)的Keccak算法4輪區(qū)分器

劉景美1，薛 寧1，趙林森2

（1. 西安電子科技大學(xué)綜合業(yè)務(wù)網(wǎng)國家重點(diǎn)實(shí)驗(yàn)室 西安 710071；2. 西安郵電大學(xué)電子工程學(xué)院 西安 710061）

Keccak算法是新一代Hash函數(shù)標(biāo)準(zhǔn)SHA-3的獲勝算法。 如何構(gòu)造一個(gè)好的區(qū)分器是當(dāng)前Hash函數(shù)中的研究熱點(diǎn)。該文在分析Keccak算法及算法中各個(gè)置換性質(zhì)的基礎(chǔ)上，通過線性分析方法和差分分析方法，研究了整體Keccak算法的差分傳播特性。利用Keccak旋轉(zhuǎn)變換和z周期性質(zhì)，成功構(gòu)造出4輪Keccak置換的區(qū)分器。通過分析Keccak算法的旋轉(zhuǎn)對(duì)的傳播特性，對(duì)Morawiecki區(qū)分器的構(gòu)造方法進(jìn)行了修正改進(jìn)。實(shí)驗(yàn)結(jié)果表明該區(qū)分隨機(jī)置換和Keccak變換的區(qū)分概率更大，區(qū)分效果比Morawiecki構(gòu)造的區(qū)分器區(qū)分效果更好。

差分分析； Hash函數(shù)； Keccak算法； 隨機(jī)置換

隨著被廣泛使用的MD5與SHA-1等Hash算法破解技術(shù)的發(fā)現(xiàn)，美國國家標(biāo)準(zhǔn)與技術(shù)研究院（NIST）發(fā)起了新一代密碼雜湊算法-（SHA-3）的公開競賽［1］。SHA-3候選算法在設(shè)計(jì)消息填充、壓縮函數(shù)的非線性變換部件時(shí)，充分借鑒了MD算法的不足之處，同時(shí)采用了新的迭代結(jié)構(gòu)，如sponge、wide pipe和HAIFA等。這些改進(jìn)措施可以有效地防止相關(guān)的多碰撞攻擊、原象攻擊和第二原象攻擊，不僅安全性高，且具有較好的運(yùn)行效率和適用性。2012年10月NIST確認(rèn)Keccak算法為SHA-3標(biāo)準(zhǔn)［2］，同時(shí)Keccak算法也成為密碼分析者攻擊的首選對(duì)象。文獻(xiàn)［3］結(jié)合差分分析和代數(shù)分析，提出了目標(biāo)差分攻擊，并對(duì)Keccak進(jìn)行了4輪碰撞攻擊，擴(kuò)大了攻擊的輪數(shù)，在個(gè)人PC上幾分鐘內(nèi)就可以發(fā)現(xiàn)碰撞。目前還存在一些其他相關(guān)的分析，如旋轉(zhuǎn)特性分析、區(qū)分器構(gòu)造和縮減輪數(shù)攻擊等［4-13］。本文在分析Keccak算法中Keccak置換的性質(zhì)和差分傳播特性的基礎(chǔ)上，改進(jìn)了文獻(xiàn)［4］中區(qū)分器的構(gòu)造方法，得到了一種區(qū)分效果更好的4輪區(qū)分器，可以更好地區(qū)分Keccak置換和隨機(jī)置換。

1 Keccak算法介紹

SHA-3算法的評(píng)選活動(dòng)中，NIST對(duì)候選算法要求至少包含4種輸出長度，n∈（224，256，384，512），把不同參數(shù)的Keccak算法根據(jù)Hash輸出長度的大小分別記作Keccak-224、Keccak-256、Keccak-384、Keccak-512。獲選的Keccak算法采用了標(biāo)準(zhǔn)的sponge結(jié)構(gòu)［14］，可將任意長度的輸入比特映射成固定長度的輸出比特。

圖1 海綿結(jié)構(gòu)

Keccak算法采用的海綿結(jié)構(gòu)如圖1所示，其中M為任意長度的消息，Z為Hash后的輸出， f為Keccak-f［b］的置換函數(shù)，r為比特率，c為容量，且brc=+，參數(shù)c為Hash輸出長度的2倍，即c=2n。從圖中可以明顯的看出，海綿結(jié)構(gòu)有2個(gè)階段：absorbing（吸收）階段和squeezing（壓縮）階段。在absorbing階段，消息M首先被填充，然后被分組，每組有r個(gè)比特，同時(shí)b個(gè)初始狀態(tài)全部初始化為0。填充規(guī)則為在消息M后串聯(lián)一個(gè)數(shù)字串100…01，其中0的個(gè)數(shù)是使得消息M填充后長度為r的最小正整數(shù)倍。根據(jù)此規(guī)則可以發(fā)現(xiàn)最小填充的長度為2，最大為r+1。

Keccak算法的內(nèi)部狀態(tài)可看作是一個(gè)5×5×w的3維比特?cái)?shù)組，用 a［5］［5］［w］表示，其結(jié)構(gòu)如圖2所示分別有以下7種狀態(tài)：state、slice、plane、sheet、row、column、lane。獲選的Keccak-f［1 600］的狀態(tài)用a［5］［5］［64］表示。

圖2 狀態(tài)的劃分

在海綿結(jié)構(gòu)的吸收階段，每個(gè)消息分組與狀態(tài)內(nèi)部的r bit進(jìn)行異或，然后與后面固定的c比特一起封裝成1 600 bit的數(shù)據(jù)進(jìn)行輪函數(shù)f處理，然后再進(jìn)入擠壓過程。在擠壓階段，可以循環(huán)產(chǎn)生n比特固定輸出長度的Hash值，其中迭代次數(shù) nr由狀態(tài)比特?cái)?shù)b決定，即nr=12+2l，其中2l=b/25。獲選的Keccak-f［1 600］的b=1 600 bit，因此將循環(huán)執(zhí)行24次，每個(gè)循環(huán)R只有最后一步輪常數(shù)不同，但是該輪常數(shù)在碰撞攻擊時(shí)經(jīng)常被忽略不計(jì)。Keccak算法結(jié)構(gòu)如圖3所示。

圖3 Keccak-f算法結(jié)構(gòu)

從圖中可以看出，Keccak-f［1 600］每輪迭代的輪函數(shù)R都由5個(gè)映射構(gòu)成，即R=f（l，χ，π，ρ，θ）。下面分別介紹這5個(gè)變換。

θ變換：θ是一個(gè)線性映射，共涉及11 bit的運(yùn)算，即：

θ變換的逆運(yùn)算為θ-1，具有快速的擴(kuò)散能力，即輸入改變1 bit，一半的輸出比特值將會(huì)被翻轉(zhuǎn)。

ρ旋轉(zhuǎn)：主要是對(duì)Keccak的lane進(jìn)行操作，也就是對(duì)lane里面的狀態(tài)進(jìn)行移位，即：

π變換：a［x］［y］［z］←a［x′］［y′］［z］，其中：

χ變換：χ變換是Keccak變換中唯一的非線性變換，320個(gè)row各自獨(dú)立進(jìn)行變換，變換形式為：

χ變換可以看作是一個(gè)關(guān)于row的5輸入5輸出的S盒，該S盒是一個(gè)可逆映射，且每個(gè)輸出比特多項(xiàng)式的代數(shù)度數(shù)僅為2，χ-1的代數(shù)度數(shù)為3。

ι變換：可以看作是常數(shù)異或的過程，即：

一般在對(duì)Keccak算法進(jìn)行碰撞攻擊時(shí)，該輪都會(huì)被刪除，不做特別分析。

2 Keccak旋轉(zhuǎn)對(duì)的傳播特性與4輪區(qū)分器

定義 1 假設(shè)Keccak-f［1 600］兩個(gè)狀態(tài)為A和A′，如果對(duì)每個(gè)lane都滿足A［x］［y］［x］=A′［x］［y］［（z+n）mod 64］，則A和A′為旋轉(zhuǎn)對(duì)。

從定義1中可以看出，最多有64個(gè)旋轉(zhuǎn)對(duì)，旋轉(zhuǎn)對(duì)有可能會(huì)導(dǎo)致原象攻擊。同時(shí)可以看出z的周期為n，記為Rot（A［x］［y］，n）

定義 2 集合Sn為21600個(gè)狀態(tài)對(duì)經(jīng)過若干步Keccak-f［1 600］變換或逆變換所得的所有旋轉(zhuǎn)對(duì)狀態(tài)結(jié)果的集合。

定義 3 集合 Sn中任意選定的一對(duì)狀態(tài)（A，A′），則A［x］［y］［z］≠A′［x］［y］［z+n］的概率為：

式（5）可表示為pa=Pr（a0≠a1），其中

給定一個(gè)n比特的置換p：｛0，1｝n→｛0，1｝n，任意n比特輸入序列產(chǎn)生的所有可能輸出結(jié)果的集合為Pn，則集合 Pn的基數(shù)為

定義 4 設(shè)Dn是給定的某種概率分布，若Dn為均勻分布，即p∈Dn的概率Pr（p∈Dn）=1/n！,則p為隨機(jī)置換。

為了更直觀地看出Keccak算法后續(xù)過程的概率變化過程，分析Keccak算法中兩個(gè)最基本的比特運(yùn)算：AND（與）運(yùn)算和XOR（異或）運(yùn)算。設(shè)a和b為兩個(gè)輸入比特對(duì)，out是a和b經(jīng)過某種比特間運(yùn)算的輸出比特對(duì)， Pout表示輸出的兩個(gè)比特不相同的概率。

對(duì)于AND（與）運(yùn)算，有：

對(duì)于XOR（異或）運(yùn)算，有：

對(duì)于NOT（非）運(yùn)算，并不影響輸出概率，它僅僅是翻轉(zhuǎn)相關(guān)的輸入比特A［x］［y］［x］和A′［x］［ y］［z + n］的值，不改變輸入之間的相對(duì)關(guān)系。同樣旋轉(zhuǎn)運(yùn)算Rot（w，n） 變換只是交換了比特的相對(duì)位置，并不改變比特的值，因此根本不影響輸出概率。

Keccak-f［1 600］的χ、θ、π 變換都是比特間的運(yùn)算，如θ變換，只存在異或運(yùn)算，由于異或運(yùn)算的線性性，由式（7）可以計(jì)算其輸出比特不同的概率值。同理，χ變換的輸出比特不同的概率都可以用式（6）和式（7）計(jì)算。Keccak算法的最后一步是l變換，也就是lane（0，0）異或上一個(gè)輪常數(shù)，若輪常數(shù)為0，相當(dāng)于沒有做任何操作。若輪常數(shù)不為0且旋轉(zhuǎn)周期 n＞0，則l變換的異或操作將會(huì)改變輸出比特對(duì) Pout的概率，且輸出概率與Rot（w，n）和“1”的位置有關(guān)，設(shè)偏移量滿足關(guān)系：

假設(shè)考慮8 bit的旋轉(zhuǎn)對(duì)lane，若此時(shí)旋轉(zhuǎn)周期n=3，按照定義1，則有?z：A（0，0，z）=A′（0，0，z 3），因此當(dāng)A（0，0）=00000010時(shí)，有A′（0，0）=00010000，同時(shí)根據(jù)式（5）有如果A（0，0）和A′（0，0）同時(shí)異或一個(gè)8 bit的常數(shù)C=00100000，則A（0，0）= 00100010，A′（0，0），再經(jīng)過旋轉(zhuǎn)變換后，對(duì)于輪常數(shù)為64 bit的Keccak-f［1 600］，該結(jié)論依然成立，證明過程也類似。

根據(jù)以上這些性質(zhì)，可以構(gòu)造一個(gè)4輪旋轉(zhuǎn)區(qū)分器，用以區(qū)分隨機(jī)置換和Keccak變換。實(shí)驗(yàn)結(jié)果表明經(jīng)過4輪迭代之后，對(duì)于旋轉(zhuǎn)數(shù)n，存在一些坐標(biāo)（x，y，z）使得p（x，y，x）n不再服從p=0.5的二項(xiàng)分布B(N,p)，從而可以成功地區(qū)分出隨機(jī)置換和Keccak變換。本次實(shí)驗(yàn)選取n=54，起始狀態(tài)通過迭代運(yùn)算，計(jì)算更新每一輪輸出狀態(tài)的p（x，y，x）n，得到4輪區(qū)分器的概率變化過程如圖4所示。

圖4中每一個(gè)方格代表每一個(gè)比特的p（x，y，x）n概率值，不同灰度顏色與圖形標(biāo)記p（x，y，x）n的大小范圍，為了便于繪圖和觀察，每個(gè)lane都選用狀態(tài)的二維視圖，用（x， y）表示，其中一個(gè)單一的小方塊代表了p的值或范圍。Keccak算法共有25個(gè)lane，每個(gè)lane有64 bit，因此可以看到圖中狀態(tài)可以表示成坐標(biāo)（25，64），圖中每一行都代表一個(gè)lane，每一列代表一個(gè)slice。例如表示第6排最左邊的小方格，而表示最后第25排最右邊的小方格。

圖4 4輪區(qū)分器的概率變化過程

該區(qū)分器模擬建立過程中，仿真環(huán)境是Pentium（R） Dual-Core CPU E5300 2.6 G，仿真軟件采用python，迭代生成得到每一個(gè)點(diǎn)數(shù)據(jù)，再根據(jù)它的值加上色彩和不同的圖形實(shí)現(xiàn)。

在區(qū)分器建立的起始時(shí)刻，所有旋轉(zhuǎn)對(duì)的對(duì)應(yīng)位都相等，根據(jù)式（6）和式（7），因此有通過迭代運(yùn)算，計(jì)算更新每一輪的輸出狀態(tài)值。經(jīng)過首輪ι變換的常數(shù)異或后的一部分概率值將會(huì)發(fā)生改變，并且這些變化在后續(xù)的迭代過程中會(huì)一直傳播并影響其他比特。對(duì)于大多數(shù)的旋轉(zhuǎn)周期n，在4輪迭代后的部分取值會(huì)偏離0.5，但大部分都接近0.5。經(jīng)過計(jì)算仿真，4輪Keccak后也就是最終選取的旋轉(zhuǎn)周期n=54。

為了驗(yàn)證區(qū)分器，隨機(jī)選擇20 000個(gè)旋轉(zhuǎn)對(duì)經(jīng)過4輪Keccak-f［1 600］變換，發(fā)現(xiàn)有11 750個(gè)旋轉(zhuǎn)對(duì)的比特位有不相同的值。對(duì)于一個(gè)服從參數(shù)為B（N = 20 000， p）的二項(xiàng)分布隨機(jī)序列，可以得到其樣本均值m=10 000，，方差2=712所以經(jīng)過4輪Keccak-f［1 600］變換得到的均值應(yīng)該在10 000 ±3×71的范圍內(nèi)，但是顯然11 750不在這個(gè)置信區(qū)間內(nèi)，從而得出結(jié)論：實(shí)驗(yàn)結(jié)果不符合二項(xiàng)分布B（N，0.5），即可以將Keccak-f［1600］變換從一個(gè)隨機(jī)置換中區(qū)分出來，從而成功地構(gòu)造出4輪Keccak變換的區(qū)分器。仿真數(shù)據(jù)表明，本文選取構(gòu)造區(qū)分器，區(qū)分概率比文獻(xiàn)［4］選取的0.5 625要大，具有更好的區(qū)分效果。

3 結(jié) 論

Keccak算法是SHA-3標(biāo)準(zhǔn)的最終獲勝算法，到目前為止表現(xiàn)出了良好的抗碰撞攻擊性能。它僅存在低輪數(shù)的原象攻擊和近似碰撞攻擊，并未對(duì)完整輪數(shù)實(shí)現(xiàn)實(shí)際可行的攻擊。本文詳細(xì)描述了Keccak算法的變換過程和內(nèi)部輪函數(shù)，并且根據(jù)Keccak算法置換的旋轉(zhuǎn)變換特性，成功地構(gòu)造了4輪Keccak算法的旋轉(zhuǎn)區(qū)分器，用以區(qū)分隨機(jī)置換和Keccak置換，經(jīng)過仿真分析得到了比文獻(xiàn)［4］更好的區(qū)分結(jié)果。Keccak完整算法為24輪，且僅存的低輪數(shù)碰撞攻擊仍具有較高的數(shù)據(jù)復(fù)雜度，因此如何提高攻擊的輪數(shù)，降低攻擊的復(fù)雜度，仍然是未來研究的主要熱點(diǎn)問題。

［1］ National Institute of Standards and Technology. SHA-3 competition（2007-2012）［S/OL］. ［2014-01-01］. http：//csrc. nist.gov/groups/ST/ hash/sha-3/index.html.

［2］ CHANG Shu-jen， RAY P， WILLIAM E B， et al. Third round report of the SHA-3 cryptographic Hash algorithm competition［M］. Washington， America： U.S. Department of Commerce， 2012.

［3］ DINUR I， DUNKELMAN O， SHAMIR A. New attacks on keccak-224 and keccak-256［C］//19th International Workshop， Fast Software Encryption 2012. Washington：Springer-Verlag， 2012， 7549： 442-461.

［4］ PAWE? M， JOSEF P， MARIAN S. Rotational cryptanalysis of round-reduced Keccak［C］//20th International Workshop，F(xiàn)ast Software Encryption 2013. Singapore： Springer-Verlag，2014， 8424： 241-262.

［5］ JEAN J， NAYA P M， PEYRIN T. Improved rebound attack on the finalist gr?stl［C］//19th International Workshop， Fast Software Encryption 2012. Washington： Springer-Verlag：2012， 7549： 110-126.

［6］ 李倩男， 李云強(qiáng)， 蔣淑靜， 等. Keccak類非線性變換的差分性質(zhì)研究［J］. 通信學(xué)報(bào)， 2012， 33（9）： 140-146. LI Qian-nan， LI Yun-qiang， JIANG Shu-jing， et al. Research on differential properties of Keccak-like nonlinear transform［J］. Journal on Communications， 2012， 33（9）：140-146.

［7］ PAWEL S， GERGOR L， CHRISTOF P. Keccak und der SHA-2［J］. Datenschutz Und Datensicherheit， 2013， 37（11）：712-719.

［8］ MARíA N P， ANDREA R， WILLI M. Practical analysis of reduced-round Keccak［C］//12th International Conference on Cryptology. Chennai， India： Springer-Verlag， 2011， 7107：236-254.

［9］ MOSTAFA T， PATRICK S. Differential power analysis of MAC-Keccak at any key-length［C］//8th International Workshop on Security， IWSEC 2013. Okinawa， Japan：Springer-Verlag， 2013， 8231： 68-82.

［10］ ELENA A， BART M， BART P. Open problems in Hash function security［J］. Designs， Codes and Cryptography，2015， 77（2）： 611-631.

［11］ SUGIER J. Low cost FPGA devices in high speed implementations of Keccak-f Hash algorithm［C］// Proceedings of the 9th International Conference on Dependability and Complex Systems DepCoSRELCOMEX. Runów， Poland： Springer-Verlag， 2014， 286：433-441.

［12］ KUILA S， SAHA D， PAL M， et al. Practical distinguishers against 6-round Keccak-f exploiting self-symmetry［C］//7th International Conference on Cryptology. Marrakesh， Africa：Springer-Verlag， 2014， 8469： 88-108.

［13］ SOURAV D， WILLI M. Differential biases in reducedround Keccak［C］//7th International Conference on Cryptology. Marrakesh， Africa： Springer-Verlag， 2014，8469： 241-262.

［14］ Federal Information Processing Standards Publication. SHA-3 standard： Permutation-based Hash and extendableoutput functions［S/OL］. ［2014-01-10］. http：//nvlpubs.nist. gov/nistpubs/FIPS/NIST.FIPS.202.pdf.

編 輯 葉 芳

Improved 4-Round Distinguisher for the Keccak Algorithm

LIU Jing-mei1， XUE Ning1， and ZHAO Lin-sen2
（1. National Key Laboratory of Integrated Service Networks， Xidian University Xi'an 710071；2. College of Electronic Engineering， Xi'an University of Post & Telecommunications Xi'an 710061）

The Keccak algorithm is selected as the new Hash function standard of SHA-3 fianally. How to construct a good distinguisher is a hot topic in cryptanalysis of the Hash function at present. In this paper， on the base of the permutation property， we research the differential propagation characteristics of the Keccak algorithm by the linear and differential cryptanalysis methods. By using the Keccak rotation transform characteristics and z cycle properties， we construct the distinguisher of the 4-round Keccak permutation successfully. Then we improve the 4-round Morawiecki' distinguisher of the Keccak algorithm by using the propagation characteristics of the rotational pair. The research results show that our improved rotational distinguisher can distinguish the random permutation from the Keccak permutation with a higher probability， and the distinguish effect is better than Morawiecki's distinguisher.

differential cryptanalysis； Hash function； Keccak algorithm； random permutation

TP309

A

10.3969/j.issn.1001-0548.2016.02.024

2014 - 05 - 22；

2015 - 11 - 20

國家自然科學(xué)基金（60903199）；高等學(xué)校創(chuàng)新引智基地基金（B08038）；國家留學(xué)基金委項(xiàng)目（201506965088）

劉景美（1979 - ），女，博士，副教授，主要從事密碼分析與網(wǎng)絡(luò)安全方面的研究.