Hash Functions: What One Must Do

Easy to compute. H(x) is relatively easy to compute for any given x, so that the scheme is practical in hardware and software.

Deterministic. The same input always gives the same digest. This is obvious and is worth stating, because it is why a hash cannot be used as an encryption: there is no key and nothing is hidden from somebody who can guess the input.

The avalanche property. A one-bit change in the input changes about half the bits of the output. Not a formal requirement but a consequence of the other three, and the thing a reader can measure.

What a hash is used for, and which property each use needs

The last row is worth stating in an answer: a non-cryptographic hash for a hash table is not a weak cryptographic hash, it is a different thing for a different purpose, and using SHA-256 to index a dictionary is as much a mistake as the reverse.

And password storage needs slowness, which is not on the list of hash requirements at all: a fast hash is a feature for authentication and a defect for passwords, because the attacker's guessing is as fast as your checking. That is why password hashing uses a deliberately slow, salted, parameterised construction rather than a bare hash.

Worked example: which property has failed, and does it matter

The situation. A collision is published for a hash function H: two different files with the same digest. Four systems use H. Which are broken?

System 1: signatures on college certificates. Broken. A forger prepares a genuine certificate and a fraudulent one with the same digest, has the genuine one signed, and attaches the signature to the fraudulent one. Collision resistance is exactly what this needs.

System 2: passwords stored as H(password). Not broken by this. The attacker holding a digest still needs a preimage, and a collision gives them nothing: they need the password for that digest, not any pair of colliding strings. (The system has other problems: no salt and a fast hash.)

System 3: HMAC over H for authenticating packets. Not broken. HMAC's security proof does not rest on collision resistance of the underlying hash. This is why RFC 6194 could restrict SHA-1 while HMAC-SHA-1 remained acceptable.

System 4: file integrity, comparing a downloaded file's digest against a published one. Broken, but the attack is harder than it sounds. The attacker needs a second preimage for the specific published file, which a collision does not give. However, if the attacker can influence the original file, they can prepare a colliding pair and substitute afterwards, so the answer depends on who created the file.

The step that carries the marks. Naming the property each system depends on, and noticing that a collision is not a universal break. An answer that says "the hash is broken so everything using it is broken" has not understood the three properties.

Distinctions that carry marks

What beginners get wrong here

Merging the three resistances. They differ in what the attacker is given, and the collision cost is the square root of the other two.

Saying a broken hash breaks everything using it. It depends which property failed and which property the system needs.

Saying a hash is "one-way encryption". There is no key, nothing is recoverable, and nothing is hidden from somebody who can guess the input. It is not encryption.

Using a bare fast hash for passwords. A fast hash helps the attacker as much as the defender. Passwords need salt and deliberate slowness.

Using a cryptographic hash for a hash table. Different purpose, much slower, and no benefit.

Quick revision

• A hash takes any length to a fixed length, with no key, and is deterministic.
• Preimage: given a digest, find a message. Cost 2 to the power n.
• Second preimage (weak collision resistance): given a message, find a different one with the same digest. Cost 2 to the power n.
• Collision (strong collision resistance): find any pair. Cost 2 to the power n/2, by the birthday bound.
• Collision resistance is the weak one, and it is why MD5 and SHA-1 fell to collisions long before preimages.
• Signatures need collision resistance. HMAC does not. That is why SHA-1 in a signature is unacceptable and SHA-1 inside HMAC is not.
• Other requirements: any input size, fixed output, easy to compute, deterministic; plus the avalanche property as a consequence.
• Uses: message authentication, password storage (needs slowness, not on the list), file integrity, signatures, commitment, deduplication, proof of work.

Test yourself

1. Define a cryptographic hash function and its three resistance properties. A function taking a variable-length input to a fixed-length digest, with no key. Preimage resistance: given a digest, it is infeasible to find any message hashing to it. Second preimage resistance: given a message, it is infeasible to find a different message with the same digest. Collision resistance: it is infeasible to find any two distinct messages with the same digest.

2. Why is collision resistance weaker than the other two for the same digest size? Because the attacker chooses both messages and is not tied to any given value, so the birthday bound applies: among about 2 to the power n/2 randomly chosen messages a matching pair becomes likely. Preimage and second preimage resistance both require hitting a specific target and cost 2 to the power n.

3. Why is SHA-1 unacceptable in a digital signature but acceptable inside HMAC? Because a signature is computed over the digest, so a collision produces two documents that one signature covers, and collision resistance is therefore essential; SHA-1's collision resistance has been broken. HMAC's security does not rest on the collision resistance of its hash, so a collision does not give an attacker a forgery, and HMAC-SHA-1 remains acceptable.

4. State the other requirements on a hash function besides the three resistances. It must apply to a block of data of any size; it must produce a fixed-length output; it must be relatively easy to compute for any input, so that implementations are practical; and it must be deterministic. As a consequence of the resistances it will also exhibit the avalanche property, that a one-bit input change alters about half the output bits.

5. Which property does password storage depend on, and what does it need beyond the three? Preimage resistance, because the attacker holds the digest and wants a password that produces it. Beyond the three it needs deliberate slowness and a per-password salt, because a fast hash lets an attacker test guesses as quickly as the system verifies them, and a salt prevents one precomputed table covering all users.

6. A collision is published for a hash function. Which of these is broken: signatures, password storage, HMAC? Signatures are broken, because a forger can obtain a signature on an innocent document and attach it to a colliding fraudulent one. Password storage is not broken by a collision, because the attacker needs a preimage of a specific digest rather than any colliding pair. HMAC is not broken, because its security does not rest on collision resistance.

7. Why is a hash function not a form of encryption? Because it has no key, so nothing distinguishes an authorised computation from an unauthorised one; because it is not invertible even in principle, since many inputs share each output; and because it hides nothing from an attacker who can guess the input, as they can simply hash their guess and compare.