Avalanche in DES

Flip one bit of the plaintext, or one bit of the key. Count the differing bits after every round, and compare the two curves.

DiffusionAvalanchedemo

Objectives

Measure the bits that differ after each round from a one-bit input change.
Compare the diffusion of a plaintext bit against the diffusion of a key bit.
Predict the round at which the difference first reaches half the block.
Identify the eight key bits whose change produces no difference at all.
Interpret a single pair of blocks as one sample rather than as an average.

25%

One changed bit, counted round by round, and then averaged over many pairs.

Change exactly one bit and hold everything else fixed. Changing a plaintext bit keeps the key. Changing a key bit keeps the plaintext. Both blocks below are the worked example published with FIPS 46.

Bit to change, numbered from 1 at the most significant end

The two runs, before anything is encrypted

The plaintext and the key used by each of the two encryptions, and the position at which they differ.
Input	First run	Second run	Differs at
Plaintext	01 23 45 67 89 AB CD EF	81 23 45 67 89 AB CD EF	position 1
Key	13 34 57 79 9B BC DF F1	13 34 57 79 9B BC DF F1	nothing

The two runs differ in one position, position 1, and in nothing else. The marked row is the input you are changing.

The two ciphertexts

The ciphertext produced by each of the two runs, and the number of bits at which the two ciphertexts differ.
Run	Ciphertext
First	85 E8 13 54 0F 0A B4 05
Second	AD 9D FD 6C 35 DE 8D EC
Bits differing	33 of 64

One input bit changed 33 of the 64 output bits. The next step counts that change round by round.

Run both encryptions again and stop after every round. The state is the two halves L and R together, 64 bits, so the count below is a comparison of two 64-bit values at the same point in the cipher.

Plaintext bit 1 changed

The number of state bits that differ between the two encryptions after each round, out of 64.
Round	Bits differing	Out of 64
0, just after IP	1 of 64
1	7 of 64
2	21 of 64
3	34 of 64
4	32 of 64
5	27 of 64
6	27 of 64
7	25 of 64
8	26 of 64
9	25 of 64
10	27 of 64
11	33 of 64
12	33 of 64
13	32 of 64
14	35 of 64
15	37 of 64
16	33 of 64

Round 0 is the state just after the initial permutation. IP moves the changed bit to another position and does not copy it, so exactly one bit still differs there.

The count first reaches 32 of 64 at round 3, out of 16. After that it stays near 32 rather than climbing further, which is what a well diffused state looks like.

The final permutation is a permutation, so it moves bits without changing how many of them differ. The count after round 16 is therefore the same number as the ciphertext count in the step above.

A one-bit key change and a one-bit plaintext change end at the same place by different routes. The plaintext change starts inside the state. The key change starts outside it, in the subkeys, and has to be carried into the state by the round function first.

DES stores a 64-bit key. PC-1 selects 56 of those positions for the key register and never names the other eight. A bit that PC-1 does not name reaches no subkey, so changing it changes nothing.

What the current choice does

A plaintext bit is being changed. Choose a key bit to test this.

the 64 stored key positions, one row per byte

A cell marked P is a parity bit and a cell marked k is key material. The parity bits form the last column, because they are bit 8 of each of the eight key bytes. Choose any cell and the two steps above are recomputed for it.

Every parity bit, against the same plaintext

The ciphertext produced when each of the eight parity bits of the key is changed, and whether it equals the baseline ciphertext.
Key position changed	Ciphertext	Against the baseline
none, the baseline	85 E8 13 54 0F 0A B4 05	baseline
8	85 E8 13 54 0F 0A B4 05	identical
16	85 E8 13 54 0F 0A B4 05	identical
24	85 E8 13 54 0F 0A B4 05	identical
32	85 E8 13 54 0F 0A B4 05	identical
40	85 E8 13 54 0F 0A B4 05	identical
48	85 E8 13 54 0F 0A B4 05	identical
56	85 E8 13 54 0F 0A B4 05	identical
64	85 E8 13 54 0F 0A B4 05	identical

The eight positions PC-1 never names are 8, 16, 24, 32, 40, 48, 56, 64. That list is derived from the PC-1 table rather than typed, and it is the same list the grid marks.

This is the concrete proof that DES has a 56-bit key. Eight of the 64 stored bits are a per-byte parity check for transmission, not key material, and an attacker who searches keys never guesses them. Every cost figure for DES therefore uses 2^56.

One pair of blocks is a sample of size one. Repeat the experiment with a fresh plaintext, a fresh key and a fresh position each time, and average the ciphertext bits that change. Three draws are compared: a plaintext bit, a key bit taken from the 56 that PC-1 keeps, and a key bit taken from all 64 stored positions.

Trials per draw

100

Each trial is two real DES encryptions, and three draws are run, so the button needs a few seconds at the higher settings. Nothing is computed until you press it.

No sample yet

Press the button above. The three averages appear here, with the value each one is expected to sit near.

Good diffusion is a statistical property of a cipher, not the result of one example. Half the output bits is the target because any other value would tell an attacker which inputs are close to each other. The DES here is a teaching implementation, written to be read and not constant time, so use a reviewed library for anything real.

step 1/4

CPE 645 / CS 685

Avalanche in DES

Encrypting and Decrypting a Block

Weak Keys and the Complementation Property