Paper 2005/448

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

Souradyuti Paul and Bart Preneel

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.

Note: In this updated version, we point out that the attack on Py6 also applies as-is to its strengthened variant TPy6. On a similar note, it is to be noted that our attack on Py as presented at FSE 2006, also applies as-is to its strengthened variant TPy.