Whirlpool的一种改进算法

刘 飞，黄玉划，吴匡时

(南京航空航天大学信息科学与技术学院，江苏南京 210016)

现代密码学是由信息化社会催生的一门新型学科，随着信息化的发展和信息安全要求的不断提高，密码学进入一个飞速发展的时代。Hash函数在数字签名、身份认证、消息认证等领域有着广泛的应用。将分组密码的构造思想引入Hash函数，已经成为构造Hash函数最常见的方法之一，最具代表的一种算法就是Whirlpool算法，该算法的分组长度等于输出长度，相当于密钥长度等于分组长度的AES－128，但效率却是AES－128算法的1/2。文中将改进该算法，在不降低该算法的安全性的前提下，提高该算法的运行效率。

1 Whirlpool算法简介

2000年，Vincent Rijmen和 Paulo S.L.M.Barreto设计了 Whirlpool算法，它是目前 NESSIE(New European Schemes for Signature，Integrity，andEncryption)唯一推荐使用的Hash函数，同时它也被国际标准组织ISO(International Organization for Standardization)和国际电子技术协会IEC(International Electrotechnical Commission)采用作为ISO/IEC 10118－3国际标准。设计者称此Hash算法能抗线性分析和差分分析，而且取512位Hash值中的任意位数都能保证达到相应的单向性和抗冲突性［1］。

Whirlpool Hash函数实现过程也是首先进行消息分组，分组的长度为512位，填充同MD5，其中消息长度占最后256位，因此输入长度不得超过2256bit的字符串，用到专门的压缩函数W。W类似于Rijndael，与之相比有以下不同［2］:分组长度固定、轮数固定、密钥扩展用的是轮函数、用到的归约多项式稍有不同;S－盒不同;轮常量不同;扩散层不同。

下面介绍Whirlpool Hash函数的消息扩展算法［3］:Whirlpool首先将消息填充并分组，填充和分组的方法与MD5相似，每个分组长度512 bit，每个分组需要R轮迭代，因此需要R+1个子密钥，消息的扩展与寄存器数据的更新采用相同的轮函数。密钥扩展需要轮常量cr、线性扩展层θ、循环变换π和非线性层γ，密钥加法 σ［k］。

密钥的扩展过程就是先计算每轮的轮常量cr，根据密钥加法σ［k］将轮常量和上一轮扩展密钥Kr－1异或运算，将运算后结果依次进行线性扩展层置换θ，循环变换π和非线性层置换γ，变换后的结果即为第r轮的子密钥Kr。

2 Whirlpool的改进算法

常用的Hash函数的分组长度一般大于输出长度，Whirlpool算法的分组长度等于输出长度，相当于密钥长度等于分组长度的AES－128，都是10轮迭代，对AES来说，无论加密多少个分组，分组密码只需一次密钥编排，AES的密钥编排与加密一个分组耗时相当，当分组较多时，密钥编排的耗时可以忽略，但对Hash函数，每个分组消息都要进行消息扩展，Whirlpool的消息扩展算法和寄存器的数据更新算法采用相同的轮函数，因此，Whirlpool效率相当于AES－128的1/2，但如果将Whirlpool的分组长度变为1 024 bit，同时将迭代轮数改为14轮，相当于密钥长度等于分组长度2倍的AES－256算法［4］，这样，消息分组长度变为原来的两倍，分组数变为原来的1/2，但每个分组耗时相当于原来的1.4倍，相当于耗用原来1.4倍的时间来处理原来两倍的消息，即效率提高为原来的1.4倍。

改进Whirlpool算法，将Whirlpool的消息分组长度变成1 024 bit［5］，同时每组迭代轮数由10轮增长为14轮，消息扩展算法所用到的轮函数会发生一些变化，但是寄存器中数据更新所采用的轮函数不变。改进后密钥扩展算法如下:将1 024 bit的一组消息K映射到有限域 GF(28)上的一个8×16矩阵，即K∈M8×16［GF(28)］，根据K，首先计算出 KeyR，(R=0，1，2，…，7)，再将KeyR拆分后，得到每轮的子密钥KR，R=0，1…15。

其中，轮常量c'r是映射到有限域GF(28)上的一个8×16 矩阵，c'r∈M8×16［GF(28)］，定义如下

密钥扩展的轮函数 ρ'［k］= σ'［k］·θ'·π'·γ;与改进前的算法相比，除非线性层γ外，密钥加法σ'［k］线性扩展层 θ'循环变换 π'均发生变化。

密钥加法变化 σ'［k］:σ'［k］(a)=b⇔bij=aij⊕kij，0≤i≤7，0≤j≤15。

线性扩展层 θ':θ'(a)=b⇔b=(aT·C)T，其中矩阵a为8×16矩阵，将该矩阵转置后与矩阵C相乘，再将结果转置成8×16矩阵。

经过迭代后，生成8个分别对应有限域GF(28)上的8×16的矩阵，将这8个8×16的矩阵拆分成16个8 ×8 的矩阵 KR，R=0，1，…，15，拆分方法为:取一个矩阵的8 行0、2、4、6、8、10、12、14 列组成第一个 8 ×8矩阵，取矩阵的 8 行 1、3、5、7、9、11、13、15 列组成第 2个8×8的矩阵，这样可以获得16个8×8的矩阵，对应16个子密钥。其中初始阶段用到两个子密钥，之后进行14轮迭代用到14个子密钥。

