Abstract
Cascade chaining is a very efficient and popular mode of operation for building various kinds of cryptographic hash functions. In particular, it is the basis of the most heavily utilized SHA function family. Recently, many researchers pointed out various practical and theoretical deficiencies of this mode, which resulted in a renewed interest in building specialized modes of operations and new hash functions with better security. Unfortunately, it appears unlikely that a new hash function (say, based on a new mode of operation) would be widely adopted before being standardized, which is not expected to happen in the foreseeable future.
Instead, it seems likely that practitioners would continue to use the cascade chaining, and the SHA family in particular, and try to work around the deficiencies mentioned above. In this paper we provide a thorough treatment of how to soundly design a secure hash function H′ from a given cascade-based hash function H for various cryptographic applications, such as collision-resistance, one-wayness, pseudorandomness, etc. We require each proposed construction of H′ to satisfy the following “axioms”.
-
1
The construction consists of one or two “black-box” calls to H.
-
1
In particular, one is not allowed to know/use anything about the internals of H, such as modifying the initialization vector or affecting the value of the chaining variable.
-
1
The construction should support variable-length inputs.
-
1
Compared to a single evaluation of H(M), the evaluation of H′(M) should make at most a fixed (small constant) number of extra calls to the underlying compression function of H. In other words, the efficiency of H′ is negligibly close to that of H.
We discuss several popular modes of operation satisfying the above axioms. For each such mode and for each given desired security requirement, we discuss the weakest requirement on the compression function of H which would make this mode secure. We also give the implications of these results for using existing hash functions SHA-x, where x ∈ {1,224,256,384,512}.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
An, J.H., Bellare, M.: Constructing VIL-MACs from FIL-MACs: Message Authentication under Weakened Assumptions. In: Wiener, M.J. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 252–269. Springer, Heidelberg (1999)
Bellare, M.: New Proofs for NMAC and HMAC: Security without Collision-Resistance. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, Springer, Heidelberg (2006)
Bellare, M., Canetti, R., Krawczyk, H.: Pseudorandom Functions Re-visited: The Cascade Construction and Its Concrete Security. In: Proc. 37th FOCS, pp. 514–523. IEEE, Los Alamitos (1996)
Bellare, M., Canetti, R., Krawczyk, H.: Keying hash functions for message authentication. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, Springer, Heidelberg (1996)
Bellare, M., Rogaway, P.: Collision-Resistant Hashing: Towards Making UOWHFs Practical. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, Springer, Heidelberg (1997)
Bellare, M., Rogaway, P.: Random oracles are practical : a paradigm for designing efficient protocols. In: Proceedings of the First Annual Conference on Computer and Communications Security, ACM, New York (1993)
Bellare, M., Ristenpart, T.: Multi-Property-Preserving Hash Domain Extension and the EMD Transform. In: Lai, X., Chen, K. (eds.) ASIACRYPT 2006. LNCS, vol. 4284, Springer, Heidelberg (2006)
Bellare, M., Ristenpart, T.: Hash Functions in the Dedicated-Key Setting: Design Choices and MPP Transforms. In: Arge, L., Cachin, C., Jurdziński, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, Springer, Heidelberg (2007)
Coron, J.-S., Dodis, Y., Malinaud, C., Puniya, P.: Merkle-Damgård Revisited: How to Construct a Hash Function. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 430–448. Springer, Heidelberg (2005)
Damgård, I.: A Design Principle for Hash Functions. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 416–427. Springer, Heidelberg (1990)
Dodis, Y., Gennaro, R., Håstad, J., Krawczyk, H., Rabin, T.: Randomness Extraction and Key Derivation Using the CBC, Cascade and HMAC Modes. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, Springer, Heidelberg (2004)
Dodis, Y., Puniya, P.: Getting the Best Out of Existing Hash Functions or What if We Are Stuck with SHA (ful version), http://people.csail.mit.edu/dodis/ps/sha.ps
FIPS 180-1, Secure hash standard, Federal Information Processing Standards Publication 180-1, U.S. Department of Commerce/N.I.S.T., National Technical Information Service, Springfield, Virginia, April 17 (1995) (supersedes FIPS PUB 180)
Halevi, S., Krawczyk, H.: Strengthening Digital Signatures Via Randomized Hashing. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 41–59. Springer, Heidelberg (2006)
Joux, A.: Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 306–316. Springer, Heidelberg (2004)
Kelsey, J. In: CRYPTO 2005, Rump Session (2005)
Kelsey, J., Kohno, T.: Herding Hash Functions and the Nostradamus Attack. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 183–200. Springer, Heidelberg (2006)
RFC 1321, The MD5 message-digest algorithm, Internet Request for Comments 1321, R.L. Rivest (April 1992)
Merkle, R.: One way hash functions and DES. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 428–446. Springer, Heidelberg (1990)
Maurer, U., Renner, R., Holenstein, C.: Indifferentiability, Impossibility Results on Reductions, and Applications to the Random Oracle Methodology. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 21–39. Springer, Heidelberg (2004)
Maurer, U.M., Sjödin, J.: Single-Key AIL-MACs from Any FIL-MAC. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 472–484. Springer, Heidelberg (2005)
National Institute of Standards and Technology, NIST’s Plan for New Cryptographic Hash Functions, http://www.csrc.nist.gov/pki/HashWorkshop/index.html
Naor, M., Yung, M.: Universal One-Way Hash Functions and their Cryptographic Applications. In: STOC 1989, pp. 33–43 (1989)
Simon, D.R.: Finding Collisions on a One-Way Street: Can Secure Hash Functions Be Based on General Assumptions? In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 334–345. Springer, Heidelberg (1998)
Shoup, V.: A Composition Theorem for Universal One-Way Hash Functions. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 445–452. Springer, Heidelberg (2000)
Wang, X., Yu, H., Yin, Y.L.: Efficient Collision Search Attacks on SHA-0. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 1–16. Springer, Heidelberg (2005)
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
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dodis, Y., Puniya, P. (2008). Getting the Best Out of Existing Hash Functions; or What if We Are Stuck with SHA?. In: Bellovin, S.M., Gennaro, R., Keromytis, A., Yung, M. (eds) Applied Cryptography and Network Security. ACNS 2008. Lecture Notes in Computer Science, vol 5037. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-68914-0_10
Download citation
DOI: https://doi.org/10.1007/978-3-540-68914-0_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-68913-3
Online ISBN: 978-3-540-68914-0
eBook Packages: Computer ScienceComputer Science (R0)