基于混沌的Hash函數(shù)的安全性分析

譚　雪　周　琥　王世紅

(北京郵電大學(xué)理學(xué)院　北京 100876)

?

基于混沌的Hash函數(shù)的安全性分析

譚雪周琥王世紅

(北京郵電大學(xué)理學(xué)院北京 100876)

摘要隨著現(xiàn)代密碼學(xué)的發(fā)展，Hash函數(shù)算法越來(lái)越占有重要的地位。針對(duì)基于耦合映像格子的并行Hash函數(shù)算法和帶密鑰的基于動(dòng)態(tài)查找表的串行Hash函數(shù)算法進(jìn)行了安全性分析。對(duì)于前者，發(fā)現(xiàn)耦合映像格子系統(tǒng)導(dǎo)致算法中存在一種結(jié)構(gòu)缺陷，在分組序號(hào)和分組消息滿足特定約束關(guān)系的條件下，無(wú)需復(fù)雜的計(jì)算可以直接給出特定分組和消息的中間Hash值。對(duì)于后者，分析了產(chǎn)生碰撞緩存器狀態(tài)的約束條件。在此條件下，找到算法的輸出碰撞的代價(jià)為O(2100)，遠(yuǎn)大于生日攻擊的代價(jià)。

關(guān)鍵詞Hash函數(shù)混沌碰撞安全性分析

0引言

Hash函數(shù)是密碼學(xué)中的一項(xiàng)重要技術(shù)，能夠?qū)⑷我忾L(zhǎng)度的消息壓縮成固定長(zhǎng)度的消息摘要，被廣泛應(yīng)用于消息認(rèn)證和數(shù)字簽名等方面。一個(gè)安全的Hash函數(shù)應(yīng)該能夠抵抗碰撞攻擊。所謂碰撞就是能夠找到兩個(gè)不同的消息使它們產(chǎn)生相同的Hash值。攻擊者可以利用碰撞攻擊來(lái)偽造消息，因此抗碰撞特性是非常重要的。

在密碼學(xué)Hash函數(shù)中，傳統(tǒng)的Hash算法有MD5[1]、SHA-1[2]，以及最新提出的SHA-3標(biāo)準(zhǔn)Keccak算法[3]。隨著混沌動(dòng)力學(xué)的發(fā)展，越來(lái)越多的基于混沌的Hash算法相繼被提出。例如，有的是基于簡(jiǎn)單混沌映射的[4,5]，有的是基于混沌神經(jīng)網(wǎng)絡(luò)的[6-8]，還有基于耦合映像格子的[9-11]。隨著對(duì)Hash函數(shù)效率要求的提高，越來(lái)越多的并行Hash算法被提出[12-16]，這些算法為Hash函數(shù)的并行執(zhí)行提供了思路和方法，但有些算法仍然存在很多問(wèn)題，不能抵抗偽造攻擊，碰撞攻擊等[17-19]。

文獻(xiàn)[15]提出了一種并行的基于耦合映像格子的Hash函數(shù)，該算法將耦合映像混沌系統(tǒng)與并行結(jié)構(gòu)有效結(jié)合，達(dá)到了提高效率的目的。而文獻(xiàn)[20]提出的則是一種基于動(dòng)態(tài)查找表的帶密鑰的Hash函數(shù)，它是一種典型的串行結(jié)構(gòu)，利用混沌映射產(chǎn)生初值，經(jīng)過(guò)MD結(jié)構(gòu)的處理得到最終的Hash值。分析已有的Hash函數(shù)的安全性有助于設(shè)計(jì)安全的Hash函數(shù)。本文將對(duì)這兩個(gè)算法進(jìn)行安全性分析。

1基于耦合映像格子的并行Hash函數(shù)介紹

1.1近鄰耦合映像格子

基于耦合映像格子的并行Hash函數(shù)(簡(jiǎn)稱算法1)采用的是近鄰耦合映像格子，其表達(dá)式如下：

xn+1(i)=(1-ε)f(xn(i))+εf(xn(i+1))

(1)

其中，n=1,2,…，i=1,2,…,16。式(1)采用周期邊界條件，函數(shù)f是帳篷映射：

(2)

其中，xi∈(0,1)，b∈(0,1)分別是狀態(tài)變量和參數(shù)。

1.2算法1的描述

H=H0&H1&…&Hn-1

(3)

其中，運(yùn)算符號(hào)“&”的定義如下：

(4)

其中，S是符號(hào)“&”之前的中間Hash值運(yùn)算結(jié)果。例如，對(duì)于第一個(gè)&，S=H0，對(duì)于第二個(gè)&，S=H0&H1，依此類推。

