# Can you explain “weak keys” for DES?

A weak key for DES is a key $K$ such that $DES_{k_1}(DES_{k_2}(x))=x$ for all $x$.

I don't get why are the 4 keys $k_1||k_2$: $1^{112}$, $0^{112}$, $0^{56}||1^{56}$, $1^{56}||0^{56}$ considered as weak. (Also didn't find some detailed explanation in the web.)

-

Did you try Wikipedia?

DES consists of 16 rounds of the form:

$$L_{i+1} = R_{i}, \quad R_{i+1} = L_i \oplus F(R_i, K_i),$$

which are identical except for the round subkeys $K_i$. (The last round is slightly different, in that the half-blocks $L$ and $R$ are not swapped as they are after all other rounds, but that makes no cryptanalytic difference.)

The subkeys $K_i$ are derived from the encryption key $K$ using the DES key schedule, which takes the form:

$$K_L \,\|\, K_R = P_1(K)$$ $$K_i = P_2(K_L \lll n_i, K_R \lll n_i)$$

where $K_L$ and $K_R$ are the left and right halves of the permuted key $P_1(K)$, the functions $P_1$ and $P_2$ are fixed maps that basically just shuffle the bits around, and $\lll n_i$ denotes bit rotation by the fixed number of positions $n_i$, where

$$(n_0, n_1, \dotsc, n_{15}) = (1, 2, 4, 6, 8, 10, 12, 14, 15, 17, 19, 21, 23, 25, 27, 28).$$

The important thing to note here is that, if $K_L$ and $K_R$ each consist of all zero or all one bits, then rotating them has no effect, and so all the subkeys $K_i$ will be equal, which in turn implies that all 16 rounds of DES encryption using these keys will be identical. Since there are two choices (all ones or all zeros) for each of $K_L$ and $K_R$, this gives us a total of four weak keys.

In particular, because DES is a Feistel cipher, and therefore each DES round is its own inverse (except for the swapping of the half-blocks), the fact that all the rounds are identical also makes the full DES function self-inverse: that is, for weak keys, DES encryption is the same as decryption.

Ps. DES also has six pairs of "semi-weak keys", for which encryption with one of the keys in the pair is equivalent to decryption with the other (and vice versa). Basically, these are the keys for which the bit patterns of $K_L$ and $K_R$ repeat with a period of 2, i.e. $$K_L, K_R \in \{000000{\dotsc}00,\, 010101{\dotsc}01,\, 101010{\dotsc}10,\, 111111{\dotsc}11\}$$ (excluding the four weak keys described above). Because the bit patters have repeat with period 2, the round subkeys $K_i$ for these keys can only take two possible values, depending on whether the rotation constant $n_i$ is odd or even.

In particular, reversing the bits of each of $K_L$ and $K_R$ (or, equivalently, rotating them by one bit) for any of these semi-weak keys gives another "complementary" semi-weak key that generates the same two round subkeys, but switched around. If you look at the DES rotation constants listed above, you'll notice that $n_i$ is odd if and only if $n_{16-i}$ is even, and thus this swapping of the round subkeys is equivalent to reversing the key schedule. Since DES decryption is the same as encryption with the key schedule reversed, this means that encryption using a semi-weak key is equivalent to decryption using its complementary pair.

There are also 48 "possibly weak keys" for which the bit patterns of $K_L$ and $K_R$ have a period of 4, and which thus generate only four distinct round subkeys. These keys don't have such obvious encryption/decryption symmetry properties as the weak and semi-weak keys, but they nonetheless produce a much simpler key schedule than usual, which might conceivably be exploited somehow.

Of course, in practice, all these types of weak keys are pretty much irrelevant: if your keys are chosen randomly (or by a good KDF), the chance of picking a weak (or semi-weak or possibly weak) key is negligibly small ($1/2^{50}$). And if you did suspect that a system was, for some reason, more likely to use weak keys than one would expect by chance, a much more efficient way to exploit this knowledge would be to just test all these 64 keys and see if any of them indeed happened to be the correct one. Not to mention that any (single) DES key is "weak" nowadays, simply because the 56-bit keyspace is too small to resist brute force attacks (although triple DES, which doubles the keyspace, does also have the same kind of weak keys as single DES).

-
I saw that wikipedia page but it didn't explained as you did :) –  Bush Dec 9 '13 at 0:02