Abstract
We introduce the notion of a weak ideal compression function, which is vulnerable to strong forms of attack, but is otherwise random. We show that such weak ideal compression functions can be used to create secure hash functions, thereby giving a design that can be used to eliminate attacks caused by undesirable properties of compression functions.
We prove that the construction we give, which we call the “zipper hash,” is ideal in the sense that the overall hash function is indistinguishable from a random oracle when implemented with these weak ideal building blocks.
The zipper hash function is relatively simple, requiring two compression function evaluations per block of input, but it is not streamable. We also show how to create an ideal (strong) compression function from ideal weak compression functions, which can be used in the standard iterated way to make a streamable hash function.
Chapter PDF
Similar content being viewed by others
Keywords
References
Biham, E., Chen, R., Joux, A., Carribault, P., Lemuet, C., Jalby, W.: Collisions of SHA-0 and reduced SHA-1. In: Cramer [5], pp. 36–57
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)
Brassard, G. (ed.): CRYPTO 1989. LNCS, vol. 435. Springer, Heidelberg (1990)
Coron, J., Dodis, Y., Malinaud, C., Punyia, P.: Merkle-Damgård revisited:how to construct a hash function. In: Shoup [18], pp. 430–448
Cramer, R. (ed.): EUROCRYPT 2005. LNCS, vol. 3494, pp. 22–26. Springer, Heidelberg (2005)
Damgård, I.: A design principle for hash functions. In: Brassard [3], pp. 416–427
Dean, R.: Formal aspects of mobile code security. Ph.D. Dissertation, Princeton University (1999)
Franklin, M. (ed.): CRYPTO 2004. LNCS, vol. 3152. Springer, Heidelberg (2004)
Hoch, J., Shamir, A.: Breaking the ICE - finding multicollisions in iterated concatenated and expanded (ICE) hash functions. In: Robshaw, M. (ed.) FSE 2006. LNCS, vol. 4047, Springer, Heidelberg (2006)
Joux, A.: Multicollisions in iterated hash functions, application to cascaded constructions. In: Franklin [8], pp. 306–316
Kelsey, J., Kohno, T.: Herding hash functions and the Nostradamus attack. Available on eprint: article 2005/281 (2005)
Kelsey, J., Schneier, B.: Second preimages on n-bit hash functions for much less than 2n work. In: Cramer [5], pp. 474–490
Lucks, S.: A failure-friendly design principle for hash functions. In: Roy, B. (ed.) ASIACRYPT 2005. LNCS, vol. 3788, pp. 474–494. Springer, Heidelberg (2005)
Merkle, R.C.: A certified digital signature. In: Brassard [3], pp. 218–238
Nandi, M., Stinson, D.R.: Multicollision attacks on a class of hash functions. Available on IACR eprint archive, paper 2006-2055 (2006)
Preneel, B.: Analysis and design of cryptographic hash functions. Ph. D. thesis, updated version (2003)
Preneel, B.: Hash functions: past, present and future. In: Roy, B. (ed.) ASIACRYPT 2005. LNCS, vol. 3788, Springer, Heidelberg (2005)
Shoup, V. (ed.): CRYPTO 2005. LNCS, vol. 3621. Springer, Heidelberg (2005)
Wang, X., Lai, X., Feng, D., Chen, H., Yu, X.: Cryptanalysis of the hash functions MD4 and RIPEMD. In: Cramer [5], pp. 1–18
Wang, X., Yin, Y.L., Yu, H.: Finding collisions in the full SHA-1. In: Shoup [18], pp. 17–36
Wang, X., Yu, H.: How to break MD5 and other hash functions. In: Cramer [5], pp. 19–35
Wang, X., Yu, H., Yin, Y.L.: Efficient collision search attacks on SHA-0. In: Shoup [18], pp. 1–16
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Liskov, M. (2007). Constructing an Ideal Hash Function from Weak Ideal Compression Functions. In: Biham, E., Youssef, A.M. (eds) Selected Areas in Cryptography. SAC 2006. Lecture Notes in Computer Science, vol 4356. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-74462-7_25
Download citation
DOI: https://doi.org/10.1007/978-3-540-74462-7_25
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-74461-0
Online ISBN: 978-3-540-74462-7
eBook Packages: Computer ScienceComputer Science (R0)