Abstract
Block-cipher-based compression functions serve an important purpose in cryptography since they allow to turn a given block cipher into a one-way hash function. While there are a number of secure double-block-length compression functions, there is little research on generalized constructions. This paper introduces the Counter-bDM family of multi-block-length compression functions, which, to the best of our knowledge, is the first provably secure block-cipher-based compression function with freely scalable output size. We present generic collisionand preimage-security proofs for it, and compare our results with those of existing double-block-length constructions. Our security bounds show that our construction is competitive with the best collision- and equal to the best preimage-security bound of existing double-block-length constructions.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Armknecht, F., Fleischmann, E., Krause, M., Lee, J., Stam, M., Steinberger, J.: The Preimage Security of Double-Block-Length Compression Functions. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 233–251. Springer, Heidelberg (2011)
Aumasson, J.-P., Henzen, L., Meier, W., Phan, R.C.-W.: SHA-3 proposal BLAKE. Submission to NIST, Round 3 (2010)
Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: Sponge functions. Ecrypt Hash Workshop (May 2007)
Biham, E., Dunkelman, O.: The SHAvite-3 Hash Function. Submission to NIST, Round 2 (2009)
Black, J.A., 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)
Meyer, C., Matyas, S.: Secure Program Load With Manipulation Detection Code (1988)
Chang, D., Nandi, M., Lee, J., Sung, J., Hong, S., Lim, J., Park, H., Chun, K.: Compression Function Design Principles Supporting Variable Output Lengths from a Single Small Function. IEICE Transactions 91-A(9), 2607–2614 (2008)
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)
Ewan Fleischmann. Analysis and Design of Blockcipher Based Cryptographic Algorithms. PhD thesis, Bauhaus-Universität Weimar (2013)
Fleischmann, E., Forler, C., Gorski, M., Lucks, S.: Collision-Resistant Double-Length Hashing. In: Heng, S.-H., Kurosawa, K. (eds.) ProvSec 2010. LNCS, vol. 6402, pp. 102–118. Springer, Heidelberg (2010)
Fleischmann, E., Forler, C., Lucks, S.: The Collision Security of MDC-4. In: Mitrokotsa, A., Vaudenay, S. (eds.) AFRICACRYPT 2012. LNCS, vol. 7374, pp. 252–269. Springer, Heidelberg (2012)
Fleischmann, E., Forler, C., Lucks, S., Wenzel, J.: Weimar-DM: A Highly Secure Double-Length Compression Function. In: Susilo, W., Mu, Y., Seberry, J. (eds.) ACISP 2012. LNCS, vol. 7372, pp. 152–165. Springer, Heidelberg (2012)
Fleischmann, E., Gorski, M., Lucks, S.: On the Security of Tandem-DM. In: Dunkelman, O. (ed.) FSE 2009. LNCS, vol. 5665, pp. 84–103. Springer, Heidelberg (2009)
Fleischmann, E., Gorski, M., Lucks, S.: Security of Cyclic Double Block Length Hash Functions. In: Parker, M.G. (ed.) Cryptography and Coding 2009. LNCS, vol. 5921, pp. 153–175. Springer, Heidelberg (2009)
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., 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. (ed.) FSE 2006. LNCS, vol. 4047, pp. 210–225. Springer, Heidelberg (2006)
Hirose, S.: Some Plausible Constructions of Double-Block-Length Hash Functions. In: Robshaw, M. (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, D.R. (ed.) Advances in Cryptology - CRYPTO 1993. LNCS, vol. 773, pp. 379–390. Springer, Heidelberg (1994)
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)
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)
Krause, M., Armknecht, F., Fleischmann, E.: Preimage Resistance Beyond the Birthday Bound: Double-Length Hashing Revisited. IACR Cryptology ePrint Archive 2010, 519 (2010)
Lai, X., Massey, J.L.: Hash Functions Based on Block Ciphers. In: Rueppel, R.A. (ed.) Advances in Cryptology - EUROCRYPT1992. LNCS, vol. 658, pp. 55–70. Springer, Heidelberg (1993)
Lee, J.: Provable Security of the Knudsen-Preneel Compression Functions. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 504–525. Springer, Heidelberg (2012)
Lee, J., Kwon, D.: The Security of Abreast-DM in the Ideal Cipher Model. Cryptology ePrint Archive, Report 2009/225 (2009), http://eprint.iacr.org/
Lee, J., Kwon, D.: The Security of Abreast-DM in the Ideal Cipher Model. IEICE Transactions 94-A(1), 104–109 (2011)
Lee, J., Stam, M.: MJH: A Faster Alternative to MDC-2. In: Kiayias, A. (ed.) CT-RSA 2011. LNCS, vol. 6558, pp. 213–236. Springer, Heidelberg (2011)
Lee, J., Stam, M., Steinberger, J.: The Collision Security of Tandem-DM in the Ideal Cipher Model. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 561–577. Springer, Heidelberg (2011)
Lee, J., Steinberger, J.P.: Multiproperty-Preserving Domain Extension Using Polynomial-Based Modes of Operation. IEEE Transactions on Information Theory 58(9), 6165–6182 (2012)
Lucks, S.: A Collision-Resistant Rate-1 Double-Block-Length Hash Function. In: Symmetric Cryptography (2007)
Luo, Y., Lai, X.: Attacks On a Double Length Blockcipher-based Hash Proposal. IACR Cryptology ePrint Archive 2011, 238 (2011)
Rabin, M.: Digitalized Signatures. In: De Millo, R., Dobkin, D., Jones, A., Lipton, R. (eds.) Foundations of Secure Computation, pp. 155–168. Academic Press (1978)
Mennink, B.: Optimal Collision Security in Double Block Length Hashing with Single Length Key. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 526–543. Springer, Heidelberg (2012)
Merkle, R.C.: One Way Hash Functions and DES. In: Brassard, G. (ed.) Advances in Cryptology - CRYPT0 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)
Ferguson, N., Lucks, S., Schneier, B., Whiting, D., Bellare, M., Kohno, T., Callas, J., Walker, J.: Skein Source Code and Test Vectors, http://www.skein-hash.info/downloads
Özen, O., Stam, M.: Another Glance at Double-Length Hashing. In: Parker, M.G. (ed.) Cryptography and Coding 2009. LNCS, vol. 5921, pp. 176–201. Springer, Heidelberg (2009)
Peyrin, T., Gilbert, H., Muller, F., Robshaw, M.J.B.: Combining Compression Functions and Block Cipher-Based Hash Functions. In: Lai, X., Chen, K. (eds.) ASIACRYPT 2006. LNCS, vol. 4284, pp. 315–331. Springer, Heidelberg (2006)
Rogaway, P., Shrimpton, T.: Cryptographic Hash-Function Basics: Definitions, Implications, and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance. In: Roy, B., Meier, W. (eds.) FSE 2004. LNCS, vol. 3017, pp. 371–388. Springer, Heidelberg (2004)
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)
Satoh, T., Haga, M., Kurosawa, K.: Towards Secure and Fast Hash Functions. TIEICE: IEICE Transactions on Communications/Electronics/Information and Systems (1999)
Stam, M.: Beyond Uniformity: Better Security/Efficiency Tradeoffs for Compression Functions. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 397–412. Springer, Heidelberg (2008)
Stam, M.: Blockcipher-Based Hashing Revisited. In: Dunkelman, O. (ed.) FSE 2009. LNCS, vol. 5665, pp. 67–83. Springer, Heidelberg (2009)
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)
Robert, S., Winternitz: A Secure One-Way Hash Function Built from DES. In: IEEE Symposium on Security and Privacy, pp. 88–90 (1984)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Abed, F., Forler, C., List, E., Lucks, S., Wenzel, J. (2014). Counter-bDM: A Provably Secure Family of Multi-Block-Length Compression Functions. In: Pointcheval, D., Vergnaud, D. (eds) Progress in Cryptology – AFRICACRYPT 2014. AFRICACRYPT 2014. Lecture Notes in Computer Science, vol 8469. Springer, Cham. https://doi.org/10.1007/978-3-319-06734-6_26
Download citation
DOI: https://doi.org/10.1007/978-3-319-06734-6_26
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-06733-9
Online ISBN: 978-3-319-06734-6
eBook Packages: Computer ScienceComputer Science (R0)