杂凑函数原象攻击的方法研究
|
摘要
Hash函数作为密码学的一个重要工具,在数字签名、消息认证和数据完整性方面有着广泛的应用。关于Hash函数的安全性分析是密码学中的一个重要而活跃的研究课题。近来出现的常见Hash函数算法的原象攻击方法,对于Hash函数的研究具有重要意义。与碰撞攻击相比较,原象攻击的难度较大,但原象攻击对Hash函数的影响将是致命的。
本论文对近两年国际上提出的对MD-4、MD-5和SHA-0的原象攻击方法进行了深入的分析与研究,提出了改进方案,主要完成的工作如下:
(1)对MD-4布尔函数的吸收特性、压缩函数的可逆性、消息扩展方式的特殊性、中间相遇攻击以及随机图理论进行了深入的研究和总结。
(2)对Leurent提出的MD-4原象攻击的方法进行了改进,分别提出两种改进方案。第一种方案将攻击的空间复杂度从231降低到216,第二种方案将攻击的时间复杂度从2102降低到298。
(3)深入分析了Yu Sasaki等的MD-5原象攻击方法,进一步探讨了Leurent的方法用于MD-5原象攻击的困难性。对已有的减少轮次的MD-5原象攻击方法和完整的MD-5原象攻击方法进行了分析比较,剖析了完整的MD-5原象攻击方法的思路来源。同时对一种新的可行初始结构方式进行了探讨。
(4)深入分析了Cannière等的50步SHA-0原象攻击方法和K. Aoki等的52步SHA-0原象攻击方法,并尝试用消息修改技术解决状态变量的选取问题;同时对部分伪原象的计算与转化的复杂度的平衡点问题进行了探索。
As an important tool in cryptography,hash functions have been widely used in digital signatures, message authentication, data integrity and so on. The security analysis of hash functions is a dominant and active topic in cryptography. Recently appeared preimage attacks on hash function algorithms play a very important role in this realm. Compared with the collision attack,the preimage attack is more difficult to achieve. However, the preimage attack has a fatal effect on hash functions.
In this thesis, the methods of preimage attacks on MD-4, MD-5 and SHA-0 which were proposed on the international conference for the past two years are analyzed. Then the improved schemes are proposed. The main work in this thesis includes:
(1) The absorption properties of boolean functions, reversibility of compression functions, specificity of message expansion on MD-4, the meet-in-middle attacks and random graph theory are researched and summarized deeply.
(2) Leurent’s method is improved by our methods. The space complexity of the attack is reduced from 231 to 216 by the first scheme. The time complexity of the attack is reduced from 2102 to 298 by the second scheme.
(3) The difficulties that the Leurent’s method applies to MD-5 are further analyzed. After comparision of preimage attacks between ones to the reduced steps MD-5 and full MD-5, the idea source of Yu Sasaki’s preimage attack on full MD-5 is analyzed. Another feasible initial structure is experimented.
(4) Two preimage attacks for reduced SHA-0 are analyzed. One is the 50 steps of SHA-0 propsed by Cannière, and the other is the 52 steps of SHA-0 propsed by K.Aoki. Message modification techniques are tried to apply for choosing the state variables. At the same time, the balance complexity between the calculation and transformation of partial pseudo-preimage is explored.
本论文对近两年国际上提出的对MD-4、MD-5和SHA-0的原象攻击方法进行了深入的分析与研究,提出了改进方案,主要完成的工作如下:
(1)对MD-4布尔函数的吸收特性、压缩函数的可逆性、消息扩展方式的特殊性、中间相遇攻击以及随机图理论进行了深入的研究和总结。
(2)对Leurent提出的MD-4原象攻击的方法进行了改进,分别提出两种改进方案。第一种方案将攻击的空间复杂度从231降低到216,第二种方案将攻击的时间复杂度从2102降低到298。
(3)深入分析了Yu Sasaki等的MD-5原象攻击方法,进一步探讨了Leurent的方法用于MD-5原象攻击的困难性。对已有的减少轮次的MD-5原象攻击方法和完整的MD-5原象攻击方法进行了分析比较,剖析了完整的MD-5原象攻击方法的思路来源。同时对一种新的可行初始结构方式进行了探讨。
(4)深入分析了Cannière等的50步SHA-0原象攻击方法和K. Aoki等的52步SHA-0原象攻击方法,并尝试用消息修改技术解决状态变量的选取问题;同时对部分伪原象的计算与转化的复杂度的平衡点问题进行了探索。
As an important tool in cryptography,hash functions have been widely used in digital signatures, message authentication, data integrity and so on. The security analysis of hash functions is a dominant and active topic in cryptography. Recently appeared preimage attacks on hash function algorithms play a very important role in this realm. Compared with the collision attack,the preimage attack is more difficult to achieve. However, the preimage attack has a fatal effect on hash functions.
In this thesis, the methods of preimage attacks on MD-4, MD-5 and SHA-0 which were proposed on the international conference for the past two years are analyzed. Then the improved schemes are proposed. The main work in this thesis includes:
(1) The absorption properties of boolean functions, reversibility of compression functions, specificity of message expansion on MD-4, the meet-in-middle attacks and random graph theory are researched and summarized deeply.
(2) Leurent’s method is improved by our methods. The space complexity of the attack is reduced from 231 to 216 by the first scheme. The time complexity of the attack is reduced from 2102 to 298 by the second scheme.
(3) The difficulties that the Leurent’s method applies to MD-5 are further analyzed. After comparision of preimage attacks between ones to the reduced steps MD-5 and full MD-5, the idea source of Yu Sasaki’s preimage attack on full MD-5 is analyzed. Another feasible initial structure is experimented.
(4) Two preimage attacks for reduced SHA-0 are analyzed. One is the 50 steps of SHA-0 propsed by Cannière, and the other is the 52 steps of SHA-0 propsed by K.Aoki. Message modification techniques are tried to apply for choosing the state variables. At the same time, the balance complexity between the calculation and transformation of partial pseudo-preimage is explored.
引文
[1] R. L. Rivest. The MD4 Message Digest Algorithm[C]. CRYPTO 1990. Springer-Verlag, 1991. 303-311.
[2] R. L. Rivest. The MD5 Message Digest Algorithm[C]. Request for Comments (RFC 1320), Internet Activities Board, Internet Privacy Task Force, 1992.
[3] Y. Zheng, J. Pieprzyk, J. Seberry. HAVAL-A One-way Hashing Algorithm with Variable Length of Output[C]. Auscrypto’92 Proceedings. 83-104.
[4] RIPE, Integrity Primitives for Secure Information Systems, Final Report of RACE Integrity Primitives Evalutiobn (RIPE-RACE 1040), LNCS 1007.1995.
[5] FIPS 180-0, Secure Hash Standard[S]. NIST, US Department of Commerce, Washington D. C., May 1993.
[6] FIPS 180-1, Secure Hash Standard[S]. NIST, US Department of Commerce, Washington D.C., April 1995. Springer-Verlag, 1996.
[7] FIPS 180-2, Secure Hash Standard[S]. http: // csrc. nist. gov/ publications/ , 2002.
[8] B. Preneel. Analysis and Design of Cryptographic Hash Functions[D]. PhD thesis, Katholieke Universiteit Leuven, 1993.
[9] Alfred J. Menezes, Paul C. van Oorschot, Scott A.Vanstone著.胡磊,王鹏等译.应用密码学手册[M].北京:电子工业出版社. 2005.
[10] X. Y. Wang, X. J. Lai, D. G. Feng, H. Chen, X. Y. YU. Cryptanalysis of the Hash Functions MD4 and RIPEMD [C]. EUROCRYPT 2005. LNCS 3494. 2005. 1-18.
[11] X.Y. Wang, H. B. Yu. How to Break MD5 and Other Hash Function [C]. EUROCRYPT 2005, LNCS 3494. 2005. 19-35.
[12] X.Y. Wang, H. B.Yu. Finding Collisions in the Full SHA-1[C]. CRYPTO 2005. LNCS 3621. 2005. 17-36.
[13] G. Leurent. MD4 is Not One-Way[C]. FSE 2008. LNCS 5086. 2008. 412–428.
[14] C. De Cannière and C. Rechberger. Preimages for Reduced SHA-0 and SHA-1[C]. CRYPTO 2008. LNCS 5157. 2008. 179-202.
[15] K. Aoki, Y. Sasaki. Meet-in-the-Middle Preimage Attacks Against Reduced SHA-0 and SHA-1[C]. CRYPTO 2009. LNCS 5677. 2009. 70-89.
[16] Y. Sasaki, K. Aoki. Finding Preimages in Full MD5 Faster than ExhaustiveSearch[C]. EUROCRYPT 2009. LNCS 5479. 2009. 134-152.
[17]章照止主编.现代密码学基础[M].北京邮电大学出版社. 2004年.
[18]于红波.杂凑函数以及HMAC/NMAC的安全性分析[D].济南:山东大学, 2007.4.
[19]杨波.现代密码学[M].清华大学出版社. 2003.163-184.
[20] Birthday Attack. http://en.wikipedia.org/wiki/Birthday_attack.
[21] X. J. Lai, J. L. Massey. Hash Function Based on Block Ciphers[C], EUROCRYPT 1992.
[22] M.-J.O. Saarinen, A Meet-in-the-Middle Collision Attack Against the New FORK-256[C]. INDOCRYPT 2007. LNCS 4859. 2007. 10-17.
[23] A. Joux. Multicollisions in Iterated Hash Functions[C]. CRYPTO 2004. LNCS 3152. 2004. 306–316.
[24] Krystian Matusiewicz, M.Sc. Analysis of Modern Dedicated Cryptographic Hash Functions[D]. Macquarie University, 2007.8.
[25] R. D. Dean. Formal Aspects of Mobile Code Security[D]. Princeton University, 1999. http://www.cs.princeton.edu/sip/pub/ddean-dissertation.php3.
[26] J. Kelsey, B. Schneier. Second Preimages on n-Bit Hash Functions for Much Less than 2n Work[C]. EUROCRYPT 2005. LNCS 3494. 2005. 474-490.
[27] H. Dobbertin. The First Two Rounds of MD4 are Not One -Way [C]. FSE 1998. LNCS 1372.1998. 284–292.
[28]温巧燕,钮心忻,杨义先著.现代密码学中的布尔函数[M].北京:科学出版社. 2000. 8.
[29] H. Yu, G. Wang, G. Zhang, X. Wang. The Second-Preimage Attack on MD4[C].CANS 2005. LNCS 3810. 2005. 1-12.
[30] V. Klima. Finding MD5 Collisions on a Notebook PC Using Multi-message Modifications[C]. ISCSPI 2005.
[31] Y. Sasaki, K. Aoki. Preimage Attacks on Step-Reduced MD5[C]. ACISP 2008. LNCS 5107. 2008. 282–296.
[32] J. -P. Aumasson, W. Meier, F. Mendel, Preimage Attacks on 3-pass HAVAL and Step-Reduced MD5[C]. SAC 2008. LNCS 5381. 2009. 120-135.
[33] K. Aoki, Y. Sasaki. Preimage Attacks on One-Block MD4, 63-Step MD5 and More[C]. SAC 2008. LNCS 5381. 2009. 103-119.
[34] J. Black, M. Cochran, T. Highland. A Study of MD5 Attacks: Insights and Improvements[C]. FSE 2006. LNCS 4047. 2006. 262-277.
[35]徐金福. HASH函数HAS-160和MD5潜在威胁的分析[D].济南:山东大学.2007.5.
[36]梁杰. MD5-HASH函数的安全性分析[D].上海:上海交通大学. 2007.1.
[37]冯登国著.密码分析学[M].清华大学出版社. 2000. 8.
[38]王小云,张金清. MD5报文摘要算法的各圈函数分析[J].计算机工程与科学. 18.(2), 1996.4.
[39] T. Xie, F. B. Liu, D. G. Feng. Could the 1-MSB Input Difference Be The Fastest Collsion Attack for MD5[C].Cryptology eprint Archive. 2008.
[40] Y. Sasaki, K. Aoki. A Preimage Attack for 52-steps HAS-160 [C]. In: Preproceedings of Information Security and Cryptology ICISC 2008.
[41] Y. Sasaki, K. Aoki. Preimage Attacks on 3, 4, and 5-Pass HAVAL[C]. ASIACRYPT 2008. LNCS 5350. 2008. 253–271.
[42] C . De Cannière, F .Mendel, C. Rechberger. Collisions for 70-Step SHA-1: On the Full Cost of Collision Search[C]. SAC 2007. LNCS 4876. 2007. 56-73.
[2] R. L. Rivest. The MD5 Message Digest Algorithm[C]. Request for Comments (RFC 1320), Internet Activities Board, Internet Privacy Task Force, 1992.
[3] Y. Zheng, J. Pieprzyk, J. Seberry. HAVAL-A One-way Hashing Algorithm with Variable Length of Output[C]. Auscrypto’92 Proceedings. 83-104.
[4] RIPE, Integrity Primitives for Secure Information Systems, Final Report of RACE Integrity Primitives Evalutiobn (RIPE-RACE 1040), LNCS 1007.1995.
[5] FIPS 180-0, Secure Hash Standard[S]. NIST, US Department of Commerce, Washington D. C., May 1993.
[6] FIPS 180-1, Secure Hash Standard[S]. NIST, US Department of Commerce, Washington D.C., April 1995. Springer-Verlag, 1996.
[7] FIPS 180-2, Secure Hash Standard[S]. http: // csrc. nist. gov/ publications/ , 2002.
[8] B. Preneel. Analysis and Design of Cryptographic Hash Functions[D]. PhD thesis, Katholieke Universiteit Leuven, 1993.
[9] Alfred J. Menezes, Paul C. van Oorschot, Scott A.Vanstone著.胡磊,王鹏等译.应用密码学手册[M].北京:电子工业出版社. 2005.
[10] X. Y. Wang, X. J. Lai, D. G. Feng, H. Chen, X. Y. YU. Cryptanalysis of the Hash Functions MD4 and RIPEMD [C]. EUROCRYPT 2005. LNCS 3494. 2005. 1-18.
[11] X.Y. Wang, H. B. Yu. How to Break MD5 and Other Hash Function [C]. EUROCRYPT 2005, LNCS 3494. 2005. 19-35.
[12] X.Y. Wang, H. B.Yu. Finding Collisions in the Full SHA-1[C]. CRYPTO 2005. LNCS 3621. 2005. 17-36.
[13] G. Leurent. MD4 is Not One-Way[C]. FSE 2008. LNCS 5086. 2008. 412–428.
[14] C. De Cannière and C. Rechberger. Preimages for Reduced SHA-0 and SHA-1[C]. CRYPTO 2008. LNCS 5157. 2008. 179-202.
[15] K. Aoki, Y. Sasaki. Meet-in-the-Middle Preimage Attacks Against Reduced SHA-0 and SHA-1[C]. CRYPTO 2009. LNCS 5677. 2009. 70-89.
[16] Y. Sasaki, K. Aoki. Finding Preimages in Full MD5 Faster than ExhaustiveSearch[C]. EUROCRYPT 2009. LNCS 5479. 2009. 134-152.
[17]章照止主编.现代密码学基础[M].北京邮电大学出版社. 2004年.
[18]于红波.杂凑函数以及HMAC/NMAC的安全性分析[D].济南:山东大学, 2007.4.
[19]杨波.现代密码学[M].清华大学出版社. 2003.163-184.
[20] Birthday Attack. http://en.wikipedia.org/wiki/Birthday_attack.
[21] X. J. Lai, J. L. Massey. Hash Function Based on Block Ciphers[C], EUROCRYPT 1992.
[22] M.-J.O. Saarinen, A Meet-in-the-Middle Collision Attack Against the New FORK-256[C]. INDOCRYPT 2007. LNCS 4859. 2007. 10-17.
[23] A. Joux. Multicollisions in Iterated Hash Functions[C]. CRYPTO 2004. LNCS 3152. 2004. 306–316.
[24] Krystian Matusiewicz, M.Sc. Analysis of Modern Dedicated Cryptographic Hash Functions[D]. Macquarie University, 2007.8.
[25] R. D. Dean. Formal Aspects of Mobile Code Security[D]. Princeton University, 1999. http://www.cs.princeton.edu/sip/pub/ddean-dissertation.php3.
[26] J. Kelsey, B. Schneier. Second Preimages on n-Bit Hash Functions for Much Less than 2n Work[C]. EUROCRYPT 2005. LNCS 3494. 2005. 474-490.
[27] H. Dobbertin. The First Two Rounds of MD4 are Not One -Way [C]. FSE 1998. LNCS 1372.1998. 284–292.
[28]温巧燕,钮心忻,杨义先著.现代密码学中的布尔函数[M].北京:科学出版社. 2000. 8.
[29] H. Yu, G. Wang, G. Zhang, X. Wang. The Second-Preimage Attack on MD4[C].CANS 2005. LNCS 3810. 2005. 1-12.
[30] V. Klima. Finding MD5 Collisions on a Notebook PC Using Multi-message Modifications[C]. ISCSPI 2005.
[31] Y. Sasaki, K. Aoki. Preimage Attacks on Step-Reduced MD5[C]. ACISP 2008. LNCS 5107. 2008. 282–296.
[32] J. -P. Aumasson, W. Meier, F. Mendel, Preimage Attacks on 3-pass HAVAL and Step-Reduced MD5[C]. SAC 2008. LNCS 5381. 2009. 120-135.
[33] K. Aoki, Y. Sasaki. Preimage Attacks on One-Block MD4, 63-Step MD5 and More[C]. SAC 2008. LNCS 5381. 2009. 103-119.
[34] J. Black, M. Cochran, T. Highland. A Study of MD5 Attacks: Insights and Improvements[C]. FSE 2006. LNCS 4047. 2006. 262-277.
[35]徐金福. HASH函数HAS-160和MD5潜在威胁的分析[D].济南:山东大学.2007.5.
[36]梁杰. MD5-HASH函数的安全性分析[D].上海:上海交通大学. 2007.1.
[37]冯登国著.密码分析学[M].清华大学出版社. 2000. 8.
[38]王小云,张金清. MD5报文摘要算法的各圈函数分析[J].计算机工程与科学. 18.(2), 1996.4.
[39] T. Xie, F. B. Liu, D. G. Feng. Could the 1-MSB Input Difference Be The Fastest Collsion Attack for MD5[C].Cryptology eprint Archive. 2008.
[40] Y. Sasaki, K. Aoki. A Preimage Attack for 52-steps HAS-160 [C]. In: Preproceedings of Information Security and Cryptology ICISC 2008.
[41] Y. Sasaki, K. Aoki. Preimage Attacks on 3, 4, and 5-Pass HAVAL[C]. ASIACRYPT 2008. LNCS 5350. 2008. 253–271.
[42] C . De Cannière, F .Mendel, C. Rechberger. Collisions for 70-Step SHA-1: On the Full Cost of Collision Search[C]. SAC 2007. LNCS 4876. 2007. 56-73.