Abstract
Hash functions are one-way functions that map arbitrary-length input to fixed-length output. Moreover, they have many cryptographic applications, such as integrity checks, password storage, and signatures. Cryptographic hash functions have some additional properties that can be formulated as hard problems: pre-image resistance, second pre-image resistance, and collision resistance. A significant technological development in this area is unlikely. Standardized hash functions are considered secure, and open-source implementations can be used at no cost. To conclude, the security properties required from hash functions depend on the intended purpose.
You have full access to this open access chapter, Download chapter PDF
1 Introduction
Hash functions are one-way functions that map arbitrary-length input to fixed-length output. Cryptographic hash functions enjoy additional properties, making them suitable for many cryptographic applications. Established hash functions are considered secure, and no significant development is expected in this area. Insecure hash functions should be discarded, and existing secure hash functions should be promoted and adequately used.
2 Analysis
Hash functions have a wide range of cryptographic applications, such as:
-
Integrity check: Files having the same hash value are supposedly equal. Hence, an unchanged hash value indicates an unchanged file.
-
Password storage: The hash value of a password does not reveal any information on the password. Hence, passwords should be stored suitably hashed on the server side.
-
Signatures: In digital signatures, message hashes are signed rather than the whole message itself (see Chap. 15).
-
MACs: By carefully combining a secret key with the input data, hash functions can be used to compute Message Authentication Codes (MACs) that guarantee the authenticity of the data, e.g., in HMACs [1].
-
Key derivation: Small changes in the input lead to a random-looking change in the output (diffusion property). That makes them useful in key derivation functions [2].
There exist standardized hash functions that are considered secure, i.e., they satisfy the required properties. We are unaware of a quantum algorithm that poses a general risk for standard hash functions. For example, the asymptotically quadratic speedup of Grover’s quantum search algorithm [3] can be countered using hash functions of sufficient length.
2.1 Definition
Cryptographic hash functions are functions mapping input of arbitrary length to a fixed-size output and having some additional properties that can be formulated as hard problems [4] :
-
Pre-image resistance: It is hard to find an input that maps to a given hash value.
-
Second pre-image resistance: It is hard to find an input that maps to the same value as a given different input.
-
Collision resistance: It is hard to find two input values that map to the same value.
Hash functions having these properties are considered secure and are suitable for a wide range of cryptographic applications. On the contrary, the hash function is considered broken as soon as one of the above three problems can be solved by brute force or significantly faster than by brute force.
2.2 Trends
The last competition to find and standardize a new Secure Hash Algorithm (SHA-3) ended in 2012 [5] with the winner’s announcement, namely Keccak. However, both SHA-3 (FIPS PUB 202, [6]) and its predecessor SHA-2 (FIPS PUB 180-4, [7]) with a minimal length of 256 bits are considered secure (concerning the properties mentioned in Sect. 5.2.1) and we see no indication that this will change in the next few years. Furthermore, other hash functions are considered secure (e.g., BLAKE) [8]. We, therefore, consider a significant development in this area unlikely.
3 Consequences for Switzerland
Switzerland should continue to use and promote the use of cryptographically secure and standardized hash functions.
3.1 Implementation Possibilities
Standardized hash functions considered secure in Sect. 5.2.1 exist, and open-source implementations thereof can be used at no cost. There is hence no need for Switzerland to develop its hash functions.
The security properties required from hash functions depend on the intended purpose. For example, a collision attack on the used hash functions has catastrophic consequences when it is used in signature schemes (see [9] for an attack scenario), whereas this is not necessarily problematic when it is used in HMACs. Nevertheless, insecure hash functions should not be used anymore, independently of their area of application.
Numerous hash functions are considered secure concerning the properties mentioned in 5.2.1; their design and properties differ. For example, SHA-2 is vulnerable to length extension attacks, whereas SHA-3 is not [8]. This is why hash functions cannot be used interchangeably and should be chosen carefully depending on the intended purpose.
There exist a wide range of cryptographic applications that make use of hash functions. The US National Institute of Standards and Technology (NIST) publishes standards for hash functions (FIPS 180-4 in [7], FIPS 202 in [6]) as well as methods making use of hash functions (e.g., HMAC in FIPS 198-1, HKDF in SP 800-56A/B, digital signatures in FIPS 186-5).
4 Conclusion
Hash functions have been in use in cryptographic applications for a long time. There exist established hash functions, and their pitfalls are known and documented. The development in computing power, including Quantum Computers, is not expected to yield a general problem with hash functions in the foreseeable future. As a consequence, not much development in this area is expected. Insecure hash functions should be discarded and existing secure hash functions adequately used.
References
James M Turner. The Keyed-Hash Message Authentication Code (HMAC), 2008. Federal Inf. Process. Stds. (NIST FIPS), National Institute of Standards and Technology, Gaithersburg, MD.
Lily Chen. Recommendation for Key Derivation Using Pseudorandom Functions, 2022. Federal Inf. Process. Stds. (NIST FIPS), National Institute of Standards and Technology, Gaithersburg, MD.
Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 212–219, 1996.
Bart Preneel. Cryptographic hash functions. European Transactions on Telecommunications, 5(4):431–448, 1994.
Crypto competitions: SHA-3: a secure hash algorithm. https://competitions.cr.yp.to/sha3.html, June 2022.
Morris J. Dworkin. Sha-3 standard: Permutation-based hash and extendable-output functions, August 2015. Federal Inf. Process. Stds. (NIST FIPS), National Institute of Standards and Technology, Gaithersburg, MD.
Quynh Dang. Secure Hash Standard (SHS). March 2012. Federal Inf. Process. Stds. (NIST FIPS), National Institute of Standards and Technology, Gaithersburg, MD.
Wikipedia, Hash function security summary. https://en.wikipedia.org/w/index.php?title=Hash_function_security_summary&oldid=1054598969, November 2021.
Marc Stevens, Arjen Lenstra, and Benne de Weger. Chosen-prefix collisions for MD5 and colliding X. 509 certificates for different identities. In M. Naor, editor, Annual International Conference on the Theory and Applications of Cryptographic Techniques — EUROCRYPT 2007, volume 4515, pages 1–22. Springer, 2007.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Open Access This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.
The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
Copyright information
© 2023 The Author(s)
About this chapter
Cite this chapter
Wagner, U., Lugrin, T. (2023). Hash Functions. In: Mulder, V., Mermoud, A., Lenders, V., Tellenbach, B. (eds) Trends in Data Protection and Encryption Technologies . Springer, Cham. https://doi.org/10.1007/978-3-031-33386-6_5
Download citation
DOI: https://doi.org/10.1007/978-3-031-33386-6_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-33385-9
Online ISBN: 978-3-031-33386-6
eBook Packages: Computer ScienceComputer Science (R0)