圖1　算法1的整體結(jié)構(gòu)

1.3壓縮函數(shù)h的介紹

這里我們以分組消息Mj為例對(duì)壓縮函數(shù)做簡(jiǎn)要介紹。分組序號(hào)值j是64比特，如果分組序號(hào)值大于264，則分組序號(hào)值j=jmod264。初始變量IV，分組消息Mj和分組序號(hào)值j由8比特的分組表示，即：

IV=IV(0)|IV(1)|…|IV(15)

Mj=Mj(0)|Mj(1)|…|Mj(15)

(5)

j=j(0)|j(1)|…|j(7)

將上述式子轉(zhuǎn)化為實(shí)數(shù)形式：

fIV(i)=(IV(i)+0.8)/256i=0,1,…,15

(6)

fMj(i)=(Mj(i)+0.8)/256i=0,1,…,15

(7)

fj(i)=(j(i)+0.8)/256i=0,1,…,7

(8)

利用上述實(shí)數(shù)值初始化式(1)的狀態(tài)值X0(i)和參數(shù)值b(i)：

X0(i)=fj(i),i=0,1,…,7X0(i)={[fMj(i)+fMj(i-8)]/2+fj(i-8)}/2i=8,9,…,15

(9)

b(i)=0.5+0.01×fIV(i)i=0,1,…,15

(10)

迭代式(1)，迭代次數(shù)為k+10a，k=55，a=?j/264」，j是相應(yīng)的分組序號(hào)。

以不同的參數(shù)和初始值再次迭代耦合格子，迭代次數(shù)為k=55。為了便于區(qū)分，耦合格子表示為：

Yn+1(i)=(1-ε)f(Yn(i))+εf(Yn(i+1))i=1,2,…,16

(11)

其中，初值和參數(shù)分別為：

Y0(i)=fMj(i)i=0,1,…,15

(12)

b(i)=Xk+10a(i)i=0,1,…,15

(13)

將式(11)的輸出變量表示為二進(jìn)制，每個(gè)變量取小數(shù)點(diǎn)后9至16位的8個(gè)比特組成128比特的Zj，那么中間Hash值為：

Hj=Mj⊕Zj

(14)

2算法1的安全性分析

在下面分析中，假設(shè)初始向量IV的16個(gè)分組相同，即：

IV(0)=IV(1)=…=IV(15)

(15)

那么根據(jù)式(6)和式(10)可知，式(1)的16個(gè)參數(shù)b(i)的值相等。

圖2　兩個(gè)消息分組的循環(huán)移位關(guān)系圖

由圖2可知，如果：

X0(0)=X0(8)

(16)

Mj(8)+Mj(0)=j(0)

(17)

即當(dāng)分組序號(hào)值j和分組消息明文Mj滿足式(17)時(shí)，可以在分組序號(hào)值j和分組消息明文Mj都左循環(huán)1字節(jié)的情況下，使式(1)中的初始值也左循環(huán)1字節(jié)，再根據(jù)1.3節(jié)中介紹的原算法的計(jì)算步驟，很容易推出以下關(guān)系式：

Hj′=Hj<<<1

(18)

即j′分組的中間散列值Hj′為j分組的中間散列值Hj循環(huán)左移1字節(jié)。

根據(jù)上面的分析可以得到如下結(jié)論：在IV滿足式(15)，Mj和j滿足式(17)的條件下，如果已知消息分組Mj及其對(duì)應(yīng)的中間Hash值Hj，那么無(wú)需復(fù)雜的計(jì)算就可以準(zhǔn)確地知道第j′=j<<<1個(gè)消息分組Mj′=Mj<<<1的中間Hash值Hj′，即Hj′=Hj<<<1。

同理，我們很容易推算出Mj和j在不同循環(huán)移位位數(shù)的情況下，Mj和j滿足的關(guān)系，如表1所示。在此條件下，輸出的中間散列值也滿足相應(yīng)的循環(huán)移位關(guān)系。

表1　Mj和j在不同的循環(huán)移位條件下，Mj和j滿足的關(guān)系

續(xù)表1

綜上所述，當(dāng)消息分組Mj和位置參數(shù)j滿足表1中約束條件的情況下，根據(jù)消息Mj及其中間Hash值Hj可以直接得到Hj′的值，那么我們就可以偽造出消息Mj′，從而找到碰撞。

3帶密鑰的基于動(dòng)態(tài)查找表的Hash函數(shù)

