Abstract
We provide a proof of security for a huge class of double block length hash function that we will call Cyclic-DM. Using this result, we are able to give a collision resistance bound for Abreast-DM, one of the oldest and most well-known constructions for turning a block cipher with n-bit block length and 2n-bit key length into a 2n-bit cryptographic hash function. In particular, we show that when Abreast-DM is instantiated using a block cipher with 128-bit block length and 256-bit key length, any adversary that asks less than 2124.42 queries cannot find a collision with success probability greater than 1/2. Surprisingly, this about 15 years old construction is one of the few constructions that have the desirable feature of a near-optimal collision resistance guarantee.
We are also able to derive several DBL constructions that lead to compression functions offering an even higher security guarantee and more efficiency than Abreast-DM(e.g. share a common key). Furthermore we give a practical DBL construction that has the highest security guarantee of all DBL compression functions currently known in literature. We also provide a (relatively weak) analysis of preimage resistance for Cyclic-DM.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
ANSI. ANSI X9.31:1998: Digital Signatures Using Reversible Public Key Cryptography for the Financial Services Industry (rDSA). American National Standards Institute, pub-ANSI:adr (1998)
Black, J., Rogaway, P., Shrimpton, T.: Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 320–335. Springer, Heidelberg (2002)
Bosselaers, A., Preneel, B.: Integrity Primitives for Secure Information Systems. In: Bosselaers, A., Preneel, B. (eds.) RIPE 1992. LNCS, vol. 1007, p. 239. Springer, Heidelberg (1995)
Meyer, C., Matyas, S.: Secure program load with manipulation detection code (1988)
Coppersmith, D., Pilpel, S., Meyer, C.H., Matyas, S.M., Hyden, M.M., Oseas, J., Brachtl, B., Schilling, M.: Data authentication using modification dectection codes based on a public one way encryption function. U.S. Patent No. 4,908,861, March 13 (1990)
Cramer, R. (ed.): EUROCRYPT 2005. LNCS, vol. 3494. Springer, Heidelberg (2005)
Dean, R.D.: Formal aspects of mobile code security. PhD thesis, Princeton, NJ, USA, Adviser-Andrew Appel (1999)
den Boer, B., Bosselaers, A.: Collisions for the Compression Function of MD-5. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 293–304. Springer, Heidelberg (1994)
Even, S., Mansour, Y.: A construction of a cipher from a single pseudorandom permutation. In: Matsumoto, T., Imai, H., Rivest, R.L. (eds.) ASIACRYPT 1991. LNCS, vol. 739, pp. 210–224. Springer, Heidelberg (1991)
Fleischmann, E., Gorski, M., Lucks, S.: On the Security of Tandem-DM. In: Robshaw [33], pp. 84–103
Fleischmann, E., Gorski, M., Lucks, S.: Security of cyclic double block length hash functions including abreast-dm. Cryptology ePrint Archive, Report 2009/261 (2009), http://eprint.iacr.org/
Dobbertin, H.: The status of MD5 after a recent attack (1996)
Hattori, M., Hirose, S., Yoshida, S.: Analysis of double block length hash functions. In: Paterson, K.G. (ed.) Cryptography and Coding 2003. LNCS, vol. 2898, pp. 290–302. Springer, Heidelberg (2003)
Hirose, S.: Provably secure double-block-length hash functions in a black-box model. In: Park, C.-s., Chee, S. (eds.) ICISC 2004. LNCS, vol. 3506, pp. 330–342. Springer, Heidelberg (2005)
Hirose, S.: Some Plausible Constructions of Double-Block-Length Hash Functions. In: Robshaw, M.J.B. (ed.) FSE 2006. LNCS, vol. 4047, pp. 210–225. Springer, Heidelberg (2006)
Hohl, W., Lai, X., Meier, T., Waldvogel, C.: Security of iterated hash functions based on block ciphers. In: Stinson [39], pp. 379–390
ISO/IEC. ISO DIS 10118-2: Information technology - Security techniques - Hash-functions, Part 2: Hash-functions using an n-bit block cipher algorithm. First released in 1992 (2000)
J. Lee, D. Kwon. The Security of Abreast-DM in the Ideal Cipher Model. Cryptology ePrint Archive, Report 2009/225 (2009), http://eprint.iacr.org/
Kelsey, J., Schneier, B.: Second Preimages on n-Bit Hash Functions for Much Less than 2\(^{\mbox{n}}\) Work. In: Cramer [6], pp. 474–490
Kilian, J., Rogaway, P.: How to protect des against exhaustive key search. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 252–267. Springer, Heidelberg (1996)
Knudsen, L.R., Lai, X., Preneel, B.: Attacks on fast double block length hash functions. J. Cryptology 11(1), 59–72 (1998)
Knudsen, L.R., Muller, F.: Some attacks against a double length hash proposal. In: Roy, B. (ed.) ASIACRYPT 2005. LNCS, vol. 3788, pp. 462–473. Springer, Heidelberg (2005)
Lai, X., Massey, J.L.: Hash Functions Based on Block Ciphers. In: Rueppel, R.A. (ed.) EUROCRYPT 1992. LNCS, vol. 658, pp. 55–70. Springer, Heidelberg (1993)
Rabin, M.: Digitalized Signatures (1978)
Menezes, A., van Oorschot, P.C., Vanstone, S.A.: Handbook of Applied Cryptography. CRC Press, Boca Raton (1996)
Merkle, R.C.: One way hash functions and DES. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 428–446. Springer, Heidelberg (1990)
Nandi, M., Lee, W.I., Sakurai, K., Lee, S.-J.: Security analysis of a 2/3-rate double length compression function in the black-box model. In: Gilbert, H., Handschuh, H. (eds.) FSE 2005. LNCS, vol. 3557, pp. 243–254. Springer, Heidelberg (2005)
NIST National Institute of Standards and Technology. FIPS 180-1: Secure Hash Standard (April 1995), http://csrc.nist.gov
NIST National Institute of Standards and Technology. FIPS 180-2: Secure Hash Standard (April 1995), http://csrc.nist.gov
Preneel, B., Govaerts, R., Vandewalle, J.: Hash functions based on block ciphers: A synthetic approach. In: Stinson [39], pp. 368–378
Rivest, R.L.: RFC 1321: The MD5 Message-Digest Algorithm. Internet Activities Board (April 1992)
Rivest, R.L.: The md4 message digest algorithm. In: Menezes, A., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 303–311. Springer, Heidelberg (1991)
Robshaw, M.J.B. (ed.): FSE 2009. LNCS, vol. 5665, pp. 260–276. Springer, Heidelberg (2009)
Rogaway, P., Steinberger, J.P.: Constructing cryptographic hash functions from fixed-key blockciphers. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 433–450. Springer, Heidelberg (2008)
Rogaway, P., Steinberger, J.P.: Security/efficiency tradeoffs for permutation-based hashing. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 220–236. Springer, Heidelberg (2008)
Satoh, T., Haga, M., Kurosawa, K.: Towards secure and fast hash functions. TIEICE: IEICE Transactions on Communications/Electronics/Information and Systems (1999)
Stam, M.: Blockcipher Based Hashing Revisited. In: Robshaw [33]
Steinberger, J.P.: The collision intractability of mdc-2 in the ideal-cipher model. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 34–51. Springer, Heidelberg (2007)
Stinson, D.R. (ed.): CRYPTO 1993. LNCS, vol. 773. Springer, Heidelberg (1994)
Wang, X., Lai, X., Feng, D., Chen, H., Yu, X.: Cryptanalysis of the hash functions md4 and ripemd. In: Cramer [6], pp. 1–18
Wang, X., Yin, Y.L., Yu, H.: Finding collisions in the full sha-1. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 17–36. Springer, Heidelberg (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fleischmann, E., Gorski, M., Lucks, S. (2009). Security of Cyclic Double Block Length Hash Functions. In: Parker, M.G. (eds) Cryptography and Coding. IMACC 2009. Lecture Notes in Computer Science, vol 5921. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-10868-6_10
Download citation
DOI: https://doi.org/10.1007/978-3-642-10868-6_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-10867-9
Online ISBN: 978-3-642-10868-6
eBook Packages: Computer ScienceComputer Science (R0)