With limited computing and storage resources, many network applications of encryption algorithms require low power devices and fast computing components. CHESS64 is designed by employing simple key scheduling and DataDependent operations (DDO) as main cryptographic components. Hardware performance for Field Programmable Gate Arrays (FPGA) and for Application Specific Integrated Circuits (ASIC) proves that CHESS64 is a very flexible and powerful new cipher. In this paper, the security of CHESS64 block cipher under relatedkey differential cryptanalysis is studied. Based on the differential properties of DDOs, we construct two types of relatedkey differential characteristics with onebit difference in the master key. To recover 74 bits key, two key recovery algorithms are proposed based on the two types of relatedkey differential characteristics, and the corresponding data complexity is about 2
^{42.9}
chosenplaintexts, computing complexity is about 2
^{42.9}
CHESS64 encryptions, storage complexity is about 2
^{26.6}
bits of storage resources. To break the cipher, an exhaustive attack is implemented to recover the rest 54 bits key. These works demonstrate an effective and general way to attack DDObased ciphers.
1. Introduction
S
ecurity and privacy are primary requirements for wired and wireless communication. As a most common method, encryption is used to provide secure and secret communication. In the field of ubiquitous computing systems
[1]
, sensor networks
[2]
, wireless networks
[3]
, IPsec
[4]
and mobile communication
[5]
, limited computing and storage resources bring a variety of privacy and security challenges for encryption algorithms. As a result, more efficient cryptographic primitives are badly needed to provide high performance on resourceconstrained devices.
In the past decade, for encryption applications requiring a fast hardware implementation with limited computing and storage resources, DataDependent permutations (DDPs)
[6]
have been used as main cryptographic primitives in a number of fast block ciphers, namely SpectrH64
[7]
, CobraH64/128
[8]
, CIKS128H
[9]
, DDP64
[10]
and so on. As a linear primitive, DDP conserves weights of transformed bit string, and DDPbased ciphers show their natural weaknesses against differential cryptanalytic attacks. In 2004,
[11]
proposed relatedkey differential attacks on fullround CIKS128 and CIKS128H. In 2005, CobraH64 and CobraH128 were proved to be insecure under relatedkey differential attacks
[12]
. It was proved that DDP64 do not have a high security level as the designer promised
[13]
.
To strengthen the security of DDPbased ciphers, more powerful cryptographic primitive, namely DataDependent operations (DDOs) are introduced to design block ciphers
[14
,
15
,
16
,
17
,
18]
implemented on resourceconstrained devices. In order to achieve higher speed and cost fewer computing and storage resources, these ciphers usually use simple key schedule. For DDObased ciphers, there is no general cryptanalysis method as DDPbased ciphers, and security problem turns out to be a stumbling block for the application of high speed DDObased ciphers. Consequently, the security evaluation gradually makes a significant task for the application of DDObased ciphers on resourceconstrained devices.
As an example of DDObased cipher, CHESS64 was designed to achieve more efficient hardware implementations than any existing DDPbased ciphers. In 2009, Lee et al proposed a relatedkey differential attack on CHESS64 by constructing a relatedkey differential characteristic with high probability
[19]
. In our work, we point out some flaws in Lee et al’s work on constructing relatedkey differential characteristic and recovering key. As a result, Lee et al’s attack won’t work as promised.
Further, in this paper, we construct two types of relatedkey differential characteristics with onebit difference in the master key, based on which, two key recovery algorithms are proposed. Specifically, the first key recovery algorithm could recover 42 bits of the master key with about 2
^{42.4}
chosenplaintexts, 2
^{42.4}
CHESS64 encryptions and 2
^{12.2}
bits of storage resources, while the second key recovery algorithm could recover another 32 bits of the master key requiring about 2
^{41.1}
chosenplaintexts, 2
^{41}
CHESS64 encryptions and 2
^{26.6}
bits of storage resources. To break CHESS64, we perform an exhaustive search to recover the rest 54 bits of the master key. We firstly proposed correct cryptanalytic results on CHESS64 so far, and we present a new and common method to analyze the security of DDObased ciphers. We summarize our results and existing cryptanalytic results on some typical DDPbased and DDObased ciphers in
Table 1
.
Cryptanalytic Results of some typical DDPbased and DDObased ciphers
Data: RelatedKey Chosen Plaintexts, Time: Encryption Units
Outline.
This paper is organized as follows. In Section 2, we firstly give some notations, and then we briefly describe the structure of CHESS64. In Section 3, we study the relatedkey differential properties of CHESS64, construct two types of relatedkey differential characteristics, and point out some flaws in existing cryptanalytic results on CHESS64. In Section 4, two key recovery algorithms are presented on CHESS64. Finally, we conclude in Section 5.
2. Description of CHESS64
In this section, we firstly present some notations in this paper, and then we give a brief introduction of the particular DDOs used in CHESS64 and the structure of CHESS64.
 2.1 Notations
