@InProceedings{KRS85a,
  replaced-by =  { KRS88 },                  
  author = 	 { Kaliski, Jr., Burton S. and Ronald L. Rivest and Alan T. Sherman },
  title = 	 { Is the {Data Encryption Standard} a Group? (Preliminary Abstract) },
  pages = 	 { 81--95 },
  OPTurl =       { http://dx.doi.org/10.1007/3-540-39805-8_10 },
  doi =          { 10.1007/3-540-39805-8_10 },
  booktitle =    { Advances in Cryptology---EUROCRYPT '85, Workshop on the Theory and
                   Applications of Cryptographic Techniques },
  date =         { 1986 },                  
  isbn =         { 978-3-540-16468-5 },                  
  editor = 	 { Franz Pichler },
  publisher =    { Springer },                  
  series = 	 { Lecture Notes in Computer Science },
  volume = 	 { 219 },
  OPTyear = 	 { 1985 },
  OPTmonth =     { April },                  
  eventtitle =   { EUROCRYPT '85 },                  
  eventdate =    { 1985-04 },
  venue =        { Linz, Austria },                  
  keywords =     { birthday paradox, closed cipher, cryptanalysis, cycle-detection algorithm,
                   Data Encryption Standard, finite permutation group, idempotent cryptosystem,
                   multiple encryption, pure cipher },                  
  abstract =     {
                  The Data Encryption Standard (DES) defines an indexed
                  set of permutations acting on the message space $mathcal{M} =
                  \{0,1\}^{64}$ . If this set of permutations were closed
                  under functional composition, then 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
                  We describe two statistical tests 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 test takes a pseudo-random walk
                  in the message space until a cycle is detected. For
                  each step of the pseudo-random walk, the previous
                  ciphertext is encrypted under a key chosen by a
                  pseudo-random 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, we applied
                  the cycling test to DES. Our experiments show, with
                  a high degree of confidence, that DES is not a
                  group.
                 },
}