Cryptographic hash function
A cryptographic hash function is a deterministic algorithm that maps an input of arbitrary finite length to a bit string whose length is fixed by the function definition. The resulting value is called a hash, message digest, or digest. Cryptographic hash functions are distinguished from general-purpose hash functions by security properties concerning the computational difficulty of reversing the mapping or finding distinct inputs with related outputs.
Hashing does not constitute encryption, because it provides no decryption operation and uses no secret key in its basic form. The same input always produces the same digest, while even a small alteration of the input generally changes many output bits. This diffusion of input differences is commonly described as the avalanche effect, although avalanche behavior alone does not establish cryptographic security.
Mathematical model
A fixed-output cryptographic hash function can be represented as
[ H:{0,1}^{*}\rightarrow{0,1}^{n}, ]
where ({0,1}^{*}) denotes the set of finite binary strings and (n) is the digest length. Because the input domain is unbounded and the output set contains only (2^n) values, the pigeonhole principle guarantees that multiple inputs have the same digest. These pairs are called collisions, and their unavoidable existence differs from the computational problem of locating one.
Security analysis commonly compares a concrete function with an idealized random mapping. Under that model, the most efficient generic attacks have costs determined primarily by (n). Structural weaknesses in an actual function can reduce these costs, sometimes enough to make a nominally large digest unsuitable for cryptographic use.
An extendable-output function generalizes the fixed-output model by producing a digest of a requested length. Such a function is often represented as mapping an arbitrary input to an arbitrarily long pseudorandom output stream, subject to the limits established by its internal state and security parameters. The SHAKE functions standardized with SHA-3 are prominent examples.
Security properties
Preimage resistance
Preimage resistance concerns the recovery of an input from a specified digest. Given a value (y), an adversary attempts to find any (x) satisfying
[ H(x)=y. ]
For an ideal (n)-bit hash function, generic preimage search requires approximately (2^n) evaluations. This property supports applications in which publication of a digest is not intended to reveal the underlying message, although low-entropy inputs remain recoverable through exhaustive examination of their limited input space.
Preimage resistance is not equivalent to secrecy. A digest of a predictable record can identify that record even when the function has no cryptanalytic weakness, because the candidate records can be hashed independently and compared with the published value.
Second-preimage resistance
Second-preimage resistance is defined relative to a particular input. Given (x), the adversary seeks a distinct value (x') for which
[ H(x')=H(x). ]
An ideal (n)-bit function requires approximately (2^n) work for a generic second-preimage attack. Iterated constructions can exhibit different bounds for exceptionally long messages, since their internal state transitions provide additional opportunities for matching an existing computation.
This property is relevant when an established document is identified by its digest and substitution with a different document is the attack objective. It differs from collision resistance because the original document is fixed before the adversary begins the search.
Collision resistance
Collision resistance concerns the discovery of any distinct pair (x) and (x') satisfying
[ H(x)=H(x'). ]
For an ideal (n)-bit function, the birthday attack finds a collision after approximately (2^{n/2}) evaluations. The square-root reduction follows from the increasing probability that some pair among many sampled outputs will coincide.
A practical collision attack does not necessarily provide control over both resulting messages. More advanced attacks may construct messages with selected prefixes or constrained formats, thereby making the collision relevant to documents, certificates, or executable files. The demonstrated chosen-prefix collision attacks against MD5 and SHA-1 illustrate the distinction between an abstract collision and one embedded in structured data.
Iterated constructions
Many historically important hash functions use an iterated compression structure. A message is padded, divided into fixed-size blocks, and processed sequentially through a compression function. Each invocation combines the current message block with a chaining value derived from the preceding invocation, while a specified initialization value begins the computation.
Ralph Merkle and Ivan Damgård independently formalized the construction now called the Merkle–Damgård construction. With appropriate length-encoding padding, collision resistance of the compression function transfers to the complete iterated hash under the assumptions of the construction. This framework influenced MD4, MD5, SHA-1, and the members of SHA-2.
The construction also explains the length-extension attack applicable to several iterated hashes. When the digest exposes the final chaining value, knowledge of (H(m)) and the length of (m) can permit computation of a digest corresponding to the padded message followed by an extension. The original message itself remains unknown during this calculation. Consequently, direct secret-prefix constructions of the form (H(k\mathbin|m)) do not provide the security properties of a standardized message authentication code.
HMAC addresses this structural issue through nested hashing with separately derived inner and outer key blocks. Its security analysis does not require the underlying hash to behave as though the digest were an opaque final state, and collision attacks against the hash do not automatically produce corresponding HMAC forgeries.
Sponge construction and SHA-3
A sponge function maintains a fixed-size internal state divided conceptually into a rate and a capacity. During absorption, message blocks are combined with the rate portion before a public permutation transforms the entire state. During squeezing, output is taken from the rate portion, with further permutation calls producing additional output when necessary.
The capacity controls the generic security bounds, while the rate determines how much input or output is handled by each permutation call. Unlike the conventional Merkle–Damgård arrangement, a sponge does not ordinarily expose its entire internal state as the digest. Its structure supports fixed-length hashes, extendable-output functions, and domain-separated cryptographic modes within a common permutation framework.
The Keccak submission to the NIST hash function competition listed Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles Van Assche, and You Watanabe as its designers. Their design used the Keccak-f family of permutations together with sponge-based absorption and squeezing. The submission was selected in 2012 and subsequently formed the basis of the SHA-3 standard published as FIPS 202 in 2015.
SHA-3 defines fixed-length functions corresponding to several digest sizes, while SHAKE128 and SHAKE256 provide variable-length output. The standardized SHA-3 functions use domain-separation suffixes that distinguish them from the original Keccak competition parameters, so equal messages do not generally receive equal digests under nominally corresponding Keccak and SHA-3 variants.
Development of major hash families
Early dedicated hash designs developed alongside research on digital signatures, one-way functions, and authenticated communication. During the 1980s and 1990s, practical construction increasingly centered on software-oriented compression functions that transformed relatively small machine words through repeated Boolean and arithmetic operations.
Ronald Rivest designed MD4 and its successor MD5 as members of the Message Digest family. MD4 strongly influenced later designs, including MD5, SHA-1, and several European hash functions. Cryptanalysis eventually produced practical collisions for both MD4 and MD5, while chosen-prefix techniques made MD5 collisions applicable to structured certificate and document formats.
SHA-1 was standardized by the United States National Institute of Standards and Technology after development involving the National Security Agency. It produces a 160-bit digest and follows an iterated structure related to the MD4 family. Successive cryptanalytic improvements reduced collision-search complexity below the generic birthday bound, and a public collision was computed in 2017.
SHA-2 retained an iterated compression architecture but introduced substantially different round functions and larger internal word sizes in several variants. No practical collision has been demonstrated for the full standardized SHA-2 functions. The later SHA-3 competition selected a structurally independent standard rather than a direct replacement based on a revised Merkle–Damgård design.
Cryptographic use
In a digital signature system, the signature algorithm commonly operates on a digest rather than directly on an arbitrarily long document. Hashing binds the signature computation to the document while reducing variable-length input to the format expected by the signature scheme. The security of this composition depends on both the hash properties and the encoding rules of the signature algorithm.
A digest can also act as a content identifier when accidental corruption or non-adversarial modification is the principal concern. In adversarial settings, an unkeyed digest does not authenticate its source because an attacker who can replace the message can generally calculate a new digest as well. Authentication requires a keyed construction such as HMAC or an authenticated digital signature.
Commitment schemes often incorporate hashing to bind a participant to a value while delaying its disclosure. A typical construction combines the value with fresh randomness before hashing, since randomness prevents straightforward enumeration when the committed value has a small set of possibilities. Formal hiding and binding properties depend on the complete commitment construction rather than solely on the name of the hash function.
Password storage uses specialized password hashing and key derivation functions rather than ordinary fast message-digest computation. Algorithms such as Argon2 incorporate configurable computational and memory costs, which increase the resources consumed by large-scale password guessing. A salt separates identical passwords across records and prevents reuse of a single precomputed table, but it does not increase the entropy of the password itself.
Limits of interpretation
Digest equality establishes that two inputs map to the same output under a specified function; it does not establish that the inputs are identical as a matter of logic. Collision resistance makes an adversarially constructed counterexample computationally difficult within a defined resource model, while accidental collision probability depends on the digest length and the number of hashed objects.
Digest inequality establishes that the encoded inputs differ, although the semantic reason for the difference remains outside the hash function. Changes in character encoding, metadata representation, serialization order, or canonicalization can therefore produce different digests for information that an application treats as equivalent. Cryptographic analysis normally applies to the exact bit strings supplied to the function.
Security classifications also change when cryptanalysis improves or available computation increases. A function can remain reliable for detecting random transmission errors after losing collision resistance, because those uses impose different threat models. Conversely, a long output does not compensate for exploitable internal structure when an attack bypasses generic search.