We use the following notations in this paper. Note that a bit string will be numbered from left to right, starting with bit 1. For example, for
L
= (
l
_{1}
,
l
_{2}
,⋯,
l_{n}
),
l
_{1}
is the left most bit and
l_{n}
is the right most bit.

e_{i}
: a binary string
e
in which the
i
th bit is one and the others are zeros;

D
(
i
) : the
i
th bit of a 32bit string, namely
D
;

F
_{n/m}
: a DDO with
m
bits as controlling binary string, and
n
bits as input and output, respectively;
 >>>16 : a 16bit right cyclic rotation;

X
,
Y
: a 64bit plaintext and a 64bit ciphertext, respectively;

X^{i}
,
Y^{i}
: the input and output of the
i
th round of CHESS64.
 2.2 DDOs used in CHESS64
CHESS64 employs three DDOs as its nonlinear operations which are depicted in
Fig. 1
.
(a) F_{32/96}, (b) F^{1}_{32/96}, (c) F_{32/80}’
As shown in
Fig. 1
(a) and
Fig. 1
(b), due to the symmetric structure,
F
_{32/96}
and
differ only in the distribution of controlling bits over the basic building block
F
_{2/1}
, which is defined as follows.
While the basic building block
F
_{2/1}
' used in
F
_{32/80}
' is defined as follows.
 2.3 Structure of CHESS64
CHESS64 is a pure DDObased cipher which only employs DDOs and other linear operations. Composed of initial transformation (IT), round function
Crypt
, and final transformation (FT), CHESS64 is an 8round iterated block cipher with a block size of 64 bits and 128 bits master key. The cipher’s general structure and round function are shown in
Fig. 2
(a) and
Fig. 2
(b), respectively.
(a) Structure of CHESS64, (b) Round function Crypt
As shown in
Fig. 2
(a), the cipher uses two 64bit key blocks
RK
^{0}
and
RK
^{9}
to transform the input data and output data, respectively. For the former 7 rounds, two 32bit output blocks would be swapped for the input of the next round, but not for the last round .
As shown in
Fig. 2
(b), round function
Crypt
is composed of five kinds of operations: bitwise module 2 addition, two extendfunctions (
E
,
E
'), three DDOs (
F
_{32/96}
,
,
F
_{32/80}
'), two cyclic rotations (<<<16,>>>7), and an involution (
I
).
Details of transformation components of round function
Crypt
could be obtained in
[8]
.
To obtain a high speed performance, CHESS64 employs a very simple key schedule. The 128bit master key
K
of CHESS64 is divided into four 32bit key blocks
K
_{1}
,
K
_{2}
,
K
_{3}
,
K
_{4}
, and round keys are presented in
Table 2
, where
K_{m}
(
m
=1,2,3,4) donates a 32bit key block, and
RK^{i}
(
i
=1,2,⋯,8) donates round key of the
i
th round.
Key schedule of CHESS64
Encryption procedure of CHESS64 is presented in the following table.
3 Properties for Components of CHESS64
In this section, we firstly describe some differential properties for the basic building blocks of DDOs, which allow us to analyze differential properties for DDOs in the next step. And then, by adding onebit difference in the master key, we construct three kinds of oneround relatedkey differential characteristics with high probability. Finally, two types of fullround relatedkey differential characteristics are constructed by employing properties of DDOs and oneround relatedkey differential characteristics.
 3.1 Differential properties for the basic building blocks
As components of round function
Crypt
,
F
_{32/96}
(
),
F
_{32/80}
' employ
F
_{2/1}
,
F
_{2/1}
' as basic building blocks, respectively.
The following properties hold for
F
_{2/1}
.
Property 1.
For
F
_{2/1}
, if the difference weight of controlling string is 0, and the difference weight of input is 1, the output difference is
Property 2.
For
F
_{2/1}
, if the difference weight of controlling string is 0, and the difference weight of input is 2, the output difference is
Property 3.
For
F
_{2/1}
, if the difference weight of controlling string is 1, and the difference weight of input is 0, the output difference is
Analogously, the following properties hold for
F
_{2/1}
'.
Property 4.
For
F
_{2/1}
', if the difference weight of controlling string is 0, and the difference weight of input is 1, the output difference is
Property 5.
For
F
_{2/1}
', if the difference weight of controlling string is 0, and the difference weight of input is 2, the output difference is
Property 6.
For
F
_{2/1}
', if the difference weight of controlling string is 1, and the difference weight of input is 0, the output difference is
 3.2 Differential properties for DDOs
