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

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.

• Looks like a ciphertext from DES XOR with a key k1, doesn't increase the security of a cipher at all. Anyone can explain it why ? – MrJab Jun 19 at 8:19
• i don't understand the question very well. – MrJab Jun 19 at 8:27
• The equation given defines a variant of DES, with two key components. You are given a few plaintext/ciphertext pairs $(p_i,c_i)$ with $c_i=\operatorname{DESA}_{k,k_1} (p_i)$. The goal is to find $k,k_1$. You have a calculator/computer that can compute $⊕$, and also $\operatorname{DES}_k(x)$ if given $k$ and $x$. Hint: How would you confirm/infirm a guess of $k$, with no clue given on $k_1$? – fgrieu Jun 19 at 8:35
• Hint: It is critical to note here that you have more than one plaintext-ciphertext pair. – SEJPM Jun 19 at 10:01
• Actually, it was solved with the hints. Apply brute force and for every key encrypt the two plaintexts and x-or the output... – kelalaka Jun 19 at 12:29

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.

• Thank you , i will check it. – MrJab Jun 19 at 13:00
• You may want to note that DES keys only have 56 and 128 bit effective length and that DES blocks are also only 64-bit. – SEJPM Jun 19 at 13:48
• thanks and fixed – TTZ Jun 19 at 15:28