Attack against $\operatorname{DESA}_{k,k_1} (x) \underset{\text{def}}= \operatorname{DES}_k(x)⊕k_1$

Question

Problem 5.16 in this pdf, from the book: Christof Paar, Jan Pelzl, Understanding Cryptography

5.16. This is your chance to break a cryptosystem. As we know by now, cryptography is a tricky business. The following problem illustrates how easy it is to turn a strong scheme into a weak one with minor modifications. We saw in this chapter that key whitening is a good technique for strengthening block ciphers against brute-force attacks. We now look at the following variant of key whitening against DES, which we’ll call DESA: $$\operatorname{DESA}_{k,k_1} (x) \underset{\text{def}}= \operatorname{DES}_k(x)⊕k_1$$ Even though the method looks similar to key whitening, it hardly adds to the security. Your task is to show that breaking the scheme is roughly as difficult as a brute-force attack against single DES. Assume you have a few pairs of plaintext– ciphertext.

Answer 1

Normal DES

Let's say you have a normal DES plaintext-ciphertext pair encrypted with 56 bits key $k$ where $C_1=DES_k(P_1)$. In the worst case, one needs to try the $2^{56}$ possible keys to find the encryption key. And later on, one can decrypt all Ciphertext encrypted with the key $k$

DESA

Let's say one has 2 pairs of plaintext-ciphertext pairs ecnrypted with $k$ (the usual 56 bits key size) and $k_1$ (64 bits since the block size) where $C_2=DESA_{k,k_1}(P_2)$ and $C_3=DESA_{k,k_1}(P_3)$ So one can x-or given two ciphertext and:

$C_2\oplus C_3 = DESA_{k,k_1}(P_2)\oplus DESA_{k,k_1}(P_3)= DES_k(P_2)\oplus k_1\oplus DES_k(P_3)\oplus k_1=DES_k(P_2)\oplus DES_k(P_3)$

So, $k_1$ is gone. In the worst case, one tries $2^{56}$ times and get $k$ with two plaintext-ciphertext pair.

Then, for any ciphertext with the help of previous equation one can calculate the $k_1$

$$C_1 = DES_k(P_1)\oplus k_1$$

knowing the key $k$ one can calculate $k_1$.

So in total $2^{57}+1$ DES encryption is called, instead of $2^{56+64}$ key size.