基于混沌的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结语

本文对两个基于混沌的散列函数算法进行了安全性分析。基于耦合映像格子的并行散列函数，由于耦合映像格子系统的特点导致算法结构上存在着缺陷，在满足一定的约束条件下，特定分组的特定消息的中间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