# An Upper Bound of the Longest Impossible Differentials of Several Block Ciphers.

1. Introduction

Block ciphers play a large part in the process of constructing numerous symmetric cryptographic plans whose core security is determined by the ability of the underlying block ciphers to fight the existing cryptanalytic technologies. Differential cryptanalysis (DC) is one of the most essential cryptanalytic techniques [1]. Most block ciphers are currently designed to be resilient to the attack of the differential cryptanalysis. In order to verify the security of a block cipher resistance differential cryptanalysis, the usual way is to find a longest differential characteristics path which is able to differentiate from a random permutation. To a certain degree, the success of this attack depends chiefly on the opponents careful analysis of the internal structure of the encryption algorithm.

Impossible differential cryptanalysis (IDC) was first proposed by Biham et al. to attack Skipjack [2] and applied by Knudsen against DEAL [3]. It is a filtering way which utilizes differentials with probability zero to find the correct key by throwing away the wrong keys. Until now, a lot of well-known lightweight block ciphers being attacked using IDC, have been published, such as AES, Camellia [4], CLEFIA [5], ARIA[6] and Zodiac[7].

IDC is generally composed of two steps. To begin with, the adversary attempts to find out an impossible differential trail, i.e., the probability of the trail is zero. Next, after obtaining a serial of plaintext-ciphertext pairs, the opponent supposes some subkey sets involved in the outer rounds of the impossible differential path, and then encrypts/decrypts partially each pair of plaintext-ciphertext to verify whether the corresponding internal difference states are identical. Once the input and output differences of the impossible differentials are identical, the supposed subkey will be abandoned. The correct key must be found if we get rid of all incorrect keys.

The success of IDC is mainly depended on the number of the rounds of the impossible differential paths, the detail of input/output difference patterns and the strength of complexity of one-round encryption/decryption. Among them, one important aspect is the detail of input/output difference, because we can improve attacks [8] in the time/data complexities with higher possibilities. However, the core aspect of influencing IDC is the length of the rounds because the attack will be more close to the real encryption algorithm with the number becoming longer and has more practical significance, and this paper is aimed to explore an upper bound of the longest impossible differentials.

An important approach, which can be used to search for differential characteristics of the block cipher, is proposed by Sun et al. in ASIACRYPT 2014 [9] and it is based on MILP which can evaluate the security (obtain security bound) of a block cipher against the differential attacks. They successfully proved that they attained the security bounds for LBlock and PRESENT-80 against related-key differential attacks. Also, they presented a new approach to find characteristics for DESL, LBlock and PRESENT-128, which involved more rounds or higher probability than the previous results. There are several other automatic methods of the block ciphers to get the truncated impossible differentials effciently, such as U-method [10], UID-method [11] and WW-method [12]. The U-method was proposed by Kim et al. in Indocrypt 2003. Its goal is to search the impossible differentials through the miss-in-the-middle technique and the matrix operations. However, it has drawbacks in ascertaining some types of contradictions and several longer impossible differentials. The UID-method improved the evaluation of impossible differentials by removing some conditions in the U-method and making full use of more contradictory conditions. The WW-method was proposed by Wu et al. in Indocrypt 2012 and improved and extended the approach of the above two methods. The above methods are mainly used to search the differential characteristics or impossible differentials as more as possible.

In CRYPTO 2015, Sun et al. have proved that they found almost all impossible differentials of a block cipher [13]. And they first proposed the concept of structure, the independent of the choices of the S-boxes and the dual structure. The dual structure is used to link zero correlation linear hulls and impossible differentials. Constructing zero correlation linear hulls of the dual structure is equal with building impossible differentials of a structure.

In EUROCRYPT 2016, Sun et al. chiefly researched the security of structures resistance impossible differential [14]. They first proposed the problem whether there exists an r-round impossible differential. As a result, there does not exist any 5-round impossible differentials of AES or ARIA, and any 9-round independent impossible differentials of the Camellia without F L/F [L.sup.-1] layer unless the details of the non-linear layer of them are considered.

Our Contribution. This paper aims to find an upper bound of the longest impossible differentials of Several Block Ciphers. We analyze several important block ciphers of the SPN and feistel structure in detail. Then, we apply the matrix to express the linear transformation layer of these block ciphers and give a detailed process.

