Abstract
The security of cellular automata for stream cipher applications is investigated. A cryptanalytic algorithm is developed for a known plaintext attack where the plaintext is assumed to be known up to the unicity distance. The algorithm is shown to be successful on small computers for key sizes up to N between 300 and 500 bits. For a cellular automaton to be secure against more powerful adversaries it is concluded that the key size N needs to be about 1000 bits.
The cryptanalytic algorithm takes advantage of an equivalent description of the cryptosystem in which the keys are not equiprobable. It is shown that key search can be reduced considerably if one is contented to succeed only with a certain success probability. This is established by an information theoretic analysis of arbitrary key sources with non-uniform probability distribution.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
I. Damgård, A Design Principle for Hash Functions, Advances in Cryptology—Crypto’89, Proceedings, pp. 416–427, Springer-Verlag, 1990.
W. Diffie, The First Ten Years of Public-Key Cryptography, Proceedings of the IEEE, pp. 560–577, 1988.
P. Grassberger, Toward a Quantitative Theory of Self-Generated Complexity, International Journal of Theoretical Physics, Vol. 25, pp. 907–938, 1986.
U. Maurer, A Universal Statistical Test for Random Bit Generators, Proceedings of Crypto’90, Springer-Verlag, to appear.
C.E. Shannon, A Mathematical Theory of Communication, Bell Syst. Tech. Journal, Vol. 27, pp. 379–423, 623–656, 1948.
S. Wolfram, Origins of Randomness in Physical Systems, Physical Review Letters, Vol. 55, pp. 449–452, 1985.
S. Wolfram, Random Sequence Generation by Cellular Automata, Advances in Applied Mathematics 7, pp. 123–169, 1986.
S. Wolfram, Cryptography with Cellular Automata, Advances in Cryptology—Crypto’85, Proceedings, pp. 429–432, Springer-Verlag, 1986.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1991 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Meier, W., Staffelbach, O. (1991). Analysis of Pseudo Random Sequences Generated by Cellular Automata. In: Davies, D.W. (eds) Advances in Cryptology — EUROCRYPT ’91. EUROCRYPT 1991. Lecture Notes in Computer Science, vol 547. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46416-6_17
Download citation
DOI: https://doi.org/10.1007/3-540-46416-6_17
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-54620-7
Online ISBN: 978-3-540-46416-7
eBook Packages: Springer Book Archive