# How can semi-weak DES keys be leveraged to attack DES?

I see how DES weak keys can be leveraged under chosen plaintext attack where an adversary feeds the ciphertext encrypted by a weak-key back to the DES encryption function and gets plaintext as a result.

The probability that both keys from the semi-weak key pair are used seems to be very small ($6/2^{56} \times 1/2^{56} \approx 1/2^{110}$) making chosen ciphertext attack significantly slower as compared to exhaustive key search ($1/2^{56}$). If this logic is correct, then how can one leverage semi-weak keys to attack DES?

## 1 Answer

The answer is that they cannot. DES weak keys will be chosen with such a small probability that they don't matter at all. The only reason that weak keys are of interest is when you want to use a block cipher as an "ideal cipher" like in order to construct a collision resistant hash function. These sort of constructions break completely when a cipher has weak keys. But, this is not a criticism of DES or other block ciphers; they are made to be pseudorandom permutations and are not made to be hash functions. Rather, in my personal opinion, this is a criticism of people who try to use primitives designed for one purpose for something completely different.

• Further, the question asks about semi-weak keys, which are keys pairs $(K_1,K_2)$ such that $K_1\ne K_2\text{ and }\forall m, E_{K_1}(E_{K_2}(m))=E_{K_2}(E_{K_1}(m))$; it is even more difficult to exhibit a situation where that is a problem than it is for weak keys, such that $\forall m, E_{K_1}(E_{K_1}(m))=m$. – fgrieu Mar 6 '17 at 9:08
• @fgrieu Agreed, but the same issue; the chances of them ever being chosen is so small that it just doesn't matter. – Yehuda Lindell Mar 7 '17 at 8:02