We first analyse the national standard of the Russian Federation in 2015, Kuznyechik, which utilizes the 16-byte LFSR to achieve the linear transformation. By the analysis, we conclude that there is no any 3-round impossible differential of the Kuznyechik without the consideration of the specific S-boxes. We next ascertain the longest impossible differentials of several other important block ciphers by using the matrix method which can be extended to many other block ciphers. Finally, we provide technical support about IDC for a lot of block ciphers because we can quickly find the longest impossible differentials.

As a result, we show that, unless considering the details of the S-boxes, there is no impossible differential path more than or equal to 3-round, 5-round, 7-round and 9-round impossible differentials for Kuznyechik[15], KLEIN[16] [17], Midori64[18] and MIBS[19] [20] respectively.

Organization of the paper. Section 2 describes some notations used in this paper such as SPN structure, Feistel structure, the matrix of linear transformation and impossible differentials. Section 3 presents the impossible differentials cryptanalysis of the SPN structure and proves the upper bound of the longest impossible differential paths of Kuznyechik, KLEIN and Midori64. Then, Section 4 depicts the impossible differentials cryptanalysis of the Feistel structure and gives the upper bound of the longest impossible differential trails of MIBS. Finally, we draw our conclusion in Section 5.

2. Preliminaries

These notations and basic knowledge are used in this article. Notations. [mathematical expression not reproducible] : a vector with length b.

[mathematical expression not reproducible] : the vector space over [mathematical expression not reproducible] with dimension n.

Z : the integer ring.

[chi](X) : the truncated characteristic of X.

P : the matrix of the linear layer of the block ciphers, where [mathematical expression not reproducible]

P*: the characteristic matrix of P, where P* = ([p*.sub.ij]) [member of] [Z.sup.nxn].

[parallel] : concatenation.

[[epsilon].sup.(r).sub.SP] : an r-round SPN structure.

[F.sup.(r).sub.SP] : an r-round Feistel structure with SP-type round function.

The Block Ciphers of SPN Structure. The SPN structure is broadly used in cryptographic primitives' composition. One round of an SPN cipher typically has three layers (Fig. 1, Left): the SubkeyAddition layer, the nonlinear transformation Sbox-layer and the linear permutation layer P. The SubkeyAddition layer is omitted in this paper because it does not cause the propagation of differences. The Sbox-layer can accomplish confusion and P-layer can achieve diffusion. We divide the input a of Sbox-layer into n parts, i.e., a = ([a.sub.0],...,[a.sub.n-1]), where [a.sub.i](0 <=i <= n - 1) is a b-bit byte.

To begin with, ai is implemented by the non-linear transformation si as follows:

[mathematical expression not reproducible] (1)

Then, y is transformed by [mathematical expression not reproducible]. Additionally, we omit the last round linear permutation layer P since it does not influence the length of an impossible differential, i.e., an r-round SPN structure can be signified by [(S * P).sup.(r-1)] * S.

Specifically, the SP-type function is denoted as [mathematical expression not reproducible] in this paper.

The Block Ciphers of Feistel Structure. The Feistel structure is depicted on the right of Fig. 1. Let [mathematical expression not reproducible] and [mathematical expression not reproducible] be the input and output of the round function F of the i-th round, respectively, where 0 [less than or equal to] i [less than or equal to] r - 1.

[mathematical expression not reproducible] (2)

Similar to the SPN structure, the SubkeyAddition is omitted. In order to keep the consistency of encryption and decryption process, the left and the right are not exchanged in the last round. Notice that the speed of encryption is slow since every bit can be encrypted with two rounds.

Impossible Differentials. Let G : [F.sup.n.sub.2] [right arrow] [F.sup.m.sub.2], [delta] [member of] [F.sup.n.sub.2] and [DELTA] [member of] [F.sup.m.sub.2]. The probability of [delta] [right arrow] [DELTA] is defined as

p([delta] [right arrow] [DELTA]) = #{x [member of] [F.sup.n.sub.2] | G(x) [symmetry] G(x [symmetry] [delta]) = [DELTA]} /[2.sup.n] (3)

If p([delta] [right arrow] [DELTA]) = 0, then [delta] [right arrow] [DELTA] is called an impossible differential of G.

Definition 1([14]). Let E : [F.sup.n.sub.2] [right arrow] [F.sup.n.sub.2] be a encryption algorithm of a block cipher, whose non-linear components are the bijective S-boxes. A structure [[epsilon].sup.E] [member of] [F.sup.n.sub.2] is denoted as a group of block ciphers E' which is equal to E, besides the S-boxes of E' can take all possible bijective transformations. Let [alpha], [beta] [member of] [F.sup.n.sub.2]. If for any E' [member of] [[epsilon].sup.E], [alpha] [??] [beta] is an impossible differential of E'. Then a [??] [beta] is called an impossible differential of [[epsilon].sup.E].

