Is the data encryption standard a group? (Results of cycling experiments on DES) (Q1112006)

DES defines an indexed set of permutations acting on the message space \(m=\{0,1\}^{64}\). There are \(M=2^{64}\) messages and \(K=2^{56}\) keys. In this paper two statistical tests are presented to determine whether (in whole generality) an indexed set of permutations acting on a finite message space forms a group under functional composition. If the set of permutations according to DES would be a group, or would satisfy some other algebraic closure properties, two well known methods to strengthen DES via multiple encryption would be equivalent to single encryption. As an even more drastic consequence of this assumption, DES would be vulnerable to a known-plaintext attack running in \(2^{28}\) steps (on the average). Several experiments with the tests confirm the a priori belief with high confidence, that DES doesn't form a group. The first test is a ``meet-in- the-middle'' algorithm based on the Birthday Paradox, and uses 0(\(\sqrt{K})\) time and space, where K is the size of the key space. The second test represents a new cycling algorithm that uses 0(\(\sqrt{K})\) time, but only a small constant amount of space. The tests yield known- plaintext attacks on any finite, deterministic cryptosystem that generates a small group, without using specific structural properties of the underlying set of permutations. The results are discussed in detail and a list of open questions about the algebraic structure of DES is included.