Cryptanalysis of Stream Ciphers Based on Arrays and Modular Addition
Publication Info: PhD thesis, ISBN 978-90-5682-754-0, Katholieke Universiteit Leuven, B. Preneel (advisor), 145+22 pages, 2006.
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.
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.