Truncated Characteristic. X = ([x.sub.0],..., [x.sub.n-1]), where [mathematical expression not reproducible] and [mathematical expression not reproducible]. Let [mathematical expression not reproducible] be defined as

[mathematical expression not reproducible] (4)

Then, [chi](X) denotes the truncated characteristic of X, as follows:

[chi](X) = ([theta]([x.sub.0]),...,[theta]([x.sub.n-1])) [member of] [F.sup.n.sub.2] (5)

The Matrix of Linear Permutation. Let the matrix P represent the linear permuation of the block cipher, where [mathematical expression not reproducible]. For the block ciphers of SPN structure, the matrix P represents the linear permutation layer P, i.e., not including the SubkeyAddition layer and the nonlinear transformation Sbox-layer. For the block ciphers of Feistel structure, the matrix P represents the linear permutation layer P of the round function.

AES is one of the most popular SPN ciphers so far. The SubBytes(SB) is the only non-linear transformation. The linear permutation includes ShiftRows(SR) and MixColumns(MC). Let the state after SB be S which consists of [a.sub.i], where i = 0,1,2,...,15 and the length of [a.sub.i] is 8 bits. The state after SR and MC can be described as follows:

[mathematical expression not reproducible]

If we consider the 4 x 4 state S as a vector S' in [mathematical expression not reproducible], the linear permutation which includes the SR and the MC can be also written as the following P x S', where the linear permutation matrix P is in [mathematical expression not reproducible] as follows:

Similar to SPN, we can use the matrix P to represent the linear permutation operations of the round function of Feistel strucures with SP-type round functions.

Characteristic Matrix. Let P* = ([p*.sub.ij]) [member of] [Z.sup.nxn] denote the characteristic matrix of P = ([p.sub.ij]) [member of] [F.sup.nxn] for 0 [less than or equal to] i, j [less than or equal to] n - 1, where [p*.sub.ij] =[theta]([p.sub.ij]), i.e., [p*.sub.ij] = 0 if [p.sub.ij] = 0 and [p*.sub.ij] = 1 otherwise. Let the matrix B = ([b.sub.ij]) [member of] [Z.sup.nxn]. B be non-negative if all [b.sub.ij] are non-negative, and positive if all [b.sub.ij] are positive. Obviously, P (*) is always non-negative. Then the characteristic matrix P (*)of AES as shown above.

3. Impossible Differentials of the SPN Structure

We use the matrix method to ascertain the upper bound of the longest impossible differentials for several SPN ciphers.

3.1 An Upper Bound for the Rounds of Impossible Differentials

Definition 2. Let [mathematical expression not reproducible], P* be the characteristic matrix of P, and

[f.sub.m](P*) = [(P*).sup.m] (6)

Then the smallest integer m is called type 1 primitive index of P (for SPN structure), s.t. [f.sub.m] (P*) is a positive matrix. For example, if m = 3, then [f.sub.3]( P*) = [(P*).sup.3] is a positive matrix, but [f.sub.2](P*) = [(P*).sup.2] is not positive matrix.

Assume [micro] [right arrow] v is a possible differential of [[epsilon].sup.(r).subSP]. So, there is always a few a' and [beta]', s.t.,

[mathematical expression not reproducible] (7)

is a possible differential of [[epsilon].sup.(r).subSP]. Thus for any [mu]* and v*, s.t., [chi]([mu]*) = [chi]([mu]) and [chi](v*) = [chi](v),

[mathematical expression not reproducible] (8)

is also a possible differential.

As discussed previously, we can ascertain the longest of impossible differentials. Next, we will present an upper bound for the length of impossible differentials with considering merely the property of the P layer for an SPN structure.

Fig.2 describes the maximal length of impossible differential trail of an SPN cipher. Let the intermediate [[mu].sub.1] be m bytes. If anyone byte of [[mu].sub.1] has a difference, then each byte of [v.sub.1] has a difference after encrypting [R.sub.1](P) rounds, i.e., | [chi]([[mu].sub.1])|= 1 and | [chi]([v.sub.1])|= m. In a similar way, if anyone byte of [[mu].sub.2] has a difference, then each byte of [v.sub.1] has a difference after decrypting [R.sub.-1](P) rounds, i.e., | [chi]([[mu].sub.1])|= 1 and | [chi]([v.sub.2])|= m. Since| [chi]([v.sub.1])|=| [chi]([v.sub.2])|= m [v.sub.1] [right arrow] [v.sub.2] is a one-round possible differential. So the following theorem holds.

