Abstract
Stream ciphers play an important role in symmetric cryptology because of their suitability in high speed applications where block ciphers fall short. A large number of fast stream ciphers or pseudorandom bit generators (PRBG’s) can be found in the literature that are based on arrays and simple operations such as modular additions, rotations and memory accesses (e.g. RC4, RC4A, Py, Py6, ISAAC etc.). This paper investigates the security of array-based stream ciphers (or PRBG’s) against certain types of distinguishing attacks in a unified way. We argue, counter-intuitively, that the most useful characteristic of an array, namely, the association of array-elements with unique indices, may turn out to be the origins of distinguishing attacks if adequate caution is not maintained. In short, an adversary may attack a cipher simply exploiting the dependence of array-elements on the corresponding indices. Most importantly, the weaknesses are not eliminated even if the indices and the array-elements are made to follow uniform distributions separately. Exploiting these weaknesses we build distinguishing attacks with reasonable advantage on five recent stream ciphers (or PRBG’s), namely, Py6 (2005, Biham et al.), IA, ISAAC (1996, Jenkins Jr.), NGG, GGHN (2005, Gong et al.) with data complexities 268.61, 232.89, 216.89, 232.89 and 232.89 respectively. In all the cases we worked under the assumption that the key-setup algorithms of the ciphers produced uniformly distributed internal states. We only investigated the mixing of bits in the keystream generation algorithms. In hindsight, we also observe that the previous attacks on the other array-based stream ciphers (e.g. Py, etc.), can also be explained in the general framework developed in this paper. We hope that our analyses will be useful in the evaluation of the security of stream ciphers based on arrays and modular addition.
This work was supported in part by the Concerted Research Action (GOA) Ambiorix 2005/11 of the Flemish Government and in part by the European Commission through the IST Programme under Contract IST-2002-507932 ECRYPT.
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
Baignères, T., Junod, P., Vaudenay, S.: How Far Can We Go Beyond Linear Cryptanalysis? In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS, vol. 3329, pp. 432–450. Springer, Heidelberg (2004)
Biham, E., Seberry, J.: Py (Roo): A Fast and Secure Stream Cipher using Rolling Arrays. eSTREAM, ECRYPT Stream Cipher Project, Report 2005/023 (2005)
Biham, E., Seberry, J.: Pypy: Another Version of Py. eSTREAM, ECRYPT Stream Cipher Project, Report 2006/038 (2006)
Biham, E., Seberry, J.: C Code of Py6, eSTREAM, ECRYPT Stream Cipher Project (2005), available from: http://www.ecrypt.eu.org/stream/py.html
Crowley, P.: Improved Cryptanalysis of Py. In: Workshop Record of SASC 2006 – Stream Ciphers Revisited, ECRYPT Network of Excellence in Cryptology, Leuven, Belgium, February 2006, pp. 52–60 (2006)
Ecrypt, http://www.ecrypt.eu.org
Fluhrer, S.R., McGrew, D.A.: Statistical Analysis of the Alleged RC4 Keystream Generator. In: Schneier, B. (ed.) FSE 2000. LNCS, vol. 1978, pp. 19–30. Springer, Heidelberg (2001)
Gong, G., Gupta, K.C., Hell, M., Nawaz, Y.: Towards a General RC4-Like Keystream Generator. In: Feng, D., Lin, D., Yung, M. (eds.) CISC 2005. LNCS, vol. 3822, pp. 162–174. Springer, Heidelberg (2005)
Halevi, S., Coppersmith, D., Jutla, C.S.: Scream: A Software-Efficient Stream Cipher. In: Daemen, J., Rijmen, V. (eds.) FSE 2002. LNCS, vol. 2365, pp. 195–209. Springer, Heidelberg (2002)
Robert, J., Jenkins Jr., R.J.: ISAAC. In: Gollmann, D. (ed.) FSE 1996. LNCS, vol. 1039, pp. 41–49. Springer, Heidelberg (1996)
Mantin, I., Shamir, A.: A Practical Attack on Broadcast RC4. In: Matsui, M. (ed.) FSE 2001. LNCS, vol. 2355, pp. 152–164. Springer, Heidelberg (2002)
Nawaz, Y., Gupta, K.C., Gong, G.: A 32-bit RC4-like Keystream Generator. Cryptology ePrint Archive, 2005/175 (2005)
NESSIE: New European Schemes for Signature, Integrity and Encryption, http://www.cryptonessie.org
Paul, S., Preneel, B.: A New Weakness in the RC4 Keystream Generator and an Approach to Improve the Security of the Cipher. In: Roy, B., Meier, W. (eds.) FSE 2004. LNCS, vol. 3017, pp. 245–259. Springer, Heidelberg (2004)
Paul, S., Preneel, B., Sekar, G.: Distinguishing Attacks on the Stream Cipher Py. In: Robshaw, M.J.B. (ed.) FSE 2006. LNCS, vol. 4047, pp. 405–421. Springer, Heidelberg (2006)
Paul, S., Preneel, B.: On the (In)security of Stream Ciphers Based on Arrays and Modular Addition (Full Version), Cryptology ePrint Archive: Report 2005/448, IACR (2005), Available online at: http://eprint.iacr.org/2005/448
Pudovkina, M.: A known plaintext attack on the ISAAC keystream generator, Cryptology ePrint Archive: Report 2001/049, IACR (2001)
Wu, H.: A New Stream Cipher HC-256. In: Roy, B., Meier, W. (eds.) FSE 2004. LNCS, vol. 3017, pp. 226–244. Springer, Heidelberg (2004)
Wu, H.: Cryptanalysis of a 32-bit RC4-like Stream Cipher. Cryptology ePrint Archive 2005/219 (2005)
Zoltak, B.: VMPC One-Way Function and Stream Cipher. In: Roy, B., Meier, W. (eds.) FSE 2004. LNCS, vol. 3017, pp. 210–225. Springer, Heidelberg (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Paul, S., Preneel, B. (2006). On the (In)security of Stream Ciphers Based on Arrays and Modular Addition. In: Lai, X., Chen, K. (eds) Advances in Cryptology – ASIACRYPT 2006. ASIACRYPT 2006. Lecture Notes in Computer Science, vol 4284. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11935230_5
Download citation
DOI: https://doi.org/10.1007/11935230_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-49475-1
Online ISBN: 978-3-540-49476-8
eBook Packages: Computer ScienceComputer Science (R0)