# Understanding Cryptography by Christof Paar and Jan Pelzl - Chapter 3 Solutions - Ex3.5

- 3 mins- Return to index
- Exercise 3.1
- Exercise 3.2
- Exercise 3.3
- Exercise 3.4
- Exercise 3.5
- Exercise 3.6
- Exercise 3.7
- Exercise 3.8
- Exercise 3.9
- Exercise 3.10
- Exercise 3.11
- Exercise 3.12
- Exercise 3.13

## Exercise 3.5

Remember that it is desirable for good block ciphers that a change in one input bit affects many output bits, a property that is called diffusion or the avalanche effect. We try now to get a feeling for the avalanche property of DES. We apply an input word that has a “1” at bit position 57 and all other bits as well as the key are zero. (Note that the input word has to run through the initial permutation.)

- How many S-boxes get different inputs compared to the case when an all-zero plaintext is provided?
- What is the minimum number of output bits of the S-boxes that will change according to the S-box design criteria?
- What is the output after the first round?
- How many output bit after the first round have actually changed compared to the case when the plaintext is all zero? (Observe that we only consider a single round here. There will be more and more output differences after every new round. Hence the term avalanche effect.)

### Solution

*This solution is verified as correct by the official Solutions for Odd-Numbered Questions manual.*

1. Where is the plaintext, maps bit 57 to bit 33. This means that and .

When calculating we can, as in Ex3.3, discount the 0 key (since ).

maps bit 1 to bit 2 and 48.

This means that all take 0 as input. now takes as input, and takes .

2. As per the design criteria, the minimum number of output bits that will be changed (per S-box) as a result of a 1 bit change in input is 2.

3. The output of the S-boxes is as follows:

This is then permuted by to produce the following:

This value is then XORed with to produce but this step can be skipped because we know that is 0.

As such, the computed values of and are:

4. We now compare the binary output of with that produced during Ex 3.3:

We can see clearly that 5 output bits of are now different, caused by a change of one input bit.

Remember that is simply wired through unchanged. It therefore also reflects the single changed input bit of .

This means that the total number of output bits changed after one round is 6, since would be 0 otherwise.