Theorem 1( [14]). Let [R.sub.1](P) and [R.sub.-1](P) be the type 1 primitive indexes of P and [P.sup.-1] respectively. There is no any impossible differential r of [[epsilon].sup.(r).sub.SP] for r [greater than or equal to] R(P) + [R.sub.-1] (P) +1 (As shown in Fig. 2).

For AES, we only consider the property of the P layer. The state is [S.sub.0] which consists of [a.sub.i] for i =0,1,2,... 15, where the length of [a.sub.i] is 8 bits. The state after the Matrix P of Linear Permutation (one round) is [S.sub.1] which consists of [b.sub.i] for i = 0,1,2,..., 15. Then the state after the Matrix P again is [S.sub.2] which consists of [c.sub.i] for i = 0,1,2,...,15. [S.sub.0], [S.sub.1] and [S.sub.2] are depicted as follows.

Obviously, if | [chi]([S.sub.0])|= 1, then | [chi]([S.sub.1])|= 4 and | [chi]([S.sub.2])|= 16. In other words, P* is not a positive matrix, however, [(P*).sup.2] is a positive matrix. So [R.sub.1](P)= 2. Similarly, [R.sub.-1](P) = 2.

3.2 Cryptanalysis of Kuznyechik Cipher

Kuznyechik [15] is the national standard [GOST R 34.12-2015] of the Russian Federation in 2015. It applies cryptographic techniques to process and protect information, including the confidentiality, authenticity, and integrity of data. The Standard complies with modern cryptographic requirements and is designed for efficient implementation of hardware and software.

Kuznyechik(see Fig.3) is a 128-bit block cipher with 256 bits key. The encryption algorithm is a replacement [mathematical expression not reproducible] which is defined on [mathematical expression not reproducible], as shown below:

[mathematical expression not reproducible] (9)

where a = [a.sub.15] [parallel] [a.sub.14] [parallel] [a.sub.13] *** [parallel] [a.sub.2] [parallel] [a.sub.1] [parallel] [a.sub.0] and [mathematical expression not reproducible] (0 [less than or equal to] i [less than or equal to] 15).

Moreover, X denotes AddRoundKey, and S represents the bijective nonlinear mapping, i.e., S(a) = S([a.sub.15] [parallel] [a.sub.14] [parallel] [a.sub.13] *** [parallel] [a.sub.2] [parallel] [a.sub.1] [parallel] [a.sub.0]) = [b.sub.15] [parallel] [b.sub.14] [parallel] [b.sub.13] *** [parallel] [b.sub.2] [parallel] [b.sub.1] [parallel] [b.sub.0], where [b.sub.i] = [pi]([a.sub.i])(0 < i < 15). L means [R.sup.16], i.e., the linear transformation layer, where R(b) = R([b.sub.15] [parallel] [b.sub.14] [parallel] [b.sub.13] *** [parallel] [b.sub.2] [parallel] [b.sub.1] [parallel] [b.sub.0]) = l([b.sub.15], ***, [b.sub.0]) [parallel] [b.sub.15] [parallel] [b.sub.14] [parallel] [b.sub.13] *** [parallel] [b.sub.2] [parallel] [b.sub.1] is a 16-byte LFSR. The register moves 8 bits each time, and the new state is denoted by the state of LFSR after moving 16 times. The detailed descriptions of LFSR are in Fig. 4.

For Kuznyechik, the P layer means the L operation, i.e., P = [R.sup.16]. Then we consider the 16 states as a vector in [mathematical expression not reproducible] and the irreducible polynomial over this finite fields is [x.sup.8] + [x.sup.7] + [x.sup.6] + x +1. By calculation, the following matrix can be used to represent R, [R.sup.2] and [R.sup.16].

For R, the 16 elements in row 0 are non-zero, and there are 15 zeros and one 1 in the other 15 rows. For [R.sup.2], the 16 elements in row 0 and row 1 are non-zero, and there are 15 zeros and one 1 in the other 14 rows. Note that the multiplication of any two nonzero numbers is still nonzero in the finite field.