3.1分段線性混沌映射

帶密鑰的基于動(dòng)態(tài)查找表的Hash函數(shù)(簡(jiǎn)稱算法2)采用的是分段線性混沌映射(PWLCM)，其表達(dá)式如下：

(19)

其中，x(k)∈[0,1]是狀態(tài)變量，參數(shù)α∈(0,0.5)。初值x(0)和參數(shù)α是密鑰。

3.2轉(zhuǎn)移函數(shù)、查找表和復(fù)合函數(shù)

算法2中有四個(gè)32比特的緩存器T,U,V,W，用四個(gè)轉(zhuǎn)移函數(shù)f0,f1,f2,f3來(lái)更新緩存器的狀態(tài)值。四個(gè)轉(zhuǎn)移函數(shù)的定義如下：

(20)

(21)

(22)

(23)

算法2是基于動(dòng)態(tài)查找表的Hash函數(shù)，表2給出的是初始查找表的一部分。其中Index∈[0,255]代表輸入消息，Quaternary是Index對(duì)應(yīng)的四進(jìn)制數(shù)，對(duì)于每一個(gè)Index=β3β2β1β0(四進(jìn)制數(shù))，F(xiàn)index(*)表示index下的復(fù)合函數(shù)：

Findex(*)=Fβ3β2β1β0(*)=fβ3°fβ2°fβ1°fβ0

(24)

式(24)決定了四個(gè)緩存器T、U、V、W的更新順序。所謂動(dòng)態(tài)查找表意味著index與四進(jìn)制數(shù)一一對(duì)應(yīng)的關(guān)系發(fā)生變化。

表2　初始查找表的一部分

3.3算法2的具體描述

算法2對(duì)消息的處理整體結(jié)構(gòu)如圖3所示。

圖3　算法2的整體結(jié)構(gòu)圖

(1) 緩存器初始化

選取初值x(0)和參數(shù)α，迭代分段線性映射式(19)128次，得到128個(gè)狀態(tài)值，如果狀態(tài)值小于0.5，取整數(shù)0，否則取整數(shù)1。把得到的128比特分別賦給緩存器T，U，V，W，每個(gè)狀態(tài)值是32比特。

(2) 消息處理

對(duì)任意長(zhǎng)度的輸入消息按MD5的填充規(guī)則進(jìn)行填充，使得填充后的消息長(zhǎng)度是l=128比特(分組長(zhǎng)度)的整數(shù)倍。由圖3可知，消息分組Mi(i=1,2,…,p)按順序處理。下面重點(diǎn)描述壓縮函數(shù)Hk的處理。壓縮函數(shù)主要由以下步驟組成：

更新緩存器根據(jù)查找表找到index對(duì)應(yīng)的四進(jìn)制數(shù)β3β2β1β0，再由其對(duì)應(yīng)的復(fù)合函數(shù)Findex(*)確定T，U，V，W的處理順序，結(jié)合循環(huán)移位τi的值，計(jì)算式(20)-式(23)。

s?s+Y(mod256)s+Y+1(mod256)?s+2Y+1(mod256)s+2Y+2(mod256)?s+3Y+2(mod256)…s+15Y+15(mod256)?s+16Y+15(mod256)

(25)

式(25)表示箭頭左右兩個(gè)index對(duì)應(yīng)的四進(jìn)制數(shù)進(jìn)行位置交換。

輸出緩存器值所有子分組處理完成得到新的值newT,newU,newV,newW，將初始緩存器值與新的值進(jìn)行異或，即T=T⊕newU，U=U⊕newV，V=V⊕newW和W=W⊕newT。

(3) Hash值輸出

所有消息分組都處理完之后，最終的Hash值就是處理最后一個(gè)消息的輸出，即Hk(M)=Hk(Mp)=T‖U‖V‖W。

4算法2的安全性分析

4.1碰撞攻擊

(26)

(27)

(28)

(29)

(30)

(31)

(T14+U14⊕X)<<3=T14(U14+T14⊕X)>>3=U14

(32)

其中X=V14⊕W14⊕(232-1)。求解式(32)，可以發(fā)現(xiàn)，當(dāng)X=0時(shí)，U14=T14=0；當(dāng)X=232-1時(shí)，U14=T14=232-1。由于X=V14⊕W14⊕(232-1)，也就意味著有232個(gè)V14和W14的組合，即式(32)總共有233個(gè)解。

下面我們來(lái)計(jì)算尋找上述碰撞所付出的代價(jià)。

表和對(duì)應(yīng)所有特殊狀態(tài)合成函數(shù)和解的個(gè)數(shù)

