2005 | OriginalPaper | Chapter
Near Optimal Algorithms for Solving Differential Equations of Addition with Batch Queries
Authors : Souradyuti Paul, Bart Preneel
Published in: Progress in Cryptology - INDOCRYPT 2005
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Combination of
modular addition
(+) and
exclusive-or
(⊕) is one of the widely used symmetric cipher components. The paper investigates the strength of
modular addition
against
differential cryptanalysis
(DC) where the differences of inputs and outputs are expressed as
XOR
. In particular, we solve two very frequently used equations (1)
and
(2) , known as the
differential equations of addition
(DEA), with a set of
batch
queries. In a companion paper, presented at ACISP’05, we improved the algorithm by Muller (at FSE’04) to design optimal algorithms to solve the equations with
adaptive
queries. However, a
nontrivial
solution with
batch
queries has remained open. The major contributions of this paper are (
i
) determination of lower bounds on the required number of
batch
queries to solve the equations and (
ii
) design of two algorithms which solve them with queries close to optimal. Our algorithms require 2
n
− − 2
and 6 queries to solve (1) and (2) where the lower bounds are (theoretically proved) and 4 (based on extensive experiments) respectively (
n
is the bit-length of
x
,
y
,
α
,
β
,
γ
). This exponential lower bound is an important theoretical benchmark which certifies (1) as
strong
against DC. On the other hand, the constant number of batch queries to solve (2) discovers a major weakness of
modular addition
against DC.
Muller, at FSE’04, showed a key recovery attack on the Helix stream cipher (presented at FSE’03) with 2
12
adaptive chosen plaintexts
(ACP). At ACISP 2005, we improved the data complexity of the attack to 2
10.41
. However, the complexity of the attack with
chosen plaintexts
(CP) was unknown. Using our results we recover the secret key of the Helix cipher with only 2
35.64
chosen plaintexts
(CP) which has so far been the only CP attack on this cipher (under the same assumption as that of Muller’s attack). Considering the abundant use of this component, the results seem useful to evaluate the security of many block ciphers against DC.