By computing, there is no 0 element in [R.sup.16], i.e., [R.sup.16] is a positive matrix. For Kuznyechik, the linear transformation of each round is iterated 16 times, which is equivalent to 16 rounds of other block cipher algorithms. Therefore, the characteristic matrix of [R.sup.16] (i.e. P*) is also the positive matrix. Then we have R(P) = 1.. In a similar way, [R.sub.-1](P)= 1. Then we get the following conclusion:

Proposition 1. There is no any more than or equal to 3-round impossible differential of [[epsilon].sup.Kuznyechik]. Or equivalently, there is no any 3-round impossible differential of the Kuznyechik unless considering the details of the S-boxes.

3.3 Cryptanalysis of KLEIN Cipher

KLEIN family [16] is proposed by Gong et al. at RFIDSec 2011, with a fixed 64-bit block size. It supports three key of 64-bit, 80-bit and 96-bit, along with 12,16 and 20 rounds respectively. The experimental implementation results of hardware and software show that KLEIN has a good performance in constrained resource environments.

KLEIN uses 4-bit Sboxes and AES MixColumn in a SPN structure. Such a combination is low memory implementation in both hardware and software, but KLEIN family may exists serious risks and they are not validated with further external analysis. The present cryptanalysis results of KLEIN, shown by designers, are about 4-round differential and linear attacks, 5-round integral attack. The designers also considered the Key schedule attack, algebraic attack and side-channel attack. And we can apply the high order differential and the high order integral properties to improve the result of the integral analysis. Ahmadian et al. shown a full round attack on KLEIN by using a biclique [17].

KLEIN supports 64-bit, 80-bit and 96-bit three key sizes but all of them are 64-bit block sizes. In this paper we focuse only on KLEIN-64 (see Fig. 5) whose round function consists of four steps as below.

(1) AddRoundKey(AK), the 64-bit state is XORed with a 64-bit round key.

(2) SubNibbles(SN), which divides the 64-bit intermediate state into sixteen 4-bit nibbles and puts them into the same sixteen 4 x 4 S-boxes.

(3) RotateNibbles(RN), the 64-bit state are rotated left 16 bits in every round.

(4) MixNibbles(MN), two AES MixColumn are applied concurrently, each 32-bit is operated by one AES Mix-Column.

The AES MixColumn operation is the following matrix(M1) multiplication in GF(28 ) and multiply modulo x4 + 1. The corresponding irreducible polynomial is : [x.sup.8] + [x.sup.4] + [x.sup.3] + x + 1.

Let the state after SN be S which consists of [a.sub.i] for i = 0,1,2,...,7, where the length of [a.sub.i] is 8 bits. These two operations of RN and MN can be denoted as follows:

If we consider the state S as a vector S' in [mathematical expression not reproducible], the linear permutation, which includes RN and MN, can be also written as the following P x S', where the linear permutation matrix P is

[mathematical expression not reproducible]

Since P* is negative and [(P*).sup.2] is positive, we have R(P) = 2. Similarly, [R.sub.-1](P) = 2. Then we get the following conclusion:

Proposition 2. There is no any more than or equal to 5-round impossible differential of [[epsilon].sub.KLEIN]. Or equivalently, there is no any 5-round impossible differential of the KLEIN unless considering the details of the S-boxes.

3.4 Cryptanalysis of Midori64 Cipher

The Midori64 [18] is another popular SPN ciphers and designed by Banik et al. at A SIACRYPT 2015. Midori family is also a lightweight block ciphe. Midori-64 support 64-bit block sizes and 128-bit keys along with 16 rounds. The designers try to optimize every part of the circuit in order to decrease the energy consumption and make both encryption and decryption achieved by a little adjustment in the circuit. The designers declared that there does not exist any more than 7-round impossible differential trail for Midori64.

In this paper, we focus on Midori64(see Fig.6) whose round function consists of four steps as below.

(1) SubCell(SC), apply the same 16 non-linear S-boxes on the state in parallel.

(2) ShuffeCell(SFC), the shuffe is as follows: ([a.sub.0], [a.sub.1], [a.sub.2],..., [a.sub.13], [a.sub.14], [a.sub.15]) [left arrow] ([a.sub.0], [a.sub.10], [a.sub.5], [a.sub.15], [a.sub.14], [a.sub.4], [a.sub.11], [a.sub.1], [a.sub.9], [a.sub.3], [a.sub.12], [a.sub.6], [a.sub.7], [a.sub.12], [a.sub.6], [a.sub.7], [a.sub.13], [a.sub.2], [a.sub.8]).

