基于混沌的Hash函數的安全性分析

譚　雪　周　琥　王世紅

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

?

基于混沌的Hash函數的安全性分析

譚雪周琥王世紅

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

摘要隨著現代密碼學的發展，Hash函數算法越來越占有重要的地位。針對基于耦合映像格子的并行Hash函數算法和帶密鑰的基于動態查找表的串行Hash函數算法進行了安全性分析。對于前者，發現耦合映像格子系統導致算法中存在一種結構缺陷，在分組序號和分組消息滿足特定約束關系的條件下，無需復雜的計算可以直接給出特定分組和消息的中間Hash值。對于后者，分析了產生碰撞緩存器狀態的約束條件。在此條件下，找到算法的輸出碰撞的代價為O(2100)，遠大于生日攻擊的代價。

關鍵詞Hash函數混沌碰撞安全性分析

0引言

Hash函數是密碼學中的一項重要技術，能夠將任意長度的消息壓縮成固定長度的消息摘要，被廣泛應用于消息認證和數字簽名等方面。一個安全的Hash函數應該能夠抵抗碰撞攻擊。所謂碰撞就是能夠找到兩個不同的消息使它們產生相同的Hash值。攻擊者可以利用碰撞攻擊來偽造消息，因此抗碰撞特性是非常重要的。

在密碼學Hash函數中，傳統的Hash算法有MD5[1]、SHA-1[2]，以及最新提出的SHA-3標準Keccak算法[3]。隨著混沌動力學的發展，越來越多的基于混沌的Hash算法相繼被提出。例如，有的是基于簡單混沌映射的[4,5]，有的是基于混沌神經網絡的[6-8]，還有基于耦合映像格子的[9-11]。隨著對Hash函數效率要求的提高，越來越多的并行Hash算法被提出[12-16]，這些算法為Hash函數的并行執行提供了思路和方法，但有些算法仍然存在很多問題，不能抵抗偽造攻擊，碰撞攻擊等[17-19]。

文獻[15]提出了一種并行的基于耦合映像格子的Hash函數，該算法將耦合映像混沌系統與并行結構有效結合，達到了提高效率的目的。而文獻[20]提出的則是一種基于動態查找表的帶密鑰的Hash函數，它是一種典型的串行結構，利用混沌映射產生初值，經過MD結構的處理得到最終的Hash值。分析已有的Hash函數的安全性有助于設計安全的Hash函數。本文將對這兩個算法進行安全性分析。

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

1.1近鄰耦合映像格子

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

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

(1)

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

(2)

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

1.2算法1的描述

H=H0&H1&…&Hn-1

(3)

其中，運算符號“&”的定義如下：

(4)

其中，S是符號“&”之前的中間Hash值運算結果。例如，對于第一個&，S=H0，對于第二個&，S=H0&H1，依此類推。

圖1　算法1的整體結構

1.3壓縮函數h的介紹

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

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

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

(5)

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

將上述式子轉化為實數形式：

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)

利用上述實數值初始化式(1)的狀態值X0(i)和參數值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)，迭代次數為k+10a，k=55，a=?j/264」，j是相應的分組序號。

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

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

(11)

其中，初值和參數分別為：

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

(12)

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

(13)

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

Hj=Mj⊕Zj

(14)

2算法1的安全性分析

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

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

(15)

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

圖2　兩個消息分組的循環移位關系圖

由圖2可知，如果：

X0(0)=X0(8)

(16)

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

(17)

即當分組序號值j和分組消息明文Mj滿足式(17)時，可以在分組序號值j和分組消息明文Mj都左循環1字節的情況下，使式(1)中的初始值也左循環1字節，再根據1.3節中介紹的原算法的計算步驟，很容易推出以下關系式：

Hj′=Hj<<<1

(18)

即j′分組的中間散列值Hj′為j分組的中間散列值Hj循環左移1字節。

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

同理，我們很容易推算出Mj和j在不同循環移位位數的情況下，Mj和j滿足的關系，如表1所示。在此條件下，輸出的中間散列值也滿足相應的循環移位關系。

表1　Mj和j在不同的循環移位條件下，Mj和j滿足的關系

續表1

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

