Science in China Ser.F Information Sciences2005V ol.48No.51–121
An attack on hash function HA V AL-128
WANG Xiaoyun1,FENG Dengguo2&YU Xiuyuan3
1.School of Mathematics and System Sciences,Shandong University,Jinan250100,China;
2.Institute of Software,Chine Academy of Sciences,Beijing100080,China;
3.Mathematics Department, Hangzhou T eachers College,Hangzhou310012,China
Correspondence should be addresd to Wang Xiaoyun(email:xywang@sdu.edu)
Received October18,2004;revid February2,2005
Abstract In this paper,we give a fast attack against hash function——HAVAL-128. HAVAL was prented by Y.L.Zheng et al.at Auscrypto’92.It can be procesd in3, 4or5pass,and produces128,160,192,or224-bitfingerprint.We break the HAVAL with128-bitfingerprint.The conclusion is that,given any1024-bit message m,we just make some modifications about m,and the modified messag
e m can collide with another message m only with the probability of1/27,where m =m+ m,in which m is a fixed difference lected in advance.In addition,two collision examples for HAVAL-128
are given in this paper.
Keywords:hash function,collision,differential attack,differential characteristic.
DOI:10.1360/122004-107
Hash function directly applies to data integrity,and can be the curity guarantee for many cryptosystems and protocols such as signature,group signature,message authentica-tion code,e-cash,bit commitment,coin-flipping,e-voting,etc.According to the structure of the existing hash functions,it can be mainly divided into two kinds:one is bad on the cipher blocks,the other is directly constructed.We name the cond the standard hash function.
According to the different message process,the standard hash functions can be di-vided into two families:MDx family(MD4[1],MD5[2],HA V AL[3],RIPEMD[4],RIPEMD-160[5])and SHA family(SHA-1[6],SHA-256,384,512[7]).The hashing algorithms reveal the main design technology of the hash functions.
婴儿贫血怎么办
The cryptoanalysis for MDx hash functions has en much progress.Dobbertin gave an attack for the full MD4[8]in1996,which canfind a collision with the probability of 2−22.The latest attack on MD4is a more efficient attack described by Kaslman in 1997[9].As for MD5,den Boer and Boslaersobber found a kind of pudo-collision for MD5which is compod of the same message with two ts of different initial values[10]. In Eurocrypto’96,Dobbertin prented one collision of MD5which is made up of two different messages under another t of initial values[11].Other analysis results about MDx reduced versions can be en in refs.[12–16].
Copyright by Science in China Press2005
2Science in China Ser.F Information Sciences2005V ol.48No.51–12 For SHA family,Chabaud and Joux[17]prented a differential attack on SHA-0which canfind a collision with probability2−61.Joux[18]announced a4-block collision for the full SHA-0in which the complexity offinding the collision is about251.Biham and Chen[19]also gave a near-collision attack on SHA-0,and described their improved results on SHA-0and SHA-1in the Rump ssion[20].
The purpo of this paper is to break the full HA V AL with128-bitfingerprint rapidly. Before our break,the latest cryptanalysis is an attack on HA V AL-128given by Rompay et al.[21],which canfind a collision with about229HA V AL-128computations.
Our attack has the following properties:
1.The attack is a modular differential attack,and all the differential characteristics in the collision are given.
2.The attack gives all the conditions that guarantee all the differential characteristics to occur.
3.The attack is very fast to be performed by computer.Its running time is only about 27times that of HA V AL-128.
1HA V AL scheme
HA V AL is a hashing algorithm that can compress any length messages in3,4or5pass and produce a variable length output——128-bit,160-bit,192or224-bitfingerprint.The purpo of this paper is to break HA V AL with3pass(called HA V AL-128),so we only describe the details of HA V AL-128.
HA V AL-128employs three pass,H1,H2and H3.Each pass includes one high non-linear function that performs bit-wi operations on32-bit words.
f1(x6,x5,x4,x3,x2,x1,x0)=x1x4⊕x2x5⊕x3x6⊕x0x1⊕x0,
f2(x6,x5,x4,x3,x2,x1,x0)=x1x2x3⊕x2x4x5⊕x1x2⊕x1x4
⊕x2x6⊕x3x5⊕x4x5⊕x0x2⊕x0, f3(x6,x5,x4,x3,x2,x1,x0)=x1x2x3⊕x1x4⊕x2x5⊕x3x6⊕x0x3⊕x0.
Description of HA V AL-128.Pad the original message M to make the length of the message be a multiple of1024bits.We neglect the padding details[3]becau it has no relation with our attack.For one1024-bit block m of M,the compressing process is as follows:
1.a0=a,b0=b,c0=c,d0=d,e0=e,f0=f,g0=g,h0=h, (a,b,c,d,e,f,g,h)are the initial input parameters for m.If m is thefirst1024-bit message block to be hashed,it is the initial values:
a=0x243f6a88,b=0x85a308d3,c=0x13198a2e,d=0x03707344,
e=0xa4093822,f=0x299f31d0,g=0x082efa98,h=0xec4e6c89. Copyright by Science in China Press2005
An attack on hash function HA V AL-1283 Otherwi it is the last t of outputs in the former message block.
糟饼
2.For j=1,2,3,for i=32(j−1),32(j−1)+1,32(j−1)+2,···,32(j−1)+31
p i=f j(φj(g i,f i,e i,d i,c i,b i,a i),
r=(p i≫7)+(h i≫11)+m ord(j,i)+k j,i,
h i+1=g i,
g i+1=f i,
f i+1=e i,
e i+1=d i,
d i+1=c i,
c i+1=b i,
b i+1=a i,
谨慎的拼音
a i+1=r.
3.Let a=a96,b=b96,c=c96,d=d96,e=e96f96,g=g96,h=h96.
4.a=a96+a,b=b96+b,...,h=h96+h.the message m is the last 1024-bit block,the128-fingerprint y3∗y2∗y1∗y0is computed as follows:
h=h3∗h2∗h1∗h0,
g=g3∗g2∗g1∗g0,
f=f3∗f2∗f1∗f0,
e=e3∗e2∗e1∗e0,
y3=d+h3∗g2∗f1∗e0,
y2=c+h2∗g1∗f0∗e3,
y1=b+h1∗g0∗f3∗e2,
y0=a+h0∗g3∗f2∗e1.
The operation in each step employs a constant k j,i(e ref.[3]),where k0,i=0, 0 i 31.“≫”reprents the circular right shift.“+”is additive operation modular 232.x∗y denotes the concatenation of x and y.
The compressing process for m includes96steps.Steps1–32belong to pass one,pass two is from33-th step to64-th step,and pass three is from65-th to96-th step.
The orders of message words in each pass are defined by Table1.视死忽如归
There are three permutations of variablesφi(i=1,2,3)(e Table2).
2Some basic conclusions and notations
Wefirst describe some properties of nonlinear functions f1◦φ,f2◦φand f3◦φ,which are important for breaking HA V AL-128.
4Science in China Ser.F Information Sciences2005V ol.48No.51–12
Table1The orders of message words
H1(ord(1,i))00010203040506070809101112131415 16171819202122232425262728293031 H2(ord(2,i))05142618112807160023202201100408 30032109172429061912151302253127 H3(ord(3,i))19090420281708222914251224301626 31150703010018271306211023110502
Table2Theφ-permutation of variables in three pass
Permutation x6x5x4x3x2x1x0φ1x1x0x3x5x6x2x4
φ2x4x2x1x0x5x3x6
φ3x6x1x2x3x4x5x0
f1(φ1(x6,x5,x4,x3,x2,x1,x0))=x2x3⊕x0x6⊕x1x5⊕x2x4⊕x4,
f2(φ2(x6,x5,x4,x3,x2,x1,x0))=x0x3x5⊕x1x2x5⊕x4x5⊕x0x2⊕x3x5
⊕x1x3⊕x1x2⊕x5x6⊕x6,
f3(φ3(x6,x5,x4,x3,x2,x1,x0))=x3x4x5⊕x2x5⊕x1x4⊕x3x6⊕x0x3⊕x0. Proposition1.Let y1=f1(φ1(x6,x5,x4,x3,x2,x1,x0)),y1,i=f1(φ1(x6,···, x i+1,¬x i,x i−1···,x0)).Then
b型血天蝎座
1.y1=y1,0if and only if x6=0.
2.y1=y1,1if and only if x5=0.
3.y1=y1,2if and only if x3⊕x4=0.
4.y1=y1,3if and only if x2=0.
5.y1=y1,4if and only if x2=1.
6.y1=y1,5if and only if x1=0.
7.y1=y1,6if and only if x0=0.
Here,x i∈{0,1}(0 i 6),and¬x i is the complement of x i.预测方法
Proof.we just prove(3),others can be proven in the same way.
=⇒From y1=y1,2,we know:
x2x3⊕x0x6⊕x1x5⊕x2x4⊕x4=¬x2x3⊕x0x6⊕x1x5⊕¬x2x4⊕x4. So,
x2x3⊕x2x4=¬x2x3⊕¬x2x4.
Thus
x3⊕x4=0.
Copyright by Science in China Press2005
An attack on hash function HA V AL-1285
⇐=From x3⊕x4=0,it is easy to prove y1=y1,2.
Proposition2.Let y2=f2(φ2(x6,x5,x4,x3,x2,x1,x0)),y2,i=f2(φ2(x6,···,
x i+1,¬x i,x i−1···,x0)).Then
1.y2=y2,0if and only if x3x5⊕x2=0.
2.y2=y2,1if and only if x2x5⊕x2⊕x3=0.
情人节情话简短3.y2=y2,2if and only if x1x5⊕x0⊕x1=0.
4.y2=y2,3if and only if x0x5⊕x1⊕x5=0.
5.y2=y2,4if and only if x5=0.
6.y2=y2,5if and only if x0x3⊕x1x2⊕x3⊕x4⊕x6=0.
7.y2=y2,6if and only if x5=1.
Proposition3.y3=f3(φ3(x6,x5,x4,x3,x2,x1,x0)),y3,i=f3(φ3(x6,···,x i+1,¬x i, x i−1···,x0)).Then
1.y3=y3,0if and only if x3=1.
2.y3=y3,1if and only if x4=0.
3.y3=y3,2if and only if x5=0.
4.y3=y3,3if and only if x0⊕x6⊕x4x5=0.
5.y3=y3,4if and only if x1⊕x3x5=0.
6.y3=y3,5if and only if x2⊕x3x4=0.
7.y3=y3,6if and only if x3=0.
Notations.In order to describe our attack conveniently,we define some notations.
1.m=(m0,m1,···,m31),m =(m 0,m 1,···,m 31)are two1024-bit messages.
2. m i=m i−m i, a i=a i−a i,··· h i=h i−h i, p i=p i−p i denote the modular differences of two variables.The notations are ud to describe differential characteristics with±symbols in our attack.
It is remarked that the modular difference definition is a bit different from that given by Biham and Shamir[22],which is defined as the XOR of two variables.暑期实践
3.a i,b i,c i,d i,e i,f i,g i,h i reprent the outputs of i-th step.
According to the HA V AL algorithm,we know that b i=a i−1,c i=a i−2,d i=a i−3,
e i=a i−4,
f i=a i−5,
g i=a i−6,
h i=a i−7.
4.x i,j denotes the j-th bit of32-bit word x i.For example,a i,j is the j-th bit of a i.