(3) MixColumn(MC), Midori-64 utilizes the matrix M2 to confuse every 4-nibble column of the state S, [i.e..sup.t] ([a.sub.i], [a.sub.i+1], [a.sub.i+2], [a.sub.i+3]) [left arrow] [M.sub.2][*.sup.t] ([a.sub.i], [a.sub.i+1], [a.sub.i+2], [a.sub.i+3]), where i = 0,4,8,12.

[mathematical expression not reproducible]

(4) AddKey(AK), the 64-bit state is XORed with a 64-bit round key.

Similar to KLEIN, we consider the 4 x 4 matrix of Midori-64 as the state [mathematical expression not reproducible], where the size of each cell of S is 4 bits. Let the state S after SC be described as shown above, and the state after SFC and MC can be written as follows.

[mathematical expression not reproducible]

The matix P of linear permutation can be written as the following 16 x 16 matrix over [mathematical expression not reproducible]. It is clear that the characteristic matrix P* of P equals P. By calculating, [(P*).sup.2] is negative, but [(P*).sup.3] is positive. So, we get R(P) = 3. Similarly, [R.sub.-1](P) = 3. Then we get the following conclusion:

Proposition 3. There is no any more than or equal to 7-round impossible differential of [[epsilon].sup.Midori64]. Or equivalently, there is no any 7-round impossible differential of the Midori64 unless considering the details of the S-boxes.

In 2016, Chen et al. used the path (0, a, 0, 0, 0, 0, 0, 0, 0, 0, 0, a, 0, 0, 0, 0) [right arrow] (0, 0, 0, 0, 0,*, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0), a 6-round impossible differential path, to attack 10-round Midori64, where 0 denotes zero difference, a and * denote non-zero difference [21]. The impossible difference path is consistent with our conclusion in proposition 3.

4. Impossible Differentials of the Feistel Structures with SP-Type Round Functions

We use the matrix method to ascertain the upper bound of the longest impossible differentials of the Feistel Structures with SP-Type Round Functions.

4.1 An Upper Bound for the Rounds of Impossible Differentials

The principle to study the Feistel structure with SP-type round functions are almost the same as that of the SPN structure(As shown in Fig. 7).

Definition 3. Let [mathematical expression not reproducible], P* be the characteristic matrix of P, and

[mathematical expression not reproducible] (10)

Then the smallest integer m is called type 2 primitive index of P, s.t. [g.sub.m](P*) is positive. For example, if m = 5, then j = 3. Thus [g.sub.m](P*) = [(P*).sup.1] + [(P*).sup.3] + [(P*).sup.5] is a positive matrix, whereas [(P*).sup.0] + [(P*).sup.2] + [(P*).sup.4] and [(P*).sup.1] + [(P*).sup.3] are not positive matrix. if m = 6, then j = 3. Thus [g.sub.m](P*) = [(P*).sup.0] + [(P*).sup.2] + [(P*).sup.4] + [(P*).sup.6] is a positive matrix, whereas [(P*).sup.1] + [(P*).sup.1] + [(P*).sup.5] and [(P*).sup.0] + [(P*).sup.2] + [(P*).sup.4] are not positive matrix.

Theorem 2. Let [R.sub.2](P) be the type 2 primitive indexes of P. Then, there is no any independent impossible differential r of [F.sup.(r).sub.SP] for r [greater than or equal to] 2[R.sub.2](P) + 5 (detailed proof, see P12-14[14]).

4.2 Cryptanalysis of MIBS Cipher

MIBS [19] is proposed by M.Izadi et al. in CANS 2009. It is a lightweight block cipher with 64-bit block size and 32-round. MIBS supports two key sizes 64-bit and 80-bit. The experimental results show that MIBS has a good performance in constrained resource environments such as RFID tags and sensor networks. MIBS is a typical block cipher of the Feistel structure and its round function(Fig. 8) includes three steps:

(1) addroundkey, the 32-bit [L.sub.i-1], the left half of the state, is XORed with a 32-bit round key.

(2) S layer, the nonlinear S -boxes transformations, divides the 32-bit intermediate state into eight 4-bit nibbles and puts them into the same eight 4 x 4 S-boxes.

(3) P layer, linear transformations layer(with branch number 5).

Let the [mathematical expression not reproducible] and [mathematical expression not reproducible] be the input and output of the P layer, respectively, for i = 1,...,8. The linear permutations(Fig. 9) is as follows.

So, P can be also written 8 x 8 matrix over F2 (8) 4 (x8). P and (P*) (2) as followins.

