International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Cryptanalysis of Stream Ciphers Based on Arrays and Modular Addition

Souradyuti Paul
Search ePrint
Search Google
Abstract: In modern cryptography, stream ciphers are most useful in applications where information needs to be encrypted/decrypted at high speed (e.g. high resolution streaming video data) or when low footprint (gates/memory) encryption is required. In the literature, there exist plenty of stream ciphers whose internal states are based on arrays and that they use modular additions to generate output streams. The abundance of array-based stream ciphers with modular additions can be attributed to the fact that, when implemented in software skillfully, they are able to produce outputs at a very high speed. The main contribution of this thesis is a unified analysis of stream ciphers based on arrays and modular addition. During the process, we detect cryptographic weaknesses in the designs of 9 widely known stream ciphers or pseudorandom bit generators (PRBGs). At first, we show some theoretical results on solving an important class of equations known as \emph{differential equations of addition} (DEA) that combine modular additions over two different algebraic groups such as GF(2) and GF($2^{32}$). The results include, \bite \item proof of the fact that the satisfiability of an arbitrary set of DEA is in the complexity class \pP,\item deriving all the solutions of an arbitrary set of DEA. \eite Next, we apply these results to attack a practical stream cipher named Helix (designed by Ferguson \emph{et al.}) with both chosen plaintexts and adaptive chosen plaintexts. In the second phase, the thesis closely scrutinizes a number of array-based stream ciphers (or PRBGs) in order to estimate their resistance against distinguishing attacks. We eventually discover, counter-intuitively, that the correlations between the array-indices and their associated array-elements, which apparently seem to be useful from the point of view of implementation purposes, can be exploited to mount distinguishing attacks on such type of ciphers if adequate precautions are not taken. In support of our theoretical findings, we point out distinguishing attacks on 8 practical array-based stream ciphers (or PRBGs), namely RC4 (designed by Rivest), RC4A (designed by Paul and Preneel), Py, Py6 (designed by Biham and Seberry), IA, ISAAC (designed by Jenkins Jr.), GGHN, NGG (by Gong \emph{et al.}); our attacks are based on the dependence of array-elements on array-indices. In all the cases we work under the assumption that the key-setup algorithms of the ciphers produce uniformly distributed internal states. We detect flaws in the mixing of bits in the keystream generation algorithms. Our analysis can be explained as the extension, development, adaptation and deeper characterization of the \ti{fortuitous states attacks} on the RC4 cipher by Fluhrer and McGrew in 2000.
  title={Cryptanalysis of Stream Ciphers Based on Arrays and Modular Addition},
  booktitle={IACR Eprint archive},
  keywords={secret-key cryptography /},
  note={Ph.D. thesis, Katholieke Universiteit Leuven, B. Preneel (supervisor), 145+xxiv pages, November 2006. 13560 received 15 Feb 2007, last revised 15 Feb 2007},
  author={Souradyuti Paul},