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 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,

proof of the fact that the satisfiability of an arbitrary set of DEA is in the complexity class P,
deriving all the solutions of an arbitrary set of DEA.

Next, we apply these results to attack a practical stream cipher named Helix (designed by Ferguson 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 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 fortuitous states attacks on the RC4 cipher by Fluhrer and McGrew in 2000.

Full paper: post-script and pdf.

Presentation: Power point.

Post-publication Note: None.

Contact: Find the email here.

Copyright Notice: This article is solely meant for non-commercial (mainly academic) use as it is copyrighted by the respective publisher(s). Your comments/remarks/suggestions on the paper (of any kind from typographical error to technical ambiguity) are kindly solicited and will be gratefully acknowledged.