Global Sales Contact List

Contact   A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

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

Notes:
Connect with EMCConnect with EMC
Need help immediately? EMC Sales Specialists are standing by to answer your questions real time.
Use Live Chat for fast, direct access to EMC Customer Service Professionals to resolve your support questions.
Explore and compare EMC products in the EMC Store, and get a price quote from EMC or an EMC partner.
We're here to help. Send us your sales inquiry and an EMC Sales Specialist will get back to you within one business day.
Want to talk? Call us to speak with an EMC Sales Specialist live.