A cryptographic hash function is a deterministic algorithm that transforms a message into a compact value, usually of fixed length, called a hash, digest, or message digest. Unlike an ordinary hash function, which may be designed primarily for fast indexing or error detection, a cryptographic hash function is intended to remain secure when an adversary deliberately chooses its inputs. Its principal security goals are to make it computationally infeasible to recover an input from its digest, find a second input with the same digest as a given input, or find any two different inputs with the same digest.
These functions are basic components of cryptography and information security. They support digital signatures, message authentication, password verification, software integrity checks, and authenticated data structures. Their security depends not only on the underlying algorithm but also on digest length, input encoding, implementation, and the surrounding protocol. Major design families include iterated compression-function constructions, sponge constructions, and tree-based designs; their history includes both widely deployed standards and algorithms retired after practical attacks.
Mathematical definition and security properties
An idealized fixed-output cryptographic hash function has the form
where denotes all finite binary strings and is the digest length in bits. Real standards generally impose a maximum message length, although that limit is often far beyond ordinary application needs. The same input always produces the same digest, and no secret key is required. A digest may be displayed in hexadecimal or another textual encoding, but that representation does not change its underlying information content. For example, a 256-bit digest occupies 32 bytes or 64 hexadecimal characters.
Three distinct security properties define the conventional model. Preimage resistance means that, given a digest generated under the relevant input distribution, finding a message such that should be infeasible. Second-preimage resistance means that, given a particular message , finding a different message with should be infeasible. Collision resistance means that finding any pair of distinct messages with equal digests should be infeasible. The distinction matters: a successful collision attack need not provide a way to invert a digest or replace an arbitrary existing document.
Because the input space is larger than the output space, collisions necessarily exist. Security therefore cannot mean that every message has a unique digest. Instead, it concerns the computational complexity of finding useful collisions. Cryptographic claims are made relative to an adversary’s resources, the information available to that adversary, and a specified success probability. A 256-bit output is not, by itself, evidence of 256-bit security against every attack.
A desirable supporting behavior is diffusion: changing one input bit should typically change about half the output bits. This is often described as the avalanche effect. Diffusion and statistical balance are useful design objectives, but neither establishes cryptographic security. A function can produce outputs that pass statistical tests while retaining an exploitable algebraic structure. Conversely, particular applications may require properties beyond the conventional three, such as pseudorandom behavior when used inside a keyed construction.
Hashing is distinct from encryption. Encryption is designed to permit recovery of plaintext using an appropriate key; hashing normally provides no corresponding decryption operation. Nevertheless, hashing does not automatically conceal information. If a message comes from a small predictable set, an observer can hash every candidate and compare the results. A digest of a four-digit code, for example, cannot provide strong secrecy merely because the hash algorithm itself resists generic inversion.
Generic attacks and security strength
Generic attacks exploit the size of the input or output space rather than a weakness in the internal design. For an ideal -bit hash, a randomly chosen trial matches a specified target digest with probability . Finding a preimage therefore requires work on the order of evaluations. Second-preimage search has a similar generic cost for ordinary target messages, although special constructions and exceptionally long messages can introduce additional considerations.
Collision search is substantially easier because an attacker can compare many candidate messages against one another. After hashing independently selected inputs, the approximate probability of at least one collision is
This relationship is an application of the birthday paradox. A collision probability near one-half occurs at approximately samples. Consequently, an ideal 256-bit digest offers about 128 bits of classical collision security, rather than 256.
These estimates explain why output length must be matched to the security property required by a protocol. A system that relies on collision resistance generally needs a longer digest than one seeking the same nominal strength against a single preimage target. Truncating an otherwise secure digest to bits normally limits generic collision resistance to about work and preimage resistance to about . A truncated digest can be appropriate in a specified protocol, but its security is governed by the retained bits, not the original output length.
The number of targets also matters. If an attacker succeeds by matching any of many independent target digests, success can become more likely than in the single-target case. Likewise, a database containing billions of short identifiers faces a different accidental-collision problem from a system storing only a few hundred. Security calculations must distinguish an accidental collision among honest inputs from a deliberately constructed collision chosen to defeat a protocol.
Limited input entropy can dominate every output-size calculation. If a secret is selected uniformly from only possibilities, an attacker can enumerate that space even when its digest is 512 bits long. If some candidates are much more probable than others, the attacker can try those first. This connects practical hash security to probability distributions, not simply to digest length.
Time and memory also trade off. A simple birthday search stores a large collection of digests, whereas cycle-finding methods can reduce storage for suitable collision searches. Parallel processing changes elapsed time and hardware cost without necessarily changing the exponent in the attack’s total work. Security-strength figures are therefore compact estimates, not complete descriptions of an attack’s engineering requirements.
Compression functions, sponges, and tree constructions
Many established hash functions process a message in fixed-size blocks while maintaining an internal chaining value. A compression function combines the current state with the next block:
The initial state is specified by the algorithm, and the final state, sometimes after an additional transformation, determines the digest. The message is padded so that its length fits the block structure. Despite the name, a cryptographic compression function is not a data-compression algorithm: it deliberately maps a larger fixed-size input to a smaller output and does not preserve recoverable message content.
The Merkle–Damgård construction, formalized independently by Ralph Merkle and Ivan Damgård in 1989, gives an important connection between compression-function security and whole-message collision resistance. With an appropriate length-encoding padding rule, collision resistance of the compression function implies collision resistance of the iterated hash. MD5, SHA-1, and SHA-256 belong to this broad design tradition, although their internal operations and security records differ substantially.
Iteration introduces structural issues that are not visible from digest length alone. In a classic construction that exposes its full chaining state as the digest, someone who knows and the length of can often compute the digest of , its padding, and a chosen suffix without knowing . This length-extension property does not constitute a collision or preimage attack, but it can break incorrectly designed authentication schemes. Wide-pipe designs, output transformations, and other constructions can prevent straightforward exploitation.
A sponge construction instead maintains a larger internal state divided into a rate portion and a capacity portion. During absorption, message blocks are combined with the rate portion and a fixed permutation is repeatedly applied. During squeezing, output is read from the rate portion, with further permutations when more output is required. The capacity provides a security margin: in standard idealized analyses, important generic distinguishing bounds depend on roughly half the capacity. The SHA-3 family uses this architecture.
Tree constructions divide a message into chunks, hash chunks independently, and combine their results through a hierarchy. This permits parallel computing and efficient processing of very large inputs. Correct designs distinguish leaf nodes, internal nodes, and other roles through explicit formatting or domain separation. Without such distinctions, different structural interpretations can lead to unintended equivalences. BLAKE3 is a prominent modern tree-based design, while ParallelHash provides a standardized parallel-hashing construction based on the SHA-3 family.
An extendable-output function, or XOF, permits the caller to request a variable amount of output. SHAKE128 and SHAKE256 are standardized examples. Requesting more output does not increase security without limit: the primitive’s internal parameters still impose a ceiling. Output length and intrinsic security strength are separate properties.
Development and major algorithm families
Cryptographic hashing developed alongside digital signatures and other techniques requiring compact representations of large messages. Ralph Merkle’s work in the late 1970s included hash-based authentication structures, and subsequent research established increasingly systematic ways to construct and analyze message digests. During the 1990s, practical deployment expanded rapidly with network security, software distribution, and public-key infrastructures.
Ronald Rivest designed MD4 in 1990 and MD5 in 1991; MD5 was documented in RFC 1321 in 1992. Both produce 128-bit digests, but MD5 added operations intended to strengthen MD4’s design. Their historical importance is substantial: they influenced later algorithms and became common in software and network protocols. Cryptanalytic advances eventually demonstrated that their collision resistance was inadequate for adversarial uses. Continued availability in a software library does not imply that a legacy algorithm remains suitable for security-sensitive applications.
The United States Secure Hash Standard introduced the original SHA in 1993, now commonly called SHA-0. SHA-1 followed in 1995 with a modified message schedule and a 160-bit digest. SHA-1 became widespread in digital certificates, signed software, and version-control systems. Its retirement illustrates the difference between a function continuing to compute well-defined outputs and continuing to meet its original security goals: an algorithm can remain operational after its cryptographic assumptions have failed.
SHA-2 was standardized in 2002 with SHA-256, SHA-384, and SHA-512; SHA-224 was added later, and the family also includes SHA-512/224 and SHA-512/256. SHA-256 uses 32-bit words, 512-bit message blocks, and 64 rounds per block. SHA-512 uses 64-bit words, 1,024-bit blocks, and 80 rounds. These related algorithms combine bitwise Boolean operations, rotations, shifts, and modular addition. Their different word sizes mean performance depends on processor architecture rather than digest length alone.
The National Institute of Standards and Technology launched a public competition in 2007 to select a new hash standard. In 2012 it selected Keccak, designed by Guido Bertoni, Joan Daemen, Michaël Peeters, and Gilles Van Assche. SHA-3 was published as FIPS 202 in 2015, specifying four fixed-output hashes and the two SHAKE functions. Standard SHA-3 and earlier raw Keccak variants are not interchangeable: differences in domain-separation padding produce different digests for the same message.
Other influential families include RIPEMD, Whirlpool, BLAKE, BLAKE2, and BLAKE3. BLAKE was a SHA-3 competition finalist; BLAKE2 was introduced in 2012, and BLAKE3 in 2020. These families demonstrate that cryptographic hashing is not represented by a single engineering trade-off. Designs differ in hardware suitability, software throughput, parallelism, keyed modes, and output flexibility, while standardization and protocol compatibility influence adoption independently of speed.
Cryptanalysis and the consequences of collisions
Cryptanalysis seeks attacks that outperform generic search by exploiting a function’s internal structure. Analysts study how differences between two messages propagate through intermediate states, how message words influence later rounds, and whether conditions can be imposed to cancel differences. Reduced-round attacks are common research tools: they identify weaknesses in simplified versions without necessarily compromising the complete standardized algorithm.
A major class of techniques is differential cryptanalysis. Instead of treating outputs as unrelated random values, an attacker searches for message pairs whose internal differences follow a favorable path. Message modification and related techniques can increase the probability of satisfying that path. In 2004, Xiaoyun Wang and collaborators announced practical collision results against MD5 and other hash functions, accelerating the abandonment of several widely used designs.
In 2005, Wang, Yiqun Lisa Yin, and Hongbo Yu reported a theoretical SHA-1 collision attack below the generic work factor. Subsequent research improved the attack. In 2017, the SHAttered project, involving researchers from CWI and Google, demonstrated the first publicly announced full SHA-1 collision by producing two different PDF files with the same SHA-1 digest. This was a collision demonstration, not a method for recovering arbitrary messages from their SHA-1 hashes.
A chosen-prefix collision gives the attacker greater flexibility. The attacker begins with two different prefixes, then constructs suffixes that cause the completed messages to hash to the same value. In 2008, researchers used a chosen-prefix MD5 collision to create a rogue certification-authority certificate under particular certificate-issuance conditions. In 2020, Gaëtan Leurent and Thomas Peyrin published a practical chosen-prefix collision attack on SHA-1. Such attacks can be more relevant to document forgery than collisions in messages whose content is almost entirely constrained by the cryptanalytic process.
The effect of a collision depends on the application. A signature scheme that signs a digest can be vulnerable if an attacker prepares two colliding documents, obtains a signature on one, and presents the signature with the other. By contrast, a collision attack does not automatically reveal passwords, recover authentication keys, or produce a second preimage for an arbitrary historical file. These are different attack goals with different prerequisites.
Structural attacks also extend beyond ordinary collisions. Joux’s multicollision technique shows that certain iterated hashes permit large families of colliding messages more cheaply than an idealized whole-message random function would suggest. Long-message second-preimage techniques and herding attacks reveal further distinctions between construction-level behavior and simple output-size estimates. These findings make the threat model essential: “broken” is meaningful only when the failed property and the attacker’s capabilities are identified.
Digital signatures, authentication, and key derivation
Hashing makes digital signatures efficient by reducing a potentially large message to a short representative. Schemes based on the RSA cryptosystem, elliptic curves, and other mathematical structures incorporate hashing in different ways. The exact encoding and signature scheme are important: a digest is not ordinarily signed by applying an unformatted mathematical operation. Collision resistance is especially significant when an attacker can influence the messages presented for signing.
An unkeyed digest alone does not provide authentication. If an attacker can replace both a file and the digest supplied with it, the replacement will verify against its own digest. A trusted distribution channel, authenticated signature, or secret-key mechanism is needed to connect an integrity check to a trusted source. This distinction explains why publishing a checksum beside a download offers a different guarantee from publishing a signed release manifest.
A message authentication code, or MAC, uses a secret key to authenticate data. The HMAC construction, published in 1996 by Mihir Bellare, Ran Canetti, and Hugo Krawczyk and standardized in RFC 2104 in 1997, combines a hash with inner and outer keyed processing:
Here is the key normalized to the hash’s block size, denotes exclusive OR, and denotes concatenation. The two pads are distinct fixed byte patterns.
HMAC avoids the straightforward length-extension problem that affects naive constructions such as with certain iterated hashes. Its security analysis is also different from ordinary collision resistance, so a collision attack on an underlying hash does not automatically yield an HMAC forgery. Nevertheless, algorithm selection must follow the requirements of the relevant protocol rather than treating every hash use as equivalent.
A key derivation function transforms secret material into one or more cryptographic keys. HKDF, specified in RFC 5869 in 2010, uses HMAC in an extract-and-expand design. Its extraction stage produces a pseudorandom key from input keying material; expansion produces output associated with an application-supplied context. Context labels help prevent the same secret from producing interchangeable keys for different purposes. Transport Layer Security version 1.3 uses HKDF in its key schedule and hashes handshake transcripts to bind key establishment to the exchanged messages.
These uses also require unambiguous input encodings. Simply concatenating variable-length fields can erase their boundaries: the byte sequences representing “ab” followed by “c” and “a” followed by “bc” are identical. Length prefixes, fixed-width fields, or explicitly specified serialization formats preserve structure. Cryptographic strength cannot compensate for a protocol that hashes different logical messages into the same byte sequence before hashing even begins.
Password hashing and resistance to guessing
Password verification presents a different optimization problem from general-purpose hashing. An ordinary cryptographic hash is normally designed to process data efficiently. For stored passwords, that efficiency can benefit an attacker who has obtained the verification database: each candidate password can be tested without interacting with the legitimate service. This is an offline guessing attack, and its feasibility depends heavily on password predictability and the cost of each verification attempt.
A password-hashing scheme combines the password with a salt and adjustable computational parameters. A salt is a per-record value, usually randomly generated and stored openly with the verifier. It makes equal passwords produce different stored values across records and prevents a single precomputed table from being directly reused everywhere. A salt is not a second password, does not have to remain secret, and does not increase the entropy of the password itself.
Dedicated schemes increase the cost of each guess. PBKDF2 repeatedly applies a pseudorandom function, often HMAC, with an iteration count. Bcrypt, introduced in 1999 by Niels Provos and David Mazières, uses a costly key setup derived from Blowfish. Scrypt, introduced by Colin Percival in 2009, adds substantial memory requirements to make highly parallel specialized attacks more expensive. These designs differ in parameterization, input handling, implementation history, and resistance to particular hardware advantages.
Argon2 won the Password Hashing Competition in 2015. Its variants include Argon2d, which uses data-dependent memory access; Argon2i, which uses data-independent access; and Argon2id, which combines aspects of both. Argon2id is specified in RFC 9106, published in 2021. Memory size, number of passes, and degree of parallelism are explicit parameters. The goal is not to make guessing impossible, but to force each guess to consume meaningful resources under a defined attacker model.
Memory hardness responds to the economics of graphics processing units and application-specific integrated circuits. These devices can evaluate many fast hashes concurrently. Requiring substantial memory per candidate constrains how many simultaneous guesses fit within a hardware budget, although time–memory trade-offs and implementation details still matter. Parameter choices therefore describe a resource cost rather than a permanent security guarantee.
Some systems also use a separately protected secret, often called a pepper, in addition to the per-record salt. This changes the consequences of a database-only compromise but introduces a separate secret-management dependency. Password verification is consequently a system property involving storage, secret protection, rate limiting for online attempts, and migration between parameter sets. Merely applying SHA-256 repeatedly without a fully specified construction is not equivalent to adopting a dedicated password-hashing scheme.
Integrity checking and authenticated data structures
A digest is a compact fingerprint of a precisely defined byte sequence. Software-distribution systems use hashes to detect altered packages, backup systems use them to identify content, and storage systems use them to check objects after retrieval. These applications differ from ordinary error detection. A checksum designed for accidental transmission errors may be easier to compute or update, but it is not necessarily resistant to an adversary who deliberately constructs a matching replacement.
In content-addressed storage, an object’s identifier is derived from its contents. This permits independent retrieval and verification: after receiving an object, a client can compute its digest and compare it with the expected identifier. Deduplication can also identify repeated objects, although systems must account for collision assumptions and their own reliability requirements. Git uses hash-derived identifiers for repository objects, including objects that refer to other objects. Its historical use of SHA-1 and development of SHA-256 support illustrate how a hash choice can become embedded in data formats and interoperability rules.
A Merkle tree extends this idea to collections. Leaf values represent data items or their digests; internal nodes hash their children’s representations; and a root digest commits to the whole structure. A membership proof supplies the sibling hashes along the path from a leaf to the root. In a balanced binary tree with leaves, proof size grows on the order of , allowing verification without transferring the entire collection. Correct verification also depends on knowing the tree’s encoding and structural rules.
Merkle structures support authenticated directories, distributed storage, software transparency, and blockchain systems. Certificate Transparency logs use Merkle-tree structures to provide inclusion proofs and consistency proofs for append-only histories. A consistency proof concerns the relationship between two tree states; it does not establish that the logged content is truthful or authorized. Hashing can authenticate relationships among records without validating their real-world claims.
Hashes also support commitment schemes, but the required properties must be separated. Collision resistance can provide a form of binding: it should be difficult to open one commitment as two different messages. Hiding is another matter. Publishing reveals a low-entropy message through enumeration. A construction that incorporates suitably chosen secret randomness can address this problem under appropriate assumptions, but a bare digest is not automatically a secure commitment.
Finally, a digest identifies bytes rather than an abstract meaning. Text with different line endings, different Unicode representations, or differently ordered serialized fields can have different hashes despite appearing equivalent to a user. Conversely, careless preprocessing can erase distinctions that a protocol needs to preserve. Applications must specify whether they authenticate raw files, canonicalized documents, parsed structures, or some other representation. The boundary between data and its interpretation is often as important as the hash algorithm itself.
Security models, implementation, and quantum effects
The random oracle model idealizes a hash as a publicly accessible random function that returns a consistent, independently random output for every new input. It enables proofs for many cryptographic constructions, including signature and encryption schemes. A concrete standardized hash is not literally a random oracle: it has a finite algorithmic description and a specific internal structure. A proof in this model establishes security under an idealization, not an unconditional guarantee for every possible implementation.
Different applications require different abstractions. Collision resistance alone may suffice for one authenticated data structure, whereas another protocol requires pseudorandomness, extraction properties, or resistance to related-input attacks. Sponge constructions are often analyzed using idealized permutations, and keyed hash modes have their own security definitions. Proofs therefore have to match the interface actually exposed to an adversary; a function’s familiar name does not make all of its possible uses interchangeable.
Implementation introduces additional failure modes. Endianness mistakes, incorrect padding, integer-width errors, and mishandled streaming state can produce nonstandard results. Test vectors check known inputs and outputs, including empty messages and boundary lengths, while more extensive validation examines multi-block processing and unusual update patterns. Hardware acceleration and vectorized implementations can improve throughput, but they must preserve the exact specified computation. Formal verification can establish selected implementation properties relative to a model, although the validity of the model and its connection to deployed code remain relevant.
For unkeyed hashing of public data, timing variations often reveal little that is confidential. The situation changes when hashing processes secret material inside password verification, HMAC, or key derivation. Secret-dependent behavior and early-exit comparison of authentication tags can create side channels. Hash state management also matters: exposing an intermediate state or incorrectly reusing a keyed context can violate assumptions that the underlying mathematical primitive does not address.
A quantum computer would change generic attack estimates. Grover’s algorithm offers a quadratic query speedup for unstructured preimage search, reducing an ideal -bit target from roughly classical evaluations to roughly quantum oracle queries. Quantum collision algorithms can achieve query complexity on the order of in standard theoretical models. These are query bounds, not complete engineering estimates: coherent access, circuit size, quantum memory, error correction, and parallelization affect physical feasibility.
These developments connect hashes to post-quantum cryptography. Hash-based signature schemes use carefully organized one-time or few-time signing components, authentication trees, and domain-separated hashing rather than the mathematical problems underlying RSA or elliptic-curve signatures. NIST standardized the stateless hash-based signature scheme SLH-DSA, derived from SPHINCS+, in FIPS 205 in 2024. Its security depends on defined properties of its hash components and construction, while signature size, computation, and state-management requirements distinguish different hash-based approaches.