基于混沌动态参数的散列函数.doc

第10期郭伟等：基于混沌动态参数的散列函数101基于混沌动态参数的散列函数郭伟1,2, 曹杨1,2, 王小敏2, 何大可1,2（1. 西南交通大学 信息安全与国家计算网格实验室，四川 成都610031；2. 西南交通大学 信息科学与技术学院，四川 成都610031）摘 要：结合混沌系统与传统单向散列函数的优点，提出了一种基于混沌动态参数的带密钥单向散列函数构造方案。该方案以混沌系统生成动态参数，替换传统散列算法中的固定参数参与轮函数的运算并生成散列摘要。与现有混沌散列算法相比，新方案没有将消息分组直接参与混沌迭代，而采用传统散列算法作为散列迭代的核心，充分吸取了传统散列函数迭代结构完善且处理速度高的优点，在利用混沌动态参数提高散列算法安全性的同时有效地避免了混沌系统对算法速度的影响。研究结果表明：新方案具有很好的单向性、初值/密钥敏感性和较大的密钥空间，且速度快，易于实现。关键词：散列函数；混沌；动态参数中图分类号：TP 309.2 文献标识码：A 文章编号：1000-436X(2008)10-0093-08One-way hash function with chaotic dynamic parametersGUO Wei1, 2, CAO Yang1, 2, WANG Xiao-min2, HE Da-ke1,2(1. Laboratory of Information Security & National Computing Grid, Southwest Jiaotong University, Chengdu 610031, China;2. School of Information Science & Technology, Southwest Jiaotong University, Chengdu 610031, China)Abstract: A novel keyed one-way hash function based on chaotic dynamic parameters was presented which combines the advantage of both chaotic system and conventional one-way hash function. In the proposed approach the fixed parameters of conventional hash function is replaced by chaotic dynamic parameters. Compared with the existing chaotic hash functions, the new method takes conventional hash function as essential part of iteration instead of using the message blocks directly in chaotic iteration, thus improves the security of hash function and avoids bringing down system performance at the same time. Theoretical and experimental results show that the proposed method has high performance, strong one way property, large key space, sensitivity to initial conditions and chaotic systems parameters.Key words: hash function; chaos; dynamic parameter1 引言收稿日期：2008-06-20；修回日期：2008-09-27基金项目：国家自然科学基金资助项目（60702025）；西南交通大学博士创新基金资助项目（2006）Foundation Items：The National Natural Science Foundation of China(60702025)；The Doctoral Innovation Fund of Southwest Jiaotong University(2006)单向散列函数根据是否使用密钥，分为带密钥的散列函数(K-HF, keyed-hash function)和不带密钥的散列函数1。传统的K-HF构建方案主要可以归为两类：一类是使用分组密码的方案，另一类是使用专用散列函数的方案。由于前者效率较低，更多方案是基于专用散列函数的。专用散列函数，其压缩函数是专为散列迭代而设计，一般基于复杂度假设构造，利用异或、模加和移位等逻辑运算进行多轮分组迭代，可以达到很高的数据处理速度。MD5和SHA-12, 3是两种重要的专用散列算法，为了达到较好的置乱效果，它们在每步迭代中都使用了一些固定参数参与运算，但这些固定参数对于抵抗差分分析等攻击手段没有任何作用4, 5。2004年以来，对MD5、SHA-1等专用散列函数的差分碰撞攻击有了重大的进展，直接使用MD5函数已被证明是不安全的6。近年来，利用混沌系统的确定性和对初值的敏感性来构造散列算法成为了国内外研究的热点。文献710分别用广义混沌映射切换、时空混沌、超混沌和可变参数的分段线性混沌映射(PWLCM，piecewise linear chaotic map)来构造单向散列函数。它们均用消息分组直接参与混沌迭代，使用了越来越复杂的混沌函数，在增加了算法复杂度的同时安全性并没有得到显著提高。现有混沌散列算法很少借鉴传统密码学理论中的散列设计思路，文献11给出了现有的部分混沌散列函数由于迭代结构设计不严谨或者明文分组处理不恰当而造成的碰撞缺陷。文献12提出了利用传统密码学中的经典理论来构造兼顾安全性和复杂度的混沌单向散列算法的新思路，但文中提出的算法是基于分组密码中的S-Box结构，其S-Box的构建方式复杂且迭代效率低，算法速度受到了很大的限制，安全性也没有得到充分的检验。另外，该文在构建密钥空间时将初始迭代次数作为密钥的一部分，导致密钥空间与运算速度处于矛盾的地位。针对现有混沌单向散列算法的不足，本文提出了基于混沌参数的Keyed-Chaotic-MD5/SHA1算法。新算法首先选择了一个混沌Tent映射Gn (xi)，将混沌控制参数、系统初值x0和位移参数s作为密钥K=(, x0, s )，用混沌控制参数和系统初值x0控制混沌系统迭代，并用固定长度比特流作为位移参数对混沌系统的输出进行移位操作，输出数据经筛选和截取后作为动态参数，替换原MD5/SHA-1算法中的固定参数参与散列运算。新算法没有将消息分组直接参与混沌迭代，而将现有的成熟散列算法MD5和SHA-1作为迭代运算的核心，利用离散混沌系统对初值和参数的极端敏感性、混沌序列的白噪声统计特性和遍历性等优良特性构建混沌动态参数。在散列迭代的每一步以混沌动态参数替代原有的固定参数参加运算。新算法充分吸取了专用散列函数迭代结构较完善且处理速度较高的优点，在提高系统安全性的同时极大地提高了算法效率。理论分析和实验结果表明了新算法具有很好的单向性、置乱性、初值与密钥敏感性，且兼顾安全性和复杂度，是一个易于实现的K-HF算法。2 符号说明Gm (x0)：G为扩展Tent映射函数，为混沌控制参数，x0为混沌系统初值，m为初始迭代次数。x(n)：混沌函数G迭代n次的输出，即x(n) = Gn(x0)。ai ：混沌函数经过初始迭代m次，再迭代i次的输出，即ai = Gm+i (x0) = x(m+i)。ai(n) ：表示ai右起的第(n+1) bit，ai的二进制形式可以表示为ai (63) ai(62) ai(1) ai(0)。Tx ：MD5和SHA-1中使用的固定参数，宽度为32 bit。s：位移参数，长度为2p。s的二进制形式可以表示为s(2p-1) s (2p-2) s (1) s (0)。对于Keyed-Chaotic- MD5函数，p取值为68；对于Keyed-Chaotic-SHA1函数，p取值为85。| s(2n-1) s(2n-2)| ：二进制流s(2n-1) s(2n-2)的算术值，有0、1、2、3共4种取值。：表示ai右起第(32+ |s(2i-1)s(2i-2)|)bit。bj ：新算法中的动态参数，宽度为32bit，j1, , p-1, p。3 混沌系统与K-HF3.1 MD5与SHA-1函数MD5和SHA-1是两种基于Merkle-Damgrd迭代结构13的散列函数，能将任意长度的消息分别转换成128bit和160bit消息摘要。在MD5和SHA-1算法的实现中要使用大量的固定参数。MD5中共有68个参数，其中有4个是寄存器的初始值，其余64个参数则是每步运算所对应的工作参数Tx，Tx=232abs(sinx)，1x64。SHA-1中共有85个参数，其中有5个参数是寄存器的初始值，其余80个参数则是每步运算中所使用的工作参数Tx，Tx描述如下：Tx = 0x 5a827999 for 1x20= 0x 6ed9eba1 for 21x40= 0x 8f1bbcdc for 41x60= 0x ca62c1d6 for 61x80对于MD5和SHA-1算法，这些固定参数参与了每一步的迭代运算。比如在SHA-1运算中，首先需要分别将5个初始值IV0(A)、IV0(B)、IV0(C)、IV0(D)、IV0(E)注入对应的寄存器中，然后参数T1到T80将分别参与算法的第1步到第80步的迭代运算。这些预先固定的参数在运算中主要起到置乱的作用，对于抵抗差分分析没有任何效果。3.2 混沌系统与K-HF与不带密钥的散列函数相比，K-HF会随密钥的改变而生成不同的摘要，这样就可以在完整性验证的同时实现源认证，因而K-HF在认证、密钥共享和软件保护等方面有着广泛的应用14。混沌是指确定性非线性系统普遍具有的一种复杂动力学行为，它对系统初始状态或系统参数异常敏感。混沌序列具有遍历性和类噪声统计特性，因此，混沌映射本身是不可逆和难以长期预测的。K-HF要求充分的密钥敏感性和足够大的密钥空间来抵御统计分析和暴力搜索等攻击。而混沌系统对初值或参数极端敏感，生成的混沌序列具有良好的统计特性，且其初值或参数取值空间在理想状态下可以无穷大。将专用散列函数中的固定参数用特性良好的混沌序列来替代，并将混沌系统的初值和参数作为密钥所构建的K-HF，不仅保证了其强度，也解决了对于混沌散列中将消息分组的线性变换直接参与混沌迭代而引起的计算量问题。3.3 混沌Tent映射Tent映射是一个PWLCM，定义如下(1)文献15基于F引入了一个混沌特性较好的扩展Tent映射，定义如下 (2)其中0|-0.5|I，01，F()，I为一个足够小的间隔。由于xi-1=0, 1的情况较少，所以一般不作为混沌参数使用。在理想情况下，映射(2)对密钥和初值非常敏感，并且在(0, 1)区间服从均匀分布16。但由于混沌系统数字化实现中的有限字长效应，映射(2)的特性将受到影响。为尽量减小有限字长效应，本文将计算精度设定为双精度浮点运算。根据IEEE-754实数编码标准，双精度浮点数的符号位为ai (63)，阶位为ai (62), ai (61), , ai (52)，尾数位为ai (51), ai (50), , ai (0)。通过观察，可以发现混沌迭代中符号位不会发生变化，阶位变化也很缓慢，而尾数位中位数越低变化速度越快。为了让混沌动态参数更加合理，参数将从混沌迭代输出ai的尾数位ai (34), ai (33), , ai (0) 这35bit中选取。图1是混沌系统(2)迭代5 000次后，这35bit混沌序列的算术值分布情况。可以看到，选定的部分混沌序列的算术值在0235-1之间均匀分布，具备了构造K-HF的条件。图1 扩展Tent映射部分混沌序列分布4 基于混沌动态参数的K-HF构造本文引入扩展Tent映射G来构造动态参数，在随机特性得到了保证后，还应注意两个方面：一是动态参数不能重复，二是有足够的密钥空间。为此引入参数筛选逻辑和位移控制逻辑。前者通过比对筛选可以防止生成重复的动态参数；后者则根据密钥中的位移参数控制混沌输出按位右移，从而增加了输出序列的安全性并令密钥空间进一步加大。图2和图3分别是Keyed-Chaotic-MD5的结构和Keyed-Chaotic- MD5/SHA1算法流程，两种算法描述如下。1) 将混沌控制参数、混沌系统初值x0和位移参数s作为密钥K，K=(, x0, s)，固定为01之间的常数，初始化参数i，j=1。对混沌系统G(x0)进行初始迭代，共m次。2) 混沌系统G(x0)继续迭代1次，对应的混沌输出ai = Gm+i (x0)，即ai是G(x0)完成m次初始迭代后继续迭代i次的输出。3) 对于混沌输出ai进行移位和截取处理。根据混沌迭代步数i确定位移参数s中对应比特的算术值|s(2i-1) s(2i-2)|，并以此控制输出序列ai按位右移。图2 Keyed-Chaotic-MD5的结构图3 Keyed-Chaotic-MD5/SHA1算法流程然后截取序列末尾32bit作为动态参数。输出的参数可表示为。由于|s(2i-1) s(2i-2)|的取值范围为03，所以动态参数实际是从ai (34), ai (33), , ai (0)这35bit中选取。4) 对混沌参数进行筛选(3)其中，。如果ai满足式(3)，则bj =然后j+1；否则舍去。5) 判断是否大于，成立则执行6)；否则i+1，同时转2)。6) 将b1, b2, , bp依次写入Tx和IV0。7) Keyed-Chaotic-MD5/SHA1算法将固定参数替换为动态参数后，在散列运算中沿用MD5和SHA-1算法的轮函数、迭代结构以及消息的分组、填充和扩展模式。5 算法分析5.1 算法的密钥空间分析一个安全的K-HF要求有足够大的密钥空间来保证算法强度，一般要求密钥长度不能低于128bit。新算法的密钥K来源于三个方面，即混沌控制参数、系统初值x0和位移参数s。混沌控制参数和系统初值x0由于受到了有限字长效应的影响，只能在有限范围内取值。算法定义中和x0都是双精度浮点数，长度为64bit。但混沌控制参数需在0|-0.5|I的范围内取值，当I取值为0.01时，混沌映射(2)在区间(0, 1)中满足均匀分布17。所以需在(0.49, 0.51)区间内取值，根据IEEE-754标准，双精度浮点数的有效小数位数为1516位，因此，其密钥空间约为21013。而由于x0的取值范围是(0,1)，则其取值空间约为1015。对于Keyed-Chaotic- MD5/SHA1算法，其位移参数s的分别是136bit和170bit，则相应的密钥空间分别是2136和2170。综合起来，Keyed-Chaotic-MD5算法的密钥空间为2101310152136=2230，而Keyed-Chaotic-SHA1算法的密钥空间为2101310152170=2264。新算法的密钥空间远大于现有暴力破解能力的边界值。5.2 算法的初始迭代次数分析新算法所需的动态参数取自混沌迭代输出的ai (34), ai (33), , ai (0) 这35bit，下面将对于这35bit在混沌迭代中的变化速度做定量的分析。参照文献12的测试方法，考虑混沌控制参数的取值范围为0|-0.5|0.01，混沌系统初值x0的取值区间为(0, 1)。随机选取一组参数(, x0)，针对双精度浮点数的有效计算精度10-15，设=+10-15， =-10-15，x0= x0+10-15，x0 = x0-10-15，选取以下5组参数(, x0)，(, x0) ，(, x0) ，(, x0) ，(, x0)，分别作为混沌映射(2)的混沌控制参数和初值，生成的混沌输出序列取其末尾35bit，记为序列B, B1, B2, B3, B4。将序列B与其他4组序列的差别比特数目记为L1, L2, L3, L4。考察100组不同取值的参数，做出曲线如图4所示。由图4中的仿真结果可以看出，在迭代37次的时候，4组数据都基本变化了总位数的一半。可以认为这时输出序列B1, B2, B3, B4与原序列B已经是完全不同的序列。所以对于混沌输出的末尾35bit，参数和x0在双精度允许范围内的任何微小扰动，经混沌迭代37次以后均可得到差别很大序列，由此将混沌初始迭代次数m定为40。图4 混沌序列末尾35bit变化情况5.3 算法的单向性和碰撞分析新算法由两部分构成：一是以MD5和SHA-1算法为核心的迭代结构，二是由密钥控制的混沌动态参数生成系统。MD5和SHA-1算法均是成熟散列算法，单独使用的情况下均具有很好的单向性。采用它们作为新算法的迭代结构，使得攻击方即使在已知密钥的情况下仍无法由散列摘要恢复出明文的任何信息。混沌动态参数的引入则进一步提高新算法的抗碰撞能力。原MD5和SHA-1算法由于其使用的寄存器初值和工作参数固定，使其对于差分碰撞攻击抵御能力较弱。而新算法的寄存器初值与每一步迭代所使用的工作参数，都会随密钥K = (, x0, s)的改变而改变。混沌系统的确定性和初值敏感性使得混沌动态参数对密钥K极端敏感，对没有掌握密钥K的敌手，将无法知道确切的寄存器初值与每步迭代的工作参数，使得攻击方无法找到攻击的启动点。6 Keyed-Chaotic-MD5/SHA1的安全性分析6.1 混乱与扩散性质统计分析在Shannon的信息论中提出了混乱与扩散的概念，加密体制中要求明文在密文空间中充分的扩散与混乱，K-HF中同样如此，不仅要求相应明文与对应的散列 值不相关，同时还要求密钥敏感性。散列结果的二进制表示中每比特只取0或1，因此理想的散列函数应该是密钥或初值的每比特变化都将导致散列结果的每比特都以50 %的概率变化。通常定义下面4个统计变量对新算法进行混乱与扩散的统计分析。平均变化比特数(4)平均变化概率(5) (6)B的均方差 (7)P的均方差(8)(9)其中N为统计次数，Bi为第i次测试结果的变化比特数。初值敏感测试：在明文空间中随机选取一段明文进行散列测试，然后改变明文任意1bit的值，得到另一散列结果，比较两者差别的比特数目。由于新算法是基于MD5/SHA1迭代结构的K-HF算法，在密钥固定情况下，新算法的初值敏感性与MD5/SHA-1算法接近。N次比较的结果如表1和表2所示。表1 Keyed-Chaotic-MD5算法初值敏感测试迭代次数2565121 0242 048总平均64.22364.02164.06664.19564.126B6.0035.5885.6865.7385.754PMD5/%50.17450.01750.04950.15350.098 PMD5/%4.69 4.3654.4424.4784.494Bmax80 82 85 83 82.5 Bmin51 46 48 40 46.25 表2 Keyed-Chaotic-SHA1算法初值敏感测试迭代次数2565121 0242 048总平均80.17680.19779.86079.86280.024B6.7956.5386.3566.2156.476PSHA1/%50.11 50.12349.91249.91450.015PSHA1/%4.2474.0863.9733.8844.0475Bmax101 100 99 102 100.5 Bmin61 59 61 60 60.25 密钥敏感性测试：为了考察密钥K=(, x0, s)对于散列结果的影响，计算随机选取的一段明文和密钥K的散列值，然后保持明文不变，随机改变密钥K的1bit数据，再次计算散列值并比较，N次比较的结果如表3和表4所示。表3 Keyed-Chaotic-MD5算法密钥敏感测试迭代次数2565121 0242 048总平均63.65664.22264.14963.91063.98425B5.4075.6745.7795.6135.61825PMD5/%49.73150.17350.11649.9349.9875PMD5/%4.2244.4324.5154.3854.389表4 Keyed-Chaotic-SHA1算法密钥敏感测试迭代次数2565121 0242 048总平均80.33280.06880.13679.88280.1045B6.0666.5435.9796.4446.258 PSHA1/%50.20750.04250.08549.92650.065 PSHA1/%3.7914.0893.7374.0273.911 由仿真数据的统计结果分析可见，对于输入明文或者密钥的微小变化，新算法的平均变化比特数和平均变化概率都已非常接近理想状况下的一半的变化概率，相当充分和均匀地利用了密文空间。而B、P标志着散列混乱与散布性质的稳定性，越接近0就越稳定，文中算法的都已很小，从而也可看出本文算法对明文的混乱与散布能力强而稳定。初值和密钥的极端敏感性，以及平均稳定的散布性使攻击者无法得到任何有用的统计信息，为抵御现有的已知密文攻击和差分线性攻击提供了很好的保证。6.2 算法速度比较下文对Keyed-Chaotic-MD5/SHA1算法的效率进行实验研究。实验中将本文提出的Keyed-Chaotic- MD5/SHA1算法与文献7, 8, 12提出的混沌散列方案进行仿真对比。为了数据的准确性，每组数据取100次测试结果的平均值。在32位计算机平台下，分别用5种算法对不同长度的随机数据计算摘要，其中Keyed-Chaotic-MD5/SHA1的混沌初始迭代次数取40，文献12所提算法的混沌初始迭代次数取100，散列摘要长度取128。各个算法计算时间见表5。表5混沌散列算法效率比较文本长度/bit501002001 0001104Keyed-Chaotic-MD5算法/ms0.007790.008210.007970.009800.01664Keyed-Chaotic-SHA1算法/ ms0.009540.009840.009780.012190.02997文献7算法/ms0.146180.217650.649982.4982918.54381文献8算法/ms28.12 83.12 482.55 16153.95 1243998.51 文献12算法/ms0.203600.256830.708862.0145211.76467从表5中可以看出，本文算法的效率远高于三个参考算法。文献7和文献8所提算法由于直接将消息分组参与到混沌迭代中，其时间复杂度与消息长度成正比，效率很低。而文献12的S-Box 散列虽然也采用了与本文类似的避免消息分组直接参与混沌迭代的思路，但由于S-Box构建过程复杂，迭代结构不够优化，与文献7的算法相比没有明显的效率优势。从混沌迭代次数上分析，初始迭代都取100次的情况下，S-Box 散列共需迭代2 148次，而本文提出的两种算法在最好情况下分别只需迭代168次和185次。由于新算法的分组为512bit，将表中文本长度为50bit、100bit、200bit三种情况与1 000bit、1104bit两种情况相比较，可以发现：在单分组的情况下，单独迭代过程所占时间比重很小，所以文本长度越长，新算法性能接近原MD5/SHA-1算法。7 结束语本文提出了一种基于混沌动态参数的单向散列函数构造方案。该方案将现有成熟散列算法作为散列迭代的核心，利用混沌系统生成的动态参数替代原有固定参数参与散列运算。仿真结果和理论分析表明：新算法具有很好的单向性；原始数据每比特的变化均将引起散列 值中近50 %比特发生改变，具有理想的明文雪崩特性；当初始迭代次数大于40时，密钥改变任意1bit都将引起散列 值中近50%比特发生改变，具有很高的密钥敏感性。借鉴了成熟散列算法高效安全的迭代结构，有很高的运算速度。新算法结合混沌系统对初值和参数的极端敏感性、混沌序列的白噪声统计性和遍历性，在兼顾安全性的同时实现了极高的数据处理速度。参考文献：1冯登国, 裴定一. 密码学导引M. 北京:科学出版社, 1999.FENG D G, PEI D Y. The Guide of CryptologyM. Beijing: Science Press, 1999.2RIVEST R L. The MD5 Message Digest AlgorithmS. RFC 1321, 1992.3National Institute of Standards and Technology. Secure Hash StandardS. Federal Information Processing Standard, 180-1, 1995.4WANG X Y, YU H B. How to break MD5 and other hash functionsA. Advances in Cryptology Eurocrypt05C. Aarhus, 2005. 19-35.5WANG X Y, YIN Y L, YU H B. Finding collisions in the full SHA-1A. Advances in Cryptology Crypto05C. Santa Barbara, 2005.17-36.6STEVENS M, LENSTRA A, DE W B. Target Collisions for MD5 and Colliding X.509 Certificates for Different IdentitiesR. Cryptology ePrint Archive, 2006, 360.7王小敏, 张家树, 张文芳. 基于广义混沌映射切换的单向散列函数构造J. 物理学报, 2003, 52(11): 2737-2742.WANG X M, ZHANG J S, ZHANG W F. One way hash function construction based on the extended chaotic maps switchJ. Acta Physica Sinica, 2003, 52(11): 2737-2742.8张瀚, 王秀峰, 李朝晖等. 基于时空混沌系统的单向散列函数构造J. 物理学报, 2005, 54(9): 4006-4011.ZHANG H, WANG X F, LI C H, et al. One way hash function construction based on spatiotemporal chaosJ. Acta Physica Sinica, 2005, 54(9): 4006-4011.9彭飞, 丘水生, 龙敏. 基于二维超混沌映射的单向散列函数构造J. 物理学报, 2005, 54(10): 4562-4568.PENG F, QIU S S, LONG M. One-way hash function construction based on two-dimensional hyper-chaotic mappingsJ. Acta Physica Sinica, 2005, 54(10): 4562-4568.10XIAO D, LIAO X F, DENG S J. One-way hash function construction based on the chaotic map with changeable-parameterJ. Chaos, Solitons and Fractals, 2005, 24: 65-71.11王继志, 王英龙, 王美琴. 一类基于混沌映射构造散列函数方法的碰撞缺陷J. 物理学