@Article{KRS88, author = { Kaliski, Jr., Burton S. and Ronald L. Rivest and Alan T. Sherman }, title = { Is the {Data Encryption Standard} a Group? ({R}esults of cycling experiments on {DES}) }, journal = { Journal of Cryptology }, publisher = { Springer }, issn = { 0933-2790 }, OPTyear = { 1988 }, OPTmonth = { January }, date = { 1988-01 }, volume = { 1 }, number = { 1 }, pages = { 3--36 }, doi = { 10.1007/BF00206323 }, keywords = { birthday parado, closed cipher, cryptanalysis, cryptology, cryptography, cycle-detection algorithm, Data Encryption Standard (DES), finite permutation group, idempotent cryptosystem, multiple encryption, pure cipher, weak keys }, abstract = { The Data Encryption Standard (DES) defines an indexed set of permutations acting on the message space $M = \left{0,1\right}^{64}$. If this set of permutations were closed under functional composition, then the two most popular proposals for strengthening DES through multiple encryption would be equivalent to single encryption. Moreover, DES would be vulnerable to a known-plaintext attack that runs in $2^{28}$ steps on the average. It is unknown in the open literature whether or not DES has this weakness. \par Two statistical tests are presented for determining if an indexed set of permutations acting on a finite message space forms a group under functional composition. The first test is a ``meet-in-the-middle'' algorithm which uses $O(\sqrt(K))$ time and space, where $K$ is the size of the key space. The second test, a novel cycling algorithm, uses the same amount of time but only a small constant amount of space. Each test yields a known-plaintext attack against any finite, deterministic cryptosystem that generates a small group. \par The cycling closure test takes a pseudorandom walk in the message space until a cycle is detected. For each step of thie pseudorandom walk, the previous ciphertext is encrypted under a ky chosen by a pseudorandom function of the previous ciphertext. Results of the test are asymmetrical: long cycles are overwhelming evidence that the set of permutations is not a group; short cycles are strong evidence that the set of permutations has a structure different from that expected from a set of randomly chosen permutations. \par Using a combination of software and special-purpose hardware, the cycling closure test was applied to DES. Experiments show, with overwhelming confidence, that DES is not a group. Additional tests confirm that DES is free of certain other gross algebraic weaknesses. But one experiment discovered fixed points of the so-called ``weak-key'' transformations, thereby revealing a previously unbpublished additional weakness of weak keys. }, }