What is the avalanche effect in hash functions, and why is it a critical property?

Changing a single bit in the input causes approximately 50% of all output bits to change — this is the avalanche effect.

* The number of flipped bits follows a Binomial(256, ½) — sharply peaked at 128, so "about half" is overwhelmingly likely. *

Statistically, when you flip one input bit:

• Each output bit flips with probability 1/2
• So on average, half the hash bits change
• For a 256-bit hash: ~128 bits flip
• For a 512-bit hash: ~256 bits flip

This is quantified using binomial coefficients: the probability that exactly $m$ of $n$ bits change follows $\binom{n}{m}$, which is maximal at $m = n/2$.

Concrete numbers for n = 256:

• Exactly 128 bits change: ~5% of cases
• Between 118-138 bits change: ~81% of cases
• Between 108-148 bits change: ~99% of cases
• Fewer than 50 or more than 206 bits change: ~$10^{-21}$% of cases (essentially never)

Why it matters: Without the avalanche effect, an attacker could make small changes to a document and predict how the hash changes — making forgery much easier.

Go deeper:

• Avalanche effect (Wikipedia) — the property (and the stronger "strict avalanche criterion") for hashes and block ciphers.