# 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

Remember that the initial value is split into two halves, and each half is shifted independently. If all the bits in each half are either 0 or 1, then the key used for any cycle of the algorithm is the same for all the cycles of the algorithm. This can occur if the key is entirely 1s, entirely 0s, or if one half of the key is entirely 1s or the other half is entirely 0s.

Also, remember that every 8th bit is not used in DES key schedule.

There are four weak keys of this type.

Weak key Value (with parity bits)

0101 0101 0101 0101
1F1F 1F1F 0E0E 0E0E
E0E0 E0E0 F1F1 F1F1
FEFE FEFE FEFE FEFE


Actual Keys (Note that every 8th bit is removed)

0000000 0000000
0000000 FFFFFFF
FFFFFFF 0000000
FFFFFFF FFFFFFF


Another types of keys called semiweak keys are one which repeat with a period of two. Due to the way in which DES generates subkeys; instead of generating 16 different subkeys, these keys generate only two different subkeys. Each of these subkeys is used eight times in the algorithm.

There are six pairs of this type of keys.

DES Semiweak Key Pairs

01FE 01FE 01FE 01FE and FE01 FE01 FE01 FE01
1FE0 1FE0 0EF1 0EF1 and E01F E01F F10E F10E
01E0 01E0 01F1 01F1 and E001 E001 F101 F101
1FFE 1FFE 0EFE 0EFE and FE1F FE1F FE0E FE0E
011F 011F 010E 010E and 1F01 1F01 0E01 0E01
E0FE E0FE F1FE F1FE and FEE0 FEE0 FEF1 FEF1


The third type of keys which repeat after a period of four. They produce four subkeys, each used four times in the algorithm (total 16). These are called possibly weak keys.

There are 48 keys of this type.

DES Possibly Weak Keys

1F 1F 01 01 0E 0E 01 01
E0 01 01 E0 F1 01 01 F1
01 1F 1F 01 01 0E 0E 01
FE 1F 01 E0 FE 0E 01 F1
1F 01 01 1F 0E 01 01 0E
FE 01 1F E0 FE 01 0E F1
01 01 1F 1F 01 01 0E 0E
E0 1F 1F E0 F1 0E 0E F1
E0 E0 01 01 F1 F1 01 01
FE 01 01 FE FE 01 01 FE
FE FE 01 01 FE FE 01 01
E0 1F 01 FE F1 0E 01 FE
FE E0 1F 01 FE F1 0E 01
E0 01 1F FE F1 01 0E FE
E0 FE 1F 01 F1 FE 0E 01
FE 1F 1F FE FE 0E 0E FE
FE E0 01 1F FE F1 01 0E
1F FE 01 E0 0E FE 01 F1
E0 FE 01 1F F1 FE 01 0E
01 FE 1F E0 01 FE 0E F1
E0 E0 1F 1F F1 F1 0E 0E
1F E0 01 FE 0E F1 01 FE
FE FE 1F 1F FE FE 0E 0E
01 E0 1F FE 01 F1 0E FE
FE 1F E0 01 FE 0E F1 01
01 01 E0 E0 01 01 F1 F1
E0 1F FE 01 F1 0E FE 01
1F 1F E0 E0 0E 0E F1 F1
FE 01 E0 1F FE 01 F1 0E
1F 01 FE E0 0E 01 FE F1
E0 01 FE 1F F1 01 FE 0E
01 1F FE E0 01 0E FE F1
01 E0 E0 01 01 F1 F1 01
1F 01 E0 FE 0E 01 F1 FE
1F FE E0 01 0E FE F0 01
01 1F E0 FE 01 0E F1 FE
1F E0 FE 01 0E F1 FE 01
01 01 FE FE 01 01 FE FE
01 FE FE 01 01 FE FE 01
1F 1F FE FE 0E 0E FE FE
1F E0 E0 1F 0E F1 F1 0E
FE FE E0 E0 FE FE F1 F1
01 FE E0 1F 01 FE F1 0E
E0 FE FE E0 F1 FE FE F1
01 E0 FE 1F 01 F1 FE 0E
FE E0 E0 FE FE F1 F1 FE
1F FE FE 1F 0E FE FE 0E
E0 E0 FE FE F1 F1 FE FE


Before condemning DES for having weak keys, consider that this list of 64 keys is minuscule compared to the total set of 72,057,594,037,927,936 possible keys.

If you select a random key, the odds of picking one of these keys is negligible. If you are truly paranoid, you could always check for weak keys during key generation.

There are another type of keys called complement keys. Take the bit-wise complement of a key; that is, replace all the 0s with 1s and the 1s with 0s. Now, if the original key encrypts a block of plaintext, then the complement of the key will encrypt the complement of the plaintext block into the complement of the ciphertext block.

if x' is the complement of x, then the identity is as follows:

E(K, P) = C

E(K', P') = C'

This isn't anything mysterious. The subkeys are XORed with the right half after the expansion permuted in every round. This complementation property is a direct result of that fact.

-