結(jié)合表3所顯示的12種不同消息狀態(tài)，找到一對(duì)消息碰撞需要付出的代價(jià)為O(2103/12)≈O(2100)，遠(yuǎn)大于生日攻擊的代價(jià)O(264)。

4.2多碰撞攻擊

對(duì)于一個(gè)Hash函數(shù)H，如果可以找到多個(gè)不同的消息M1，M2，…，MK使得它們有相同的Hash值輸出，那么就稱M1，M2，…，MK是該Hash函數(shù)的K個(gè)碰撞，即多碰撞。

對(duì)于一個(gè)迭代型的Hash函數(shù)，如果它的內(nèi)部狀態(tài)為w比特，最終的Hash值輸出為n比特，那么只有當(dāng)w≥2n時(shí)，它才能抵抗多碰撞攻擊。

根據(jù)對(duì)算法2的分析，我們發(fā)現(xiàn)，處理消息過(guò)程中由于動(dòng)態(tài)查找表的存在，它的內(nèi)部狀態(tài)空間由2128變?yōu)?136。算法2類似一個(gè)擴(kuò)展了內(nèi)部狀態(tài)空間的MD結(jié)構(gòu)，傳統(tǒng)的MD結(jié)構(gòu)已經(jīng)被證明是不抵抗多碰撞攻擊的，即使本算法內(nèi)部狀態(tài)已經(jīng)有所擴(kuò)展，但其內(nèi)部狀態(tài)未達(dá)到理想的2256，因此是不能抵抗多碰撞攻擊的。

4.3算法2的改進(jìn)思路

對(duì)于串行的Hash函數(shù)，最有力的攻擊就是多碰撞攻擊，我們所知道的寬管道結(jié)構(gòu)和海綿結(jié)構(gòu)都是抵抗該攻擊的串行Hash結(jié)構(gòu)。由這兩種結(jié)構(gòu)得到啟發(fā)，若要使得算法2有效抵抗多碰撞攻擊，需要對(duì)其內(nèi)部狀態(tài)進(jìn)行擴(kuò)展或?qū)ψ罱K輸出狀態(tài)進(jìn)行截?cái)嗷驂嚎s。由于現(xiàn)代安全Hash函數(shù)要求輸出Hash值長(zhǎng)度至少為128比特，所以我們的改進(jìn)建議是對(duì)算法2的內(nèi)部狀態(tài)進(jìn)行相應(yīng)的擴(kuò)展，使其空間至少為2256，這樣就可以抵抗多碰撞攻擊。

5結(jié)語(yǔ)

本文對(duì)兩個(gè)基于混沌的散列函數(shù)算法進(jìn)行了安全性分析。基于耦合映像格子的并行散列函數(shù)，由于耦合映像格子系統(tǒng)的特點(diǎn)導(dǎo)致算法結(jié)構(gòu)上存在著缺陷，在滿足一定的約束條件下，特定分組的特定消息的中間Hash值也是特定的，這種特性是不符合安全Hash算法的要求的。對(duì)基于動(dòng)態(tài)查找表的帶密鑰的Hash函數(shù)，我們從結(jié)構(gòu)分析的角度發(fā)現(xiàn)，在已知密鑰的情況下，可以用O(2100)的代價(jià)找到其輸出碰撞，此代價(jià)遠(yuǎn)大于生日攻擊的代價(jià)，該算法可以抵抗生日攻擊。由于算法內(nèi)部狀態(tài)比特值不足以達(dá)到輸出狀態(tài)比特值的2倍，因此是不能抵抗多碰撞攻擊的。為了能夠抵抗多碰撞攻擊，需要對(duì)內(nèi)部狀態(tài)進(jìn)行擴(kuò)展。

參考文獻(xiàn)

[1]RivestR.TheMD5message-digestalgorithm[J/OL].RFC1321,1992(1):1-21.https://tools.ietf.org/html/rfc1321.

[2]EastlakeD,JonesP.USSecureHashAlgorithm[J/OL].RFC3174,2001(1):1-22.http://www.hjp.at/doc/rfc/rfc3174.html.

[3]BertoniG,DaemenJ,PeetersM,etal.Keccak[C]//AdvancesinCryptology-EUROCRYPT2013.SpringerBerlinHeidelberg,2013:313-314.

[4]XiaoD,LiaoX,DengS.One-wayHashfunctionconstructionbasedonthechaoticmapwithchangeable-parameter[J].Chaos,Solitons&Fractals,2005,24(1):65-71.

