[Resource Topic] 2005/448: On the (In)security of Stream Ciphers Based on Arrays and Modular Addition (Full Version)

Welcome to the resource topic for 2005/448

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

Authors: Souradyuti Paul, Bart Preneel


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

ePrint: https://eprint.iacr.org/2005/448

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .