Cryptographic hash functions reduce arbitrary byte strings to fixed-size digests. Protocols rely on specific resistance properties rather than on the mere act of hashing, because a fast unkeyed digest provides neither message authentication nor safe password storage.
Hash Functions #
A hash function maps an arbitrarily large input domain to a finite output domain, often a fixed-length bit string:
H: {0, 1}* -> {0, 1}^nNo security property follows from that definition. For example, f(x) = 0 for
every input is a hash function. It is unsuitable for a hash table because all
entries occupy one bucket, although the result is poor performance rather than
a cryptographic failure.
Cryptographic uses impose stronger requirements. A database should not retain a user’s plaintext password merely because the database might be disclosed. Its stored password verifier must make an offline guessing attack expensive; a general-purpose hash alone does not achieve that goal. Similarly, a digest may detect accidental corruption, but an attacker who can replace the message can also replace its digest. A plain hash supplies neither origin authentication nor active-adversary integrity.
Because the input domain is larger than the digest domain, every fixed-length hash has collisions: distinct inputs with the same digest. Cryptography therefore asks whether an adversary can find a useful collision, or an input for a specified digest, with feasible resources.
The Birthday Bound #
The birthday paradox has two equivalent presentations. In a group of randomly chosen people, the probability that two share a birthday exceeds 50% with only 23 people. Conversely, if birthdays can be queried one person at a time, a surprisingly small number of queries gives a substantial chance of finding a matching pair. Once 366 people have been considered under a 365-day model, the pigeonhole principle guarantees a pair.
The second presentation is more useful for hashing. Hash inputs need not be
drawn from a bounded population: an attacker can keep choosing fresh inputs
and evaluating the public function. After q outputs have been sampled from
an ideal hash with N uniformly likely output values, the probability of at
least one repeated output is approximately
1 - exp(-q(q - 1) / (2N)).The approximation follows by considering the complementary event. The first
output is unrestricted; the next must avoid one occupied value, the next two,
and so on. Multiplying those probabilities gives a product that decreases
approximately as the exponential above. A constant probability of a collision
therefore requires on the order of sqrt(N) evaluations. For an n-bit
digest, where N = 2^n, the generic collision cost is about 2^(n/2).
Uniform output distribution is an ideal-model assumption. Biases or structural
weaknesses can make collisions easier, while a function such as f(x) = 0
collides immediately. The birthday bound nonetheless describes an unavoidable
limit for an ideal fixed-output hash; enlarging the input space cannot improve
it. A birthday attack is simply this generic collision search, retaining
previous digests until a duplicate appears.
For example, an ideal 32-bit hash reaches about a 1% collision probability after roughly 9,300 trials and about a 50% probability after roughly 77,000. Such a digest is inadequate where collision resistance matters. The birthday bound concerns any pair of inputs, not recovery of a particular input.
Cryptographic Hash Function Security Properties #
A cryptographic hash function is an unkeyed hash intended to resist specified
attacks. “Cryptographic hash function” is not one formal security game; its
meaning depends on which properties a protocol requires. For a hash H, the
preimage of a value y is any message m for which H(m) = y.
The following games differ in what the attacker receives and may choose:
- Preimage resistance: given a target digest
y, find anymsuch thatH(m) = y. - Second-preimage resistance: given a particular message
m1, find a distinctm2such thatH(m1) = H(m2). - Collision resistance: find any distinct pair
m1,m2such thatH(m1) = H(m2). - Chosen-prefix collision resistance: given two different prefixes
p1andp2, find suffixess1ands2such thatH(p1 || s1) = H(p2 || s2).
A collision attack lets the attacker choose both messages, whereas a second-preimage game fixes one message. A preimage game fixes the digest instead. The games should not be collapsed into a universal ordering: properties can have formal implications under particular distributions and models, but weaknesses can be target-specific. A protocol must select the property that matches its attacker-controlled inputs.
For an ideal n-bit hash, generic preimage and second-preimage searches take
about 2^n work, while the birthday method finds a collision in about
2^(n/2) work. Collision resistance means that no attack materially improves
on that generic birthday cost, not that collisions do not exist.
Chosen-prefix collisions are more capable than a pair of unrelated colliding files. They let an attacker begin with two meaningful, different prefixes—for example, the headers and initial content of two document formats—and generate suffixes that yield the same digest. Practical chosen-prefix collisions against MD5 illustrated how a collision can be embedded in artifacts with different semantics, including forged certificate-related material. Such attacks made collision-sensitive uses of MD5 unacceptable.
Unkeyed hashes do not take secret keys. A construction that accepts a key is a message-authentication code, a keyed hash in some terminology, or another primitive; its security requirements must be assessed separately.
Hash Design and Constructions #
An effective cryptographic design distributes small input changes widely across its output, an effect called the avalanche effect. Avalanche behavior is a useful diagnostic, but it neither proves preimage resistance, second-preimage resistance, nor collision resistance. Those properties concern an adversary’s best algorithm.
Many iterative hashes begin with a compression function. Given a chaining value and one fixed-size message block, it produces a new chaining value of the same width:
C: {0, 1}^n x {0, 1}^b -> {0, 1}^nThe word “compression” refers to the total input being longer than the output; it does not mean that the function is reversible. Security analyses seek appropriate one-way and collision-resistance properties for this component. Classical constructions can build compression functions from block ciphers, although modern standardized hash families use dedicated designs.
Merkle–Damgård Construction #
The Merkle–Damgård construction turns a fixed-input compression function into a variable-length hash. It starts from an initial chaining value, pads the message into blocks, and feeds each block with the current chaining value into the compression function. The final chaining value is the digest.
Merkle–Damgård strengthening appends an encoding of the original message length as part of padding. Subject to its conditions, a collision-resistant compression function then yields a collision-resistant variable-length hash: without strengthening, a collision in padded inputs can arise from ambiguous message boundaries. MD5, SHA-1, and SHA-2 use this broad construction; their compression functions and digest lengths determine their actual security.
Length encoding does not prevent the related length-extension property.
For a conventional Merkle–Damgård hash, a digest of m exposes the chaining
value after processing m and its padding. An attacker who knows the digest
and the length of m can often compute a valid digest for
m || padding(m) || extension without knowing m. The result matters when a
system authenticates data as:
SHA-256(secret || message)An attacker can extend message and calculate the corresponding digest if
the secret length can be guessed. Do not use a bare Merkle–Damgård hash as a
secret-prefix MAC. Use HMAC instead:
HMAC(K, m) = H((K XOR opad) || H((K XOR ipad) || m))HMAC’s nested keyed construction resists length extension and is suitable for message authentication when used with a current hash such as SHA-256. Protocols must still define key generation, truncation, message encoding, and key separation.
Domain Separation and Salting #
One hash function often serves several roles within a protocol. Domain separation prevents values from one role from being accepted in another. A standardized construction may prepend a fixed function identifier, place a context string in a dedicated field, or derive independent keys for each role. The encoding must be unambiguous: concatenating variable-length values without lengths or a specified serialization can map different field sequences to the same byte string.
Use the domain-separation mechanism defined by the protocol or primitive. Changing a prefix or inventing a local encoding changes the protocol and requires separate analysis. SHA-3 functions, the customizable cSHAKE functions, and key-derivation protocols expose different separation mechanisms, so their inputs are not interchangeable.
A salt solves a different problem. Password verifiers use a unique random salt per credential so equal passwords do not produce equal stored values and an attacker cannot amortize one precomputed table across accounts. The salt is stored with the verifier and is not secret. It does not add password entropy, authenticate a message, or replace domain separation.
Password hashing must also impose configurable time and memory cost. Use Argon2id according to RFC 9106 where available; scrypt, bcrypt, or PBKDF2 may be required by platform and compliance constraints. Store the algorithm identifier, parameters, salt, and derived output so parameters can be upgraded after a successful login.
Selecting Hash Algorithms #
Use a modern general-purpose hash such as SHA-256, SHA-512/256, SHA-3, or BLAKE2 according to the applicable standard, interoperability needs, and protocol. SHA-256 provides a 256-bit digest and an ideal generic collision work factor of 128 bits. SHA-512/256 is a distinct SHA-512-based algorithm with a 256-bit output, not an informal truncation of SHA-512.
MD5 is broken for collision resistance and must not be selected for collision-sensitive security applications. SHA-1 has practical collision and chosen-prefix collision attacks and is likewise deprecated for digital signatures, certificates, and similar uses. Legacy verification may require recognizing these algorithms, but new designs must not create MD5 or SHA-1 signatures. Migration needs an explicit algorithm identifier, an allowlist for newly generated data, a deadline for removing legacy verification, and protection against downgrade to the obsolete algorithm.
Comments
Read or comment on GitHub (sign-in required to comment)