基于缩减轮数的SHA-1的LPMAC区分攻击和53步SHA-1-MAC的部分密钥恢复攻击
|
摘要
随着信息化的迅猛发展,信息已经成为世界发展过程中不可或缺的资源,而信息安全在信息社会中扮演着至关重要的角色,它直接关系到社会生活方方面面的正常运行。特别是近些年随着电子商务的崛起,全球对信息安全方面的要求进一步提升,信息加密、认证技术及安全传输等方面变得格外重要。
密码技术是实现信息安全的基本方法,杂凑函数作为基础密码算法之一广泛应用于各个领域。近年来随着对杂凑函数破解的突破性进展,杂凑函数的设计与安全性分析成为密码学领域研究的热点。而杂凑函数的发展推动了消息认证码的研究,基于杂凑函数的消息认证码的安全性分析受到更多的关注。
本文主要是对基于缩减轮数的SHA-1的消息认证码(MAC)的安全性进行分析,在导师的悉心指导下,主要有以下结果：
(1)基于63步(5-67)SHA-1的LPMAC的区分攻击
首先在对SHA体系的碰撞攻击及王小云等关于LPMAC区分攻击思想进行学习的基础上,对乔思远等人基于63步(8-70步)SHA-1的LPMAC区分攻击进行分析,指出其中存在的问题,并通过编程搜索筛选出具有一定概率优势的差分路线,虽然扰动向量相同,但是差分路线整体进行了平移,利用王小云等提出的新的区分器构造方法,对基于63步(5-67步)SHA-1的LPMAC进行区分攻击。复杂度为2155次MAC询问,成功概率为0.70。
(2)基于66步(15-80)SHA-1的LPMAC的区分攻击
乔思远等人基于65步(12-76步)SHA-1的LPMAC区分攻击,避开原本不能超过40个条件的限制,使用单条路线代替两条路线进行区分器构造。同样利用该区分器构造方法,重新分析并寻找满足条件的差分路线,将LPMAC区分攻击扩展到了66步(15-80步),其复杂度为281次MAC询问,成功概率为0.51。
(3)基于53步(20-72步)SHA-1-MAC的部分密钥恢复攻击
结合Contini等人关于HMAC-MD5部分密钥恢复攻击技术及王小云等人关于MD5-MAC部分密钥恢复攻击的思想,搜索并筛选出符合条件的差分路线,该路线最初由Rechberger提出,在推导出路线成立的充要条件的基础上,提出53步(20-72步)的SHA-1-MAC的部分密钥恢复攻击,由于截断的SHA-1是从第二轮开始,所以对于SHA-1-MAC中的子密钥K1只看作是分为3个32比特的K1[1],K1[2]和K1[3],最终恢复K的96比特以及子密钥K0的160比特,复杂度为2106次MAC询问。
With the rapid development of information, information has become an important resource for the world development. Information security plays a very important role, which is directly related to the normal operation of all respects in society life. Particu-larly, with the rise of e-commerce in recent years, requirements on global information security improves, message encryption, authentication and security transmission beco-me more and more important.
The cipher technique is the basic method in the information security application, as one of its based algorithms, the hash function not only has become the theory foundation, but also has been extensively applied in many fields. Recently, with the breakthrough of the analysis of hash function, hash function design and analysis of the filed of information security has become a hot issue. Furthermore, the development of hash function promotes the research of Message Authentication Code(MAC). The security of hash-based MAC algorithms gets more attention.
The thesis analyzes the security of MAC algorithms based on SHA-1, under the guidance of our tutor, the results are as follows:
(1) Distinguishing attacks on LPMAC instantiated with 63-step(5-67) SHA-1
Based on the in-depth analysis of collisions of SHA-System and Wang et.al's distinguishing attacks on LPMAC, point out and correct the mistakes in Qiao et.al's distinguishing attacks on LPMAC instantiated with 63-step(8-70) SHA-1. Then, design a program to search for and choose a suitable differential path. The disturbance vector we found is same with the one Qiao et.al used, but shifted to different position. Combined with the new distinguisher proposed by Wang et. al, we successfully apply the distinguishing attack on LPMAC instantiated with 63-step SHA-1, while the complexity is 2155 queries and success rate is 0.70.
(2) Distinguishing attacks on LPMAC instantiated with 66-step(15-80) SHA-1
The method,which is used on distinguishing attack on LPMAC instantiated with 65-step SHA-1 by Qiao et. al, makes use of a single differential path instead of the doubled differential path to surpass the restriction of 40 conditions. We re-construct distinguisher, search for and choose a suitable differential path.By this way, we can reach up to 66-step SHA-1, with the complexity is 281 queries and success rate is 0.51.
(3) Partial key recovery attacks on 53-step(20-72) SHA-1-MAC
Combined with Contini et.al's partial key recovery attacks on HMAC-MD5 and Wang et.al's key recovery attacks on MD5-MAC, using the differential path found by program,which is first proposed by Rechberger, and deducing the necessary and sufficient conditions that the differential path holds, we give the partial key recovery attacks on 53-step(20-72) SHA-1-MAC. Because the differential path starts at the 20th step, we only consider the subkey K1 is transformed into 3 32-bit K1[1], K1[2] and K1[3].We recovery subkey K1 of 96 bits and subkey Ko of 160 bits. The complexity is 2106 MAC queries.
密码技术是实现信息安全的基本方法,杂凑函数作为基础密码算法之一广泛应用于各个领域。近年来随着对杂凑函数破解的突破性进展,杂凑函数的设计与安全性分析成为密码学领域研究的热点。而杂凑函数的发展推动了消息认证码的研究,基于杂凑函数的消息认证码的安全性分析受到更多的关注。
本文主要是对基于缩减轮数的SHA-1的消息认证码(MAC)的安全性进行分析,在导师的悉心指导下,主要有以下结果：
(1)基于63步(5-67)SHA-1的LPMAC的区分攻击
首先在对SHA体系的碰撞攻击及王小云等关于LPMAC区分攻击思想进行学习的基础上,对乔思远等人基于63步(8-70步)SHA-1的LPMAC区分攻击进行分析,指出其中存在的问题,并通过编程搜索筛选出具有一定概率优势的差分路线,虽然扰动向量相同,但是差分路线整体进行了平移,利用王小云等提出的新的区分器构造方法,对基于63步(5-67步)SHA-1的LPMAC进行区分攻击。复杂度为2155次MAC询问,成功概率为0.70。
(2)基于66步(15-80)SHA-1的LPMAC的区分攻击
乔思远等人基于65步(12-76步)SHA-1的LPMAC区分攻击,避开原本不能超过40个条件的限制,使用单条路线代替两条路线进行区分器构造。同样利用该区分器构造方法,重新分析并寻找满足条件的差分路线,将LPMAC区分攻击扩展到了66步(15-80步),其复杂度为281次MAC询问,成功概率为0.51。
(3)基于53步(20-72步)SHA-1-MAC的部分密钥恢复攻击
结合Contini等人关于HMAC-MD5部分密钥恢复攻击技术及王小云等人关于MD5-MAC部分密钥恢复攻击的思想,搜索并筛选出符合条件的差分路线,该路线最初由Rechberger提出,在推导出路线成立的充要条件的基础上,提出53步(20-72步)的SHA-1-MAC的部分密钥恢复攻击,由于截断的SHA-1是从第二轮开始,所以对于SHA-1-MAC中的子密钥K1只看作是分为3个32比特的K1[1],K1[2]和K1[3],最终恢复K的96比特以及子密钥K0的160比特,复杂度为2106次MAC询问。
With the rapid development of information, information has become an important resource for the world development. Information security plays a very important role, which is directly related to the normal operation of all respects in society life. Particu-larly, with the rise of e-commerce in recent years, requirements on global information security improves, message encryption, authentication and security transmission beco-me more and more important.
The cipher technique is the basic method in the information security application, as one of its based algorithms, the hash function not only has become the theory foundation, but also has been extensively applied in many fields. Recently, with the breakthrough of the analysis of hash function, hash function design and analysis of the filed of information security has become a hot issue. Furthermore, the development of hash function promotes the research of Message Authentication Code(MAC). The security of hash-based MAC algorithms gets more attention.
The thesis analyzes the security of MAC algorithms based on SHA-1, under the guidance of our tutor, the results are as follows:
(1) Distinguishing attacks on LPMAC instantiated with 63-step(5-67) SHA-1
Based on the in-depth analysis of collisions of SHA-System and Wang et.al's distinguishing attacks on LPMAC, point out and correct the mistakes in Qiao et.al's distinguishing attacks on LPMAC instantiated with 63-step(8-70) SHA-1. Then, design a program to search for and choose a suitable differential path. The disturbance vector we found is same with the one Qiao et.al used, but shifted to different position. Combined with the new distinguisher proposed by Wang et. al, we successfully apply the distinguishing attack on LPMAC instantiated with 63-step SHA-1, while the complexity is 2155 queries and success rate is 0.70.
(2) Distinguishing attacks on LPMAC instantiated with 66-step(15-80) SHA-1
The method,which is used on distinguishing attack on LPMAC instantiated with 65-step SHA-1 by Qiao et. al, makes use of a single differential path instead of the doubled differential path to surpass the restriction of 40 conditions. We re-construct distinguisher, search for and choose a suitable differential path.By this way, we can reach up to 66-step SHA-1, with the complexity is 281 queries and success rate is 0.51.
(3) Partial key recovery attacks on 53-step(20-72) SHA-1-MAC
Combined with Contini et.al's partial key recovery attacks on HMAC-MD5 and Wang et.al's key recovery attacks on MD5-MAC, using the differential path found by program,which is first proposed by Rechberger, and deducing the necessary and sufficient conditions that the differential path holds, we give the partial key recovery attacks on 53-step(20-72) SHA-1-MAC. Because the differential path starts at the 20th step, we only consider the subkey K1 is transformed into 3 32-bit K1[1], K1[2] and K1[3].We recovery subkey K1 of 96 bits and subkey Ko of 160 bits. The complexity is 2106 MAC queries.
引文
[1]冯登国,裴定一,密码学导引,科学出版社,1999年4月
[2]R.Merkle. One Way Hash Functions and DES. Proceedings, CRYPTO89, Published by Springer-Verlag,1989.
[3]R. Merkle,:Security, Authentication and Public Key System. Ph. D. Thesis, Stanford University, June 1979.
[4]B.Preneel. Analysis and Design of Cryptographic Hash Functions, PhD Thesis, Feb. 2003.
[5]E.Bilham, A.Shamir. Differential cryptanalysis of DES-like cryptosystems, Journal of Cryptology, Vol.4, No.1,pp.3-72,1991.
[6]X. Wang and H. Yu, How to Break MD5 and Other Hash Funtions, Advances in Cryptology-Proceedings of EUROCRYPT2005, LNCS 3494, pp.19-35, Springers-Verlog,2005.
[7]X. Wang, X.Lai, D.Feng, H. Chen and X. Yu, Cryptanalysis of the Hash Funtions MD4 and RIPEMD, Advances in Cryptology-Proceedings of EUROCRYPT 2005, LNCS 3494, pp.1-18, Springers-Verlag,2005.
[8]王小云安全杂凑函数(SHA-体制)的攻击(国内交流)
[9]FIPS 180-1:Secure Hash Standard, Federal Inforation Processing Standards Publication, NIST, April 1995.
[10]M. Bellare, J. Kilian, P. Rogaway. The Security of the Cipher Block Chaining Message Authentication Code, CRYPTO 1994, LNCS 839, pp.342-358, Springer-Verlag,1994.
[11]ISO/IEC 9797, Data Cryptographic Techniques-Data Integrity Mechanism Using a Cryptographic Check Function Employing a Block Cipher Algorithm,1989.
[12]K.Kurosawa and T. Iwatw, TMAC:Two-Key CBC MAC. Topics in Cryptology, Proceedings of CT-RSA 2003,LNCS 2612,pp.33-49,Springer-Verlag,2003.
[13]T. Iwata and K. Kurosawa, OMAC:One-Key CBC MAC, Proceedings of FSE 2003, LNCS 2887, pp.129-153. Springer-Verlag,2003.
[14]E. Jaulmes, A. Joux and F. Valette, On the security of randomized CBC-MAC beyond the birthday paradox limit:A new construction,Pro-ceedings of FSE 2002,LNCS 2365, pp.237-251. Springer-Verlag,2002.
[15]M. Bellare, R. Canetti and H. Krawczyk, Keying Hash Funtions for Messang Authentication, Advances in Cryptology-Proceedings of CRYPTO 1996, LNCS 1109, pp.1-15, Springer-Verlag,1996.
[16]G.Tsudik. Message Authentication with One-Way Hash Functions.ACM Computer Communications Review, vol.22,no.5,pp.29-38,1992.
[17]B. Preneel, P. C. van Oorschot, MDx-MAC and building fast MACs from hash funtions, Advances in Cryptology-Proceedings of CRYPTO 1995, lncs 963, pp.1-14, Springer-Verlag,1995.
[18]M. Bellare, R. Guerin, P. Rogaway. XOR MACs:New Methods for Message Authentication Using Finite Pseudorandom Functions. Advances in Cryptology-CRYPTO'95, LNCS 963, pp.15-28, Springer,1995.
[19]J. Black, S. Halevi, H. Krawczyk. UMAC:Fast and Secure Message Authentication. Advances in Cryptology-CRYPTO'99, LNCS 1666, pp.79, Springer, Berlin/Heidelberg,1999.
[20]NIST. SP 800-38D, Recommendation for Block Cipher Modes of Operation: Galois/Counter Mode(GCM) and GMAC.2007.
[21]G. Rose, A Stream Cipher Based on Linear Feedback over GF(2), Proceedings of ACISP 1998, LNCS 1438, pp.135-146, Springers-Verlag,1998.
[22]Wang,X., Yu, H., Wang,W., Zhang, H., Zhan, T.:Cryptanalysis on HMAC/NMAC-MD5 and MD5-MAC. In:Joux, A. (ed.)EUROCRYPT 2009. LNCS, vol 5479, pp.121-133. Springer, Heidelberg(2009)
[23]X.Wang, W.Wang, K.Jia, M. Wang. New Distinguishing Attack on MAC using Secret-Prefix Method. FSE 2009, LNCS vol 3810, pp.363-374. Springer, Heidelberg(2009)
[24]S. Contini, Y.L. Yin, Forgery and Key-Recovery Attacks on HMAC and NMAC Using Hash Collisions. ASIACRYPT 2006, LNCS 4284, pp.37-53, Springer,2006
[25]P. A. Fouque, G. Leurent, P. Q. Nguyen. Full Key-Recovery Attacks on HMAC/NMAC-MD4 and NMAC-MD5.CRYPTO 2007.LNCS 4622,pp.13-30. Springer, Heidelberg 2007.
[26]L.Wang, K.Ohta, N. Kunihiro. New Key-Recovery Attacks on HMAC/NMAC-MD4 and NMAC-MD5.EUROCRYPT 2008.LNCS 4965,pp.237-253. Springer, Heidelberg 2008.
[27]M,Bellare.:New proofs for NMAC and HMAC:Security without collision resistance. In:Dwork, C.(ed.) CRYPTO 2006. lncs, VOL.4117, pp.602-619. Springer, Heidelberg(2006)
[28]X. Wang, Y. L. Yin and H. Yu, Finding Collisions in the Full SHA-1, Advances in Cryptology-Proceedings of CRYPTO 2005, LNCS 3621, pp.17-36, Springers-Verlag,2005.
[29]X. Wang, H.Yu and Y. L.Yin, Efficirnt Collision Search Attacks on SHA-0, Advances in Cryptology-Proceedings of CRYPTO 2005, LNCS 3494, pp.1-16, Springers-Verlag,2005.
[30]H. Yu, G.Wang, G. Zhang and X. Wang, The Second-Preimage Attack on MD4, Proceedings of CANS 2005, LNCS 3810, pp.1-12, Springers-Verlag,2005.
[31]E. Biham and R. Chen, Near-Collisions of SHA-0, Advances in Cryptology-Proceedings of CRYPTO 2004, LNCS 3152, pp.290-305,Springers-Verlag,2004.
[32]E. Biham, R. Chen, A. Joux, P.Carribault, C.Lemuet and W. Jalby, Collisions of SHA-0 and Reduced SHA-1, Advances in Cryptology-Proceedings of EUROCRYPT 2005, LNCS 3494, pp.22-35, Springers-Verlag,2005.
[33]J.Kim, A.Biryukov, B.Preneel, S.Hong:On the Security of HMAC and NMAC Based on HAVAL, MD4, MD5, SHA-0 and SHA-1. SCN 2006, LNCS 4116, pp. 242-256. Springer,2006.
[34]B. den Boer, A. Bosselaers.:Collisions for the Compression Function of MD5. In:Helleseth, T.(ed.) EUROCRYPT 1993. LNC3, vol.765, pp.293-304. Springer, Heidelberg(1994).
[35]C. Rechberger, V. Rijmen.:On Authentication with HMAC and Non-random Properties. In:Dietrich, S., Dhamija, R.(eds.) Financial Cryptography 2007. LNCS, vol.4886, pp.119-133. Springer, Heidelberg(2007).
[36]C. Rechberger, V. Rijmen.:New Results on NMAC/HMAC when Instantiated with Popular Hash Functions. Journal of Universal Computer Science,14(3), pp.347-376(2008).
[2]R.Merkle. One Way Hash Functions and DES. Proceedings, CRYPTO89, Published by Springer-Verlag,1989.
[3]R. Merkle,:Security, Authentication and Public Key System. Ph. D. Thesis, Stanford University, June 1979.
[4]B.Preneel. Analysis and Design of Cryptographic Hash Functions, PhD Thesis, Feb. 2003.
[5]E.Bilham, A.Shamir. Differential cryptanalysis of DES-like cryptosystems, Journal of Cryptology, Vol.4, No.1,pp.3-72,1991.
[6]X. Wang and H. Yu, How to Break MD5 and Other Hash Funtions, Advances in Cryptology-Proceedings of EUROCRYPT2005, LNCS 3494, pp.19-35, Springers-Verlog,2005.
[7]X. Wang, X.Lai, D.Feng, H. Chen and X. Yu, Cryptanalysis of the Hash Funtions MD4 and RIPEMD, Advances in Cryptology-Proceedings of EUROCRYPT 2005, LNCS 3494, pp.1-18, Springers-Verlag,2005.
[8]王小云安全杂凑函数(SHA-体制)的攻击(国内交流)
[9]FIPS 180-1:Secure Hash Standard, Federal Inforation Processing Standards Publication, NIST, April 1995.
[10]M. Bellare, J. Kilian, P. Rogaway. The Security of the Cipher Block Chaining Message Authentication Code, CRYPTO 1994, LNCS 839, pp.342-358, Springer-Verlag,1994.
[11]ISO/IEC 9797, Data Cryptographic Techniques-Data Integrity Mechanism Using a Cryptographic Check Function Employing a Block Cipher Algorithm,1989.
[12]K.Kurosawa and T. Iwatw, TMAC:Two-Key CBC MAC. Topics in Cryptology, Proceedings of CT-RSA 2003,LNCS 2612,pp.33-49,Springer-Verlag,2003.
[13]T. Iwata and K. Kurosawa, OMAC:One-Key CBC MAC, Proceedings of FSE 2003, LNCS 2887, pp.129-153. Springer-Verlag,2003.
[14]E. Jaulmes, A. Joux and F. Valette, On the security of randomized CBC-MAC beyond the birthday paradox limit:A new construction,Pro-ceedings of FSE 2002,LNCS 2365, pp.237-251. Springer-Verlag,2002.
[15]M. Bellare, R. Canetti and H. Krawczyk, Keying Hash Funtions for Messang Authentication, Advances in Cryptology-Proceedings of CRYPTO 1996, LNCS 1109, pp.1-15, Springer-Verlag,1996.
[16]G.Tsudik. Message Authentication with One-Way Hash Functions.ACM Computer Communications Review, vol.22,no.5,pp.29-38,1992.
[17]B. Preneel, P. C. van Oorschot, MDx-MAC and building fast MACs from hash funtions, Advances in Cryptology-Proceedings of CRYPTO 1995, lncs 963, pp.1-14, Springer-Verlag,1995.
[18]M. Bellare, R. Guerin, P. Rogaway. XOR MACs:New Methods for Message Authentication Using Finite Pseudorandom Functions. Advances in Cryptology-CRYPTO'95, LNCS 963, pp.15-28, Springer,1995.
[19]J. Black, S. Halevi, H. Krawczyk. UMAC:Fast and Secure Message Authentication. Advances in Cryptology-CRYPTO'99, LNCS 1666, pp.79, Springer, Berlin/Heidelberg,1999.
[20]NIST. SP 800-38D, Recommendation for Block Cipher Modes of Operation: Galois/Counter Mode(GCM) and GMAC.2007.
[21]G. Rose, A Stream Cipher Based on Linear Feedback over GF(2), Proceedings of ACISP 1998, LNCS 1438, pp.135-146, Springers-Verlag,1998.
[22]Wang,X., Yu, H., Wang,W., Zhang, H., Zhan, T.:Cryptanalysis on HMAC/NMAC-MD5 and MD5-MAC. In:Joux, A. (ed.)EUROCRYPT 2009. LNCS, vol 5479, pp.121-133. Springer, Heidelberg(2009)
[23]X.Wang, W.Wang, K.Jia, M. Wang. New Distinguishing Attack on MAC using Secret-Prefix Method. FSE 2009, LNCS vol 3810, pp.363-374. Springer, Heidelberg(2009)
[24]S. Contini, Y.L. Yin, Forgery and Key-Recovery Attacks on HMAC and NMAC Using Hash Collisions. ASIACRYPT 2006, LNCS 4284, pp.37-53, Springer,2006
[25]P. A. Fouque, G. Leurent, P. Q. Nguyen. Full Key-Recovery Attacks on HMAC/NMAC-MD4 and NMAC-MD5.CRYPTO 2007.LNCS 4622,pp.13-30. Springer, Heidelberg 2007.
[26]L.Wang, K.Ohta, N. Kunihiro. New Key-Recovery Attacks on HMAC/NMAC-MD4 and NMAC-MD5.EUROCRYPT 2008.LNCS 4965,pp.237-253. Springer, Heidelberg 2008.
[27]M,Bellare.:New proofs for NMAC and HMAC:Security without collision resistance. In:Dwork, C.(ed.) CRYPTO 2006. lncs, VOL.4117, pp.602-619. Springer, Heidelberg(2006)
[28]X. Wang, Y. L. Yin and H. Yu, Finding Collisions in the Full SHA-1, Advances in Cryptology-Proceedings of CRYPTO 2005, LNCS 3621, pp.17-36, Springers-Verlag,2005.
[29]X. Wang, H.Yu and Y. L.Yin, Efficirnt Collision Search Attacks on SHA-0, Advances in Cryptology-Proceedings of CRYPTO 2005, LNCS 3494, pp.1-16, Springers-Verlag,2005.
[30]H. Yu, G.Wang, G. Zhang and X. Wang, The Second-Preimage Attack on MD4, Proceedings of CANS 2005, LNCS 3810, pp.1-12, Springers-Verlag,2005.
[31]E. Biham and R. Chen, Near-Collisions of SHA-0, Advances in Cryptology-Proceedings of CRYPTO 2004, LNCS 3152, pp.290-305,Springers-Verlag,2004.
[32]E. Biham, R. Chen, A. Joux, P.Carribault, C.Lemuet and W. Jalby, Collisions of SHA-0 and Reduced SHA-1, Advances in Cryptology-Proceedings of EUROCRYPT 2005, LNCS 3494, pp.22-35, Springers-Verlag,2005.
[33]J.Kim, A.Biryukov, B.Preneel, S.Hong:On the Security of HMAC and NMAC Based on HAVAL, MD4, MD5, SHA-0 and SHA-1. SCN 2006, LNCS 4116, pp. 242-256. Springer,2006.
[34]B. den Boer, A. Bosselaers.:Collisions for the Compression Function of MD5. In:Helleseth, T.(ed.) EUROCRYPT 1993. LNC3, vol.765, pp.293-304. Springer, Heidelberg(1994).
[35]C. Rechberger, V. Rijmen.:On Authentication with HMAC and Non-random Properties. In:Dietrich, S., Dhamija, R.(eds.) Financial Cryptography 2007. LNCS, vol.4886, pp.119-133. Springer, Heidelberg(2007).
[36]C. Rechberger, V. Rijmen.:New Results on NMAC/HMAC when Instantiated with Popular Hash Functions. Journal of Universal Computer Science,14(3), pp.347-376(2008).