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.
Category / Keywords: secret-key cryptography / Publication Info: Ph.D. thesis, Katholieke Universiteit Leuven, B. Preneel (supervisor), 145+xxiv pages, November 2006. Date: received 15 Feb 2007, last revised 24 Nov 2011 Contact author: Souradyuti Paul at esat kuleuven be Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Note: The attack on ISAAC, as claimed in the thesis, relies on a wrong interpretation of the original ISAAC algorithm with respect to the programming language C. This was pointed out by Jean Philippe Aumasson in this database in the Report 2006/438 which also claims to reveal weaknesses on the original ISAAC. The reason for this confusion has been explained in the Asiacrypt 2006 presentation the slides of which can found via author's homepage. Version: 20111124:170123 (All versions of this report) Short URL: ia.cr/2007/054 Discussion forum: Show discussion | Start new discussion