Avalanche effect in DES

Question

I couldn't understand the avalanche effect in DES. Could someone explain how avalanche effect happens in DES

Answer 1

First of all, avalanche effect is a desirable effect: it means that a very small change in the inpout will lead to a very big change in the output. A security algorithm that doesn't provide this avalanche effect can lead to an easy statistical analysis: if the change of one bit from the input leads to the change of only one bit of the output, then it's easy to guess / try to find the input: just change one bit of it and verify if it was the right one.

How it works in DES: if you take a look at the DES, you'll see that it has 16 rounds and 2 permutations. The real thing happens in the rounds: for each round, the input bits are used to look up for bits that will be used as the output (the S-box). take a look at this presentation, for example. With the shifts that are made at each round, it means that the "index bits" (the ones used to the table look up) come from the "data bits" that come from the previous round.

Changing a single bit in the input will make more bits be changed in the following rounds. Slide 6.41 of the above presentation show how many bits will change at each round.