As depicted in
Fig. 1
, DDOs are constructed with basic building blocks in layered topology. Specifically,
is constructed with 6 layers of
F
_{2/1}
, and each layer consists of 16
F
_{2/1}
in alignment; while
F
_{32/80}
' is constructed with 5 layers of
F
_{2/1}
', and each layer consists of 16
F
_{2/1}
' in alignment. Base on the differential properties of basic building blocks, we present differential properties of
,
F
_{32/80}
' when the difference weight of input is 1.
Let the input difference of
(
F
_{32/80}
') be
e_{k}
(
k
=1,2,⋯32). By Property 1 and Property 2 (Property 4 and Property 5), we can accurately obtain the probability distribution of the output differences by analyzing difference transmission properties layer by layer. For example, if the input difference of
is
e
_{16}
, the probability distribution of the output differences of
is depicted in Appendix Table 1.
Theorem 1.
For
, if the difference weight of input is 1, there are two differential routes at most that could transmit input difference
e_{k}
(
k
=1,2,⋯32) to any output difference.
Proof.
According to the topology of
, when the difference weight of input and output is 1, there exist no more than 2 onebit differential routes. Consequently, there exist 2 differential paths at most which could transmit
e_{k}
to nonzero bit of any output difference. In other words, there are two differential routes at most which could transmit
e_{k}
to any output difference.
As shown in
Fig. 3
, for
, the bold lines donate the two possible difference routes when the input difference is
e
_{31}
and the output difference is
e
_{25}
. By Property 1, for the first route (See
Fig. 3
(a)), we can exactly know that the sixbit of controlling string from top to bottom is “011000”. By Property 1 and Property 2, for the second route (See
Fig. 3
(b)), the tenbit of controlling string from top to bottom and from left to right is “1111100001”.
(a) The first difference route of e_{31}→e_{25} for F_{32/96}^{1}, (b) The second difference route of e_{31}→e_{25} for F_{32/96}^{1}
Based on our analysis above, it’s clear that there are two flaws in
[9]
, which are as follows.
(1) It’s impossible to obtain the exact sixbit of controlling string with onebit input and output difference for
.
For example, as there are two possible difference routes for
e
_{31}
→
e
_{25}
(See
Fig. 3
), it’s impossible to know which one is correct with a certain ciphertext pair.
(2) Lee et al made a mistake in calculating probability of onebit differential route in
.
For example, for
with an input difference
e
_{31}
, the output difference is
e
_{25}
with probability 2
^{6}
+ 2
^{10}
(not 2
^{6}
, as Lee et al presented in the last paragraph of subsection 4.1).
Theorem 2.
For
F
_{32/80}
', if the difference weight of input is 1, we can exactly obtain one differential route according to input difference
e_{k}
(
k
=1,2,⋯32) and output difference.
Proof.
According to the topology of
F
_{32/80}
', when the difference weight of input and output is 1, there exactly exists one onebit differential route. In other words, there exists one differential route that could transmit
e_{k}
to nonzero bit of any output difference. Consequently, we can exactly obtain one difference route according to input difference
e_{k}
(
k
=1,2,⋯32) and output difference.
As shown in
Fig. 4
, for
F
_{32/80}
', the bold line donates the certain difference route when the input difference is
e
_{17}
and the output difference is
e
_{25}
. According to Property 4, we can exactly know the fivebit of controlling string from top to bottom is “10010”.
Difference route of e_{17}→e_{25} for F_{32/80}’
Property 7.
For
(
F
_{32/80}
') , if the difference weight of controlling string is 0 and the difference weight of input is nonzero, the difference weight of output is nonzero.
Proof.
By Property 1 and Property 2 (Property 4 and Property 5), for
F
_{2/1}
(
F
_{2/1}
') , when the difference weight of controlling string is 0 and the difference weight of input is nonzero, the difference weight of output is nonzero. As
(
F
_{32/80}
') are constructed with
F
_{2/1}
(
F
_{2/1}
') in layered topology, we can certainly know that the difference weight of output is nonzero for
(
F
_{32/80}
') by analyzing differential properties layer by layer.
 3.3 Relatedkey differential characteristics
With chosenplaintexts, by adding onebit difference in the master key, Lee et al’s tried to construct oneround relatedkey differential characteristics and fullround relatedkey differential characteristics further
[9]
. However, in this paper, we show that there are two flaws in Lee et al’s work on constructing oneround relatedkey differential characteristics. And by using the properties and theorems in the previous subsections, three correct oneround relatedkey differential characteristics are constructed with onebit difference in the master key.
When Δ
K
_{3}
=
e
_{17}
, by
Table 2
, subkey differences of every round (Δ
RK^{i}
) are as follows.
According to the three kinds of subkey differences, three kinds of corresponding oneround relatedkey differential characteristics are constructed as follows.
Case1
Δ
RK^{i}
= (
e
_{17}
,0)
Since Δ
RK^{i}
= (
e
_{17}
,0) , input difference of the first
F
_{32/80}
' is Δ
L
_{2}
=
e
_{17}
. Then, according to >>>7 and
E
' , the controlling string difference of the second
F
_{32/80}
' is Δ
W
'=
e
_{56.67}
. By Property 4, the probability distribution of the output differences of the first
F
_{32/80}
' (Δ
V
_{2}
) is depicted in
Table 3
. By Property 6 and Property 4, the probability distribution of the output differences of the second
F
_{32/80}
'(Δ
V
_{3}
) is depicted in
Table 4
.
The probability distribution of the output differences of the firstF32/80’(when input difference ise17)
OD: Output Difference, P.: Probability
The probability distribution of the output differences of the secondF32/80’(when controlling string difference ise56,67)
OD: Output Difference, P.: Probability
According to
Table 3
and
Table 4
, when Δ
V
_{2}
,Δ
V
_{3}
coming from
Table 5
, the input difference of
is
I
(Δ
V
_{2}
)⨁Δ
V
_{3}
=0, and the corresponding probability is
The probability distribution that the input differences ofF132/96is 0 (△Ki=(e17,0))
The probability distribution that the input differences of F^{1}_{32/96} is 0 (△K^{i}=(e_{17},0))
According to our analysis above, the probability of oneround relatedkey differential characteristic
is
=2
^{7}
, and
[9]
made two mistakes in the procedure of constructing it, which are as follows.
(1) Lee et al made a mistake in calculating Δ
W
'.
In
[9]
, Δ
W
'=
e
_{56,77}
. However, the correct result is Δ
W
'=
e
_{56,77}
.
(2) Lee et al made a mistake in calculating the probability of oneround relatedkey differential characteristic.
Lee et al just used one pair of Δ
V
_{2}
,Δ
V
_{3}
to calculate the probability of
, and their result is 2
^{9}
. Actually, according to the six pairs of Δ
V
_{2}
,Δ
V
_{3}
, the correct probability of
is 2
^{7}
.
Case2
Δ
RK^{i}
= (0,
e
_{17}
)
As the high symmetry of round function
Crypt
, similar to Case 1, in Case 2, we could use Δ
K^{i}
= (0,
e
_{17}
) to construct another oneround relatedkey differential characteristic
whose probability is
=
=2
^{7}
.
Case3
Δ
RK^{i}
= (0,0)
holds with probability
=1.
These three correct oneround relatedkey differential characteristics are constructed with Δ
K
_{3}
=
e
_{17}
. And with any Δ
K_{m}
=
e_{j}
(
m
=1,2,3,4,1 ≤
j
≤ 32) , we can construct similar oneround relatedkey differential characteristics. To move a single step forward, we can’t ignore the fact that Δ
W
'=2 for 10 ≤
j
≤ 25 , and Δ
W
'=3 for other
j
. As a result, we should choose Δ
K_{m}
=
e_{j}
(
m
=1,2,3,4,10 ≤
j
≤ 25) to make the constructed oneround relatedkey differential characteristics with higher probability. When 10 ≤
j
≤ 25 , the probability distribution of
I
(Δ
V
_{2}
)⨁Δ
V
_{3}
=0(the input differences of
) is depicted in Appendix Table 2.
The first type of relatedkey differential characteristics
According to Appendix Table 2, when
j
=12,16,23,24, the input difference of
is
I
(Δ
V
_{2}
)⨁Δ
V
_{3}
≠0 , and the output difference of
is nonzero.
When Δ
K
_{3}
=
e_{j}
, as depicted in the left part of
Table 6
, we construct the first type of relatedkey differential characteristics with corresponding three oneround relatedkey differential characteristics, where
j
=10,11,13,14,15,17,18,19,20,21,22,25 , Δ
K
=(0,0,
e_{j}
,0), Δ
X
=(0,
e_{j}
), Δ
Y
=(0,0), and the probability is
Relatedkey differential characteristics
RDC: relatedkey differential characteristics, P.: Probability, IT: initial transformation, FT: final transformation
The second type of relatedkey differential characteristics
When Δ
K
=(0,0,
e
_{17}
,0) , based on the first type of relatedkey differential characteristics, we construct the second type of relatedkey differential characteristics by adding onebit difference to the input of
in the last round, which are depicted in the right part of
Table 6
.
In
Fig. 5
, for the second type of relatedkey differential characteristics, the differential routes of the last round is dispicted, where
donates the set of all possible output differences of
with
I
(Δ
V
_{2}
)⨁Δ
V
_{3}
=
e_{k}
as input difference. According to
Table 3
and
Table 4
, Appendix Table 3, depicts the probability distribution of
I
(Δ
V
_{2}
)⨁Δ
V
_{3}
=
e_{k}
. The second type of relatedkey differential characteristics hold with probability
The differential routes of the last round for the second type of relatedkey differential characteristics
4 Relatedkey differential attacks on CHESS64
In this section, by using the two types of relatedkey differential characteristics in the previous section, we present two key recovery algorithms on CHESS64.
 4.1 The first relatedkey differential attack algorithm
For the first type of relatedkey differential characteristics, according to Appendix Table 2, we can exactly get the output difference of the two
F
_{32/80}
' (Δ
V
_{2}
,Δ
V
_{3}
, respectively) in the last round. For the first
F
_{32/80}
', some bits of
L
_{3}
could be recovered by using
e_{j}
→Δ
V
_{2}
to recover the controlling bits of
F
_{32/80}
'. For the second
F
_{32/80}
', some bits of
L
_{2}
could be recovered by using difference of controlling string and output difference of
F
_{32/80}
' to recover the controlling bits of
F
_{32/80}
'. For a ciphertext pair of the first type of relatedkey differential characteristics, we can recover key bits by solving equations
L
_{3}
⨁
Y_{L}
=
K
_{1}
⨁
K
_{4}
and
L
_{2}
⨁<<<16(
Y_{L}
)=<<<16(
K
_{1}
)⨁
K
_{3}
.
For example, when
j
=11 , according to Appendix Table 2, we can exactly get Δ
V
_{2}
=
e
_{9}
,Δ
V
_{3}
=
e
_{1}
or Δ
V
_{2}
=
e
_{9,11}
,Δ
V
_{3}
=
e
_{1,3}
. Further, for Δ
V
_{2}
=
e
_{9}
,Δ
V
_{3}
=
e
_{1}
, by Theorem 2, five bits of
L
_{3}
could be recovered, i. e.,
L
_{3}
(31)=1,
L
_{3}
(3)=0,
L
_{3}
(8)=0,
L
_{3}
(14)=0,
L
_{3}
(19)=1, and by Property 6 and Property 4, one bit of
L
_{2}
could be recovered, scilicet,
L
_{2}
(15)=0. Then, the following equations could be constructed.
Obviously, by solving equations above, 6 bits information of the master key could be recovered. Similar to Δ
V
_{2}
=
e
_{9}
,Δ
V
_{3}
=
e
_{1}
, for Δ
V
_{2}
=
e
_{9,11}
,Δ
V
_{3}
=
e
_{1,3}
, 7 bits of the master key could be recovered by constructing and solving corresponding equations. For different
j
, the recovered bits of
K
_{1}
⨁
K
_{4}
,<<<16(
K
_{1}
)⨁
K
_{3}
are depicted in Appendix Table 4.
For
j
=11,13,15,17,18,19,21,22,25, implement Key Recovery
Algorithm 1
.
Analysis of Key Recovery Algorithm 1
According to Appendix Table 2, for
j
=11,13,15,17,18,19,21,22,25 , the probability of relatedkey differential characteristics are 2
^{38.8}
, 2
^{32}
,2
^{36.4}
,2
^{28}
,2
^{36}
,2
^{32}
,2
^{32}
,2
^{36}
,2
^{28.8}
, respectively. If we set
n_{j}
= 40.8,34,38.4,30,38,34,34,38,30.8 , the expected number of ciphertext pairs that pass Step 2 is
and further, the expected number of hits for correct key bits in Step3 is 4. According to Appendix Table 4, by Key Recovery
Algorithm 1
, we can recover 5 bits key information at least for each
j
, and the expected number of hits for wrong key bits is 4×2
^{5}
at most. Therefore, by using Key Recovery
Algorithm 1
, we can distinguish the correct key bits from the incorrect ones. As depicted in Appendix Table 3, for
j
=11,13,15,17,18,19,21,22,25 , implementing Key Recovery
Algorithm 1
, we can obtain the 30 bits of
K
_{1}
⨁
K
_{4}
and 12 bits of <<<16(
K
_{1}
)⨁
K
_{3}
.
Theorem 3.
By implementing Key Recovery
Algorithm 1
, we can recover 42 bits information of the master key with a computing complexity of 2
^{42.4}
CHESS64 encryptions, a data complexity of 2
^{44.4}
chosen plaintexts, and a storage complexity of 2
^{12.2}
bits of storage resources.
Proof.
Step 1 needs about 2
^{41.8}
+2
^{35}
+2
^{39.4}
+2
^{31}
+2
^{39}
+2
^{35}
+2
^{35}
+2
^{39}
+2
^{31.8}
≈ 2
^{42.4}
chosen plaintexts. For Step 2, the computing complexity is about 2
^{42.4}
CHESS64 encryptions, and we need about 4×64×2×9≈2
^{12.2}
bits to store ciphertext pairs. For Step 3, the computing complexity of recovering key bits is far less than the computing complexity of Step 2. Therefore, to recover 42(=30+12) bits information of the master key by implementing Key Recovery
Algorithm 1
, we need a computing complexity of 2
^{42.4}
CHESS64 encryptions, a data complexity of 2
^{44.4}
chosen plaintexts, and a storage complexity of 2
^{12.2}
bits of storage resources.
 4.2 The second relatedkey differential attack algorithm
For the second type of relatedkey differential characteristics, in the last round, if the input difference of
is
I
(Δ
V
_{2}
)⨁Δ
V
_{3}
=
e_{k}
, we can get the probability distribution of output difference of
by Property 1 and Property 2. For example, if
I
(Δ
V
_{2}
)⨁Δ
V
_{3}
=
e
_{16}
, the probability distribution of the output differences of
is depicted in Appendix Table 1.
In the following, the input difference of
is
I
(Δ
V
_{2}
)⨁Δ
V
_{3}
=
e_{k}
,
donates the set of all possible output differences of
,
L
_{4,k}
donates the set of controlling bits which determine the output differences of
, and
K
_{1,k}
donates the set of corresponding bits of
K
_{1}
which is related to
L
_{4,k}
. For example,
According to the topology of
, for every
e_{k}
(
k
=1,2,⋯,32), the output differences of
are determined by the left 16 bits and the right 7 bits of
L
_{4}
. Therefore, 
K
_{1,k}
= 
L
_{4,k}
=23 .
For
k
=7,16,23,31, implement Key Recovery
Algorithm 2
.
Analysis of Key Recovery Algorithm 2
According to Appendix Table 3, for
k
=7,16,23,31, the corresponding probability of relatedkey differential characteristics are 2
^{30}
,2
^{31}
,2
^{30}
,2
^{30}
, respectively. If we set
n
=40, there are at least 2
^{40}
×2
^{31}
=2
^{9}
ciphertext pairs that could pass Step 2 (For
, different input differences may lead to the same output difference), and further, the expected number of hits for correct
K
_{1,k}
in Step3 is 2
^{9}
. On the other hand, as there are no more than 2
^{40}
×2
^{21}
=2
^{19}
ciphertext pairs that could pass Step 2, the expected number of hits for incorrect
K
_{1,k}
is 2
^{19}
×2
^{23}
=2
^{4}
at most. Therefore, by using Key Recovery
Algorithm 2
, we can distinguish correct
K
_{1,k}
from the wrong ones.
In the following, we discuss the uniqueness of recovered
K
_{1,k}
by performing Key Recovery
Algorithm 2
.
According to the topology of
, if and only if the positions of differences in
(
k
= 7,16,23,31) cover 1,2,⋯,32 , we can get a unique
K
_{1,k}
by implementing Key Recovery
Algorithm 2
. When the input difference weight of
is 1, any bit of output difference is 1 with probability at least 1/32 . Further, as there are at least 2
^{40}
×2
^{31}
=2
^{9}
ciphertext pairs that could pass Step 2, positions of differences in
(
k
=7,16,23,31) cover 1,2,⋯,32 with probability at least 1
×(11/32)
^{29}
≈ 1。Therefore, we can get a unique
K
_{1,k}
by implementing Key Recovery
Algorithm 2
. According to Appendix Table 3, as
K
_{1}
=
K
_{1,7}
∪
K
_{1,16}
∪
K
_{1,23}
∪
K
_{1,31}
, we can get the whole 32 bits of
K
_{1}
by implementing Key Recovery
Algorithm 2
for
k
=7,16,23,31.
Theorem 4.
By implementing Key Recovery
Algorithm 2
, we can recover 32 bits of the master key with a computing complexity of 2
^{41.1}
CHESS64 encryptions, a data complexity of 2
^{41}
chosen plaintexts, and a storage complexity of 2
^{26.6}
bits of storage resources.
Proof.
Step 1 needs about 2
^{41}
chosen plaintexts. For Step 2, the computing complexity is about 2
^{41}
CHESS64 encryptions, and we need about 2
^{19}
×2×64=2
^{26}
bits of storage resources to store ciphertext pairs. Step 3 needs to compute
at most 2
^{19}
×2
^{23}
=2
^{42}
times. According to the structure of Crypt, a
computation is about a quarter of a round computation. Then, Step3 needs about 2
^{42}
×1 / 4×1 / 8=2
^{37}
CHESS64 encryptions, and about 2
^{23}
×4=2
^{25}
bits of storage resources to store guessed key. Therefore, to recover 32 bits of the master key by implementing Key Recovery
Algorithm 2
, we need a computing complexity of 2
^{41}
+2
^{37}
≈2
^{41.1}
CHESS64 encryptions, a data complexity of 2
^{41}
chosen plaintexts, and a storage complexity of 2
^{25}
+2
^{26}
≈2
^{26.6}
bits of storage resources.
Summary.
By Theorem 3 and Theorem 4, we can recover the whole 32 bits of
K
_{1}
, 30 bits of
K
_{4}
, and 12 bits of
K
_{3}
by implementing Key Recovery
Algorithm 1
and Key Recovery
Algorithm 2
. To recover 42+32=74 bits of the master key, we need about 2
^{42.4}
+2
^{41.1}
≈2
^{42.9}
CHESS64 encryptions, 2
^{42.4}
+2
^{41.1}
≈2
^{42.9}
chosen plaintexts, and 2
^{12.2}
+2
^{26.6}
≈2
^{26.6}
bits of storage resources. By performing an exhaustive search for the rest 54 bits key, we can recover the whole 128 bits of the master key and break CHESS64 absolutely.
5. Conclusion
The DDObased cipher CHESS64 has been designed for the application of fast and cheap hardware implementation and high security level, which is considerably resistant against all known attacks. In this paper, however, we put forward two key recovery algorithms on CHESS64 which are the first correct cryptanalytic results. In detail, as the two key recovery algorithms could be performed independently, we could recover 74(=42+32) bits of the cipher’s master key with 2
^{42.9}
chosenplaintexts,2
^{42.9}
fullround CHESS64 encryptions, and 2
^{26.6}
bits of storage resources. Moreover, the relatedkey differential attacks could be extended to recover the whole 128 bits master key by performing an exhaustive search for the remain 54 bits key, and the corresponding computing complexity are about 2
^{54}
CHESS64 encryptions. In this paper, we present a new method to study the properties of DDOs in the procedure of constructing relatedkey differential characteristics, which is expected to be useful for the further analysis of DDObased ciphers.
Our relatedkey differential attacks on CHESS64 provide some suggestions for the design of DDObased block ciphers. The most significant features of DDO are its good performance in hardware application and complicating plaintext data. However, according to our research on CHESS64, the combination of DDOs and Feistellike structure contribute to the results that attackers could recover data of leftside by differential route in rightside, which results in a threat to the master key. At the same time, to speed up the cipher, designer often choose simple schedule which makes the cipher vulnerable to relatedkey attack. In a word, to avoid the information leakage algorithms of DDOs under differential attacks, the designer should carefully consider the way to combine DDOs with other cryptographic primitives and the way to combine round key with data.
BIO
Wei Luo received B.S. degree from Zhengzhou Information Science and Technology Institute in 2011. He is studying for M.S. degree in cryptography in the same university. His research interests include design and analysis of block cipher.
(Email: luowei.crypt@gmail.com)
Jiansheng Guo is a professor of Zhengzhou Information Science and Technology Institute. His main subject interest is cryptography and his main teaching lies in the areas of information systems, the theory of cryptography and quantum computation. He received Ph.D. degree in cryptography from Zhengzhou Information Science and Technology Institute in 2004.
(Email: guojs2013@gmail.com)
Vu Thi Hong Nhan
,
Vu Quang Hiep
,
Lee Yang Koo
,
Bui The Duy
2012
“A user context recognition method for ubiquitous computing systems”
in Proc. of 8th International Conference on Computing Technology and Information Management (ICCM)
April 2426
Article (CrossRef Link).
568 
573
Bertrand A.
,
Szurley J.
,
Ruckebusch P.
,
Moerman I.
2012
“Efficient Calculation of Sensor Utility and Sensor Removal in Wireless Sensor Networks for Adaptive Signal Estimation and Beamforming”
IEEE Transactions on Signal Processing
Article (CrossRef Link).
60
(11)
5857 
5869
DOI : 10.1109/TSP.2012.2210888
Makris P.
,
Skoutas D.N.
,
Skianis C.
2013
“A Survey on ContextAware Mobile and Wireless Networking: On Networking and Computing Environments' Integration”
IEEE Communications Surveys & Tutorials
First Quarter, Article (CrossRef Link).
15
(1)
362 
386
DOI : 10.1109/SURV.2012.040912.00180
Yin Heng
,
Wang Haining
2007
“Building an ApplicationAware IPsec Policy System”
IEEE/ACM Transactions on Networking
Article (CrossRef Link).
15
(6)
1502 
1513
DOI : 10.1109/TNET.2007.896536
Zhang R.
,
Wang L.
,
Parr G
2013
“Advances in base and mobilestation aided cooperative wireless communications: An overview”
IEEE Vehicular Technology Magazine
Article (CrossRef Link).
8
(1)
57 
69
DOI : 10.1109/MVT.2012.2234254
Moldovyan A. A.
,
Moldovyan N. A.
2002
“A cipher based on datadependent permutation”
Journal of Cryptology
Article (CrossRef Link).
15
(1)
61 
72
DOI : 10.1007/s0014500100129
Goots N. D.
2003
“Modern cryptography: Protect Your Data with Fast Block Cipher”
ALIST Publish
Wayne
Sklavos N.
,
Moldovyan N. A.
,
Koufopavlou O.
2005
“High Speed Networking Security: Design and Implementation of Two New DDPBased Ciphers”
Mobile Networks and Applications
Article (CrossRef Link).
10
(12)
219 
231
DOI : 10.1023/B:MONE.0000048556.51292.31
Sklavos N.
,
Moldovyan N. A.
,
Koufopavlou O.
2003
“A New DDPbased Cipher CIKS128H: Architecture, Design & VLSI Implementation Optimization of CBC Encryption & Hashing over 1 GBPS”
in Proc. of The 46th IEEE Midwest Symposium on Circuits & Systems
Cairo, Egypt
December 2730
Article (CrossRef Link).
Moldovyan N. A.
2005
“Pure DDPBased Cipher: Architecture Analysis, Hardware Implementation Cost and Performance up to 6.5 Gbps”
The International Arab Journal of Information Technology
Article (CrossRef Link).
2
(1)
24 
27
Ko Youngdai
,
Lee Changhoon
,
Hong Seokhie
,
Sung Jaechul
,
Lee Sangjin
2004
“RelatedKey Attacks on DDP Based Ciphers: CIKS128 and CIKS128H”
INDOCRYPT
December 2022
LNCS 3348, Article (CrossRef Link).
191 
205
Lee Changhoon
,
Kim Jongsung
,
Sung Jaechul
,
Hong Seokhie
,
Lee Sangjin
,
Moon Dukjae
2005
“RelatedKey Differential Attacks on CobraH64 and CobraH128”
in Proc. of 10th IMA International Conference
December 1921
LNCS 3796, Article (CrossRef Link).
201 
219
Lee Changhoon
,
Lee Sangjin
,
Park Jong Hyuk
,
Hussain Sajid
,
Song Jun Hwan
2010
“Security analysis of pure DDPbased cipher proper for multimedia and ubiquitous device”
Telecommunication System
Article (CrossRef Link)
44
(34)
267 
279
DOI : 10.1007/s1123500992648
Moldovyan N. A.
,
Sklavos N.
,
Moldovyan A. A.
,
Koufopavlou O.
2005
“CHESS64, a Block Cipher Based on DataDependent Operations: Design Variants and Hardware Implementation Efficiency”
Asian Journal of Information Technology
Article (CrossRef Link).
4
(4)
323 
334
Moldovyan N.
,
Moldovyan A.
,
Eremeev M.
,
Sklavos N.
2006
“New Class of Cryptographic Primitives and Cipher Design for Networks Security”
International Journal of Network Security
Article (CrossRef Link).
2
(2)
114 
225
Moldovyan A. A.
,
Moldovyan N. A.
,
Sklavos N.
2006
“Controlled elements for designing ciphers suitable to efficient VLSI implementation”
Telecommunication System
Article (CrossRef Link).
32
(23)
149 
163
DOI : 10.1007/s1123500691355
Thi Bac Do
,
Hieu Minh Nguyen
,
Ngoc Duy Ho
2012
“An Effective and Secure Cipher Based on SDDO”
I. J. Computer Network and Information Security
Article (CrossRef Link).
11
(11)
1 
10
DOI : 10.5815/ijcnis.2012.11.01
Minh Nguyen Hieu
,
Bac Do Thi
,
Duy Ho Ngoc
2010
“New SDDOBased Block Cipher for Wireless Sensor Network Security”
International Journal of Computer Science and Network Security
Article (CrossRef Link).
10
(3)
54 
60
Lee Changhoon
,
Kim Jongsung
,
Hong Seokhie
,
Lee YangSun
2009
“Security Analysis of the FullRound CHESS64 Cipher Suitable for Pervasive Computing Environments”
Journal of Universal Computer Science
Article (CrossRef Link).
15
(5)
1007 
1022
Kang Jinkeon
,
Jeong Kitae
,
Yeo SangSoo
,
Lee Changhoon
2012
“RelatedKey Attack on the MD64 Block Cipher Suitable for Pervasive Computing Environments”
in proc. of 26th International Conference on Advanced Information Networking and Applications Workshops
March 2629
Article (CrossRef Link).
726 
731