@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.
},
}