[mathematical expression not reproducible] (10)

Obviously, if | [chi](Y) |= 1, then | [chi](Z) |= 8. In other words, P* is not a positive matrix, however, [(P (*)).sup.2] is a positive matrix. So, [(P (*)).sup.2] + I is positive, where I is the identity matrix. Then we have [R.sub.2](P) = 2 and get the following conclusion:

Proposition 4. There is no any more than or equal to 9-round (2R (P) + 5) independent impossible differential of [[epsilon].sup.MIBS]. Or equivalently, there is no any 9-round independent impossible differential of the MIBS unless considering the details of the S-boxes.

In EUROCRYPT 2017, Yu Sasaki and Yosuke Todo presented a new tool searching for impossible differentials of MIBS [22]. They found an impossible difference path with a maximum of 8 rounds, such as (00000000, 000a0000)->(00000b00, 00000000). The impossible difference path is consistent with our conclusion in proposition 4.

5. Conclusion

In this paper, we mainly explored the security of structures against impossible differential and determined whether there exists an r-round impossible differential of an SPN structure or an independent impossible differential of a Feistel structure with SP-type round functions. The main factor of influencing impossible differential cryptanalysis is the length of the rounds of the impossible differentials because the attack will be more close to the real encryption algorithm with the number becoming longer.

We first analyse Kuznyechik, which is the national standard of the Russian Federation in 2015, and draw the conclusion that there is no any 3-round impossible differential of the Kuznyechik with only considering the linear permutations.

Although we are only interested in the truncated impossible differentials, we apply the matrix to express the linear transformation layer and use the matrix method to quickly ascertain the upper bound of the longest impossible differentials for several block ciphers ignoring the nonlinear transformations. The matrix method can be extended to many other block cipher.

As a result, we show that, unless considering the details of the S-boxes, there is no any 3-round, 5-round and 7-round impossible differentials for Kuznyechik, KLEIN and Midori64 respectively and there is no any 9-round independent impossible differential for MIBS.

Acknowledgements

This work is partially supported by National Natural Science Foundation of China (Nos. 61672330, 61602287 and 11771256), and the Key Research Development Project of Shandong Province (Nos.2015GGX101047 and 2016GGX101024).

References

[1] E. Biham and A. Shamir, "Differential Cryptanalysis of the Data Encryption Standard," Springer-Verlag, pp. 1-151, 1993. Article(CrossRefLink).

[2] E. Biham and A. Biryukov and A. Shamir, "Cryptanalysis of Skipjack Reduced to 31 Rounds Using Impossible Differentials," Advances in Cryptology--EUROCRYPT '99, Vol. 1592, pp. 12-23, 1999. Article(CrossRefLink).

[3] L.R. Knudsen, "DEAL-A 128-bit block cipher," Complexity, pp. 1-151, 1998.

[4] C. Blondeau, "Impossible differential attack on 13-round Camellia-192," Information Processing Letters, Vol. 115, pp.660-666, 2015. Article(CrossRefLink).

[5] C. Boura and M. Naya-Plasencia and V. Suder, "Scrutinizing and Improving Impossible Differential Attacks: Applications to CLEFIA, Camellia, LBlock and Simon," ASIACRYPT, Vol. 8873, pp. 179-199, 2014. Article(CrossRefLink).

[6] R. Li and B. Sun and C. Li, "Impossible differential cryptanalysis of SPN ciphers," IET Information Security, Vol. 5, pp. 111-120, 2011.

[7] B. Sun and P. Zhang and C. Li, "Impossible Differential and Integral Cryptanalysis of Zodiac," Journal of Software, Vol. 22, pp. 1911-1917, 2011.

[8] C. Du and J. Chen, "Impossible Differential Cryptanalysis of ARIA Reduced to 7 rounds," CANS, Vol.6467, pp. 20-30, 2010. Article(CrossRefLink).

[9] S. Sun and L. Hu and P. Wang, "Automatic Security Evaluation and (Related-key) Differential Characteristic Search: Application to SIMON, PRESENT, LBlock, DES(L) and Other Bit-Oriented Block Ciphers," ASIACRYPT, Vol. 8873, pp. 158-178, 2014. Article(CrossRefLink).

[10] J. Kim and S. Hong and J. Lim, "Impossible differential cryptanalysis using matrix method," Discrete Mathematics, Vol. 310, pp. 988-1002, 2010. Article(CrossRefLink).

