Confusion, diffusion, and the avalanche effect

In 1949, well before AES, Claude Shannon stated the two properties that any good cipher must possess: confusion and diffusion. AES is a direct application of these principles.

Confusion

Confusion requires that the relationship between the key and the ciphertext be as complicated and opaque as possible. Ideally, each bit of the ciphertext must depend on several bits of the key, in a way so tangled that no simple analysis allows tracing back to the key.

In AES, confusion comes from the SubBytes step: the S-box is non-linear, which breaks any simple algebraic relationship between the input and the output.

Diffusion

Diffusion requires that a change in the plaintext spread over the whole ciphertext. If a single bit of the message is modified, this change must propagate until it influences a great many bits of the result.

In AES, diffusion comes from ShiftRows (which moves the bytes between columns) and from MixColumns (which mixes the bytes of the same column). Together, in a few rounds, they make one input byte end up touching the whole block.

The avalanche effect

The measurable consequence of these two principles has a name: the avalanche effect. A cipher is said to possess it when changing a single bit of the input changes about half of the bits of the output.

Let us illustrate with two messages that differ by only one bit:

Message A : 0110 1001 0011 1100 ...
Message B : 0110 1000 0011 1100 ...   (a single bit changed)
              |
              v  after AES encryption
Ciphertext A : 1011 0100 1110 0010 ...
Ciphertext B : 0001 1101 0100 1011 ...   (~50% of the bits differ)

Although A and B are almost identical, their ciphertexts have no more visible link. About one bit in two has flipped.

Why it is essential

Without the avalanche effect, an attacker could slightly modify the plaintext, observe a small variation in the ciphertext, and progressively trace back to the key or the message. The avalanche forbids this approach: the slightest modification produces a completely different result, statistically indistinguishable from randomness.

This is also what makes the ciphertext incompressible and patternless: it resembles noise, which is precisely the goal.

Without avalanche : small cause -> small effect   (exploitable)
With avalanche    : small cause -> total effect   (unpredictable)

In summary

• Shannon defined two principles: confusion (opaque key-ciphertext relationship) and diffusion (one bit of the plaintext influences the whole ciphertext).
• In AES, SubBytes ensures the confusion, ShiftRows and MixColumns ensure the diffusion.
• The avalanche effect is the consequence of it: changing 1 bit of input changes ~50% of the bits of output.
• This effect forbids progressive attacks and makes the ciphertext resemble noise.