×

New second-preimage attacks on hash functions. (English) Zbl 1365.94397

Summary: In this work, we present several new generic second-preimage attacks on hash functions. Our first attack is based on the herding attack and applies to various Merkle-Damgård-based iterative hash functions. Compared to the previously known long-message second-preimage attacks, our attack offers more flexibility in choosing the second-preimage message at the cost of a small computational overhead. More concretely, our attack allows the adversary to replace only a few blocks in the original target message to obtain the second preimage. As a result, our new attack is applicable to constructions previously believed to be immune to such second-preimage attacks. Among others, these include the dithered hash proposal of Rivest, Shoup’s UOWHF, and the ROX constructions. In addition, we also suggest several time-memory-data tradeoff attack variants, allowing for a faster online phase, and even finding second preimages for shorter messages. We further extend our attack to sequences stronger than the ones suggested in Rivest’s proposal. To this end we introduce the kite generator as a new tool to attack any dithering sequence over a small alphabet. Additionally, we analyse the second-preimage security of the basic tree hash construction. Here we also propose several second-preimage attacks and their time-memory-data tradeoff variants. Finally, we show how both our new and the previous second-preimage attacks can be applied even more efficiently when multiple short messages, rather than a single long target message, are available.
A preliminary version of this paper appeared in Eurocrypt 2008, Lect. Notes Comput. Sci. 4965, 270–288 (2008; Zbl 1149.94302).

MSC:

94A60 Cryptography

Citations:

Zbl 1149.94302

Software:

Skein Hash
PDFBibTeX XMLCite
Full Text: DOI HAL

References:

