International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: On the (In)security of Stream Ciphers Based on Arrays and Modular Addition (Full Version)

Souradyuti Paul
Bart Preneel
Search ePrint
Search Google
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 \emph{et al.}), IA, ISAAC (1996, Jenkins Jr.), NGG, GGHN (2005, Gong \emph{et al.}) with data complexities $2^{68.61}$, $2^{32.89}$, $2^{16.89}$, $2^{32.89}$ and $2^{32.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.
  title={On the (In)security of Stream Ciphers Based on Arrays and Modular Addition (Full Version)},
  booktitle={IACR Eprint archive},
  keywords={Array, Modular Addition, Symmetric Cryptology},
  note={A shorter version of the paper will be published in the proceedings of Asiacrypt 2006 13423 received 7 Dec 2005, last revised 2 Oct 2006},
  author={Souradyuti Paul and Bart Preneel},