Answer: A secure hash function \(H\) must accept any input size, give a fixed-size output, be easy to compute, and be pre-image resistant (one-way), second pre-image resistant (weak collision resistant) and collision resistant (strong collision resistant); its output should also look random (avalanche effect).
- Variable input size: \(H\) can be applied to a message of any length.
- Fixed output size: \(H\) always produces a digest of fixed length (e.g. 256 bits for SHA-256), whatever the input length.
- Efficiency: For any \(x\), \(H(x)\) is quick to compute in both hardware and software, so it can be used on large data.
- Pre-image resistance (one-way property): Given a hash value \(h\), it is computationally infeasible to find any \(x\) with \(H(x) = h\). This protects stored password hashes and secret values from being reversed.
- Second pre-image resistance (weak collision resistance): Given an input \(x\), it is infeasible to find a different \(y \ne x\) with \(H(y) = H(x)\). This stops an attacker from substituting a forged message that matches an existing signed hash.
- Collision resistance (strong collision resistance): It is infeasible to find any pair \(x \ne y\) with \(H(x) = H(y)\). Collisions must exist (infinite inputs, finite outputs) but must be hard to find; because of the birthday attack an \(n\)-bit hash gives only about \(2^{n/2}\) security, so long digests are needed. Collision resistance implies second pre-image resistance.
- Pseudo-randomness and avalanche effect: The output should pass randomness tests, and changing even one input bit should change about half of the output bits, so similar messages give completely different digests.
- Deterministic: The same input always gives the same output, so the receiver can recompute and compare.
Uses: message integrity checks, digital signatures (sign the hash), MACs (HMAC), password storage and blockchain.