[1] J.P. Allouche, Sur la complexité des suites infinies. Bull. Belg. Math. Soc.1, 133-143 (1994). citeseer.ist.psu.edu/allouche94sur.html · Zbl 0803.68094
[2] E. Andreeva, C. Bouillaguet, P. Fouque, J.J. Hoch, J. Kelsey, A. Shamir, S. Zimmer, Second preimage attacks on dithered hash functions, in ed. by N.P. Smart. Advances in Cryptology EUROCRYPT 2008, 27th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Istanbul, Turkey, April 13-17, 2008. Proceedings. Lecture Notes in Computer Science, vol. 4965 (Springer, 2008), pp. 270-288. doi:10.1007/978-3-540-78967-3_16 · Zbl 1149.94302
[3] E. Andreeva, B. Mennink, Provable chosen-target-forced-midfix preimage resistance, in eds. by A. Miri, S. Vaudenay. Selected Areas in Cryptography—18th International Workshop, SAC 2011, Toronto, ON, Canada, August 11-12, 2011. Revised Selected Papers. Lecture Notes in Computer Science, vol. 7118 (Springer, 2011), pp. 37-54. doi:10.1007/978-3-642-28496-0_3
[4] E. Andreeva, G. Neven, B. Preneel, T. Shrimpton, Seven-property-preserving iterated hashing: ROX, in ed. by K. Kurosawa. ASIACRYPT’07. Lecture Notes in Computer Science, vol. 4833 (Springer, 2007), pp. 130-146 · Zbl 1153.94342
[5] J.P. Aumasson, L. Henzen, W. Meier, R.C.W. Phan, SHA-3 proposal BLAKE. Submission to NIST (2008). http://131002.net/blake/blake.pdf
[6] M. Bellare, T. Ristenpart, Multi-property-preserving hash domain extension and the EMD transform, in eds. by X. Lai, K Chen. Advances in Cryptology—ASIACRYPT 2006, 12th International Conference on the Theory and Application of Cryptology and Information Security, Shanghai, China, December 3-7, 2006, Proceedings. Lecture Notes in Computer Science, vol. 4284 (Springer, 2006), pp. 299-314 · Zbl 1172.94561
[7] M. Bellare, P. Rogaway, Collision-resistant hashing: towards making UOWHFs practical, in ed. by Jr., B.S.K. CRYPTO. Lecture Notes in Computer Science, vol. 1294 (Springer, 1997), pp. 470-484 · Zbl 0882.94015
[8] E. Biham, R. Chen, A. Joux, P. Carribault, C. Lemuet, W. Jalby, Collisions of SHA-0 and reduced SHA-1, in ed. by R. Cramer. Advances in Cryptology—EUROCRYPT 2005, 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, May 22-26, 2005, Proceedings. Lecture Notes in Computer Science, vol. 3494 (Springer, 2005), pp. 36-57 · Zbl 1137.94337
[9] E. Biham, O. Dunkelman, A framework for iterative hash functions—HAIFA (2006). http://www.csrc.nist.gov/pki/HashWorkshop/2006/Papers/DUNKELMAN_NIST3.pdf, presented at the second NIST hash workshop (August 24-25, 2006) · Zbl 1091.68086
[10] A. Biryukov, A. Shamir, Cryptanalytic time/memory/data tradeoffs for stream ciphers, in ed. by T. Okamoto. ASIACRYPT. Lecture Notes in Computer Science, vol. 1976 (Springer, 2000), pp. 1-13 · Zbl 0980.94013
[11] C. de Cannière, F. Mendel, C. Rechberger, Collisions for 70-step SHA-1: on the full cost of collision search, in eds. by C.M. Adams, A. Miri, M.J. Wiener. Selected Areas in Cryptography. Lecture Notes in Computer Science, vol. 4876 (Springer, 2007), pp. 56-73 · Zbl 1154.94387
[12] C. de Cannière, C. Rechberger, Finding SHA-1 characteristics: general results and applications, in X. Lai, K. Chen (eds.), Advances in Cryptology—ASIACRYPT 2006, 12th International Conference on the Theory and Application of Cryptology and Information Security, Shanghai, China, December 3-7, 2006, Proceedings. Lecture Notes in Computer Science, vol. 4284 (Springer, 2006), pp. 1-20 · Zbl 1172.94572
[13] C. de Cannière, C. Rechberger, Preimages for reduced SHA-0 and SHA-1, in ed by D. Wagner. CRYPTO. Lecture Notes in Computer Science, vol. 5157 (Springer, 2008), pp. 179-202 · Zbl 1183.94027
[14] Cobham, A.: Uniform tag sequences. Mathematical Systems Theory 6(3), 164-192 (1972) · Zbl 0253.02029 · doi:10.1007/BF01706087
[15] J.S. Coron, Y. Dodis, C. Malinaud, P. Puniya, Merkle-damgård revisited: How to construct a hash function, in CRYPTO’05 (2005), pp. 430-448 · Zbl 1145.94436
[16] I. Damgård, A design principle for hash functions, in ed. by G. Brassard. CRYPTO ’89, Santa Barbara, California, USA, August 20-24, 1989, Proceedings. Lecture Notes in Computer Science, vol. 435 (Springer, 1990), pp. 416-427
[17] R.D. Dean, Formal Aspects of Mobile Code Security. Ph.D. thesis, Princeton University (January 1999)
[18] Ehrenfeucht, A., Lee, K.P., Rozenberg, G.: Subword Complexities of Various Classes of Deterministic Developmental Languages without Interactions. Theor. Comput. Sci. 1(1), 59-75 (1975). · Zbl 0316.68043 · doi:10.1016/0304-3975(75)90012-2
[19] W. Feller, An Introduction to Probability Theory and Its Applications, vol. 1, chap. 12. (Wiley, 1971) · Zbl 0219.60003
[20] N. Ferguson, S. Lucks, B. Schneier, D. Whiting, M. Bellare, T. Kohno, J. Callas, J. Walker, The Skein hash function family. Submission to NIST (2008). http://www.skein-hash.info/sites/default/files/skein.pdf
[21] N. Ferguson, S. Lucks, B. Schneier, D. Whiting, M. Bellare, T. Kohno, J. Callas, J. Walker, The Skein hash function family. Submission to NIST (Round 1) (2008). http://www.skein-hash.info/sites/default/files/skein1.1.pdf
[22] S. Halevi, H. Krawczyk, Strengthening digital signatures via randomized hashing, in ed. by C. Dwork. CRYPTO. Lecture Notes in Computer Science, vol. 4117 (Springer, 2006), pp. 41-59 · Zbl 1161.94443
[23] Hellman, M.E.: A Cryptanalytic Time-Memory Trade Off. In: IEEE Transactions on Information Theory. vol. 26, pp. 401-406 (1980). · Zbl 0436.94016 · doi:10.1109/TIT.1980.1056220
[24] Janson, S., Lonardi, S., Szpankowski, W.: On average sequence complexity. Theor. Comput. Sci. 326(1-3), 213-227 (2004). · Zbl 1091.68086 · doi:10.1016/j.tcs.2004.06.023
[25] A. Joux, Multicollisions in iterated hash functions. Application to cascaded constructions, in ed. by M.K. Franklin. CRYPTO’04. Lecture Notes in Computer Science, vol. 3152 (Springer, 2004), pp. 306-316 · Zbl 1104.68043
[26] A. Joux, S. Lucks, Improved generic algorithms for 3-collisions, in ed. by M. Matsui. Advances in Cryptology—ASIACRYPT 2009, 15th International Conference on the Theory and Application of Cryptology and Information Security, Tokyo, Japan, December 6-10, 2009. Proceedings. Lecture Notes in Computer Science, vol. 5912 (Springer, 2009), pp. 347-363 · Zbl 1267.94070
[27] A. Joux, T. Peyrin, Hash functions and the (amplified) boomerang attack, in ed. by A. Menezes. CRYPTO. Lecture Notes in Computer Science, vol. 4622. (Springer, 2007), pp. 244-263 · Zbl 1215.94056
[28] J. Kelsey, T. Kohno, Herding hash functions and the nostradamus attack, in ed. by S. Vaudenay. EUROCRYPT. Lecture Notes in Computer Science, vol. 4004 (Springer, 2006), pp. 183-200 · Zbl 1140.94354
[29] J. Kelsey, B. Schneier, Second preimages on n-bit hash functions for much less than \[2^{\text{ n }}\] n work, in ed. by R. Cramer, Advances in Cryptology—EUROCRYPT 2005, 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, May 22-26, 2005, Proceedings. Lecture Notes in Computer Science, vol. 3494 (Springer, 2005), pp. 474-490 · Zbl 1137.94350
[30] V. KeränenKeränen, Abelian squares are avoidable on 4 letters, in ed. by W. Kuich. ICALP. Lecture Notes in Computer Science, vol. 623 (Springer, 1992), pp. 41-52 · Zbl 1425.68331
[31] V. Klima, Tunnels in hash functions: MD5 collisions within a minute. Cryptology ePrint Archive, Report 2006/105 (2006). http://eprint.iacr.org/
[32] G. Leurent, Md4 is not one-way, in ed. by Nyberg, K. FSE. Lecture Notes in Computer Science, vol. 5086 (Springer, 2008), pp. 412-428 · Zbl 1154.68400
[33] Leurent, G.: Practical key-recovery attack against APOP, an MD5-based challenge-response authentication. IJACT 1(1), 32-46 (2008). · Zbl 1178.94196 · doi:10.1504/IJACT.2008.017049
[34] S. Lucks, A failure-friendly design principle for hash functions, in ed. by B.K. Roy. ASIACRYPT. Lecture Notes in Computer Science, vol. 3788 (Springer, 2005), pp. 474-494 · Zbl 1154.94414
[35] K. Matusiewicz, M. Naya-Plasencia, I. Nikolic, Y. Sasaki, M. Schläffer, Rebound attack on the full lane compression function, in ed. by M. Matsui. Advances in Cryptology—ASIACRYPT 2009, 15th International Conference on the Theory and Application of Cryptology and Information Security, Tokyo, Japan, December 6-10, 2009. Proceedings. Lecture Notes in Computer Science, vol. 5912 (Springer, 2009), pp. 106-125 · Zbl 1267.94083
[36] F. Mendel, T. Peyrin, C. Rechberger, M. Schläffer, Improved cryptanalysis of the reduced Grøstl compression function, ECHO permutation and AES block cipher, in eds. by Jr., M.J.J., Rijmen V., Safavi-Naini R. Selected Areas in Cryptography. Lecture Notes in Computer Science, vol. 5867 (Springer, 2009), pp. 16-35 · Zbl 1267.94084
[37] F. Mendel, C. Rechberger, M. Schläffer, S.S. Thomsen, The rebound attack: cryptanalysis of reduced whirlpool and Grøstl, in ed. by O. Dunkelman. FSE. Lecture Notes in Computer Science, vol. 5665 (Springer, 2009), pp. 260-276 · Zbl 1291.94130
[38] A. Menezes, P. van Oorschot, S. Vanstone, Handbook of Applied Cryptography. citeseer.ist.psu.edu/428600.html · Zbl 0868.94001
[39] R.C. Merkle, One way hash functions and DES, in ed. by G. Brassard, CRYPTO ’89, Santa Barbara, California, USA, August 20-24, 1989, Proceedings. Lecture Notes in Computer Science, vol. 435 (Springer, 1990), pp. 428-446
[40] M. Naor, M. Yung, Universal one-way hash functions and their cryptographic applications. in STOC (ACM, 1989), pp. 33-43
[41] J.J. Pansiot, Complexité des Facteurs des Mots Infinis Engendrés Par Morphismes Itérés, in ed. by J. Paredaens. 11th ICALP, Antwerpen. LNCS, vol. 172 (Springer, july 1984), pp. 380-389. http://lsiit.u-strasbg.fr/Publications/1984/Pan84a
[42] Pleasants, P.A.: Non-repetitive sequences. Mat. Proc. Camb. Phil. Soc. 68, 267-274 (1970). · Zbl 0237.05010 · doi:10.1017/S0305004100046077
[43] R.L. Rivest, Abelian square-free dithering for iterated hash functions. Presented at ECRYPT Hash Function Workshop, June 21, 2005, Krakow, and at the Cryptographic Hash workshop, November 1, 2005, Gaithersburg, Maryland (2005)
[44] P. Rogaway, T. Shrimpton, Cryptographic hash-function basics: definitions, implications, and separations for preimage resistance, second-preimage resistance, and collision resistance, in eds. by B.K., Roy, W. Meier. FSE. Lecture Notes in Computer Science, vol. 3017 (Springer, 2004), pp. 371-388 · Zbl 1079.68560
[45] Y. Sasaki, K. Aoki, Finding preimages in full md5 faster than exhaustive search, in ed. by A. Joux. EUROCRYPT. Lecture Notes in Computer Science, vol. 5479 (Springer, 2009), pp. 134-152 · Zbl 1239.94064
[46] V. Shoup, A composition theorem for universal one-way hash functions, in ed. by B. Preneel. EUROCRYPT’00. Lecture Notes in Computer Science, vol. 1807 (Springer, 2000), pp. 445-452 · Zbl 1082.94531
[47] X. Wang, X. Lai, D., Feng, H. Chen, X. Yu, Cryptanalysis of the hash functions MD4 and RIPEMD, in ed. by R. Cramer, Advances in Cryptology—EUROCRYPT 2005, 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, May 22-26, 2005, Proceedings. Lecture Notes in Computer Science, vol. 3494 (Springer, 2005), pp. 1-18 · Zbl 1137.94358
[48] X. Wang, Y.L. Yin, H. Yu, Finding collisions in the full SHA-1, in ed. by V. Shoup. Advances in Cryptology—CRYPTO 2005: 25th Annual International Cryptology Conference, Santa Barbara, California, USA, August 14-18, 2005, Proceedings. Lecture Notes in Computer Science, vol. 3621 (Springer, 2005), pp. 17-36 · Zbl 1145.94454
[49] X. Wang, H. Yu, How to break MD5 and other hash functions, in ed. by R. Cramer, Advances in Cryptology—EUROCRYPT 2005, 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, May 22-26, 2005, Proceedings. Lecture Notes in Computer Science, vol. 3494 (Springer, 2005), pp. 19-35 · Zbl 1137.94359
[50] X. Wang, H. Yu, Y.L. Yin, Efficient collision search attacks on SHA-0, in ed. by V. Shoup. Advances in Cryptology—CRYPTO 2005: 25th Annual International Cryptology Conference, Santa Barbara, California, USA, August 14-18, 2005, Proceedings. Lecture Notes in Computer Science, vol. 3621 (Springer, 2005), pp. 1-16 · Zbl 1145.94455
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.