3 算法性能分析

3.1 抗碰撞性分析

Whirlpool是少数仍然没有被破译的从一种基础分组密码构造的Hash函数之一，如果假定基础分组密码具有某些理想的性质，则这个方案是安全的［6］。Whirlpool的改进算法的安全性是基于Whirlpool算法安全性的，Whirlpool的压缩函数采用了专用的压缩函数W，该压缩函数很类似于分组密码Rijndael，但是在效率上高出很多，同时能抵抗差分攻击，改进Whirlpool的子密钥生成过程，改变的是子密钥的生成方式和时间，并没有改变压缩结构和迭代算法。

差分密码分析:对于改进后的Whirlpool，在线性扩展层变换的分支数B=7，由平方模式扩散定理可知，对W的任意两个不同的输入，在连续的6轮迭代中具有不同输入值的S盒的个数至少为B2=49个，因此，对于经过6轮后存在差分特性的概率 ＜(2－7)49=2－343，这使得古典的差分攻击不可能在完整的Hash函数上成功。

对内部分组密码W的攻击［5］:由Gllbert和Mimier提出的，对W的最好的恢复密钥攻击方法是减少到7轮，共需要2245步，Ferguson等人对7轮W的攻击的想法是可能的，但对它的复杂性非常高，需要查询2512次S盒，2128bit内存和O(2512)的明文，对更高轮的W来讲，没有比穷搜索更好的攻击方法。改进Whirlpool算法，并没有改变压缩函数的结构，而是增加了迭代的轮数，这样增大了恢复密钥攻击的方法的难度，提高了算法的安全性。

3.2 安全性测试

严格雪崩准则测试:严格雪崩准则包括完备性和雪崩效应。完备性指的是其输出的任一bit和输入的任一bit相关。Whirlpool改进算法满足雪崩效应是指改变输入1 bit，大约有1/2的输出比特发生改变。满足严格雪崩准则，是指改变输入的1 bit，每个输出比特改变的概率为0.5。随机抽取10 000个样本，随机改变其中一个比特位，分别实验256次、512次、1 024次、2 048次、4 096次，测试输出改变的位数。测试结果见表1所示。

表1 严格雪崩准则

改进后Whirlpool算法，Hash输出长度为512位，由测试可以看出，修改一位的消息明文，大约有长度256位的输出值发生改变，占全部输出长度的1/2。对于每1 bit输入的改变，每1 bit的输出改变的次数占测试次数的1/2左右，即发生变化的概率约为0.5。

为考察算法的混淆与扩散性，做如下评价标准［8］:

表2 混乱和扩散

从表2可以看出，B值接近于理想值256，P值接近于理想值的50%，ΔB和ΔP值也很小，其值越小，说明算法的混淆于扩散特性越稳定，因而利用该算法计算出的Hash值满足安全性的要求。

3.3 算法效率分析

效率是Hash函数评价中的非常重要的一个标准，包括消息扩展算法、寄存器数据变换、压缩函数效率等几个方面。改进后的Whirlpool算法并没有寄存器数据变换、压缩函数等算法，只是在消息扩展算法上有一些效率的改进。

选用不同长度的明文做测试，采用的测试平台为测试平台为芯片:Intel(R)，CPU:Core(TM)，i3，主频2.93 GHz，内存2 GB，硬盘 500 GB，测试 1 000 次，用C++语言编程测试［9］不同长度的明文消息Hash1 000次所需时间。结果如表3所示。

表3 算法效率

由表3可以看出，当消息个数＜32 Byte时，两种算法消息填充后存在一个分组消息，改进后算法处理时间反而较改进前更长一些，而随着填充后分组消息数的增加，改进后算法的效率逐渐趋近于改进前算法的1.4倍。

4 结束语

文中分析了分组密码构造Hash函数的代表算法Whirlpool算法，并着重分析其消息扩展算法，指出其中存在的不足。Whirlpool的压缩函数W，类似于分组密码AES－128，但效率相当于AES－128的1/2，借鉴AES－256的密钥扩展算法，改进Whirlpool的密钥扩展算法，使其分组长度变为1 024 bit，并将每个分组改为14轮迭代，在不降低安全性的前提下，效率将提高到约为原来的1.4倍。

［1］冯登国，林东岱，吴文玲.欧洲信息安全算法工程［M］.北京:科学出版社，2003.

［2］吴文玲，冯登国，张文涛.分组密码的设计与分析［M］.北京:清华大学出版社，2000.

［3］多磊.基于分组密码分析设计Hash函数［D］.长沙:国防科技大学，2007.

［4］张文涛.分组密码的分析与设计［D］.北京:中国科学院，2004.

［5］多磊，李超.循环移位对Rijndael密码安全性的影响［J］.通信学报，2003，24(9):153 －161.

［6］多磊，李超.Rijndael密码的逆序Square攻击［J］.电子与信息学报，2004，26(1):65 －71.

［7］郭伟，钱进，王新军.一种基于分组密码的Hash函数的安全性分析及构造［J］.计算机科学，2008，35(9):129－132.

［8］邓绍江，廖晓峰，肖迪.一种基于混沌的可并行Hash函数［J］.计算机科学，2008，35(6):217 －219.

［9］TOM S D，SIMON J.程序员密码学［M］.沈晓斌，译.北京:机械工业出版社，2007.