The Avalanche Effect

Flip one bit of the plaintext and watch the difference grow round by round. The average comes from two thousand pairs.

DiffusionMeasurementdemo

Objectives

Trace how many state bits differ after each round of a sample cipher.
Explain why a single trace cannot support a claim about diffusion.
Predict the average number of ciphertext bits a one-bit change should alter.
Compare how diffusion builds up in a Feistel network and in an SPN.
Interpret a shortfall in the average as information leaked to an attacker.

50%

One flipped bit, one trace, and then two thousand of them.

Flip one plaintext bit, encrypt both blocks with the same key, and count the state bits that differ after each step.

Plaintext bit to flip, counted from the left

The two plaintexts, bit by bit

top row is the original, bottom row is the flipped copy

≠

hex

9A7C

927C

The two blocks are one bit apart, at position 4.

Feistel network

Bits differing between the two encryptions after each step, out of 16.
Step	Original	Flipped	Bits
before round 1	9A7C	927C	1 of 16
after round 1	7C3B	7C33	1 of 16
after round 2	3BF6	33C0	5 of 16
after round 3	F67F	C0E2	9 of 16
after round 4	7F9A	E26D	12 of 16
after round 5	9A56	6D0E	10 of 16
after round 6	56CA	0EC3	5 of 16
after round 7	CAC1	C3C7	4 of 16
after round 8	C15E	C748	5 of 16

The two middle columns are the two encryptions at that step, so every count is a comparison you can redo by hand. A marked row has reached half the block or more.

The count climbs and then moves around. One pair of blocks is a sample of size one, so no single line here settles anything.

Repeat the experiment with a fresh plaintext, key and flipped bit each time, and average the ciphertext bits that change. For a good cipher about half the output bits should change on average, so 8 of 16 here.

One pair of blocks

Average ciphertext bits changed by a one-bit plaintext change.
Network	Mean	Against the target of 8
Feistel network	12.00 of 16

A marked row here sits within half a bit of the target, which is a different mark from the one in the trace above.

A single pair can be anywhere between 1 and 16. It is never 0, because both networks are permutations, so two different plaintexts cannot reach the same ciphertext. Raise the sample size and watch the number settle.

Good diffusion is a statistical property, not the result of one example. A cipher that stayed below the target would tell an attacker which plaintexts are close to each other.

step 1/2

CPE 645 / CS 685

The Avalanche Effect

A Block Cipher Is a Permutation

The Feistel Network