RSA Laboratories

3.2.5 Is DES a group?

T he question here is whether, for two arbitrary keys k1 and k2, there is always a third key k such that

Ek(m) = Ek1(Ek2(m))

for all messages m. If this were the case, the set of all keys would form an abstract group, where the composition law on k1and k2 yields k. This would be very harmful to the security of DES, as it would enable a meet-in-the-middle attack whereby a DES key could be found in about 228 operations, rather than the usual 256 operations (see [KRS88]). It would also render multiple DES encryption useless, since encrypting twice with two different keys would be the same as encrypting once with a third key. However, DES is not a group. This issue, while strongly supported by initial evidence, was finally settled in 1993 [CW93]. The result seems to imply that techniques such as triple encryption (see Question 3.2.6) do in fact increase the security of DES.

Formally, the problem can be formulated as follows; see Appendix A for mathematical concepts. Let M denote the set of all possible messages and let K denote the set of all possible keys. Encryption with a key k Î K is performed using the permutation Ek : M ® M. The set EK = of such permutations is a subset of the group SM of all permutations M ® M. The fact that EK (that is, DES) is not a group is just the fact that EK generates a subgroup of SM that is larger than the set EK. In fact, the size of this subgroup is at least 28300 [CW93]. In particular, multiple encryption gives a larger key space.

Top of the page