Hash functions and the six requirements

What a hash function is, and the one word that separates it from a MAC

A cryptographic hash function takes a message M of any length and produces a fixed-length digest h = H(M). Two facts define it. The input size is unbounded; the output size is not. And — the fact everything downstream turns on — H takes no key. A hash is a public function that anybody can compute. A MAC, which you meet in a later lesson, takes a key. That single difference is why a bare hash cannot authenticate anything: if you can compute H(M), so can the attacker who replaced M.

Before hashing, the message is padded to a whole multiple of a fixed block length, and the padding includes the original message length in bits. That is not bookkeeping — it is a security measure. It means two messages of different lengths can never be hashed as though they were the same block sequence, which makes constructing a second message with a chosen digest materially harder.

The six requirements

The first three are functional: they say H is usable at all.

1. H applies to a block of data of any size.
2. H produces a fixed-length output.
3. H(x) is relatively easy to compute for any x, in hardware and in software.

The last three are the security requirements, and they are the examinable ones.

1. Preimage resistant (one-way): given a digest h, it is computationally infeasible to find any x with H(x) = h.
2. Second preimage resistant: given x, it is computationally infeasible to find any y with y ≠ x and H(y) = H(x). Also called weak collision resistance.
3. Collision resistant: it is computationally infeasible to find any pair (x, y) with x ≠ y and H(x) = H(y). Also called strong collision resistance.

A function that satisfies requirements 1 through 5 is called a weak hash function; one that satisfies all six is a strong hash function. Note carefully that this weak/strong labelling of the function is a completely different axis from the weak/strong labelling of the properties, and the shared vocabulary is exactly what an exam question exploits. “Weak collision resistance” means second preimage resistance. It does not mean a weak function.

Worked example — a toy hash, broken in one move

Here is a hash that satisfies the three functional requirements and none of the security ones. Chop the message into 4-byte blocks, pad the last one with zero bytes, and XOR all the blocks together position by position. Any input size: yes. Fixed 4-byte output: yes. Easy to compute: extremely.

Take the message PAY BOB 0010. Three blocks: PAY , BOB , 0010. XOR them and you get the digest 223e2a30.

Now forge. Write whatever message you like — say PAY EVE 9999 — and hash it; call that digest d. XOR d with the target digest 223e2a30; the result is a 4-byte patch block. Append the patch block to your forged message and hash again. XOR is associative and commutative, so appending the patch cancels the difference exactly, and the forged message now hashes to 223e2a30. Two messages, one digest, three lines of work and no search at all.

Which requirement did that break? Requirement 6, collision resistance, and requirement 5 with it: the attacker was handed a specific message and produced a different message matching it. Requirement 4 fell too — with this H you can construct a preimage of any digest you like by the same trick.

The same one-move break defeats every simple checksum. Sum the bytes mod 256 instead of XORing them: append a single byte equal to (target - running_sum) mod 256 and you are done. Adding a rotation before each XOR — the rotated XOR hash — spreads the bits around but does not change the fact that the attacker can solve for a final block. A hash function earns its security requirements only by being infeasible to invert, not by being complicated to describe.

One more number worth carrying: over ordinary text, the high-order bit of every octet is zero, so a 128-bit XOR hash has an effectiveness of about $2^{-112}$, not $2^{-128}$. Sixteen of its bits carry no information at all.