Welcome to the resource topic for 2004/294
Title:
Solving Systems of Differential Equations of Addition and Cryptanalysis of the Helix Cipher
Authors: Souradyuti Paul, Bart Preneel
Abstract:Mixing addition modulo 2^n (+) and exclusive-or has a host of applications
in symmetric cryptography as the operations are fast and nonlinear over GF(2). We deal with
a frequently encountered equation (x+y)XOR((x XOR a)+(y XOR b))=c$. The difficulty
of solving an arbitrary system of such equations – named differential equations of
addition (DEA) – is an important consideration in the evaluation of the security of many
ciphers against differential attacks. This paper shows that the satisfiability of an
arbitrary set of DEA – which has so far been assumed \emph{hard} for large n – is in
the complexity class P. We also design an efficient algorithm to obtain all solutions to an
arbitrary system of DEA with running time linear in the
number of solutions.
Our second contribution is solving DEA in an adaptive query model where an equation
is formed by a query (a,b) and oracle output c. The challenge is to optimize the
number of queries to solve (x+y)XOR((x XOR a)+(y XOR b))=c. Our algorithm solves
this equation with only 3 queries in the worst case. Another algorithm solves the equation
(x+y)XOR(x+(y XOR b))=c$ with (n-t-1) queries in the worst case (t is the
position of the least significant `1’ of x), and thus, outperforms the previous best
known algorithm by Muller – presented at FSE~'04 – which required 3(n-1) queries. Most
importantly, we show that the upper bounds, for our algorithms, on the number of queries
match worst case lower bounds. This, essentially, closes further research in this direction
as our lower bounds are optimal.
We used our
results to cryptanalyze a recently proposed cipher Helix, which was a candidate
for consideration in the 802.11i standard. We are successful in reducing the data
complexity of a DC attack on the cipher by a factor of 3 in the worst case (a factor
of 46.5 in the best case).
ePrint: https://eprint.iacr.org/2004/294
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .