- Cryptographic hash functions map arbitrary inputs to fixed-size outputs.
- Pre-image resistance: Given $H(M)$, it is infeasible to find $M$.
- Collision resistance: It is infeasible to find any $M_1 \neq M_2$ such that $H(M_1) = H(M_2)$.
- Avalanche effect: Changing 1 input bit alters approximately 50% of output bits.
### Core Properties of Hash Functions
A cryptographic hash function $H$ must fulfill three strict properties:
1. **Pre-image Resistance (One-Way)**: Given $h$, finding $x$ such that $H(x) = h$ is hard.
2. **Second Pre-image Resistance**: Given $x_1$, finding $x_2 \neq x_1$ such that $H(x_1) = H(x_2)$ is hard.
3. **Collision Resistance**: Finding *any* pair $x_1 \neq x_2$ where $H(x_1) = H(x_2)$ is hard.