Hash functions & digital signatures

A cryptographic hash function takes an input of any size and produces a fixed-size output (a digest) with three properties: it's deterministic (same input always gives same output), it's infeasible to reverse (you can't recover the input from the digest — preimage resistance), and it's infeasible to find two different inputs with the same digest (collision resistance).

SHA-2 (specifically SHA-256 and SHA-512) is the current widely deployed standard, used in TLS, Bitcoin, code signing, and password storage schemes (combined with salting and slow key-derivation functions). SHA-3, standardized in 2015, uses a structurally different design (a sponge construction) and serves as a hedge in case future cryptanalysis weakens SHA-2.

The predecessor algorithms MD5 and SHA-1 are both cryptographically broken for collision resistance — real collisions have been publicly demonstrated for both — and neither should be used for security purposes today, only for non-adversarial checksums.

"Deterministic but unpredictable" is easiest to see with real output. SHA-256 of the five-letter string "hello" and SHA-256 of "hellp" — one letter different, one step along the alphabet — share no visible structure at all, even though the inputs are nearly identical. This is the avalanche effect in practice: a well-designed hash function is built so that changing even a single input bit flips roughly half the output bits, with no way to predict which half in advance.

SHA-256 can't hash an arbitrary-length message in one mathematical step — internally, it uses the Merkle-Damgård construction: the message is padded and split into fixed-size blocks, and a compression function processes them one at a time, feeding its output (a "chaining value") in as part of the input for the next block. The final chaining value, after the last block, is the digest.

This iterative structure is elegant and easy to reason about, but it has a well-known side effect: given only H(message) and the length of message (not the message itself), an attacker can compute H(message ‖ extra) for an attacker-chosen extra, without ever knowing the original message — a length-extension attack. It works precisely because the digest is just the last chaining value, which is all the compression function needs to keep going.

Visually, Merkle-Damgård is nothing more than a straight line of compression steps, each one blind to everything except the chaining value handed to it and the next block of message — which is exactly why an attacker who only knows the final digest and the message's length can pick up the chain right where it left off and keep extending it.

Length extension is exactly why HMAC (covered below) doesn't simply hash the key and message concatenated together — naive H(key ‖ message) is vulnerable to exactly the attack above: an attacker who knows H(key ‖ message) and its length can compute a valid H(key ‖ message ‖ extra) without ever learning the key. HMAC's nested double-hashing construction was specifically designed to close this gap, and it's why "just concatenate and hash" is one of the most common amateur cryptography mistakes.

SHA-3, standardized in 2015 after a public competition (much like AES's selection process), doesn't use Merkle-Damgård at all — it's built on a sponge construction, which absorbs input into a large internal state and then squeezes output back out. Because the internal state is larger than the final digest, and the output isn't simply "the last chaining value" the way Merkle-Damgård's is, SHA-3 is naturally immune to length-extension attacks without needing an HMAC-style workaround.

Preimage resistance (finding an input for a given digest) costs roughly 2ⁿ operations for an n-bit hash — but finding any collision (any two inputs sharing a digest) is cheaper than that, thanks to the birthday paradox: among a surprisingly small set of random values, the odds of two colliding are much higher than intuition suggests. For an n-bit hash, an attacker can expect to find a collision after roughly 2ⁿᐟ² attempts, not 2ⁿ — which is exactly why SHA-256 (256-bit output) is described as offering 128-bit collision resistance, not 256-bit.

A digital signature proves two things at once: the message came from the holder of a specific private key (authenticity), and the message wasn't altered after signing (integrity). The signer hashes the message, then encrypts (more precisely, transforms) that hash with their private key. Anyone with the public key can verify by hashing the message themselves and checking it matches.

RSA signatures and ECDSA both follow this hash-then-sign pattern. This is also why hash function security matters even in "public-key" workflows — if an attacker can find a second message with the same hash as a legitimately signed one, they can attach a valid signature to a message that was never actually signed.

HMAC combines a hash function with a secret key to produce a message authentication code — proof that a message wasn't tampered with, verifiable by anyone holding the shared key. HMAC-SHA256 is common wherever two parties share a symmetric secret and need integrity without full public-key signatures, including inside several TLS cipher suites and API authentication schemes.