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
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.
Metadata
- Available format(s)
-
PDF PS
- Publication info
- Published elsewhere. A shorter version of the paper will be published in the proceedings of Asiacrypt 2006
- Keywords
- ArrayModular AdditionSymmetric Cryptology
- Contact author(s)
- Souradyuti Paul @ esat kuleuven be
- History
- 2008-04-01: last of 9 revisions
- 2005-12-08: received
- See all versions
- Short URL
- https://ia.cr/2005/448
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2005/448, author = {Souradyuti Paul and Bart Preneel}, title = {On the (In)security of Stream Ciphers Based on Arrays and Modular Addition (Full Version)}, howpublished = {Cryptology {ePrint} Archive, Paper 2005/448}, year = {2005}, url = {https://eprint.iacr.org/2005/448} }