—140
— 对104步杂凑函数HA V AL 的原根攻击
王高丽1，潘 乔1，杨茂江2
(1. 东华大学计算机科学与技术学院，上海 201620；2. 上海格尔软件股份有限公司，上海 200042)
摘 要：针对杂凑函数HA V AL 的第1圈中圈函数的性质和消息字的顺序，结合使用穷举搜索等方法，给出对前104步HA V AL 压缩函数的原根攻击。其计算复杂度是2224次杂凑运算，需要存储238个字节，而穷举攻击的计算复杂度是2256次杂凑运算。分析结果对杂凑函数HA V AL 安全性的评估有重要的参考价值。
关键词：杂凑函数；HA V AL 算法；密码分析；原根攻击
Preimage Attack on 104-step Hash Function HA V AL
WANG Gao-li 1, PAN Qiao 1, YANG Mao-jiang 2
(1. School of Computer Science and Technology, Donghua University, Shanghai 201620; 2. Shanghai
Koal Software Co., Ltd., Shanghai 200042) 【Abstract 】According to the properties of the function in the first pass and the order of the message words in HA V AL algorithm, a preimage attack on the compression function of the first 104-step HA V AL is propod by using the exhaustive arch method. The complexity of the attack is 2224 hash function valuations with the storage of 238 Bytes. However, the complexity of brute-force to find preimage is 2256. Analysis result has some new light on the evaluation of the curity of HA V AL.
【Key words 】hash function; HA V AL algorithm; cryptanalysis; preimage attack
计 算 机 工 程 Computer Engineering 第35卷 第20期
Vol.35 No.20 2009年10月
October 2009
·安全技术·
文章编号：1000—3428(2009)20—0140—02
文献标识码：A
中图分类号：TP393.08
1 概述
杂凑函数是信息安全中一个非常重要的工具，它对一个
任意长度(二进制表示时的长度)的消息施加操作，返回一个固定长度的杂凑值，杂凑函数是公开的。安全的杂凑函数h 应满足以下3个属性：(1)抗原根攻击：对任意的杂凑值y ，找到一个消息x ，使得()h x y =是计算上不可行的；(2)抗第二原根攻击：对任意消息x ，找到另一个异于x 的消息0x ，使得0()()h x h x =是计算上不可行的；(3)抗碰撞攻击：找到2个相异的消息x 和0x ，使得0()()h x h x =是计算上不可行的。
假设杂凑值的长度是n bit ，根据生日攻击可知找到碰撞的计算复杂度是2
2n
次杂凑运算。而寻找原根和第二原根理论上只能穷举搜索，其计算复杂度都是2n
次杂凑运算。对杂凑
值是n bit 的杂凑函数，如果找到碰撞的计算复杂度小于2
2n
或者找到原根的计算复杂度小于2n 或者找到第二原根的计算复杂度小于2n ，则称该杂凑函数被理论上破解。对某杂凑函数，能找到其碰撞，却不一定能找到原根。
近来对杂凑函数安全性的分析得到了一系列重大结果：文献[1-4]对MD4系列杂凑函数HAVAL, MD5, RIPEMD, SHA-0和SHA-1等进行了碰撞攻击，认为这些杂凑函数不再安全。有些应用环境要求杂凑函数抗原根攻击，而不需要抗碰撞攻击，一些被认为不安全的杂凑函数仍在这些环境中继续使用，所以对杂凑函数进行原根攻击有着很重要的意义。文献[5]找到了前2轮MD4算法的原根，文献[6]对完整MD4算法给出了原根攻击。
杂凑函数HAVAL [7]是由Y.Zheng 等在1992年提出的，它可以进行96步、128步或160步运算并输出长度为128 bit, 160 bit, 192 bit, 224 bit 或256 bit 的杂凑值。本文考虑输出杂凑值长256 bit 的情况，对104步HAVAL 压缩函数进行原根攻击，其计算复杂度是2242次压缩运算，需要存储382Byte 。
2 HAVAL 算法
本文对104步且输出长度为256 bit 的算法进行原根攻击，故在此只描述128步且输出长256 bit 的HAVAL 算法。128步算法包括4圈，每圈包括32步，每圈采用一个非线性圈函数，分别为
16543210135624030(,,,,,,)F x x x x x x x x x x x x x x x x =⊕⊕⊕⊕
265432100161251626130525144
(,,,,,,)F x x x x x x x x x x x x x x x x x x x x x x x x x x =⊕⊕⊕⊕ ⊕⊕⊕⊕
36543210026230416565(,,,,,,)F x x x x x x x x x x x x x x x x x x x =⊕⊕⊕⊕⊕
4654321012502405601260545560406033
(,,,,,,)F x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x =⊕⊕⊕ ⊕⊕⊕⊕ ⊕⊕⊕⊕
其中，016,,,x x x "是长32 bit 的字。
首先填充最初的消息，使其长度是1 024的倍数。初始参数为
00000000(,,,,,,,)(0243688,0853083,0131982,003707344,04093822,0299310,008298,04689)
aa bb cc dd ee ff gg hh x f a x a d x a e x xa x f d x efa xec e c =
对长1 024 bit 的消息分组0131(,,,)M m m m ="，运算过程如下：
(1)0a aa =,0b bb =,0c cc =,0d dd =,0e ee =,0f ff =,
基金项目：上海市科委技专项资金基金资助项目(08DZ1500600)；东华大学校基金资助项目
作者简介：王高丽(1982－)，女，讲师、博士，主研方向：信息安全；潘 乔，讲师、博士；杨茂江，博士
收稿日期：2009-05-11 E-mail ：wanggaoli@
—141—
0g gg =,0h hh =，(,,,,,,,)aa bb cc dd ee ff gg hh 是分组M 的输入
参数，如果M 是第一个被压缩的分组，则(,,,,,aa bb cc dd ee
,,)ff gg hh 是初始参数，否则，就是前一个消息分组的压缩值。
(2)完成以下128步运算：对1,2,3,4j =，有
32(1),32(1)1,,32(1)31i j j j =−−+−+" (,,,,,,)i j i i i i i i i p F g f e d c b a =
(,),(7)(11)i i j i j i r p h m k =>>+>>++ 1111,,,i i i i i i i i h g g f f e e d ++++==== 1111,,,i i i i i i i d c c b b a a r ++++====
(3)128128128,,,aa a a bb b b hh h h =+=+=+"
如果M 是最后一个消息分组，则原消息的压缩值为||||||||||||||hh gg ff ee dd cc bb aa ，其中，“||”表示级联。每步运算中用到了一个常数,j i k (其中，0,0,031i k i = ≤≤)；“>>”表示循环右移；“＋”表示模322加运算。每圈中消息字的次序见表1。
表1 消息字的顺序
圈数 消息字的顺序
(1,i ) 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16, 17,18,19,20,21,22,23,24,25,26,27,28,29,30,31 (2,i ) 5,14,26,18,11,28,7,16,0,23,20,22,1,10,4,8,30, 3,21,9,17,24,29,6,19,12,15,13,2,25,31,27 (3,i ) 19,9,4,20,28,17,8,22,29,14,25,12,24,30,16,26, 31,15,7,3,1,0,18,27,13,6,21,10,23,11,5,2 (4,i )
24,4,0,14,2,7,28,23,26,6,30,20,18,25,19,3,22, 11,31,21,8,27,12,9,1,29,5,15,17,10,16,13
3 对104步压缩函数的原根攻击
采用与文献[6]相似的方法，结合HAVAL 算法的具体特
点，首先描述圈函数1F 和2F 的一些性质，文献[3]利用这些性质对HAVAL 进行了碰撞攻击；然后利用圈函数1F 和2F 的性质并考虑消息字的顺序，给出对104步HAVAL 压缩函数(记为CHAVAL)的原根攻击，其计算复杂度是2242。 3.1 圈函数的性质
性质1 设
116543210(,,,,,,)y F x x x x x x x =,
1,16110(,,,,,,)i i i i y F x x x x x +−=¬""，
则：
(1)11,0y y =当且仅当31x =；
(2)11,1y y =当且仅当30x =； (3)11,2y y =当且仅当40x =； (4)11,3y y =当且仅当010x x +=； (5)11,4y y =当且仅当20x =； (6)11,5y y =当且仅当60x =； (7)11,6y y =当且仅当50x =。 其中，{0,1}(06)i x i ∈≤≤。
性质2 设
226543210(,,,,,,)y F x x x x x x x =,
2,265110(,,,,,,,)i i i i y F x x x x x x +−=¬""，
则：
(1)22,5y y =当且仅当12020x x x x ++=；
(2)22,6y y =当且仅当01120x x x x ++=。
证明 在此仅证明性质1的第(4)条，其他性质同理可得。 由11,3y y =，得
135624030135624030
x x x x x x x x x x x x x x x x x x ⊕⊕⊕⊕=¬⊕⊕⊕¬⊕故13031303x x x x x x x x ⊕=¬⊕¬，因此010x x +=。反之，由010x x +=可很容易证得y 1=y 1,3。
3.2 对CHAVAL 的原根攻击
为了得到CHAVAL 的压缩值*****||||||||||hh gg ff ee dd
***||||cc bb aa ，寻找一个1 024 bit 的消息分组01(,,,M m m ="
31)m 和输入参数00000000(,,,,,,,)a b c d e f g h ，使得它们经过
CHAVAL 压缩的值等于||||||||||||||hh gg ff ee dd cc bb ∗∗∗∗∗∗∗
aa ∗。利用圈函数1F 和2F 的性质，并结合使用“中间相遇攻
击”和穷举搜索来实现目标。如下算法描述了该攻击过程。
算法 对104步HAVAL 压缩函数的原根攻击
(1)取000,a xffffffff b bb ∗==,0c cc ∗=,0d dd ∗=,00e =,
00g =,0h hh ∗=，随机取0f 。为了满足压缩值中的224 bit 是aa ∗,bb ∗,cc ∗,dd ∗,ee ∗,gg ∗,hh ∗，令104a aa ∗=−0xffffffff 32(mod 2),1040b =,1040c =,1040d =,104e ee ∗=, 104g gg ∗=,
1040h =。
(2)重复以下过程：
1)取消息字01345789111213, ,
,
, ,, , , , , , m m m m m m m m m m m 151617192021232428293031, , , , , , , , ,, ,m m m m m m m m m m m m ，使得
124568910121314160, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0,a a a a a a xffffffff a a a a a a xffffffff ============ 17182021222425293031320, 0, 0, 0, 0, 0, 0,0, 0, 0, 0a a a a a a xffffffff a a a a a ===========
分别成立；随机选择消息字：
2610141822252627, , , , , , , , m m m m m m m m m
2)对322个0f ，计算出322个中间变量7979797979(,,,,,a b c d e
797979,,)f g h ，储存在L 里。对322个104f ，计算出322个8080808080808080(,,,,,,,)a b c d e f g h ，与L 里的变量作比较，若L
里存在中间变量满足8079b a =,8079c b =,8079d c =,8079e d =,
8079f e =,8079g f =,8079h g =，则修正26m ，从而得到80a =
37979797979797979263,79((,,,,,,)7)(11)F g f e d c b a h m k >>+>>++。
(3)若hh hh ∗=，则返回消息0131(,,,)M m m m ="和输入参数00000000(,,,,,,,)a b c d e f g h 。
对算法的说明：
根据HAVAL 算法可知，取消息字
01000((,,)7)
m F g a =−>>"0(11)
h −>>32(mod2)
0100000((,,,)7)(11)m F g f a h =−>>−>>"32(mod2)
可得10a =，同理可实现操作1)。操作2)在第3圈修改了消息字26m ，
下面说明26m 的改变不会影响第1圈和第2圈里中间变量的值，从而不会影响算法的压缩值。第2圈26m 用在算法的第35步，为了保持35a 不变，修改27a 为2735(a a =−
234343434343434262,35((,,,,,,)7))11F g f e d c b a m k >>−−<<。
根据性质1和性质2知，条件240a xffffffff =,250a =,
290a =,300a =,310a =,320a =保证27a 的改变不会影响28a , 29a ,30a ,31a ,32a ,33a ,34a ，从而不会影响其后的变量值。为了
修改27a 和19a ，条件160a xffffffff =,170a =,180a =,200a =,
210a =,220a =保证19a 的改变不会影响20a ,21a ,22a ,23a ,24a , 25a ,26a 。为了修改19a 和11a ，条件80a xffffffff =,90a =, 100a =,120a =,130a =,140a =保证11a 的改变不会影响
(下转第144页) —142—
