Properties of Good Hash Functions

A good cryptographic hash function must satisfy several formal properties to be considered secure. Understanding these properties explains why certain algorithms are trusted (SHA-256) while others are broken (MD5), and helps you evaluate new hash functions.

1. Deterministic output:

The same input must always produce the same output. There is no randomness in the hash computation. This is fundamental: if SHA-256("hello") returned different values on different runs, the function would be useless for verification. Note that this does not mean different inputs always produce different outputs (that is impossible for a function with fixed output size).

2. Preimage resistance (one-way property):

Given a hash value h, it should be computationally infeasible to find any input m such that hash(m) = h. "Computationally infeasible" means requiring approximately 2^n operations for an n-bit hash. For SHA-256, finding a preimage requires about 2^256 operations. This property ensures that seeing a hash does not reveal the original input. It is why password hashes do not directly expose passwords (though fast hashing allows brute-force attacks on weak passwords).

3. Second preimage resistance:

Given an input m1, it should be infeasible to find a different input m2 such that hash(m1) = hash(m2). This is stronger than preimage resistance because the attacker has additional information (the original input). Second preimage resistance is essential for digital signatures: if an attacker could find a second preimage, they could substitute a signed document with a different document that has the same hash.

4. Collision resistance:

It should be infeasible to find any two different inputs m1 and m2 such that hash(m1) = hash(m2). Due to the birthday paradox, this requires approximately 2^(n/2) operations for an n-bit hash. Collision resistance implies second preimage resistance (in practice, if not in theory). MD5 and SHA-1 have failed this property. SHA-256 retains it with a 2^128 security level.

5. Avalanche effect:

A small change in the input should produce a dramatically different output. Flipping a single bit of the input should change approximately 50% of the output bits. This property ensures that similar inputs produce unrelated hashes, preventing attackers from learning anything about the input by observing how the hash changes. It also ensures uniform distribution of hash values, which is important for hash tables and data structures.

Bonus: efficiency:

While not a security property, a practical hash function must be efficient to compute. SHA-256 processes data at several hundred megabytes per second in software and multiple gigabytes per second with hardware acceleration. This balance between security and speed is what makes it suitable for widespread deployment.