[11] Y. Luo and X. Lai and Z. Wu and G. Gong, "A unified method for finding impossible differentials of block cipher structures," Information Science, Vol. 263, pp. 211-220, 2014. Article(CrossRefLink).

[12] S. Wu and M. Wang, "Automatic Search of Truncated Impossible Differentials for Word-Oriented Block Ciphers," INDOCRYPT, Vol. 7668, pp. 283-302, 2012. Article(CrossRefLink).

[13] B. Sun and Z. Liu and V. Rijmen and R. Li and L. Cheng and Q. Wang and H. AlKhzaimi and C. Li, "Links Among Impossible Differential, Integral and Zero Correlation Linear Cryptanalysis," CRYPTO, Vol.9215, pp. 95-115, 2015. Article(CrossRefLink).

[14] B. Sun and M. Liu and J. Guo and V. Rijmen and R. Li, "Provable Security Evaluation of Structures against Impossible Differential and Zero Correlation Linear Cryptanalysis," EUROCRYPT, Vol. 9665, pp. 196-213, 2016. Article(CrossRefLink).

[15] "Information technology CRYPTOGRAPHIC DATA SECURITY Block ciphers," NATIONAL STANDARD OF THE RUSSIAN FEDERATION, GOST R 34.12-2015, 2015.

[16] Z. Gong and S. Nikova and Y. Law, "KLEIN: A New Family of Lightweight Block Ciphers," RFIDSec, Vol. 7055, pp. 1-18, 2012. Article(CrossRefLink).

[17] Z. Ahmadian and M. Salmasizadeh and M.R. Aref, "Biclique Cryptanalysis of the Full-Round KLEIN Block Cipher," Iet Information Security, Vol. 9, pp. 294-301, 2015. Article(CrossRefLink).

[18] S. Banik and A. Bogdanov and T. Isobe and K. Shibutani and H. Hiwatari and T. Akishita and F. Regazzoni, "Midori: A Block Cipher for Low Energy (Extended Version)," ASIACRYPT, Vol. 9453, pp. 411-436, 2015. Article(CrossRefLink).

[20] A. Bay and J. Nakahara and S. Vaudenay, "Cryptanalysis of reduced-round MIBS block cipher," CANS, Vol. 6467, pp. 1-19, 2010. Article(CrossRefLink) .

[21] Z. Chen and X. Wang, "Impossible differential cryptanalysis of midori," Cryptology ePrint Archive, Report 2016/535. Article(CrossRefLink).

[22] S. Yu and Y. Todo, "New Impossible Differential Search Tool from Design and Cryptanalysis Aspects," Vol. 2017, pp.185-215. Article(CrossRefLink).

Guoyong Han is a Ph.D. candidate in the School of Information Science and Engineering, Shandong Normal University, Jinan, China. He received the B.E. (2002), and the M.E. (2006) degrees from Shan dong University, Jinan, China. He is an Associate Professor in the School of Management Engineering of the Shandong Jianzhu University. His research interests include information security and analysis and design of block ciphers. He has published over 10 research papers in refereed academic journals and conferences.

Wenying Zhang received her Ph.D.degree in Cryptography in Department of Information Research, Information Engineering University of PLA in June 2004 in Zhengzhou, Henan, China.

From July 2004 to September 2006, she was a Postdoctoral Fellow at the Institute of Software, Chinese Academy of Sciences, Beijing, China. She is now a professor and Ph.d. supervisor of Shandong Normal University. Her research interests include cryptography, Boolean function, hash function analysis. (Email:wenyingzh@sohu.com)

Hongluan Zhao received her PhD from the School of Mathematics of the Shandong University in 2007. Currently, she is an Associate Professor in the School of Computer Science and Technology of the Shandong Jianzhu University. Her research interests include computer network and information security.

Guoyong Han (1,2), Wenying Zhang (1,*) and Hongluan Zhao (3)

(1) School of Information Science and Engineering, Shandong Normal University, Jinan, China

[e-mail: wenyingzh@sohu.com]

(2) School of Management Engineering, Shandong Jianzhu University, Jinan, China

[e-mail: hgy_126@126.com]

(3) School of Computer Science and Technology, Shandong Jianzhu University, Jinan, China

(*) Corresponding author: Wenying Zhang

Received January 29, 2018; revised June 6, 2018; accepted September 12, 2018; published January 31, 2019

http://doi.org/10.3837/tiis.2019.01.024
COPYRIGHT 2019 KSII, the Korean Society for Internet Information
No portion of this article can be reproduced without the express written permission from the copyright holder.