摘要
Hash函数是密码学领域的重要分支,在数字签名、消息认证、完整性检测等领域有着广泛的应用。近年来,人们对于Hash函数的密码分析已经取得了突破性进展,设计、分析、评价Hash函数已成为密码学领域的热门话题。
Hash函数的设计主要有迭代结构和压缩函数两个方面,本文回顾了Hash函数的基本设计原理以及常用的攻击方法,介绍了最经典结构Merkle-Damg(?)rd迭代结构与它存在的缺陷和漏洞.在此基础上,研究了三种典型Hash函数的变种攻击,讨论了模差分与异或差分之间的关系,主要的研究结果如下:
Chabaud-Joux攻击是对SHA系列Hash函数最成功的攻击之一,它是基于寻找寄存器差分的修正样式.我们给出了SHA-256压缩函数的三种变种形式,分析了SHA-256的变种抵抗Chabaud-Joux攻击的能力,并与对SHA-256的攻击结果进行比较,进而分析SHA-256压缩函数选择上的优劣性。
SMASH是一个全新的Hash函数,基于前推性质,介绍了SMASH的算法设计与攻击方法,为使算法免疫这种攻击,讨论了改进SMASH的方案,改进的主要思想是破坏前推性质和增加寻找可预测差分的复杂性.
模运算和异或运算是Hash函数压缩函数中常用的两种运算,相应的差分为模差分和异或差分.本文给出了模差分与异或差分相互转化的充分必要条件,得到了在给定异或差分的条件下,求保持模差分不变的整数对的算法;讨论了模差分与异或差分在Hash函数安全性分析中的应用,作为实例,给出了寻找消息认证码(MAC)函数ASP的伪碰撞的具体方法.
Hash function is one of the most important embranchment in modern cryptology, which is widely used in digital signature schemes, message authentication and integrity checking. Recently, many break through have been made in Hash function's cryptanalysis. Now, designing, analysing and evaluating a Hash function have become a hot topic in cryptology field.
Design of hash functions includes iterated structure design and compression function design. Basic design principles and common attack methods are reviewed in this paper, the most classical iterated structure, Merkle-Damgard structure is described, limitations and leaks are also studied. On this basis, the paper explores three kinds of forms of compress functions of classic Hash, discusses the relationship between addition arithmetic and XOR arithmetic. Main work as follows:
Chabaud-Joux attack, which is based on finding a corrective pattern for the register is one of the most successful attacks on the SHA algorithms. In this paper, we present three kinds of variant forms of compress functions of SHA-256, and analysis the security of three variants against the Chabaud-Joux attack compared with SHA-256. It follows that the selection of the compression function's structure highly affects the complexity of the attack. Furthermore, a local collision in the vulnerable variant is presented.
SMASH is a new hash function proposal, based on the property of forward prediction. The design principle and attack method of SMASH are described, and some approaches such that SMASH can resist on this attack are suggested. The main measures are destroying forward prediction property and increasing the complexity of find divinable difference.
Addition arithmetic and XOR arithmetic are usually used in the design of hash functions; the corresponding differences are called addition difference and XOR difference, respectively. The paper presents a sufficient and necessary condition of the transition of addition-XOR differences, and an algorithm of finding the integer pairs which preserve addition differences when XOR differences are given, and studies their applications in analyzing the security of Hash function. As an example, we show how to find a pseudo-collision in a Message Authentication Code function which is called ASP.
引文
[1] Shannon C E. Communication Theory of Secret System. Bell System Technical Journal.1949,28: 656-715
[2] Advanced Hash Standard Competition, http: //csrc.nist.gov/pki/Hash Workshop/
[3] Bellare M. and Rogaway P.,Introduction to Modern Cryptography. UCSD course. CSE207.
[4] Rivest R.L.,The MD4 Message Digest Algorithm,Request for Comments (RFC) 1320,Internet Activities Board,Internet PrivacZ Task Force, 1992.
[5] Zheng Y.,Pieprzyk J.,and Seberry J.,HAVAL-a one way hashing algorithm with variable length of output.In Advances in Cryptology-Auscrypt'92(J.Seberry and Y.Zheng,eds.),LNCS718,pp.83-104, Springer-Verlag, 1993.
[6] Rijmen V.,Cryptanalysis and design of iterated block ciphers, Katholieke Universiteit Leuven, Belgium,9 October 1997.
[7] Dodis Y.,Oliveira R.,and Pietrzak K.,On the Generic Insecurity of the Full Domain Hash,Advances in Cryptology -CRYPTO-2005,LNCS 3621,pp.449-466,Springer-Verlag,2005.
[8] FIPS 180-1. Secure Hash standard. NIST, US Department of Commerce, Springer-Verlag:Washington DC, 1996.
[9] Barreto P. S. L. M. and Rijmen V.,The Whirlpool Hashing function. Primitive submitted to NESSIE, 2000. Available at http: //www.cryptonessie.org/.
[10] Barreto P. and Rijmen V.,The Whirlpool Hashing Function,First open NESSIE Workshop,Leuven,Belgium,13-14 November 2000.
[11] Knudsen L., Rechberger C., and Thomsen S., Grindahl - a family of hash functions, Fast Software Encryption-FSE2007, LNCS4593, pp.39-57, Springer,2007.
[12] Rabin M.O.,Digitalized Signatures. In R. A. Demillo,D. P. Dopkin,A. K. Jones and R. J.Lipton,editors,Foundations of Secure Computation, pp.l55-166,New York,1978,Academic Press.
[13] Meyer C.H. and Matyas S.M.,Cryptography: a New Dimension in Data Security. Wiley & Sons, 1982.
[14] Preneel B., Govaerts R., and J. Vandewalle, Hash functions based on block cipers, In Advances in Cryptology-CRYPTO'93, LNCS 773, pp.368-378. Springer-Verlag, 1994.
[15] Black J. Rogaway P.,and Shrimpton T.,Black-box analysis of the block-cipher-based hash function constructions from PGV, CRYPTO'02, LNCS 2442, pp.320-335, Springer-Verlag, 2002.
[16] Luby M. and Rackoff C, How to construct pseudorandom permutations from pseudorandom functions. SIAM Journal on Computing Vol. 17, pp.373-386, No. 2 (1988).
[17] Dobbertin H, Cryptanalysis of MD4. Fast Software Encryption,1996,LNCS 1039: 5369.
[18] Kasselman P. A fast attack on the MD4 Hash Function. Proceedings of the 1997 South African Symposiumon Communications and Signal Processing (COMSIG'97), 1997,147 150.
[19] Boer B den, Bosselaers A. Collisions for the compression function of MD5. Advances in Cryptology, Eurocrypt'93,1994, LNCS 765: 293-304.
[20] Dobbertin H. Cryptanalysis of MD5 Compress. Advances in Cryptology, Eurocrypt'96,Rump Session, 1996.
[21] Chabaud F, Joux A. Differential collisions in SHA-0. Advances in Cryptology, Crypto'98,1998, LNCS 1462: 56-71.
[22] Biham E, Chen R. Near collision for SHA-0. Advances in Cryptology, Crypto'04, 2004,LNCS 3152: 290-305.
[23] X. Y. Wang, D. G. Feng, X. J. Lai, and H. B. Yu. Collisions for Hash Functions MD4, MD5,HAVAL-128 and RIPEMD. Rump session of Crypto'04 and IACR Eprint archive, August 2004.
[24] X.Y.Wang and H. B. Yu. How to Break MD5 and Other Hash Functions. Advances in Cryptology-Eurocrypt'05, pp.19-35, Springer-Verlag, May 2005.
[25] X. Y. Wang. The Collision attack on SHA-O. In Chinese, to appear on www.infosec.edu.cn,1997.
[26] X.Y.Wang and H. B. Yu. Finding Collisions in the Full SHA-1. In:Victor Shoup. Advances in Cryptology CRYPTO 2005, California, USA: Springer- Verlag, 2005, 3621: 17-36.
[27] Lipmaa H and Moriai S. Efficient Algorithms for Computing Differential Properties of Addition. Fast Software Encryption 2001, 2355, 336-350.
[28] Paul C van Oorschot, Michael J Wiener.Parallel Collision Search with Cryptanalytic Applications. Journal of Cryptology, 1999;(12):l-28.
[29] Mihir Bellare, Tadayoshi Kohno.Hash Function Balance and its Impact on Birthday Attacks.In: Eurocrypt'04, LNCS 3027, Springer-Verlaq, 2004.
[30] Damgard I., A design principle for hash functions. Advances in Crypyology-CRYPTO'89,LNCS 435, pp.416-427, Springer-Verlag, 1990.
[31] Menezes A.J., Oorschot P.C. van, and Vanstone S.A., Handbook of A pp.lied Cryptography,CRC Press, 1997.
[32] Joux A., Multicollisions in iterated Hash functions. Application to cascaded constructions.Crypto-2004, LNCS 3152, pp.306-316, Springer-Verlag, 2004.
[33] Praveen Gauravaram, William Millan, Juanma Gonzalez Nieto, and Edward Dawson. 3c-a provably secure pseudorandom function and message authentication code, a new mode of operation for cryptographic hash function. Cryptology ePrint Archive, Report 2005/390,2005.http: //eprint.iarc.org
[34] Kelsey J. and Gauravaram P., Linear checksums don't help Damg°ard-Merkle, Rump session, Crypto 2006.
[35] Coron J.S.,Dodis Y., Malinaud C, and Puniya P., Merkle-Damgard revisited: How to construct a Hash Function, In Advances in Cryptology—CRYPTO'05, LNCS 3621,pp.430-448, Springer-Verlag, 2005.
[36] Dean R. D., Formal Aspects of Mobiel Code Security. Ph.D. dissertation, Princeton University, 1999.
[37] Kelsey J. and Schneier B., Second preimages on n-bit hash functions for much less than 2n work.EUROCRYPT 2005,LNCS 3494,pp.474-490,Springer-Verlag,2005.
[38]Kelsey J.and Kohno T.,Herding Hash Functions and the Nostradamus Attack,EUROCRYPT 2006,LNCS 4004,pp.183-200,Springer-Verlag,2006.
[39]Weis R.and Lucks S.Cryptographic Hash Functions Recent Results on Cryptanalysis and their Implications on System Security.
[40]Luck S.,A Failure-Friendly Design Principle for Hash Functions,ASIACRYPT 2005,LNCS3788,pp.474-494,Springer-Verlag,2005.
[41]Secure Hash Standard(SHS).National Institute of Standards and Technology,Federal Information Processing Standards(FIPS) Publication,2004,180-2.
[42]Matusiewicz K,Pieprzyk J,Pramstallern,Rechberger C,Rijmen V.Analysis of simplied variants of SHA-256.In WEWoRC 2005 Western European Workshop in Cryptology,2005,-74.
[43]Yoshida H,Biryukov A.Analysis of a SHA-256 variant.Selected Areas in Cryptography (SAC 2005),Kingston,Ontario,Canada,2005,245-260.
[44]Gllbert H,Handschuh H.Security analysis of SHA-256 and sisters.Selected Areas in Cryptography'03,Lecture Notes in Computer Science,2003,3006,175 - 193.
[45]Chabaud F,Joux A.Differential Collisions in SHA-0.Advances in Crypyology-CRYPYO'98,Lecture Notes in Computer Science,1998,1462,56-71.
[46]Hawkes P,Paddon M,Rose G.On Corrective Patterns for the SHA-2 Family.Cryptology ePrint Archive,August 2004,2004/207.
[47]L.R.Knudsen.SMASH- A Cryptographic Hash Function.In H.Gilbert and H.Handsch,editors,Fast Software Encryption,volume 3557 of Lecture Notes in Computer Science,pages228-242.Springer,2005.
[48]N.Pramstaller Breaking a New Hash Function Design Strategy Called SMASH.Conference Hash Functions- Krakow.
[49]N.Pramstaller,C.Rechberger,and V.Rijmen.Smashing SMASH.Cryptology ePrint Archive,Report 2005/081,2005.http://eprint.iacr.org/.
[50]Biham E,Chen R.Near-Collisions of SHA-0.In:Franklin,M K.Advances in Cryptology -CRYPTO 2004,California,USA:Springer-Verlag,2004,3152:290-305.
[51]Lipmaa H and Moriai S.Efficient Algorithms for Computing Differential Properties of Addition.Fast Software Encryption 2001,2355,336-350.
[52]Bellefroid Ⅰ and Beyen K.Evaluation van de Cryptografische Veiligheid Van Anti-Virus Paketten(Evaluation of the Security of Anti-Virus Software - in Dutch),EAST Laboratorium,Katholieke Universiteit Leuven,Thesis grad.,1992.
[53]多磊,《从分组密码到Hash函数设计》,博士论文.
[54]李超、魏悦川、孙兵,SHA-256压缩函数的结构安全性.应用科学学报,已录用,待发表.
[55]魏悦川、李超,模差分与异或差分的性质及其应用,第五届中国信息和通信安全学术会议(CCICS'2007),科学出版社,2007,pp.106-109.
