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.

  • $\begingroup$ 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 ? $\endgroup$ – MrJab Jun 19 at 8:19
  • $\begingroup$ i don't understand the question very well. $\endgroup$ – MrJab Jun 19 at 8:27
  • 1
    $\begingroup$ 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$? $\endgroup$ – fgrieu Jun 19 at 8:35
  • 1
    $\begingroup$ Hint: It is critical to note here that you have more than one plaintext-ciphertext pair. $\endgroup$ – SEJPM Jun 19 at 10:01
  • $\begingroup$ Actually, it was solved with the hints. Apply brute force and for every key encrypt the two plaintexts and x-or the output... $\endgroup$ – 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$


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.

| improve this answer | |
  • $\begingroup$ Thank you , i will check it. $\endgroup$ – MrJab Jun 19 at 13:00
  • 1
    $\begingroup$ 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. $\endgroup$ – SEJPM Jun 19 at 13:48
  • $\begingroup$ thanks and fixed $\endgroup$ – TTZ Jun 19 at 15:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.