What is the output of the first round of the DES algorithm when the plaintext an

Question

What is the output of the first round of the DES algorithm when the plaintext and the key are both all zeroes? 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.) a. How many S-boxes get different inputs compared to the case when an all-zero plaintext is provided? b. What is the minimum number of output bits of the S-boxes that will change according to the S-box design criteria? c. What is the output after the first round? d. 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.) Assume we perform a known plaintext attack against DES with one pair of plaintext and ciphertext. How many keys do we have to test in a worst-case scenario if we apply an exhaustive key search in a straightforward way? How many on average? b. One important property which makes DES secure is that the S-boxes are nonlinear. In this problem we verify this property by computing the output of S_1 for the input pairs x_1 = 111111 and x_2 = 000001.

Explanation / Answer

2.

The 64-bit input is x0=00...0 (64-zeroes). The initial permutation has no effect. Hence L0=00...0 (32-zeroes) and R0=00...0 (32-zeroes). Applying the key schedule which is a fixed permutation on the input bits of the key yields the round key K1= (00..0) (48-zeroes).

The round computes R1=L0 XOR f(R0, K1)

The f-function

(a)First expands R0 into 48-bit long bitstring usinga fixed permuted expansion rule. Since only permutations and repetitions are used this will yield a 48-bit 0 string.

(b)The result is XORed with K1, which produces a 48-bit zero string.

(c)The 48-bit 0 string is divided into eight 6-bit chunks and the ith chunk is transformed under the rule specified in the Si box. 000000 is mapped 8 times with boxes Si i=1,..,8 and produces the following sequence of 4-bit values: 14, 15, 10, 7, 2, 12, 4, 13.
In binary we obtain the following sequence: 1110 1111 1010 0111 0010 1100 0100 1101

(d)Finally the bit-string is permuted according to the P table to the following:
1101 1000 1101 1000 1101 1011 1011 1100
This is the result of f(R0),K1) The right half R1=L0XOR f(R0),K1) is simply the output of f(R0),K1) since the L0is zero. L1= R0= (00..0) (32-zeroes).

Concatenating both yields the following 64-bit string, which is the output of round 1.

0000 0000 0000 0000 0000 0000 0000 0000 1101 1000 1101 1000 1101 1011 1011 1100

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.