3帶密鑰的基于動態查找表的Hash函數

3.1分段線性混沌映射

帶密鑰的基于動態查找表的Hash函數(簡稱算法2)采用的是分段線性混沌映射(PWLCM)，其表達式如下：

(19)

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

3.2轉移函數、查找表和復合函數

算法2中有四個32比特的緩存器T,U,V,W，用四個轉移函數f0,f1,f2,f3來更新緩存器的狀態值。四個轉移函數的定義如下：

(20)

(21)

(22)

(23)

算法2是基于動態查找表的Hash函數，表2給出的是初始查找表的一部分。其中Index∈[0,255]代表輸入消息，Quaternary是Index對應的四進制數，對于每一個Index=β3β2β1β0(四進制數)，Findex(*)表示index下的復合函數：

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

(24)

式(24)決定了四個緩存器T、U、V、W的更新順序。所謂動態查找表意味著index與四進制數一一對應的關系發生變化。

表2　初始查找表的一部分

3.3算法2的具體描述

算法2對消息的處理整體結構如圖3所示。

圖3　算法2的整體結構圖

(1) 緩存器初始化

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

(2) 消息處理

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

更新緩存器根據查找表找到index對應的四進制數β3β2β1β0，再由其對應的復合函數Findex(*)確定T，U，V，W的處理順序，結合循環移位τi的值，計算式(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)表示箭頭左右兩個index對應的四進制數進行位置交換。

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

(3) Hash值輸出

所有消息分組都處理完之后，最終的Hash值就是處理最后一個消息的輸出，即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)，可以發現，當X=0時，U14=T14=0；當X=232-1時，U14=T14=232-1。由于X=V14⊕W14⊕(232-1)，也就意味著有232個V14和W14的組合，即式(32)總共有233個解。

下面我們來計算尋找上述碰撞所付出的代價。

表和對應所有特殊狀態合成函數和解的個數

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

4.2多碰撞攻擊

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

對于一個迭代型的Hash函數，如果它的內部狀態為w比特，最終的Hash值輸出為n比特，那么只有當w≥2n時，它才能抵抗多碰撞攻擊。

根據對算法2的分析，我們發現，處理消息過程中由于動態查找表的存在，它的內部狀態空間由2128變為2136。算法2類似一個擴展了內部狀態空間的MD結構，傳統的MD結構已經被證明是不抵抗多碰撞攻擊的，即使本算法內部狀態已經有所擴展，但其內部狀態未達到理想的2256，因此是不能抵抗多碰撞攻擊的。

4.3算法2的改進思路

對于串行的Hash函數，最有力的攻擊就是多碰撞攻擊，我們所知道的寬管道結構和海綿結構都是抵抗該攻擊的串行Hash結構。由這兩種結構得到啟發，若要使得算法2有效抵抗多碰撞攻擊，需要對其內部狀態進行擴展或對最終輸出狀態進行截斷或壓縮。由于現代安全Hash函數要求輸出Hash值長度至少為128比特，所以我們的改進建議是對算法2的內部狀態進行相應的擴展，使其空間至少為2256，這樣就可以抵抗多碰撞攻擊。

5結語

本文對兩個基于混沌的散列函數算法進行了安全性分析?；隈詈嫌诚窀褡拥牟⑿猩⒘泻瘮担捎隈詈嫌诚窀褡酉到y的特點導致算法結構上存在著缺陷，在滿足一定的約束條件下，特定分組的特定消息的中間Hash值也是特定的，這種特性是不符合安全Hash算法的要求的。對基于動態查找表的帶密鑰的Hash函數，我們從結構分析的角度發現，在已知密鑰的情況下，可以用O(2100)的代價找到其輸出碰撞，此代價遠大于生日攻擊的代價，該算法可以抵抗生日攻擊。由于算法內部狀態比特值不足以達到輸出狀態比特值的2倍，因此是不能抵抗多碰撞攻擊的。為了能夠抵抗多碰撞攻擊，需要對內部狀態進行擴展。

參考文獻

[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。譚雪，碩士生，主研領域：混沌密碼。周琥，碩士生。王世紅，教授。

中圖分類號TP399

文獻標識碼A

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