THE AVALANCHE EFFECT flip one input bit; half the output must change
A good cipher (or hash) has the avalanche property: flipping a single input bit flips about half the output bits, unpredictably. It is the measurable face of diffusion — if one bit changed only one output bit, an attacker could peel the cipher apart bit by bit. The test is brutal and simple: change one bit, count how many output bits move, and watch it climb to n/2 as the rounds stack up.
THE TECHNIQUE Hamming distance of outputs on a 1-bit input change
The stark contrast: a linear cipher (just XOR a key) changes exactly one output bit — catastrophic. A real cipher, round by round, spreads that one bit toward half the block. Measure the Hamming distance and watch it grow: live demo
HISTORY & CREDIT Feistel 1973; SAC Webster-Tavares 1985
“More output change is always better.” — the target is exactly half, not maximal. Every output bit should flip with probability 1/2, independently — the strict avalanche criterion (per-bit; mutual independence is the distinct Bit Independence Criterion). All bits always flipping is as predictable (and as broken) as none flipping; randomness at exactly 50% is the goal — and that the bit-flips be mutually independent is a separate requirement, the Bit Independence Criterion (same 1985 paper). cited
1973 · Horst Feistel — coins the term avalanche for the effect in his DES-era design. 1985 · Webster & Tavares — the Strict Avalanche Criterion (SAC): each output bit changes with probability exactly 1/2 when any single input bit flips. the driver · diffusion — the bit-permutation of an SPN (192) or the swap of a Feistel (190) — is what carries one flipped bit across the block over successive rounds.
It is a diagnostic, not a mechanism: avalanche is what good confusion + diffusion produce, and measuring it (one flip, count the change) is the cheapest way to tell a strong cipher from a broken one. Feistel 1973 / Webster-Tavares 1985
RECOMMEND FOR I-13 one bit flip, output change measured
On the canonical compiler a linear cipher fails avalanche outright — one input bit moves exactly one output bit:
$ i13 run avlin.i13 # linear cipher c = p xor k, flip one input bit
linear avalanche = 1 -- exactly 1 of 16 output bits changes: CATASTROPHIC
-- a good cipher (many rounds, S-box + permute) approaches 8 of 16
Recommend: the avalanche effect is LIT as the cipher test for I-13 — verified that a linear cipher (c = p ⊕ k) has avalanche 1 (a single flipped input bit moves exactly one output bit, so the key is trivially recoverable), computed as the Hamming distance (a popcount) of two ciphertexts on a one-bit-different input. It is the diagnostic that justifies rounds: stack S-boxes (191) and diffusion (192) and the number climbs toward n/2. For any I-13 cipher, this popcount-of-the-XOR is how you measure that it mixes — and the strict-avalanche target is exactly half, not maximal.