Is the data encryption standard a group? (Results of cycling experiments on DES)
type: Item
instance of: scholarly article
title: Is the data encryption standard a group? (Results of cycling experiments on DES)
zbMATH Open document ID: 0658.94008
DOI: 10.1007/BF00206323
author: Burton S. jun. Kaliski
author: Ronald L. Rivest
author: Alan T. Sherman
published in: Journal of Cryptology
publication date: 1988-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 94A60
zbMATH DE Number: 4077117
zbMATH Keywords: data encryption standard
zbMATH Keywords: finite permutation group
zbMATH Keywords: pure cipher
zbMATH Keywords: closed cipher
zbMATH Keywords: statistical tests
zbMATH Keywords: Birthday Paradox
reviewed by: Willi Meier
MaRDI profile type: Publication
Wikidata QID: Q56388146
cites work: Q3968873
cites work: An Approximate Probability Distribution for the order of Elements of the Symmetric Group
cites work: The Probability of Generating the Symmetric Group
cites work: Q3240862
cites work: Generators for Certain Alternating Groups with Applications to Cryptography
cites work: The probability of generating the symmetric group
cites work: Q5538132
cites work: DES-like functions can generate the alternating group
cites work: Q5555372
cites work: Probability Distributions Related to Random Mappings
cites work: A cryptanalytic time-memory trade-off
cites work: Is the Data Encryption Standard a Group? (Preliminary Abstract)
cites work: Q3935355
cites work: Q4057549
cites work: Q3728067
cites work: Secure digital communications
cites work: Q3710461
cites work: Q3773821
cites work: Information, weight of evidence, the singularity between probability measures and signal detection
cites work: A monte carlo method for factorization
cites work: Q4745878
cites work: Cycle Length in a Random Function
cites work: A method for obtaining digital signatures and public-key cryptosystems
cites work: Communication Theory of Secrecy Systems*
cites work: The Complexity of Finding Cycles in Periodic Functions
cites work: Ordered Cycle Lengths in a Random Permutation
cites work: Q5512231
cites work: Advances in cryptology. Proceedings of CRYPTO '84 (a workshop on the theory and application of cryptographic techniques held at the University of California, Santa Barbara, August 19--22, 1984)
cites work: Advances in cryptology - CRYPTO '86. Proceedings. (A Conference on the Theory and Applications of Cryptographic Techniques held at the University of California, Santa Barbara, August 11-15, 1986)
cites work: Q3873397
full work available at URL: https://doi.org/10.1007/bf00206323
OpenAlex ID: W2030209085
DBLP publication ID: journals/joc/KaliskiRS88
description: scientific article; zbMATH DE number 4077117