Fault Attacks against a Cellular Automata Based Stream Cipher
This paper presents fault attacks against a cellular automata based stream cipher. A fault attack assumes that the adversary is able to physically operate the cryptographic device and insert some errors into it. As a consequence, the adversary can induce faulty results into the device and use them to recover the stored secret key. By using this approach we provide extremely efficient and practical cryptanalytic methods: by injecting n/2 + n2/32 faults we recover the n-bit secret key from a stream cipher based on cellular automaton rule 30. To the best of our knowledge this is the first application of fault attacks against cellular automata based stream ciphers.
Dan Boneh, Richard A. DeMillo and Richard J. Lipton. On the Importance of Checking Cryptografic Protocols for Faults. Advances in Cryptology – EUROCRYPT 1997, Lecture Notes in Computers Science vol.1233, Springer-Verlag, pp. 37–51, May 1997.
A. Fuster-Sabater, P. Caballero-Gil and M.E. Pazo-Robles, Application of Linear Hybrid Cellular Automata to Stream Ciphers, EUROCAST 2007, Lecture Notes in Computer Science vol. 4739, pp. 564-571, 2007
Jonathan J. Hock and Adi Shamir. Faut Analysis of Stream Ciphers. CHES 2004, Lecture Notes in Computer Science vol. 3156, Springer-Verlag, pp. 240–253, 2004.
Willi Meier and Othmar Staffelbach. Analysis of Pseudo Random Sequences Generated by Cellular Automata. Advances in Cryptology – EUROCRYPT 1991, Lecture Notes in Computer Science vol. 547, Springer-Verlag, pp. 186–199, 1991.
S. Nandi, B.K. Par, P. Pal Chaudhuri. Theory and Application of Cellular Automata in Cryptography, IEEE Transactions on Computers, vol 43, Issue 12, pp.1346-1357, 1994 93
F. Seredynsky, P. Bouvry and A. Zomaya. Cellular Automata Computations and Secret Key Cryptography. Parallel Computing, Vol. 30, Issues 5-6, pp. 753-766, 2004.
M. Tomassini and M Perrenoud. Cryptography with Cellular Automata, Applied Soft Computing, vol 1, Issue 2, pp. 151-160, 2001.
S. Wolfram. Cryptography with Cellular Automata. Advances in Cryptology CRYPTO 1985, Proceedings, Springer-Verlag, pp. 429–432, 1986.
S. Wolfram. Random Sequence Generation by Cellular Automata. Advances in Applied Mathematics 7, pp. 123–169, 1986.