对4圈杂凑函数HAVAL-160的一个攻击
摘要
杂凑函数是信息安全中一个非常重要的工具,它对一个任意长度的消息m施加操作,返回一个固定长度的杂凑值h(m),杂凑函数是公开的,对处理过程不用保密。单向杂凑函数的安全性取决于它的单向性,其输出不依赖于输入。杂凑函数是许多密码算法和协议的安全保证,它广泛用于签名、群签名、MAC码、电子钱币、比特承诺、电子选举等。
目前受到人们广泛关注和青睐的是标准杂凑函数,而标准杂凑函数又可分为两大家族:MDx家族(MD4、MD5、HAVAL、RIPE-MD、RIPE-MD-160)和SHA家族(SHA-0、SHA-1、SHA-256,384,512)。这些杂凑算法揭示了杂凑函数主要的设计技术。
目前,标准杂凑函数的分析技术已经取得了很大的进展。Hans Dobbertin于1996年对MD4给出了一个攻击,可以以2~(-22)找到一个碰撞;1997年,Kasselman对MD4给出了一个更为有效的攻击。对于MD5,B.den Boer和A.Basselaersobber找到了MD5的一类伪碰撞——在两组不同的初始值下得到同一明文的相同的杂凑值;在1996年欧密会上,Dobbertin给出了MD5的一个碰撞——在另一初始值下得到两组不同的报文;2004年美密会上,王小云对MD5的攻击引起了国际密码界的轰动,王小云利用比特追踪法寻找碰撞路线、推出碰撞发生的必要条件、修改明文提高碰撞发生的概率可很容易找到一个碰撞。2003年,B.V.Rompay等对3圈杂凑函数HAVAL有一个攻击,其计算复杂度为2~(29)。而王小云于2004年利用破译MD5的技术同样找到了概率为2~(-7)的3圈杂凑函数HAVAL-128的碰撞。至于SHA家族,2005年一月,王小云对SHA-1的研究又取得巨大进展,其计算复杂度少于2~(69)杂凑运算。
杂凑函数HAVAL是由Y.Zheng等在Auscrypto'92提出的,该体制可以在3、4或5圈压缩任意长度的报文并输出长度为128-比特、160-比特、192-比特或224-
Hash functions play a very important role in information security. It compresses any arbitrary bit-length message m into a fixed-length hash value h(m). Hash functions are in public, and their management processes don't keep secret. The security of hash function depend on it's one-way property. The output of hash function is independent of input. Hash function can be directly used to data integrity, and be the security guarantee for many cryptosystems and protocols such as signature, group signature, message authentication code, e-cash, bit commitment, coin-flipping, e-voting etc.Recently the standard hash functions are popular and favorable. It have two families: MDx family (MD4, MD5,HAVAL, RIPEMD,RIPEMD-160) and SHA family(SHA-0, SHA-1, SHA-256,384, 512 ). These hashing algorithms reveal the main design method and technology of the hash functions.The cryptoanalysis for hash functions has made much progress. Hans Dobbertin gave an attack for the full MD4 in 1996, which can find a collision with the probability of 2'22. The latest attack on MD4 is a more efficient attack described by Kasselman in 1997. As for MD5, B.den Boer and A.Bosselaersobber found a kind of pseudo-collisions for MD5 which composed of the same message with two groups of different initial values. In Eurocrypto'96, Dobbertin presented one collision of MD5 which is made up of two different messages under another initial value. in Crypto'2004 conference Xiaoyun. Wang present a new powerful attack on MD5 which raise a stir. B.V.Rompay gave an attack for 3-pass HAVAL in 2003, which computational complexity of the attack corresponds to about 229 computations.But Xiaoyun.Wang make use of bit-trace method to search a collison line in 2004, to modify the messages, to gain sufficient conditions, which allows us to find collisions
efficiently. For SHA family, Xiaoyun.Wang has made much progress for SHA-1,she found a differential attack for SHA-1 with the probability of 2~69 in 2005,HAVAL was presented by Y. L. Zheng etc at Auscrypto'92. It can be processed in 3,4 or 5 passes, and produces 128, 160, 192, or 224-bit fingerprint.We make use of Xiaoyun.Wang' technology to break the HAVAL-160 with 4 passes. We can found a differential attack for HAVAL-160 with the probability of 2"40. The result is much better than 2'80, which is the result of birthday attack.
目前受到人们广泛关注和青睐的是标准杂凑函数,而标准杂凑函数又可分为两大家族:MDx家族(MD4、MD5、HAVAL、RIPE-MD、RIPE-MD-160)和SHA家族(SHA-0、SHA-1、SHA-256,384,512)。这些杂凑算法揭示了杂凑函数主要的设计技术。
目前,标准杂凑函数的分析技术已经取得了很大的进展。Hans Dobbertin于1996年对MD4给出了一个攻击,可以以2~(-22)找到一个碰撞;1997年,Kasselman对MD4给出了一个更为有效的攻击。对于MD5,B.den Boer和A.Basselaersobber找到了MD5的一类伪碰撞——在两组不同的初始值下得到同一明文的相同的杂凑值;在1996年欧密会上,Dobbertin给出了MD5的一个碰撞——在另一初始值下得到两组不同的报文;2004年美密会上,王小云对MD5的攻击引起了国际密码界的轰动,王小云利用比特追踪法寻找碰撞路线、推出碰撞发生的必要条件、修改明文提高碰撞发生的概率可很容易找到一个碰撞。2003年,B.V.Rompay等对3圈杂凑函数HAVAL有一个攻击,其计算复杂度为2~(29)。而王小云于2004年利用破译MD5的技术同样找到了概率为2~(-7)的3圈杂凑函数HAVAL-128的碰撞。至于SHA家族,2005年一月,王小云对SHA-1的研究又取得巨大进展,其计算复杂度少于2~(69)杂凑运算。
杂凑函数HAVAL是由Y.Zheng等在Auscrypto'92提出的,该体制可以在3、4或5圈压缩任意长度的报文并输出长度为128-比特、160-比特、192-比特或224-
Hash functions play a very important role in information security. It compresses any arbitrary bit-length message m into a fixed-length hash value h(m). Hash functions are in public, and their management processes don't keep secret. The security of hash function depend on it's one-way property. The output of hash function is independent of input. Hash function can be directly used to data integrity, and be the security guarantee for many cryptosystems and protocols such as signature, group signature, message authentication code, e-cash, bit commitment, coin-flipping, e-voting etc.Recently the standard hash functions are popular and favorable. It have two families: MDx family (MD4, MD5,HAVAL, RIPEMD,RIPEMD-160) and SHA family(SHA-0, SHA-1, SHA-256,384, 512 ). These hashing algorithms reveal the main design method and technology of the hash functions.The cryptoanalysis for hash functions has made much progress. Hans Dobbertin gave an attack for the full MD4 in 1996, which can find a collision with the probability of 2'22. The latest attack on MD4 is a more efficient attack described by Kasselman in 1997. As for MD5, B.den Boer and A.Bosselaersobber found a kind of pseudo-collisions for MD5 which composed of the same message with two groups of different initial values. In Eurocrypto'96, Dobbertin presented one collision of MD5 which is made up of two different messages under another initial value. in Crypto'2004 conference Xiaoyun. Wang present a new powerful attack on MD5 which raise a stir. B.V.Rompay gave an attack for 3-pass HAVAL in 2003, which computational complexity of the attack corresponds to about 229 computations.But Xiaoyun.Wang make use of bit-trace method to search a collison line in 2004, to modify the messages, to gain sufficient conditions, which allows us to find collisions
efficiently. For SHA family, Xiaoyun.Wang has made much progress for SHA-1,she found a differential attack for SHA-1 with the probability of 2~69 in 2005,HAVAL was presented by Y. L. Zheng etc at Auscrypto'92. It can be processed in 3,4 or 5 passes, and produces 128, 160, 192, or 224-bit fingerprint.We make use of Xiaoyun.Wang' technology to break the HAVAL-160 with 4 passes. We can found a differential attack for HAVAL-160 with the probability of 2"40. The result is much better than 2'80, which is the result of birthday attack.
引文
[1] Xiaoyun Wang,Dengguo Feng,Xiu yuan Yun,An Attack on Hash Function HAVAL-128, http//www.infsec.sdu.edu.cn.
[2] Xiaoyun Wang,Yiqun Lisa Yin,Hongbo Yu, Collision Search Attacks on SHA1, http//www.infsec.sdu.edu.cn.
[3] Xiaoyun Wang, Xiaoyun Wang and Hongbo Yu,How to Break MD5 and Other Hash Functions, Eurocryt'2005, http//www.infsec.sdu.edu.cn.
[4] Xiaoyun Wang, Crytanalysis of the Hash Functions MD4 and RIPEMD, Eurocryt'2005, http//www.infsec.sdu.edu.cn.
[5] Xiaoyun Wang, Collisions for Some Hash Functions MD4,MD5,HAVAL-128, RIPEMD,Crypt'04, http//www.infsec.sdu.edu.cn.
[6] 王小云,冯登国,于秀源,HAVAL-128的碰撞攻击,中国科学,2005,http//www.infsec.sdu.edu.cn.
[7] Biham,E.,Shamir, A.,Differential Cryptanalysis of the Data Encryption Standard,Springer Verlag, 1993.
[8] Boer, B.den.,Bosselaers,A.,An attack on the last two rounds of MD4,Advances in Cryptology, Crypto'91 Proceedings,Springer-verlag, 1992, 194-203.
[9] Boer, B.den., Bosselaers,A., Collisions for compression function of MD5, Advances in Cryptology, Eurocrypto'93 Proceedings, Springer-verlag, 1994, 294-304.
[10] Chaband,F.,Joux,A.,Differential Collisions in SHA-0,Advances in Cryptology, Crypto'98 Proceedings,Springer-verlag.
[11] H.Dobbertin,Cryptanalysis of MD4,Fast Software Encryption,LNCS 1039, Springer Verlag, 1996.
[12] Dobbertin,H., Cryptanalysis of MD5 Compress, Advances in Cryptology, Crypto'96 Proceedings,Springer-verlag, 1996.
[13] Dobbertin,H.,RIPEMD with two round compress function is not collision-free, Advances in Cryptology, Eurocrypto'97 Proceedings,Springer-verlag, 1997.
[14] Dobbertin,H.,Cryptanalysis of MD5 Compress, presented at the rump session of Eurocrypto'96,
[15] Dobbertin,H., Bosselaers,A.,Preneel,B.,RIPEMD-160:A Strengthened Version of RIPEMD,Fast Software Encryption,LNCS 1039, SpringerVerlag, 1996,71-82,
[16]FIPS 180-1,Secure hash sdandard, NIST, US Department of Commerce Washington D.C., SpringerVerlag, 1996.
[17] FIPS 180-2,Secure hash sdandard,http//csrc,nist.gov/publications/,2002.
[18] Kasselman ,P.R.,A fast attack on the MD4 hash function,IEEE Proceedings of the 1997 South African Symposium on Communications and Signal Processing, 1997.
[19] Kasselman,P,R.,Penzhom,W,T,,Cryptanalysis of reduced version of HAVAL, Electronic Letters,Vol,36,No. 1,2000.
[20] RIPE,Integrity Primitives for Secure Information Systems,Final Report of RACE Integrity Primitives Evalution(RIPE-RACE 104Q),LNCS 1007. SpringerVerlag, 1995.
[21] Rivest,R,L..The MD4 Message Digest Algorithm,Advances in Cryptology, Crypto’90 Proceedings,Springer-verlag, 1991,303-311.
[22]Rivest,R,L.,The MD5 message-digest algorithm,Requset for Comments(RFC 1320),Intemet Activities Boardjntemet PrivacyTask Force, 1992.
[23] Zheng,Y,,Pieprzyk,J.,Seberry,J.,HAVAL-A one-way Hashing Algorithm with Variable Length of Output, Advances in Cryptology, Auscrypto'92 Proceedings,Springer-verlag,1993,83-104,
[24] B.V.Rompay, A.Biryukov, B.Preneel, and J.Vandewalle, Cryptanalysis of 3-pass HAVAL, Advances in Cryptology-Asiacrypt'2003, LNCS 2894, Springer-Verlag, 2003,228-245.
[2] Xiaoyun Wang,Yiqun Lisa Yin,Hongbo Yu, Collision Search Attacks on SHA1, http//www.infsec.sdu.edu.cn.
[3] Xiaoyun Wang, Xiaoyun Wang and Hongbo Yu,How to Break MD5 and Other Hash Functions, Eurocryt'2005, http//www.infsec.sdu.edu.cn.
[4] Xiaoyun Wang, Crytanalysis of the Hash Functions MD4 and RIPEMD, Eurocryt'2005, http//www.infsec.sdu.edu.cn.
[5] Xiaoyun Wang, Collisions for Some Hash Functions MD4,MD5,HAVAL-128, RIPEMD,Crypt'04, http//www.infsec.sdu.edu.cn.
[6] 王小云,冯登国,于秀源,HAVAL-128的碰撞攻击,中国科学,2005,http//www.infsec.sdu.edu.cn.
[7] Biham,E.,Shamir, A.,Differential Cryptanalysis of the Data Encryption Standard,Springer Verlag, 1993.
[8] Boer, B.den.,Bosselaers,A.,An attack on the last two rounds of MD4,Advances in Cryptology, Crypto'91 Proceedings,Springer-verlag, 1992, 194-203.
[9] Boer, B.den., Bosselaers,A., Collisions for compression function of MD5, Advances in Cryptology, Eurocrypto'93 Proceedings, Springer-verlag, 1994, 294-304.
[10] Chaband,F.,Joux,A.,Differential Collisions in SHA-0,Advances in Cryptology, Crypto'98 Proceedings,Springer-verlag.
[11] H.Dobbertin,Cryptanalysis of MD4,Fast Software Encryption,LNCS 1039, Springer Verlag, 1996.
[12] Dobbertin,H., Cryptanalysis of MD5 Compress, Advances in Cryptology, Crypto'96 Proceedings,Springer-verlag, 1996.
[13] Dobbertin,H.,RIPEMD with two round compress function is not collision-free, Advances in Cryptology, Eurocrypto'97 Proceedings,Springer-verlag, 1997.
[14] Dobbertin,H.,Cryptanalysis of MD5 Compress, presented at the rump session of Eurocrypto'96,
[15] Dobbertin,H., Bosselaers,A.,Preneel,B.,RIPEMD-160:A Strengthened Version of RIPEMD,Fast Software Encryption,LNCS 1039, SpringerVerlag, 1996,71-82,
[16]FIPS 180-1,Secure hash sdandard, NIST, US Department of Commerce Washington D.C., SpringerVerlag, 1996.
[17] FIPS 180-2,Secure hash sdandard,http//csrc,nist.gov/publications/,2002.
[18] Kasselman ,P.R.,A fast attack on the MD4 hash function,IEEE Proceedings of the 1997 South African Symposium on Communications and Signal Processing, 1997.
[19] Kasselman,P,R.,Penzhom,W,T,,Cryptanalysis of reduced version of HAVAL, Electronic Letters,Vol,36,No. 1,2000.
[20] RIPE,Integrity Primitives for Secure Information Systems,Final Report of RACE Integrity Primitives Evalution(RIPE-RACE 104Q),LNCS 1007. SpringerVerlag, 1995.
[21] Rivest,R,L..The MD4 Message Digest Algorithm,Advances in Cryptology, Crypto’90 Proceedings,Springer-verlag, 1991,303-311.
[22]Rivest,R,L.,The MD5 message-digest algorithm,Requset for Comments(RFC 1320),Intemet Activities Boardjntemet PrivacyTask Force, 1992.
[23] Zheng,Y,,Pieprzyk,J.,Seberry,J.,HAVAL-A one-way Hashing Algorithm with Variable Length of Output, Advances in Cryptology, Auscrypto'92 Proceedings,Springer-verlag,1993,83-104,
[24] B.V.Rompay, A.Biryukov, B.Preneel, and J.Vandewalle, Cryptanalysis of 3-pass HAVAL, Advances in Cryptology-Asiacrypt'2003, LNCS 2894, Springer-Verlag, 2003,228-245.