Advanced
Related-Key Differential Attacks on CHESS-64
Related-Key Differential Attacks on CHESS-64
KSII Transactions on Internet and Information Systems (TIIS). 2014. Sep, 8(9): 3266-3285
Copyright © 2014, Korean Society For Internet Information
  • Received : March 06, 2014
  • Accepted : August 09, 2014
  • Published : September 28, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Wei Luo
Jiansheng Guo

Abstract
With limited computing and storage resources, many network applications of encryption algorithms require low power devices and fast computing components. CHESS-64 is designed by employing simple key scheduling and Data-Dependent operations (DDO) as main cryptographic components. Hardware performance for Field Programmable Gate Arrays (FPGA) and for Application Specific Integrated Circuits (ASIC) proves that CHESS-64 is a very flexible and powerful new cipher. In this paper, the security of CHESS-64 block cipher under related-key differential cryptanalysis is studied. Based on the differential properties of DDOs, we construct two types of related-key differential characteristics with one-bit difference in the master key. To recover 74 bits key, two key recovery algorithms are proposed based on the two types of related-key differential characteristics, and the corresponding data complexity is about 2 42.9 chosen-plaintexts, computing complexity is about 2 42.9 CHESS-64 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 DDO-based ciphers.
Keywords
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 resource-constrained devices.
In the past decade, for encryption applications requiring a fast hardware implementation with limited computing and storage resources, Data-Dependent permutations (DDPs) [6] have been used as main cryptographic primitives in a number of fast block ciphers, namely Spectr-H64 [7] , Cobra-H64/128 [8] , CIKS-128H [9] , DDP-64 [10] and so on. As a linear primitive, DDP conserves weights of transformed bit string, and DDP-based ciphers show their natural weaknesses against differential cryptanalytic attacks. In 2004, [11] proposed related-key differential attacks on full-round CIKS-128 and CIKS-128H. In 2005, Cobra-H64 and Cobra-H128 were proved to be insecure under related-key differential attacks [12] . It was proved that DDP-64 do not have a high security level as the designer promised [13] .
To strengthen the security of DDP-based ciphers, more powerful cryptographic primitive, namely Data-Dependent operations (DDOs) are introduced to design block ciphers [14 , 15 , 16 , 17 , 18] implemented on resource-constrained devices. In order to achieve higher speed and cost fewer computing and storage resources, these ciphers usually use simple key schedule. For DDO-based ciphers, there is no general cryptanalysis method as DDP-based ciphers, and security problem turns out to be a stumbling block for the application of high speed DDO-based ciphers. Consequently, the security evaluation gradually makes a significant task for the application of DDO-based ciphers on resource-constrained devices.
As an example of DDO-based cipher, CHESS-64 was designed to achieve more efficient hardware implementations than any existing DDP-based ciphers. In 2009, Lee et al proposed a related-key differential attack on CHESS-64 by constructing a related-key differential characteristic with high probability [19] . In our work, we point out some flaws in Lee et al’s work on constructing related-key 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 related-key differential characteristics with one-bit 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 chosen-plaintexts, 2 42.4 CHESS-64 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 chosen-plaintexts, 2 41 CHESS-64 encryptions and 2 26.6 bits of storage resources. To break CHESS-64, we perform an exhaustive search to recover the rest 54 bits of the master key. We firstly proposed correct cryptanalytic results on CHESS-64 so far, and we present a new and common method to analyze the security of DDO-based ciphers. We summarize our results and existing cryptanalytic results on some typical DDP-based and DDO-based ciphers in Table 1 .
Cryptanalytic Results of some typical DDP-based and DDO-based ciphers
PPT Slide
Lager Image
Data: Related-Key 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 CHESS-64. In Section 3, we study the related-key differential properties of CHESS-64, construct two types of related-key differential characteristics, and point out some flaws in existing cryptanalytic results on CHESS-64. In Section 4, two key recovery algorithms are presented on CHESS-64. Finally, we conclude in Section 5.
2. Description of CHESS-64
In this section, we firstly present some notations in this paper, and then we give a brief introduction of the particular DDOs used in CHESS-64 and the structure of CHESS-64.
- 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 ,⋯, ln ), l 1 is the left most bit and ln is the right most bit.
- ei : 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 32-bit 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 16-bit right cyclic rotation;
- X , Y : a 64-bit plain-text and a 64-bit cipher-text, respectively;
- Xi , Yi : the input and output of the i -th round of CHESS-64.
- 2.2 DDOs used in CHESS-64
CHESS-64 employs three DDOs as its nonlinear operations which are depicted in Fig. 1 .
PPT Slide
Lager Image
(a) F32/96, (b) F-132/96, (c) F32/80
As shown in Fig. 1 -(a) and Fig. 1 -(b), due to the symmetric structure, F 32/96 and
PPT Slide
Lager Image
differ only in the distribution of controlling bits over the basic building block F 2/1 , which is defined as follows.
PPT Slide
Lager Image
While the basic building block F 2/1 ' used in F 32/80 ' is defined as follows.
PPT Slide
Lager Image
- 2.3 Structure of CHESS-64
CHESS-64 is a pure DDO-based cipher which only employs DDOs and other linear operations. Composed of initial transformation (IT), round function Crypt , and final transformation (FT), CHESS-64 is an 8-round 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.
PPT Slide
Lager Image
(a) Structure of CHESS-64, (b) Round function Crypt
As shown in Fig. 2 -(a), the cipher uses two 64-bit key blocks RK 0 and RK 9 to transform the input data and output data, respectively. For the former 7 rounds, two 32-bit 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 extend-functions ( E , E '), three DDOs ( F 32/96 ,
PPT Slide
Lager Image
, 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, CHESS-64 employs a very simple key schedule. The 128-bit master key K of CHESS-64 is divided into four 32-bit key blocks K 1 , K 2 , K 3 , K 4 , and round keys are presented in Table 2 , where Km ( m =1,2,3,4) donates a 32-bit key block, and RKi ( i =1,2,⋯,8) donates round key of the i -th round.
Key schedule of CHESS-64
PPT Slide
Lager Image
Key schedule of CHESS-64
Encryption procedure of CHESS-64 is presented in the following table.
PPT Slide
Lager Image
3 Properties for Components of CHESS-64
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 one-bit difference in the master key, we construct three kinds of one-round related-key differential characteristics with high probability. Finally, two types of full-round related-key differential characteristics are constructed by employing properties of DDOs and one-round related-key differential characteristics.
- 3.1 Differential properties for the basic building blocks
As components of round function Crypt , F 32/96 (
PPT Slide
Lager Image
), 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
PPT Slide
Lager Image
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
PPT Slide
Lager Image
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
PPT Slide
Lager Image
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
PPT Slide
Lager Image
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
PPT Slide
Lager Image
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
PPT Slide
Lager Image
- 3.2 Differential properties for DDOs
As depicted in Fig. 1 , DDOs are constructed with basic building blocks in layered topology. Specifically,
PPT Slide
Lager Image
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
PPT Slide
Lager Image
, F 32/80 ' when the difference weight of input is 1.
Let the input difference of
PPT Slide
Lager Image
( F 32/80 ') be ek ( 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
PPT Slide
Lager Image
is e 16 , the probability distribution of the output differences of
PPT Slide
Lager Image
is depicted in Appendix Table 1.
Theorem 1. For
PPT Slide
Lager Image
, if the difference weight of input is 1, there are two differential routes at most that could transmit input difference ek ( k =1,2,⋯32) to any output difference.
Proof. According to the topology of
PPT Slide
Lager Image
, when the difference weight of input and output is 1, there exist no more than 2 one-bit differential routes. Consequently, there exist 2 differential paths at most which could transmit ek to nonzero bit of any output difference. In other words, there are two differential routes at most which could transmit ek to any output difference.
As shown in Fig. 3 , for
PPT Slide
Lager Image
, 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 six-bit of controlling string from top to bottom is “011000”. By Property 1 and Property 2, for the second route (See Fig. 3 -(b)), the ten-bit of controlling string from top to bottom and from left to right is “1111100001”.
PPT Slide
Lager Image
(a) The first difference route of e31e25 for F32/96-1, (b) The second difference route of e31e25 for F32/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 six-bit of controlling string with one-bit input and output difference for
PPT Slide
Lager Image
.
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 cipher-text pair.
(2) Lee et al made a mistake in calculating probability of one-bit differential route in
PPT Slide
Lager Image
.
For example, for
PPT Slide
Lager Image
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 sub-section 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 ek ( 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 one-bit differential route. In other words, there exists one differential route that could transmit ek to nonzero bit of any output difference. Consequently, we can exactly obtain one difference route according to input difference ek ( 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 five-bit of controlling string from top to bottom is “10010”.
PPT Slide
Lager Image
Difference route of e17e25 for F32/80
Property 7. For
PPT Slide
Lager Image
( 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
PPT Slide
Lager Image
( 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
PPT Slide
Lager Image
( F 32/80 ') by analyzing differential properties layer by layer.
- 3.3 Related-key differential characteristics
With chosen-plain-texts, by adding one-bit difference in the master key, Lee et al’s tried to construct one-round related-key differential characteristics and full-round related-key differential characteristics further [9] . However, in this paper, we show that there are two flaws in Lee et al’s work on constructing one-round related-key differential characteristics. And by using the properties and theorems in the previous sub-sections, three correct one-round related-key differential characteristics are constructed with one-bit difference in the master key.
When Δ K 3 = e 17 , by Table 2 , sub-key differences of every round (Δ RKi ) are as follows.
PPT Slide
Lager Image
According to the three kinds of sub-key differences, three kinds of corresponding one-round related-key differential characteristics are constructed as follows.
Case1 Δ RKi = ( e 17 ,0)
Since Δ RKi = ( 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)
PPT Slide
Lager Image
OD: Output Difference, P.: Probability
The probability distribution of the output differences of the secondF32/80’(when controlling string difference ise56,67)
PPT Slide
Lager Image
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
PPT Slide
Lager Image
is I V 2 )⨁Δ V 3 =0, and the corresponding probability is
PPT Slide
Lager Image
The probability distribution that the input differences ofF-132/96is 0 (△Ki=(e17,0))
PPT Slide
Lager Image
The probability distribution that the input differences of F-132/96 is 0 (△Ki=(e17,0))
According to our analysis above, the probability of one-round related-key differential characteristic
PPT Slide
Lager Image
is
PPT Slide
Lager Image
=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 one-round related-key differential characteristic.
Lee et al just used one pair of Δ V 2 V 3 to calculate the probability of
PPT Slide
Lager Image
, and their result is 2 -9 . Actually, according to the six pairs of Δ V 2 V 3 , the correct probability of
PPT Slide
Lager Image
is 2 -7 .
Case2 Δ RKi = (0, e 17 )
As the high symmetry of round function Crypt , similar to Case 1, in Case 2, we could use Δ Ki = (0, e 17 ) to construct another one-round related-key differential characteristic
PPT Slide
Lager Image
whose probability is
PPT Slide
Lager Image
=
PPT Slide
Lager Image
=2 -7 .
Case3 Δ RKi = (0,0)
PPT Slide
Lager Image
holds with probability
PPT Slide
Lager Image
=1.
These three correct one-round related-key differential characteristics are constructed with Δ K 3 = e 17 . And with any Δ Km = ej ( m =1,2,3,4,1 ≤ j ≤ 32) , we can construct similar one-round related-key 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 Δ Km = ej ( m =1,2,3,4,10 ≤ j ≤ 25) to make the constructed one-round related-key differential characteristics with higher probability. When 10 ≤ j ≤ 25 , the probability distribution of I V 2 )⨁Δ V 3 =0(the input differences of
PPT Slide
Lager Image
) is depicted in Appendix Table 2.
The first type of related-key differential characteristics
According to Appendix Table 2, when j =12,16,23,24, the input difference of
PPT Slide
Lager Image
is I V 2 )⨁Δ V 3 ≠0 , and the output difference of
PPT Slide
Lager Image
is nonzero.
When Δ K 3 = ej , as depicted in the left part of Table 6 , we construct the first type of related-key differential characteristics with corresponding three one-round related-key differential characteristics, where j =10,11,13,14,15,17,18,19,20,21,22,25 , Δ K =(0,0, ej ,0), Δ X =(0, ej ), Δ Y =(0,0), and the probability is
PPT Slide
Lager Image
Related-key differential characteristics
PPT Slide
Lager Image
RDC: related-key differential characteristics, P.: Probability, IT: initial transformation, FT: final transformation
The second type of related-key differential characteristics
When Δ K =(0,0, e 17 ,0) , based on the first type of related-key differential characteristics, we construct the second type of related-key differential characteristics by adding one-bit difference to the input of
PPT Slide
Lager Image
in the last round, which are depicted in the right part of Table 6 .
In Fig. 5 , for the second type of related-key differential characteristics, the differential routes of the last round is dispicted, where
PPT Slide
Lager Image
donates the set of all possible output differences of
PPT Slide
Lager Image
with I V 2 )⨁Δ V 3 = ek as input difference. According to Table 3 and Table 4 , Appendix Table 3, depicts the probability distribution of I V 2 )⨁Δ V 3 = ek . The second type of related-key differential characteristics hold with probability
PPT Slide
Lager Image
PPT Slide
Lager Image
The differential routes of the last round for the second type of related-key differential characteristics
4 Related-key differential attacks on CHESS-64
In this section, by using the two types of related-key differential characteristics in the previous section, we present two key recovery algorithms on CHESS-64.
- 4.1 The first related-key differential attack algorithm
For the first type of related-key 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 ej →Δ 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 cipher-text pair of the first type of related-key differential characteristics, we can recover key bits by solving equations L 3 YL = K 1 K 4 and L 2 ⨁<<<16( YL )=<<<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.
PPT Slide
Lager Image
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 .
PPT Slide
Lager Image
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 related-key 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 nj = 40.8,34,38.4,30,38,34,34,38,30.8 , the expected number of cipher-text pairs that pass Step 2 is
PPT Slide
Lager Image
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 CHESS-64 encryptions, a data complexity of 2 44.4 chosen plain-texts, 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 plain-texts. For Step 2, the computing complexity is about 2 42.4 CHESS-64 encryptions, and we need about 4×64×2×9≈2 12.2 bits to store cipher-text 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 CHESS-64 encryptions, a data complexity of 2 44.4 chosen plain-texts, and a storage complexity of 2 12.2 bits of storage resources.
- 4.2 The second related-key differential attack algorithm
For the second type of related-key differential characteristics, in the last round, if the input difference of
PPT Slide
Lager Image
is I V 2 )⨁Δ V 3 = ek , we can get the probability distribution of output difference of
PPT Slide
Lager Image
by Property 1 and Property 2. For example, if I V 2 )⨁Δ V 3 = e 16 , the probability distribution of the output differences of
PPT Slide
Lager Image
is depicted in Appendix Table 1.
In the following, the input difference of
PPT Slide
Lager Image
is I V 2 )⨁Δ V 3 = ek ,
PPT Slide
Lager Image
donates the set of all possible output differences of
PPT Slide
Lager Image
, L 4,k donates the set of controlling bits which determine the output differences of
PPT Slide
Lager Image
, and K 1,k donates the set of corresponding bits of K 1 which is related to L 4,k . For example,
PPT Slide
Lager Image
According to the topology of
PPT Slide
Lager Image
, for every ek ( k =1,2,⋯,32), the output differences of
PPT Slide
Lager Image
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 .
PPT Slide
Lager Image
Analysis of Key Recovery Algorithm 2
According to Appendix Table 3, for k =7,16,23,31, the corresponding probability of related-key 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 cipher-text pairs that could pass Step 2 (For
PPT Slide
Lager Image
, 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 cipher-text 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
PPT Slide
Lager Image
, if and only if the positions of differences in
PPT Slide
Lager Image
( 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
PPT Slide
Lager Image
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 cipher-text pairs that could pass Step 2, positions of differences in
PPT Slide
Lager Image
( k =7,16,23,31) cover 1,2,⋯,32 with probability at least 1-
PPT Slide
Lager Image
×(1-1/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 CHESS-64 encryptions, a data complexity of 2 41 chosen plain-texts, and a storage complexity of 2 26.6 bits of storage resources.
Proof. Step 1 needs about 2 41 chosen plain-texts. For Step 2, the computing complexity is about 2 41 CHESS-64 encryptions, and we need about 2 19 ×2×64=2 26 bits of storage resources to store cipher-text pairs. Step 3 needs to compute
PPT Slide
Lager Image
at most 2 19 ×2 23 =2 42 times. According to the structure of Crypt, a
PPT Slide
Lager Image
computation is about a quarter of a round computation. Then, Step3 needs about 2 42 ×1 / 4×1 / 8=2 37 CHESS-64 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 CHESS-64 encryptions, a data complexity of 2 41 chosen plain-texts, 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 CHESS-64 encryptions, 2 42.4 +2 41.1 ≈2 42.9 chosen plain-texts, 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 CHESS-64 absolutely.
5. Conclusion
The DDO-based cipher CHESS-64 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 CHESS-64 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 chosen-plaintexts,2 42.9 full-round CHESS-64 encryptions, and 2 26.6 bits of storage resources. Moreover, the related-key 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 CHESS-64 encryptions. In this paper, we present a new method to study the properties of DDOs in the procedure of constructing related-key differential characteristics, which is expected to be useful for the further analysis of DDO-based ciphers.
Our related-key differential attacks on CHESS-64 provide some suggestions for the design of DDO-based 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 CHESS-64, the combination of DDOs and Feistel-like structure contribute to the results that attackers could recover data of left-side by differential route in right-side, 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 related-key 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)
References
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 24-26 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 Context-Aware 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 Application-Aware 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 mobile-station 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 data-dependent permutation” Journal of Cryptology Article (CrossRef Link). 15 (1) 61 - 72    DOI : 10.1007/s00145-001-0012-9
Goots N. D. 2003 “Modern cryptography: Protect Your Data with Fast Block Cipher” A-LIST Publish Wayne
Sklavos N. , Moldovyan N. A. , Koufopavlou O. 2005 “High Speed Networking Security: Design and Implementation of Two New DDP-Based Ciphers” Mobile Networks and Applications Article (CrossRef Link). 10 (1-2) 219 - 231    DOI : 10.1023/B:MONE.0000048556.51292.31
Sklavos N. , Moldovyan N. A. , Koufopavlou O. 2003 “A New DDP-based Cipher CIKS-128H: 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 27-30 Article (CrossRef Link).
Moldovyan N. A. 2005 “Pure DDP-Based 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 “Related-Key Attacks on DDP Based Ciphers: CIKS-128 and CIKS-128H” INDOCRYPT December 20-22 LNCS 3348, Article (CrossRef Link). 191 - 205
Lee Changhoon , Kim Jongsung , Sung Jaechul , Hong Seokhie , Lee Sangjin , Moon Dukjae 2005 “Related-Key Differential Attacks on Cobra-H64 and Cobra-H128” in Proc. of 10th IMA International Conference December 19-21 LNCS 3796, Article (CrossRef Link). 201 - 219
Lee Changhoon , Lee Sangjin , Park Jong Hyuk , Hussain Sajid , Song Jun Hwan 2010 “Security analysis of pure DDP-based cipher proper for multimedia and ubiquitous device” Telecommunication System Article (CrossRef Link) 44 (3-4) 267 - 279    DOI : 10.1007/s11235-009-9264-8
Moldovyan N. A. , Sklavos N. , Moldovyan A. A. , Koufopavlou O. 2005 “CHESS-64, a Block Cipher Based on Data-Dependent 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 (2-3) 149 - 163    DOI : 10.1007/s11235-006-9135-5
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 SDDO-Based 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 Yang-Sun 2009 “Security Analysis of the Full-Round CHESS-64 Cipher Suitable for Pervasive Computing Environments” Journal of Universal Computer Science Article (CrossRef Link). 15 (5) 1007 - 1022
Kang Jinkeon , Jeong Kitae , Yeo Sang-Soo , Lee Changhoon 2012 “Related-Key Attack on the MD-64 Block Cipher Suitable for Pervasive Computing Environments” in proc. of 26th International Conference on Advanced Information Networking and Applications Workshops March 26-29 Article (CrossRef Link). 726 - 731