Abstract
SHA-1 uses a single set of rotation constants within the compression function. However, most other members of the MD4 family of hash functions use multiple sets of rotation constants, i.e. the rotation amounts change with the step being processed.
To our knowledge, no design rationales on the choice of rotation constants are given on any of these hash functions. This is the first paper that analyzes rotations in iterated hash functions. We focus on SHA-1-like hash functions and use recent developments in the analysis of these hash functions to evaluate the security implications of using multiple sets of rotation constants in the compression function instead of a single set. Additionally, we give some observations on the set of constants used in SHA-0 and SHA-1.
The work in this paper has been supported by the Austrian Science Fund (FWF), project P18138.
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
Biham, E., Chen, R.: Near-Collisions of SHA-0. In: Franklin, M.K. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 290–305. Springer, Heidelberg (2004)
Biham, E., Chen, R., Joux, A., Carribault, P., Lemuet, C., Jalby, W.: Collisions of SHA-0 and Reduced SHA-1. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 36–57. Springer, Heidelberg (2005)
Chabaud, F., Joux, A.: Differential Collisions in SHA-0. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 56–71. Springer, Heidelberg (1998)
Joux, A., Carribault, P., Jalby, W., Lemuet, C.: Full iterative differential collisions in SHA-0 (2004) (preprint)
KCDSA Task Force Team. The Korean Certificate-based Digital Signature Algorithm (1998), Available at: http://grouper.ieee.org/groups/1363/P1363a/contributions/kcdsa1363.pdf
Klima, V.: Finding MD5 Collisions on a Notebook PC Using Multi-message Modifications (2005) (preprint), Available at: http://eprint.iacr.org/2005/102
Leon, J.S.: A probabilistic algorithm for computing minimum weights of large error-correcting codes. IEEE Transactions on Information Theory 34(5), 1354–1359 (1988)
Lim, C.H.: The revised version of KCDSA (2000) (unpublished manuscript), Available at: http://dasan.sejong.ac.kr/~chlim/pub/kcdsa1.ps
Lim, C.H., Lee, P.J.: A Study on the Proposed Korean Digital Signature Algorithm. In: Ohta, K., Pei, D. (eds.) ASIACRYPT 1998. LNCS, vol. 1514, pp. 175–186. Springer, Heidelberg (1998)
Lloyd, J.: A Description of HAS-160 (2003), Available at: http://www.randombit.net/papers/has160.html
National Institute of Standards and Technology (NIST). FIPS-180-2: Secure Hash Standard (August 2002), Available online at: http://www.itl.nist.gov/fipspubs/
Park, N.K., Hwang, J.H., Lee, P.J.: HAS-V: A New Hash Function with Variable Output Length. In: Stinson, D.R., Tavares, S. (eds.) SAC 2000. LNCS, vol. 2012, pp. 202–216. Springer, Heidelberg (2001)
Pramstaller, N., Rechberger, C., Rijmen, V.: Exploiting Coding Theory for Collision Attacks on SHA-1. In: Smart, N.P. (ed.) Cryptography and Coding 2005. LNCS, vol. 3796, pp. 78–95. Springer, Heidelberg (2005)
Rabaey, J.M.: Digital Integrated Circuits. Prentice-Hall, Englewood Cliffs (1996)
Rijmen, V., Oswald, E.: Update on SHA-1. In: Menezes, A. (ed.) CT-RSA 2005. LNCS, vol. 3376, pp. 58–71. Springer, Heidelberg (2005)
TTA. Digital Signature Mechanism with Appendix - Part 2: Certificate-based Digital Signature Algorithm, TTAS.KO-12.0011/R1 (2000)
TTA. Hash Function Standard - Part 2: Hash Function Algorithm Standard (HAS- 160), TTAS.KO-12.0011/R1 (2000)
Wang, X., Lai, X., Feng, D., Chen, H., Yu, X.: Cryptanalysis of the hash functions MD4 and RIPEMD. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 1–18. 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)
Wang, X., Yu, H.: How to Break MD5 and Other Hash Functions. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 19–35. Springer, Heidelberg (2005)
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)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Pramstaller, N., Rechberger, C., Rijmen, V. (2006). Impact of Rotations in SHA-1 and Related Hash Functions. In: Preneel, B., Tavares, S. (eds) Selected Areas in Cryptography. SAC 2005. Lecture Notes in Computer Science, vol 3897. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11693383_18
Download citation
DOI: https://doi.org/10.1007/11693383_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-33108-7
Online ISBN: 978-3-540-33109-4
eBook Packages: Computer ScienceComputer Science (R0)