Chinese Journal of Electronics
Vol.23, No.2, Apr. 2014
Impossible Differential Evaluations for
New-Structure Series
∗
CUI Ting and JIN Chenhui
(Information Engineering University, Zhengzhou 450004, China)
Abstract — Impossible differential cryptanalysis is a
powerful tool to evaluate the strength of a block cipher
structure, and the key step of this cryptanalysis is to find
the longest impossible differential. Recently a series of
generalized Feistel structures named New-structure I, II,
III and IV were proposed, which were designed with full
consideration of differential and linear cryptanalysis secu-
rity. In this paper, we investigate the impossible differen-
tial properties of New-structure series, and we show that
there always exists 14/∞/19/15 rounds impossible differ-
ential for New-structure I, II, III and IV respectively.
Key words — Impossible differential cryptanaly-
sis, Generalized Feistel structure, New-structure series,
Substution-permutation (SP) structure.
I. Introduction
The architecture is a fundamental part of a block cipher.
It will directly affect the implementation performance and the
choice of round number
[1−3]
. The generalized Feistel struc-
tures are generalized forms of the classical Feistel cipher.
These structure reserve some advantages of classical Feistel
cipher such as flexible in the design of round functions, and
could be implementation easily by adopting tiny round func-
tions. Large series of ciphers use these structures as their
architectures
[4−6]
.
Recently, round functions of many well-known block ci-
phers are designed as SP-type network which employs small
parallelized nonlinear bijective functions (S layer) and a lin-
ear diffusion layer (P layer)
[7−9]
. And many research interests
are focus on the security evaluation of these structures
[10−18]
.
In Ref.[18], the authors provides a method to compute the
lower bound of active S-boxes in generalized Feistel structures,
then they designed 4 new generalized Feistel structures named
as New-structure I–IV respectively, and these structures pro-
vide sufficient resistances against the differential and linear
cryptanalysis
[18]
.
Impossible differential cryptanalysis was first proposed by
Knudsen
[19]
and Biham
[20]
. This cryptanalysis uses impossible
differentials to discard the wrong keys. Impossible differentials
are usually built under a miss-in-the-middle approach, i.e.an
impossible differential is based on two connected probability-
one differentials which contradict in the middle. Impossible
differential cryptanalysis has been used to attack Skipjack
[20]
,
Camellia, ARIA
[10]
,n-cell
[11,12]
,AES
[21]
etc. and got many
wonderful results. The key step of impossible differential
cryptanalysis is to find the longest impossible differentials.
Since the powerful efficiencies of impossible differential crypt-
analysis, many experts work on finding impossible differential
distinguishers for block cipher structures, and lots of wonderful
results are achieved
[11−15,22,23]
.
In this paper, we will find impossible distinguishers of New-
structure I, II, III and IV via several new inconsistencies. This
paper is organized as follows: Section II introduces some pre-
liminaries. Section III presents some differential properties of
New-structure I, II, III and IV. Section IV focuses on find-
ing impossible differential for New-structure series. Section V
concludes this paper.
II. Preliminaries
1. Notations
Throughout this paper, we will use the following symbols.
“⊕”: XOR operation; “Δx”: the XOR difference of x and
x
;“w(α)”: the number of nonzero components of vector α;
“Δ
f
(Δx)”: the output difference of f when the given input dif-
ference is Δx;“|”: matrices concatenation
∗∗
;“g ◦f(x)”: com-
position of function f and g, i.e. g ◦ f(x)=g(f(x)); “M
(i)
”:
the i-th column of matrix M
n×n
;“M
i,j
”: the i × j entry of
matrix M ;“E”: the identity matrix; “e
{i
1
,···,i
r
}
”: vector with
nonzero values only in the i
1
, ···,i
r
-th components; “e
i
k
”: the
i
k
-th component of e
{i
1
,···,i
r
}
;
Definition 1
[1]
(SP network) Let S
1
, ···,S
n
:
{0, 1}
d
→{0, 1}
d
be non-linear bijections, P : F
n
2
d
→ F
n
2
d
is a linear bijection, k =(k
1
, ···,k
n
) is the round key, then
the round function Round
SP
: F
n
2
d
× F
n
2
d
→ F
n
2
d
of SP
network (SPN) is defined by Round
SP
(x, k)=P (S
1
(x
1
⊕
∗
Manuscript Received Apr. 2012; Accepted Mar. 2013. This work is supported by the Natural Science Foundation of China
(No.61272488, No.61272041, No.61202491).
∗∗
It is well known that if f is a linear bijection, then Δ
f
(Δx)=f (Δx), and when f is a non-linear bijection, Δ
f
(Δx) may have several
values, in this case, we can choose any one for further discussion, and if possible, we will use Δ
(i)
f
(Δx) to distinguish them. And we use
Δ
(i⊕j)
f
(Δx)todenoteΔ
(i)
f
(Δx) ⊕ Δ
(j)
f
(Δx) when necessary.