[5]YiX.Hashfunctionbasedonchaotictentmaps[J].CircuitsandSystemsII:ExpressBriefs,IEEETransactionson,2005,52(6):354-357.

[6]LianS,LiuZ,RenZ,etal.Hashfunctionbasedonchaoticneuralnetworks[C]//CircuitsandSystems,2006.ISCAS2006.Proceedings.2006IEEEInternationalSymposiumon.IEEE,2006:4.

[7]XiaoD,LiaoX.Acombinedhashandencryptionschemebychaoticneuralnetwork[M]//AdvancesinNeuralNetworks-ISNN2004.SpringerBerlinHeidelberg, 2004:633-638.

[8]LianS,SunJ,WangZ.Securehashfunctionbasedonneuralnetwork[J].Neurocomputing,2006,69(16):2346-2350.

[9]WangS,HuG.Hashfunctionbasedonchaoticmaplattices[J].Chaos:AnInterdisciplinaryJournalofNonlinearScience,2007,17(2):023119.

[10]WangY,LiaoX,XiaoD,etal.One-wayhashfunctionconstructionbasedon2Dcoupledmaplattices[J].InformationSciences,2008,178(5):1391-1406.

[11]LiD,HuG,WangS.Akeyedhashfunctionbasedonthemodifiedcoupledchaoticmaplattice[J].CommunicationsinNonlinearScienceandNumericalSimulation,2012,17(6):2579-2587.

[12]XiaoD,LiaoX,DengS.Parallelkeyedhashfunctionconstructionbasedonchaoticmaps[J].PhysicsLettersA,2008,372(26):4682-4688.

[13]XiaoD,LiaoX,WangY.Parallelkeyedhashfunctionconstructionbasedonchaoticneuralnetwork[J].Neurocomputing,2009,72(10):2288-2296.

[14]DuMK,HeB,WangY,etal.ParallelHashFunctionBasedonBlockCipher[C]//E-BusinessandInformationSystemSecurity,2009.EBISS’09.InternationalConferenceon.IEEE,2009:1-4.

[15]WangY,WongKW,XiaoD.Parallelhashfunctionconstructionbasedoncoupledmaplattices[J].CommunicationsinNonlinearScienceandNumericalSimulation,2011,16(7):2810-2821.

[16]LiaoD,WangXM.ParallelhashfunctionusingDM-basedinteger-valuedchaoticmapsnetwork[EB/OL].SciencepaperOnline,(2012-12-17).[2012-12-17].http://www.paper.edu.cn/releasepaper/content/201212-353.

[17]GuoW,WangX,HeD,etal.Cryptanalysisonaparallelkeyedhashfunctionbasedonchaoticmaps[J].PhysicsLettersA,2009,373(36):3201-3206.

[18]HuangZ.Amoresecureparallelkeyedhashfunctionbasedonchaoticneuralnetwork[J].CommunicationsinNonlinearScienceandNumericalSimulation,2011,16(8):3245-3256.

[19]ZhouH,WangSH.Collisionanalysisofaparallelkeyedhashfunctionbasedonchaoticneuralnetwork[J].Neurocomputing,2012,97:108-114.

[20]LiYT,XiaoD,DengSJ.Keyedhashfunctionbasedonadynamiclookuptableoffunctions[J].InformationSciences,2012,214:56-75.

CRYPTANALYSIS OF HASH FUNCTIONS BASED ON CHAOTIC SYSTEM

Tan XueZhou HuWang Shihong

(School of Science,Beijing University of Posts and Telecommunications,Beijing 100876,China)

AbstractWith the development of modern cryptology, hash functions play an increasingly important role. In this paper, we analyse the security of two hash algorithms, one is a parallel hash function construction based on coupled map lattice, the other is the keyed serial hash function based on a dynamic lookup table. For the former, we find that the coupled map lattice leads to a structural defect in the algorithm. Under the condition of block index and block message meeting specific constraint, without the complicated computation it is able to directly give the intermediate hash value of the specific block index and block message. For the latter, we analyse the constraint condition of the state of a buffer that the collision is produced. Under this condition, the cost of output collisions of the algorithm found is O (2100), much higher than that of the birthday attack.

KeywordsHash functionChaoticCollisionSecurity analysis

收稿日期：2014-12-29。譚雪，碩士生，主研領(lǐng)域：混沌密碼。周琥，碩士生。王世紅，教授。

中圖分類號(hào)TP399

文獻(xiàn)標(biāo)識(shí)碼A

DOI:10.3969/j.issn.1000-386x.2016.06.076