Provable security against impossible differential and zero correlation linear cryptanalysis of some feistel structures

Abstract

Impossible differential and zero correlation linear cryptanalysis are two important cryptanalytic methods. In this paper, we study the security of some Feistel structures against these two cryptanalytic methods. Throughout this paper, we consider the impossible differential and zero correlation linear hull that are independent of the choices of the non-linear parts. Based on that, a method is introduced to estimate the number of rounds that the longest impossible differential could cover for one kind of Feistel-SP structure. Fortunately, our method also applies to some generalized Feistel structures, such as the Type-2 generalized Feistel structure. Then we project our results to zero correlation by the links between impossible differential and zero correlation linear hull. Lastly, as an application of our method, we prove that there do not exist 15-round impossible differential and zero correlation linear hull for LBlock and TWINE.

1 Introduction

Feistel structure and its variants are widely used in the designs of block ciphers, such as the Camellia [1], LBlock [17] and TWINE [13]. Thus the security of Feistel structure against known cryptanalytic techniques attract many attention. Impossible differential cryptanalysis (IDC) [3, 8] and zero correlation linear cryptanalysis (ZCLC) [4] are extensions of the differential cryptanalysis [2] and linear cryptanalysis [10], respectively. It had been shown that these two attacks are very efficient against many block ciphers [5, 6, 9, 14, 15]. However, the security of the Feistel cipher against IDC and ZCLC have not been well studied.

In IDC and ZCLC, the key point is constructing impossible differential (ID) or zero correlation linear hull (ZCLH) that cover as many rounds as possible. Thus to prove the security of Feistel structure against IDC and ZCLC, a common way is to estimate the number of rounds that the longest ID and ZCLH could cover. Based on that, Sun et al. studied the security of the Feistel structure with SP-type round functions (Feistel-SP structure in short) in [12]. They considered the ID and ZCLH that are independent of S-boxes. In the rest of this paper, all the ID and ZCLH represent the impossible differential and zero correlation linear hull that are independent of S-boxes. Furthermore, the authors defined a special class of ID and ZCLH, named independent ID and independent ZCLH (see definition 3 of [12]), respectively. Let b be the size of the S-box and m be the number of S-boxes for the Feistel-SP structure. In the case that $m\le 2^{b-1}-1$, Sun et al. gave upper bounds on the rounds that the longest independent ID and independent ZCLH could cover. Note that the independent ID and independent ZCLH can not cover all the ID and ZCLH for the Feistel-SP structure, and thus Sun’s upper bounds are incomplete.

In this paper, we focus on the Feistel-SP structure whose P is a permutation matrix, and we denote this structure as Feistel$^{*}$-SP structure. We aim to provide upper bounds on the rounds that the longest ID and ZCLH could cover for this structure. The main results of this paper are as follows.

• 1. Based on the characteristic matrix proposed by Kim et al. [7], a new way is introduced to predict the internal difference for Feistel$^{*}$-SP block ciphers.

• 2. A necessary and sufficient condition is given to judge whether a differential is impossible or not for Feistel$^{*}$-SP structure. Combined with our new difference-prediction way, we show that the length of ID for Feistel$^{*}$-SP structure is upper bounded by the diffusion order of the characteristic matrixes. Moreover, based on the links between ID and ZCLH, we project our results to ZCLH.

• 3. For generalized Feistel structures, we show that if their characteristic matrices are 1-property matrixes, then the above method is also valid. For example, the Type-2 generalized Feistel structure [18] has 1-property characteristic matrices.

• 4. Based on our method, we prove that there do not exist 15-round ID and ZCLH for LBlock and TWINE.

Fig. 1

Feistel structure with SP-type round function

The rest of this paper is organized as follows. Section 2 introduces some necessary preliminaries. Section 3 introduces our new way to predict the internal differences for Feistel$^{*}$- SP block ciphers. Section 4 gives upper bounds on the rounds of ID and ZCLH for the Feistel$^{*}$-SP structure. Section 5 makes an application of our method to LBlock and TWINE. Finally, conclusions are drawn in Sect. 6.

2 Preliminaries

Let $\varepsilon$ be a Feistel structure as shown in Fig. 1, where S is the S-box and P is the matrix of the permutation layer. Throughout this paper, we only deal with the P which is a permutation matrix. In [7], the characteristic matrices of $\varepsilon$ are defined as follows.

Definition 1

([7]) Let $\left( X_{0},X_{1},\ldots ,X_{n-1}\right)$ and $\left( Y_{0},Y_{1},\ldots ,Y_{n-1}\right)$ be the input and output of $\varepsilon$, respectively. The $n\times n$ encryption characteristic matrix En of $\varepsilon$ is defined as: if $Y_{i}$ is affected by $X_{j}$, then the (i, j) entry of En is set to $\mathbf {1}$; if $Y_{i}$ is affected by $S(X_{j})$, then the entry of En is set to $\mathbf {s}$; and the (i, j) entry is set to $\mathbf {0}$ if $Y_{i}$ is not affected by $X_{j}$. Reversely, the decryption characteristic matrix of $\varepsilon$ can be defined similarly.

According to Definition 1, we have

$$\begin{aligned} En=\left( \begin{array}{ll} \mathbf {s}\cdot P, &{} \quad I \\ I, &{} \quad O \end{array} \right) \text { and }De=\left( \begin{array}{cc} O, &{} \quad I \\ I, &{} \quad \mathbf {s}\cdot P \end{array} \right) , \end{aligned}$$

where I and O are $\frac{n}{2}\times \frac{n}{2}$ identity and zero matrices, respectively.

Definition 2

([7]) Let $\varvec{\Delta }=\left( \varDelta _{0},\varDelta _{1},\ldots ,\varDelta _{n-1}\right)$ be a difference vector. Then, the characteristic vector $\mathbf {V}=\left( v_{0},v_{1},\ldots ,v_{n-1}\right)$ corresponding to $\varvec{\Delta }$ is defined as

$$\begin{aligned} v_{i}=\left\{ \begin{array}{ll} 0,&{}\quad \text { if }\varDelta _{i}=0, \\ 1^{*},&{}\quad \text { if }\varDelta _{i}\text { is a nonzero fixed difference,} \\ 1,&{}\quad \text { if }\varDelta _{i}\text { is a nonzero nonfixed difference,} \\ 2^{*},&{}\quad \text { if }\varDelta _{i}\text { is a difference of the form }1\oplus 1^{*}, \\ ?,&{}\quad \text { if }\varDelta _{i}\text { is a nonfixed difference.} \end{array} \right. \end{aligned}$$

In [7], the author defined the multiplication between characteristic matrices and characteristic vectors as

$$\begin{aligned} M\cdot \mathbf {V}=\left( \sum _{j=0}^{n-1}(M)_{0,j}\cdot v_{j},\ldots ,\sum _{j=0}^{n-1}(M)_{n-1,j}\cdot v_{j}\right) , \end{aligned}$$

where $(M)_{i,j}$ is the (i, j) entry of the characteristic matrix M for $0\le i,j\le n-1$.

It can be seen that $(M)_{i,j}\cdot v_{j}$ represents the impact of the jth subblock input difference on the ith subblock output difference. The multiplication table of $(M)_{i,j}\cdot v_{j}$ is given in Table 1.

Table 1 Multiplication table of $(M)_{i,j}\cdot v_{j}$ [7]

The addition $(M)_{i,j}\cdot v_{j}+(M)_{i,j^{\prime }}\cdot v_{j^{\prime }}$ represents the exclusive-or of corresponding differences, which is defined as

$$\begin{aligned} \left\{ \begin{array}{l} 0+v=v\quad \text { for }v \in \{0,1^{*},1,2^{*},?\}; \\ ?+v=?\quad \,\,\text { for }v \in \{0,1^{*},1,2^{*},?\}; \\ 1^{*}+1=2^{*}\text { and }1+2^{*}=?\text {.} \end{array} \right. \end{aligned}$$

Let $\varDelta P$ be the input difference of $\varepsilon$. It is shown in [7] that the output difference of $\varDelta P$ after r rounds has the following form

$$\begin{aligned} \overset{r}{\overbrace{En\cdot (En\cdot (\cdots (En\cdot }}\mathbf {V}_{P}))), \end{aligned}$$

(1)

where $\mathbf {V}_{P}$ is the characteristic vector of $\varDelta P$. Thus the rth round output difference of $\varepsilon$ can be predicted round by round based on En. The same also applies to De from the decryption direction. According to Eq. (1), the 1st round output difference can be predicted from entries of En directly. While for $r>1$, we can not predict the rth round output difference from entries of En directly. To solve this problem, we propose an another way to predict the output difference.

3 A new way to predict the internal difference

Let M be the encryption or decryption characteristic matrix of $\varepsilon$ throughout this section. Let $\mathbf {V=}\left( v_{0},v_{1},\ldots ,v_{n-1}\right)$ be the characteristic vector of an input difference. In this section, we will prove that

$$\begin{aligned} \overset{r}{\overbrace{M\cdot (M\cdot (\cdots (M\cdot }}\mathbf {V} )))=M^{r}\cdot \mathbf {V} \end{aligned}$$

(2)

for $r\ge 1$. Hence, the rth round output difference can be predicted from entries of $M^{r}$ directly.

In order to compute $M^{r}$, we need to define the multiplication and addition for entries of M. First, we introduce two new entries $\mathbf {1}+ \mathbf {s}$ and $2\mathbf {s}$. For $v\in \{0,1^{*},1,2^{*},?\}$, set $(\mathbf {1}+\mathbf {s})\cdot v=0$ and $(2\mathbf {s})\cdot v=0$ if $v=0$; set $(\mathbf {1}+\mathbf {s})\cdot 1^{*}=2^{*}$ and $(2\mathbf {s} )\cdot 1^{*}= ?$ if $v=1^{*}$; otherwise, set $(\mathbf {1}+\mathbf {s} )\cdot v= ?$ and $(2\mathbf {s})\cdot v= ?$. Then, the multiplication and addition for elements in $\{\mathbf {0},\mathbf {1},\mathbf {s},\mathbf {1}+ \mathbf {s},2\mathbf {s}\}$ are given as follows.

• Multiplication

  • Set $\mathbf {0}\cdot x=\mathbf {0}$ for $x\in \{\mathbf {0},\mathbf {1}, \mathbf {s},\mathbf {1}+\mathbf {s},2\mathbf {s}\}$, since $\mathbf {0}\cdot (x\cdot v)=\mathbf {0}\cdot v$, where v is an arbitray element of $\{0,1^{*},1,2^{*},?\}$.

  • Set $\mathbf {1}\cdot x=x$ for $x\in \{\mathbf {0},\mathbf {1},\mathbf {s}, \mathbf {1}+\mathbf {s},2\mathbf {s}\}$, since $\mathbf {1}\cdot (x\cdot v)=x\cdot v$.

  • Set $\mathbf {s}\cdot \mathbf {0}=\mathbf {0}$, since $\mathbf {s}\cdot ( \mathbf {0}\cdot v)=\mathbf {0}\cdot v$; set $\mathbf {s}\cdot x=\mathbf {s}$ for $x=\mathbf {1}$ or $\mathbf {s}$, since $\mathbf {s}\cdot (x\cdot v)= \mathbf {s}\cdot v$ when $x=\mathbf {1}$ or $\mathbf {s}$; set $\mathbf {s}\cdot x=2\mathbf {s}$ for $x=\mathbf {1+s}$ or $2\mathbf {s}$, since $\mathbf {s}\cdot (x\cdot v)=(2\mathbf {s})\cdot v$ when $x=\mathbf {1+s}$ or $2\mathbf {s}$.

Note that cases “$(\mathbf {1}+\mathbf {s})\cdot x$” and “$(2\mathbf {s})\cdot x$” will not appear in $M\cdot M^{i}$, thus definitions of “$(\mathbf {1}+ \mathbf {s})\cdot x$” and “$(2\mathbf {s})\cdot x$” are omitted.

• Addition

  • Set $\mathbf {0}+x=x+\mathbf {0}=x$ for $x\in \{\mathbf {0},\mathbf {1}, \mathbf {s},\mathbf {1}+\mathbf {s},2\mathbf {s}\}$, since $\mathbf {0}\cdot v+x\cdot v=x\cdot v+\mathbf {0}\cdot v=x\cdot v$.

  • Set $\mathbf {1}+\mathbf {1}=0$, since $\mathbf {1}\cdot v+\mathbf {1} \cdot v=0$; by the definition of $\mathbf {1}+\mathbf {s}$, we have $\mathbf {1} +\mathbf {s}=\mathbf {s}+\mathbf {1}$; set $\mathbf {1}+(\mathbf {1}+\mathbf {s})=( \mathbf {s}+\mathbf {1})+\mathbf {1}=\mathbf {s}$, since $\mathbf {1}\cdot v+( \mathbf {1}+\mathbf {s})\cdot v=(\mathbf {s}+\mathbf {1})\cdot v+\mathbf {1}\cdot v=\mathbf {s}\cdot v$; set $\mathbf {1}+2\mathbf {s}=2\mathbf {s}+\mathbf {1}=2 \mathbf {s}$, since $\mathbf {1}\cdot v+(2\mathbf {s})\cdot v=(2\mathbf {s} )\cdot v+\mathbf {1}\cdot v=(2\mathbf {s})\cdot v$.

  • Set $x+y=y+x=2\mathbf {s}$ for $x,y\in \{\mathbf {s},\mathbf {1}+\mathbf {s },2\mathbf {s}\}$, since $x\cdot v+y\cdot v=y\cdot v+x\cdot v=(2\mathbf {s} )\cdot v$ for $x,y\in \{\mathbf {s},\mathbf {1}+\mathbf {s},2\mathbf {s}\}$.

It can be seen that the set $\{\mathbf {0},\mathbf {1},\mathbf {s},\mathbf {1}+ \mathbf {s},2\mathbf {s}\}$ is closed under the operations of multiplication and addition. Thus $M^{r}$ is still a matrix over $\{\mathbf {0},\mathbf {1},\mathbf {s}, \mathbf {1}+\mathbf {s},2\mathbf {s}\}$. Based on these definitions, we give some properties that are needed to prove our conclusion.

Corollary 1

If $x_{0}$$\in \{\mathbf {0},\mathbf {1},\mathbf {s}\}$ and $x_{1}\in \left\{ \mathbf {0},\mathbf {1},\mathbf {s},\mathbf {1}+\mathbf {s} ,2\mathbf {s}\right\}$, we have $x_{0}\cdot (x_{1}\cdot v)=(x_{0}\cdot x_{1})\cdot v$ for $v\in \{0,1^{*},1,2^{*},?\}$. If $x_{0},x_{1}\in \left\{ \mathbf {0},\mathbf {1},\mathbf {s},\mathbf {1}+\mathbf {s} ,2\mathbf {s}\right\}$, we have $x_{0}\cdot v+x_{1}\cdot v=(x_{0}+x_{1})\cdot v$ for $v\in \{0,1^{*},1,2^{*},?\}$.

Lemma 1

Let $x_{0}$$\in \{\mathbf {0},\mathbf {1},\mathbf {s}\}$ and $x_{1},x_{2}\in \left\{ \mathbf {0},\mathbf {1},\mathbf {s},\mathbf {1}+\mathbf {s },2\mathbf {s}\right\}$. If $\left( x_{1},x_{2}\right) \ne (\mathbf {1}, \mathbf {1})$, $(\mathbf {1},\mathbf {1}+\mathbf {s})$ and $(\mathbf {1}+\mathbf {s },\mathbf {1})$, then we have

$$\begin{aligned} x_{0}\cdot (x_{1}\cdot v_{1}+x_{2}\cdot v_{2})=(x_{0}\cdot x_{1})\cdot v_{1}+(x_{0}\cdot x_{2})\cdot v_{2} \end{aligned}$$

for $v_{1},v_{2}\in \{0,1^{*},1,2^{*},?\}$.

Proof

When $x_{0}\in \{\mathbf {0},\mathbf {1}\}$, the conclusion is obvious. Thus, we only need to prove this lemma for $x_{0}=\mathbf {s}$.

Case 1$x_{1}$ or $x_{2}$ equals to $\mathbf {0}$. Without loss of generality, we set $t_{1}=0$. Then we have $x_{0}\cdot (x_{1}\cdot v_{1}+x_{2}\cdot v_{2})=\mathbf {s}\cdot (x_{2}\cdot v_{2})$ and $(x_{0}\cdot x_{1})\cdot v_{1}+(x_{0}\cdot x_{2})\cdot v_{2}=(\mathbf {s}\cdot x_{2})\cdot v_{2}$. According to Corollary 1, we have $\mathbf {s}\cdot (x_{2}\cdot v_{2})=(\mathbf {s}\cdot x_{2})\cdot v_{2}$.

Case 2$x_{1}$ or $x_{2}$ equals to $\mathbf {1}$. Without loss of generality, we can set $x_{1}=\mathbf {1}$. Since $\left( x_{1},x_{2}\right) \ne (\mathbf {1},\mathbf {1})$ and $(\mathbf {1},\mathbf {1}+\mathbf {s})$, $x_{2}$ should be $\mathbf {s}$ or $2\mathbf {s}$. If $x_{2}=\mathbf {s}$, then we have $x_{0}\cdot (x_{1}\cdot v_{1}+x_{2}\cdot v_{2})=\mathbf {s}\cdot (v_{1}+ \mathbf {s}\cdot v_{2})$ and $(x_{0}\cdot x_{1})\cdot v_{1}+(x_{0}\cdot x_{2})\cdot v_{2}=\mathbf {s}\cdot v_{1}+\mathbf {s}\cdot v_{2}$. Since

$$\begin{aligned} \mathbf {s}\cdot (v_{1}+\mathbf {s}\cdot v_{2})=\left\{ \begin{array}{ll} \mathbf {s}\cdot v_{2},&{} \quad \text {if }v_{1}=0, \\ \mathbf {s}\cdot v_{1},&{} \quad \text {if }v_{2}=0, \\ ?, &{} \quad \text {if }v_{1}\ne 0\text { and }v_{2}\ne 0\text {.} \end{array} \right. \end{aligned}$$

and

$$\begin{aligned} \mathbf {s}\cdot v_{1}+\mathbf {s}\cdot v_{2}=\left\{ \begin{array}{ll} \mathbf {s}\cdot v_{2},&{} \quad \text {if }v_{1}=0, \\ \mathbf {s}\cdot v_{1},&{} \quad \text {if }v_{2}=0, \\ ?,&{} \quad \text {if }v_{1}\ne 0 \text { and }v_{2}\ne 0\text {.} \end{array} \right. \end{aligned}$$

(3)

we have $\mathbf {s}\cdot (v_{1}+\mathbf {s}\cdot v_{2})=\mathbf {s}\cdot v_{1}+ \mathbf {s}\cdot v_{2}$. If $x_{2}=2\mathbf {s}$, then $\mathbf {s}\cdot (v_{1}+x_{2}\cdot v_{2})=\mathbf {s}\cdot (v_{1}+2\mathbf {s}\cdot v_{2})$ and $\mathbf {s}\cdot v_{1}+(\mathbf {s}\cdot 2\mathbf {s})\cdot v_{2}=\mathbf {s} \cdot v_{1}+2\mathbf {s}\cdot v_{2}$. Since

$$\begin{aligned} \mathbf {s}\cdot (v_{1}+2\mathbf {s}\cdot v_{2})=\left\{ \begin{array}{ll} \mathbf {s}\cdot v_{1},&{}\quad \text {if }v_{2}=0, \\ ?,&{}\quad \text {if }v_{2}\ne 0\text {.} \end{array} \right. \end{aligned}$$

and

$$\begin{aligned} \text { }\mathbf {s}\cdot v_{1}+2\mathbf {s}\cdot v_{2}=\left\{ \begin{array}{ll} \mathbf {s}\cdot v_{1},&{}\quad \text {if }v_{2}=0, \\ ?,&{}\quad \text {if }v_{2}\ne 0\text {.} \end{array} \right. \end{aligned}$$

equation $\mathbf {s}\cdot (v_{1}+2\mathbf {s}\cdot v_{2})=\mathbf {s}\cdot v_{1}+2\mathbf {s}\cdot v_{2}$ holds.

Case 3$x_{1}=\mathbf {s}$ or $x_{2}=\mathbf {s}$. Without loss of generality, we can set $x_{1}=\mathbf {s}$. If $x_{2}=\mathbf {s}$, then we have $\mathbf {s}\cdot (x_{1}\cdot v_{1}+x_{2}\cdot v_{2})=\mathbf {s}\cdot ( \mathbf {s}\cdot v_{1}+\mathbf {s}\cdot v_{2})$ and $(\mathbf {s}\cdot x_{1})\cdot v_{1}+(\mathbf {s}\cdot x_{2})\cdot v_{2}=\mathbf {s}\cdot x_{1}+ \mathbf {s}\cdot x_{2}$. Note that

$$\begin{aligned} \mathbf {s}\cdot (\mathbf {s}\cdot v_{1}+\mathbf {s}\cdot v_{2})=\left\{ \begin{array}{ll} \mathbf {s}\cdot v_{2},&{}\quad \text { if }v_{1}=0, \\ \mathbf {s}\cdot v_{1},&{}\quad \text { if }v_{2}=0, \\ ?,&{}\quad \text { if }v_{1}\ne 0\text { and }v_{2}\ne 0, \end{array} \right. \end{aligned}$$

combined with Eq. (3), we have $\mathbf {s}\cdot (\mathbf {s} \cdot v_{1}+\mathbf {s}\cdot v_{2})=\mathbf {s}\cdot v_{1}+\mathbf {s}\cdot v_{2}$. If $x_{2}=\mathbf {1}+\mathbf {s}$ or $2\mathbf {s}$, then we have

$$\begin{aligned} \mathbf {s}\cdot (\mathbf {s}\cdot v_{1}+x_{2}\cdot v_{2})=\left\{ \begin{array}{ll} \mathbf {s}\cdot v_{1},&{}\quad \text {if }v_{2}=0, \\ ?,&{}\quad \text {if }v_{2}\ne 0\text {.} \end{array} \right. \end{aligned}$$

For $\mathbf {s}\cdot v_{1}+(\mathbf {s}\cdot x_{2})\cdot v_{2}$, we have the same conclusion, which implies $\mathbf {s}\cdot (\mathbf {s}\cdot v_{1}+x_{2}\cdot v_{2})=\mathbf {s}\cdot v_{1}+(\mathbf {s}\cdot x_{2})\cdot v_{2}$.

Case 4 When $x_{1},x_{2}\in \{\mathbf {1}+\mathbf {s},2\mathbf {s}\}$ , we have

$$\begin{aligned} \mathbf {s}\cdot (x_{1}\cdot v_{1}+x_{2}\cdot v_{2})=\left\{ \begin{array}{ll} 0,&{}\quad \text {if }v_{1}=v_{2}=0 \\ ?,&{}\quad \text {otherwise.} \end{array} \right. \end{aligned}$$

It can be verified that $(\mathbf {s}\cdot x_{1})\cdot v_{1}+(\mathbf {s} \cdot x_{2})\cdot v_{2}$ has the same result. Thus, we have $\mathbf {s}\cdot (x_{1}\cdot v_{1}+x_{2}\cdot v_{2})=(\mathbf {s}\cdot x_{1})\cdot v_{1}+(\mathbf {s}\cdot x_{2})\cdot v_{2}$ for $x_{1},x_{2}\in \{\mathbf {1}+\mathbf {s},2 \mathbf {s}\}$. $\square$

Remark 1

Since for the following conclusions, their proofs for $M=En$ are similar with that for $M=De$, we only give their proofs for $M=En$.

Lemma 2

Let $x_{1}$ and $x_{2}$ be any two elements in the ith row of $M^{t}$ for $1\le i\le n$ and $t\ge 1$. Then $\left( x_{1},x_{2}\right)$ can not equal to $(\mathbf {1},\mathbf {1})$, $(\mathbf {1 },\mathbf {1}+\mathbf {s})$ or $(\mathbf {1}+\mathbf {s},\mathbf {1})$.

Proof

We prove this lemma by mathematical induction on t. If $t=1$, then $x_{1}$$x_{2}$ are two elements in the ith row of M, and thus this lemma can be gotten immediately. Assume this result is true for $t<r$. Next we prove this result for $t=r$. When $t=r$, we have $M^{r}=M\cdot M^{r-1}$. Let

$$\begin{aligned} M^{r-1}=\left( \begin{array}{cc} M_{0}, &{} M_{1} \\ M_{2}, &{} M_{3} \end{array} \right) . \end{aligned}$$

Then

$$\begin{aligned} M^{r}=\left( \begin{array}{rr} s\cdot P, &{} I \\ I, &{} O \end{array} \right) \cdot \left( \begin{array}{cc} M_{0}, &{} M_{1} \\ M_{2}, &{} M_{3} \end{array} \right) =\left( \begin{array}{rr} M_{0}^{^{\prime }}+M_{2}, &{} M_{1}^{^{\prime }}+M_{3} \\ M_{0}, &{} M_{1} \end{array} \right) . \end{aligned}$$

where $M_{0}^{^{\prime }}=\mathbf {s}\cdot P\cdot M_{0}$ and $M_{1}^{^{\prime }}=\mathbf {s}\cdot P\cdot M_{1}$. Since $\mathbf {s}\cdot x\in \{\mathbf {0}, \mathbf {s},2\mathbf {s}\}$ for $x\in \{\mathbf {0},\mathbf {1},\mathbf {s}, \mathbf {1}+\mathbf {s},2\mathbf {s}\}$, all entries of $M_{0}^{^{\prime }}$ and $M_{1}^{^{\prime }}$ belong to $\left\{ \mathbf {0},\mathbf {s},2\mathbf {s} \right\}$. For any $0\le j_{0}\le \frac{n-1}{2}<j_{1}\le n-1$ and $0\le i\le n/2-1$, we have

$$\begin{aligned} \left\{ \begin{array}{c} \left( M^{r}\right) _{i,j_{0}}=\left( M_{0}^{^{\prime }}\right) _{i,j_{0}}+\left( M_{2}\right) _{i,j_{0}} \\ \left( M^{r}\right) _{i,j_{1}}=\left( M_{1}^{^{\prime }}\right) _{i,j_{1}}+\left( M_{3}\right) _{i,j_{1}} \end{array} \right. . \end{aligned}$$

Since $((M_{2}) _{i,j_{0}},(M_{3})_{i,j_{1}}) \ne (\mathbf {1},\mathbf {1})$, $(\mathbf {1},\mathbf {1}+ \mathbf {s})$ or $(\mathbf {1}+\mathbf {s},\mathbf {1})$ by assumption and $(M_{0}^{^{\prime }}) _{i,j_{0}}, (M_{0}^{^{\prime }}) _{i,j_{0}}\in \{\mathbf {0},\mathbf {s},2\mathbf {s}\}$, we have $((M^{r}) _{i,j_{0}},( M^{r}) _{i,j_{1}}) \ne (\mathbf {1},\mathbf {1})$, $(\mathbf {1},\mathbf {1}+\mathbf {s})$ or $(\mathbf {1}+\mathbf {s},\mathbf {1})$. For $0\le j_{0}<j_{1}\le \frac{n-1}{2}$ or $\frac{n+1}{2}\le j_{0}<j_{1}\le n-1$, we have similar conclusions. Thus pairs $(\mathbf {1},\mathbf {1}),(\mathbf {1},\mathbf {1}+\mathbf {s})$ and $(\mathbf {1}+\mathbf {s},\mathbf {1})$ do not appear in the ith row of $M^{r}$ for $0\le i\le \frac{n-1}{2}$. $\square$

Lemma 3

The equation $M\cdot (M^{t}\cdot \mathbf {V})=(M\cdot M^{t})\cdot \mathbf {V}$ holds for $t\ge 1$.

Proof

Let $M=\left( a_{i,j}\right) _{n\times n}$ and $M^{t}=\left( b_{i,j}\right) _{n\times n}$. Since

$$\begin{aligned} M^{t}\cdot \mathbf {V}=\left( \sum _{j=0}^{n-1}b_{0,j}\cdot v_{j},\ldots ,\sum _{j=0}^{n-1}b_{n-1,j}\cdot v_{j}\right) , \end{aligned}$$

we have

$$\begin{aligned} M\cdot (M^{t}\cdot \mathbf {V}_{P})=\left( \sum _{m=0}^{n-1}a_{0,m}\cdot u_{m},\ldots ,\sum _{m=0}^{n-1}a_{n-1,m}\cdot u_{m}\right) , \end{aligned}$$

(4)

where $u_{m}=\sum _{j=0}^{n-1}b_{m,j}\cdot v_{j}$ for $0\le m\le n-1$. On one hand, by Corollary 1, Lemmas 1 and 2, we have

$$\begin{aligned} \sum _{m=0}^{n-1}a_{k,m}\cdot u_{m}= & {} \sum _{m=0}^{n-1}a_{k,m}\cdot \left( \sum _{j=0}^{n-1}b_{m,j}\cdot v_{j}\right) \nonumber \\= & {} \sum _{m=0}^{n-1}\sum _{j=0}^{n-1}(a_{k,m}\cdot b_{m,j})\cdot v_{j} \nonumber \\= & {} \sum _{j=0}^{n-1}\left( \sum _{m=0}^{n-1}a_{k,m}\cdot b_{m,j}\right) \cdot v_{j}. \end{aligned}$$

(5)

On the other hand, we have

$$\begin{aligned} (M\cdot M^{t})\cdot \mathbf {V}= & {} \left( \sum _{m=0}^{n-1}a_{k,m}\cdot b_{m,j}\right) _{n\times n}\cdot \mathbf {V} \nonumber \\= & {} \left( \sum _{j=0}^{n-1}\left( \sum _{m=0}^{n-1}a_{0,m}\cdot b_{m,j}\right) \cdot v_{j},\ldots ,\sum _{j=0}^{n-1}\left( \sum _{m=0}^{n-1}a_{n-1,m}\cdot b_{m,j}\right) \cdot v_{j}\right) . \quad \quad \end{aligned}$$

(6)

By Eqs. (4), (5) and (6), this lemma is gotten. $\square$

By Lemma 3, we know that Eq. (2) holds. Notice that when r is big enough, there will be no entries “$\mathbf {0}$” and “$\mathbf {1}$” in $M^{t}$. We denote the minimum integer t, such that there are no entries “$\mathbf {0}$” and “$\mathbf {1}$” in $M^{t}$, as the diffusion order of M, represented by R(M). Then we present some properties that are relevant to the diffusion order.

Corollary 2

If $r=R(M)$, then we have

$$\begin{aligned} \left( M^{r}\cdot \mathbf {V}\right) _{i}=1,2^{*}\text { or }? \end{aligned}$$

for $0\le i\le n-1$, where $\left( M^{r}\cdot \mathbf {V}\right) _{i}$ represents the ith entry of vector $\left( M^{r}\cdot \mathbf {V}\right) _{i}$. If $r=R(M)+1$, then we have

$$\begin{aligned} \left\{ \begin{array}{l} \left( M^{r}\cdot \mathbf {V}\right) _{i}=?\text { and }\left( M^{r}\cdot \mathbf {V}\right) _{i+n/2-1}=1,2^{*}\text { or }?\text { when }M=En,\\ \left( M^{r}\cdot \mathbf {V}\right) _{i+n/2-1}=?\text { and }\left( M^{r}\cdot \mathbf {V}\right) _{i}=1,2^{*}\text { or }?\text { when }M=De \end{array} \right. \end{aligned}$$

for $0\le i\le n/2-1$. If $r>R(M)+1$, then we have

$$\begin{aligned} \left( M^{r}\cdot \mathbf {V}\right) _{i}= ? \end{aligned}$$

for $0\le i\le n-1$.

Proof

Since $\mathbf {V}$ is nonzero, there must be a nonzero entry in $\mathbf {V}$ . Without loss of generality, we assume $v_{j}$ is nonzero, i.e. $v_{j}=1$ or $1^{*}$. When $r=R(M)$, we know that there are no entries “$\mathbf {0}$” and “$\mathbf {1}$” in $M^{r}$. Thus, we have $\left( M^{r}\right) _{i,j}=\mathbf {s},\mathbf { 1}+\mathbf {s}$ or $2\mathbf {s}$ for $0\le i\le n-1$. Since $v_{j}=1$ or $1^{*}$, we have $(M^{r})_{i,j}\cdot v_{j}=1$, $2^{*}$, or ?, which implies that $\left( M^{r}\cdot \mathbf {V}\right) _{i}=1,2^{*}$ or ?.

When $r=R(M)+1$, we know that

$$\begin{aligned} \left\{ \begin{array}{l} \left( M^{r}\cdot \mathbf {V}\right) _{i}=\mathbf {s}\cdot (M^{r-1}\cdot \mathbf {V})_{P_{t}^{-1}(i)}+\left( M^{r-1}\cdot \mathbf {V}\right) _{i+n/2-1}\\ \left( M^{r}\cdot \mathbf {V}\right) _{i+n/2-1}=\left( M^{r-1}\cdot \mathbf {V} \right) _{i} \end{array} \right. \end{aligned}$$

for $0\le i\le n/2-1$, where $P_{t}$ is the permutation on $\{0,1,\ldots ,n/2-1\}$ induced by matrix P. Note that $\left( M^{r-1}\cdot \mathbf {V} \right) _{j}=1,2^{*}$ or ? for $0\le j\le n-1$. Thus, we have $\left( M^{r}\cdot \mathbf {V}\right) _{i}=?$ and $\left( M^{r}\cdot \mathbf {V} \right) _{i+n/2-1}=1,2^{*}$ or ? for $0\le i\le n/2-1$.

The case for $r>R(M)+1$ can be proved similarly with the case that $r=R(M)+1$. $\square$

4 Upper bounds on the rounds of ID and ZCLH for ${\varepsilon }$

In this section, we first introduce Wu and Wang’s method which aims to searching ID. Then we give upper bounds on the rounds of ID and ZCLH.

4.1 Wu and Wang’s method

In [16], Wu and Wang introduced the difference propagation system, which describes the difference propagation behavior for a block cipher. For a Feistel cipher, let $\varDelta X_{i-1}= (\varDelta X_{i-1,j}) _{0\le j\le n/2-1}$ and $\varDelta X_{i}= (\varDelta X_{i,j}) _{0\le j\le n/2-1}$ respectively represent the left and the right branch input difference of the ith round. Then the difference propagation system can be built as:

$$\begin{aligned} \left\{ \begin{array}{ll} S(\varDelta X_{i,j})\oplus \varDelta Y_{i,j}=0 &{} \quad \text { for }1\le i\le r\text { and } 0\le j\le n/2-1, \\ P\cdot \varDelta Y_{i}^{T}\oplus \varDelta X_{i-1}\oplus \varDelta X_{i}=0 &{}\quad \text { for } 1\le i\le r. \end{array} \right. \end{aligned}$$

(7)

where $\varDelta Y_{i}= (\varDelta Y_{i,j})_{0\le j\le n/2-1}$ is the output difference of $\varDelta X_{i}$ after the S-boxes. This system can be further divided into two subsystems: $\mathcal {L}$ and $\mathcal {NL}$, where $\mathcal {L}$ includes all linear equations and $\mathcal {NL}$ includes all nonlinear equations.

Based on the difference proposition system, Wu and Wang introduced an algorithm to search ID for Feistel ciphers. Throughout this paper, we call this algorithm as WW-algorithm. The idea of this algorithm is simple: given the plaintext and ciphertext differences, the internal differences can be predicted based on system (7), and some new “known” variables can be gotten. Then based on these known variables, the algorithm can continue predict new information. This progress will terminate if a contradiction is detected or no new information is gotten.

Fig. 2

3-round Feistel structure

Then we introduce that how does the algorithm predict information from the difference proposition system.

Lemma 4

([16]) Suppose $\mathcal {L}$ has solutions and $\mathcal {L}^{\prime }$ is the reduced augmented matrix of $\mathcal {L}$, then

• (1) If an affine equation with only one variable, i.e., $\varDelta X\oplus c=0$ (c is a constant), is found in $\mathcal {L}^{\prime }$, then $\varDelta X\ne 0$ if and only if $c\ne 0$.

• (2) If a linear equation with two variables, i.e., $\varDelta X\oplus \varDelta Y=0$, is found in $\mathcal {L}^{\prime }$, then $\varDelta X\ne 0$ if and only if $\varDelta Y\ne 0$.

Lemma 5

([16]) Suppose S is a bijective S-box. For an equation $S(\varDelta X)\oplus \varDelta Y=0$, $\varDelta X$ is zero (resp. nonzero) if and only if $\varDelta Y$ is zero (resp. nonzero).

Based on the above principles, the WW-algorithm can predict the internal differences when the plaintext and ciphertext differences are given. Throughout this paper, let $\varDelta P$ and $\varDelta C$ represent the plaintext and the ciphertext difference, respectively. Denote $\varDelta P=\varDelta P_{L}||\varDelta P_{R}$ (resp. $\varDelta C=\varDelta C_{L}||\varDelta C_{R}$), then the difference $\varDelta X_{2}$ in Fig. 2 can be computed by $\varDelta X_{2}=S(\varDelta P_{L})\oplus \varDelta P_{R}$ (resp. $\varDelta X_{2}=S(\varDelta C_{R})\oplus \varDelta C_{L}$). This means that the difference $\varDelta X_{2}$ can be gotten merely from $\varDelta P$ (resp. $\varDelta C$). Besides, since $\varDelta X_{2}=S^{-1}(\varDelta P_{L}\oplus \varDelta C_{R})$, then the difference $\varDelta X_{2}$ can also be gotten from $\varDelta P$ combined with $\varDelta C$. Based on these observations, we divide the information gotten from WW-algorithm into three classes: the first class information represented by $\mathcal {A}$ is the information gotten from $\varDelta P$; the second class information represented by $\mathcal {B}$ is the information gotten from $\varDelta C$; while the third class information represented by $\mathcal {C}$ is the information gotten from $\varDelta P$ combined with $\varDelta C$. From Lemmas 4 and 5, we can get that the elements in $\mathcal {A}$, $\mathcal {B}$ and $\mathcal {C}$ have the difference forms 0, $1^{*}$ or 1.

Then two conditions are given in [16] to judge whether there is a contradiction for the differential $\varDelta P\rightarrow \varDelta C$.

Proposition 1

([16]) For an r-round Feistel cipher, differential $\varDelta P\rightarrow \varDelta C$ is an impossible differential if one of the following two situations happens:

• (i) System $\mathcal {L}$ has no solution, i.e., the rank of its coefficient matrix is not equal to the rank of its augment matrix.

• (ii) There exists a variable of system (7) with both zero and nonzero values.

In [11], Sun et. al. proved that the WW-algorithm can find all truncated impossible differentials for Feistel-SP blocks, and so we have

Corollary 3

Differential $\varDelta P\rightarrow \varDelta C$ is an ID of a Feistel-SP structure if and only if one of the two conditions in Proposition 1 holds.

Based on the above theories, we give uppers bound on the rounds of ID and ZCLH for $\varepsilon$.

4.2 Upper bounds on the rounds of ID and ZCLH

4.2.1 Upper bound for ID

Theorem 1

If $r\ge R(En)+R\left( De\right) +1$, then there does not exist r-round ID for $\varepsilon$.

Before proving this theorem, we still need some other properties.

Lemma 6

The following two conditions are equivalent.

• (1) Differential $\varDelta P\rightarrow \varDelta C$ is an r-round ID of $\varepsilon$;

• (2) There exists an variable $\varDelta X_{i,j}$ in the difference proposition system such that $\varDelta X_{i,j}$ has two unequal values.

Proof

“(1)$\rightarrow$(2)”. By Corollary 3, we know that $\varDelta P\rightarrow \varDelta C$ is an ID if and only if one of the two situations in Proposition 1 happens.

For situation (ii), there is an variable with both zero and nonzero values. If the variable is some $\varDelta X_{i,j}$, then this lemma is obvious. If the variable is some $\varDelta Y_{i,j}$, then $\varDelta X_{i,j}$ is also an variable with both zero and nonzero values since $S(\varDelta X_{i,j})=\varDelta Y_{i,j}$.

For situation (i), if we fix the order of all variables in system (7) as

$$\begin{aligned} x=\left[ \varDelta X_{0},\varDelta X_{1},\varDelta X_{2},\varDelta X_{3},\ldots ,\varDelta X_{r},\varDelta X_{r+1},\varDelta Y_{1},\ldots ,\varDelta Y_{r}\right] , \end{aligned}$$

then the linear system $\mathcal {L}$ can be represented as $A\cdot x^{T}=0$, where

$$\begin{aligned} A=\left[ \begin{array}{llllllllllll} I &{} \quad O &{} \quad I &{}\quad O &{} \quad \cdots &{} \quad O &{} \quad O &{}\quad O &{}\quad P &{}\quad O &{} \quad \cdots &{} \quad O \\ O &{}\quad I &{}\quad O &{}\quad I &{}\quad \cdots &{} \quad O &{}\quad O &{}\quad O &{}\quad O &{}\quad P &{} \quad \cdots &{}\quad O \\ \vdots &{}\quad \vdots &{}\quad \vdots &{}\quad \vdots &{}\quad \ddots &{}\quad \vdots &{}\quad \vdots &{}\quad \vdots &{}\quad \vdots &{} \quad \vdots &{} \quad \ddots &{} \quad \vdots \\ O &{}\quad O &{}\quad O &{}\quad O &{}\quad \cdots &{}\quad I &{}\quad O &{}\quad I &{}\quad O &{}\quad O &{}\quad \cdots &{}\quad P \end{array} \right] . \end{aligned}$$

Since that P is a permutation matrix, any two equations in $\mathcal {L}$ have at most one common term, which is some $\varDelta X_{i,j}$. Hence we know that if each linear equation of $\mathcal {L}$ has two unknown variables, then the equations in $\mathcal {L}$ are linearly independent, i.e., system $\mathcal {L}$ has solutions. Moving all known variables to the right of the equation. Thus if system $\mathcal {L}$ has no solution, then there exist two rows such that $\varDelta X_{i,j}=u_{0}$ and $\varDelta X_{i,j}=u_{1}$ with $u_{0}\ne u_{1}$.

(2)$\rightarrow$(1). Obviously. $\square$

Lemma 7

Let $u_{0}$ and $u_{1}$ be the two unequal values of $\varDelta X_{i,j}$ in Lemma 6. Then the pair $(u_{0},u_{1})$ can not confirm to the following forms

$$\begin{aligned} \left\{ \begin{array}{ll} (?,x)\text { or }(x,?), &{}\quad \text { where }x\in \{0,1^{*},1,2^{*},?\}\text {, } \\ (1,x)\text { or }(x,1), &{}\quad \text { where }x\in \{1^{*},1,2^{*}\}, \\ (2^{*},x)\text { or }(x,2^{*}), &{}\quad \text { where }x\in \{0,2^{*}\}. \end{array} \right. \end{aligned}$$

Proof

Note that ? represents a non-fixed difference, thus if difference $\varDelta X_{i,j}$ confirms to ?, then $\varDelta X_{i,j}$ can assume any of the $2^{b}$ values, where b is the bit number of $\varDelta X_{i,j}$. Thus, if $u_{0}$ or $u_{1}$ confirms to ?, then $u_{0}$ will equal to $u_{1}$ with a positive probability. Similarly, if one of $u_{0}$ and $u_{1}$ confirms to 1 and the other one is not the zero difference, then $u_{0}$ will equal to $u_{1}$ with a positive probability. If $u_{0}$ or $u_{1}$ confirms to $2^{*}$, without loss of generality assume $u_{0}$ confirms to $2^{*}$. Then $u_{0}$ can be disposed as $u_{0}=u_{0}^{\prime }\oplus \varDelta$, where $u_{0}^{\prime }$ is a nonzero fixed difference and $\varDelta$ is a nonzero non-fixed difference. Thus, $u_{0}$ can equal to any value except $u_{0}^{\prime }$. Thus, if $u_{1}$ confirms to 0 or $2^{*}$, then $u_{0}$ will equal to $u_{1}$ with a positive probability. $\square$

Next we present some properties about the internal differences based on the characteristic matrices.

Lemma 8

Let $\mathbf {V}_{p}$ and $\mathbf {V}_{c}$ be the characteristic vectors of $\varDelta P$ and $\varDelta C$, respectively. If the value of $\varDelta X_{i,j} (0\le i\le r,0\le j\le n/2-1)$ is gotten from $\varDelta P$ (resp. $\varDelta C$), then the value of $\varDelta X_{i,j}$ confirms to $(En^{i}\cdot \mathbf {V}_{p}) _{j+n/2-1}$(resp. $(De^{r-i}\cdot \mathbf {V}_{c}) _{j+n/2-1}$).

Proof

If the value of $\varDelta X_{i,j}$ is gotten from $\varDelta P$ (resp. $\varDelta C$ ), then $\varDelta X_{i,j}$ can be seen as the output difference of $\varDelta P$ (resp. $\varDelta C$) after i (resp. $r-i$) rounds encryption (resp. decryption). Thus by the analysis of Sect. 3, we know that the value of $\varDelta X_{i,j}$ confirms to $(En^{i}\cdot \mathbf {V}_{p}) _{j}$ (resp. $(De^{r-i}\cdot \mathbf {V} _{c}) _{j}$). $\square$

Lemma 9

The third class information $\mathcal {C}$ is empty if $r\ge R(En)+R(De)+1$.

Proof

We prove this lemma by negative approach. Assuming that $\mathcal {C}$ is nonempty, then we will show that there always exists a contradiction. Since $\mathcal {C}$ is nonempty, there exist an element v in the $\mathcal { C}$, which is gotten before all the other elements in $\mathcal {C}$. Without loss of generality, we set that v indicates the difference value of $\varDelta X_{i,j}$.

Replacing $\varDelta Y_{i,j}$ by $S(\varDelta X_{i,j})$ in system (7), then there are only three equations containing $\varDelta X_{i,j}$, which are

$$\begin{aligned} \begin{array}{l} \text {(i) }S(\varDelta X_{i-1,P_{t}^{-1}(j)})\oplus \varDelta X_{i-2,j}\oplus \varDelta X_{i,j}=0, \\ \text {(ii) }S(\varDelta X_{i,j})\oplus \varDelta X_{i-1,P_{t}(j)}\oplus \varDelta X_{i+1,P_{t}(j)}=0, \\ \text {(iii) }S(\varDelta X_{i+1,P_{t}^{-1}(j)})\oplus \varDelta X_{i,j}\oplus \varDelta X_{i+2,j}=0. \end{array} \end{aligned}$$

We can see the information of $\varDelta X_{i,j}$ must be predicted through one of the three equations.

If the information is predicted through equation (i), then variables $\varDelta X_{i-1,P_{t}^{-1}(j)}$ and $\varDelta X_{i-2,j}$ must be known before $\varDelta X_{i,j}$. Let $v_{i-1,P_{t}^{-1}(j)}$ and $v_{i-2,j}$ respectively be difference values of $\varDelta X_{i-1,P_{t}^{-1}(j)}$ and $\varDelta X_{i-2,j}$ gotten by the WW-algorithm. Note that v is gotten before all the other element in $\mathcal {C}$, thus we have

$$\begin{aligned} v_{i-1,P_{t}^{-1}(j)}\in & {} \mathcal {A},v_{i-2,j}\in \mathcal {B},\text { or}\\ v_{i-1,P_{t}^{-1}(j)}\in & {} \mathcal {B},v_{i-2,j}\in \mathcal {A}. \end{aligned}$$

If $v_{i-1,P_{t}^{-1}(j)}\in \mathcal {A},v_{i-2,j}\in \mathcal {B}$, then $v_{i-1,P_{t}^{-1}(j)}$ and $v_{i-1,j}$ confirms to $\left( En^{i-1}\cdot \mathbf {V}_{p}\right) _{P_{t}^{-1}(j)+n/2-1}$ and $\left( De^{r-i+2}\cdot \mathbf {V}_{c}\right) _{j+n/2-1}$, respectively, by Lemma 8. As $r\ge R(En)+R(De)+1$, if $i-1\le R(En)+1$ then $r-i+2\ge R(De)+1$. By Corollary 2, we know that $v_{i-2,j}$ confirms to ?, which contradicts with that $v_{i-2,j}\in \mathcal {B}$. If $i-1\ge R(En)+2$, then we have $v_{i-1,P_{t}^{-1}(j)}$ confirms to ? by Corollary 2, which contradicts with that $v_{i-1,P_{t}^{-1}(j)}\in \mathcal {A}$.

If $v_{i-1,P_{t}^{-1}(j)}\in \mathcal {B},v_{i-2,j}\in \mathcal {A}$, then $v_{i-1,P_{t}^{-1}(j)}$ and $v_{i-2,j}$ confirm to $\left( De^{r-i+1}\cdot \mathbf {V}_{c}\right) _{P_{t}^{-1}(j)+n/2+1}$ and $\left( En^{i-2}\cdot \mathbf {V}_{p}\right) _{j+n/2-1}$, respectively. If $i-2\le R(En)-1$, then $r-i+1\ge R(De)+1$ and $v_{i-1,P_{t}^{-1}(j)}$ confirms to ? by Corollary 2. It contradicts with that $v_{i-1,P_{t}^{-1}(j)}\in \mathcal {B}$. If $i-2=R(En)$, then $r-i+1\ge R(De)$ . By Corollary 2, we know that $v_{i-1,P_{t}^{-1}(j)}$ and $v_{i-2,j}$ confirm to $1,2^{*}$ or ?. Since

$$\begin{aligned} \varDelta X_{i,j}=S(\varDelta X_{i-1,P_{t}^{-1}(j)})\oplus \varDelta X_{i-2,j}, \end{aligned}$$

(8)

we have v confirms to ?, which contradicts with that $v\in \mathcal {C}$. If $i-2=R(En)+1$, then $r-i+1\ge R(De)-1$. On one hand, we have $\left( En^{i-2}\cdot \mathbf {V}_{p}\right) _{j+n/2-1}=1,2^{*}$ or ?. On the other hand, note that $\left( De^{r-i+1}\cdot \mathbf {V}_{c}\right) _{P_{t}^{-1}(j)+n/2+1}=\left( De^{r-i+2}\cdot \mathbf {V}_{c}\right) _{P_{t}^{-1}(j)}$ and $r-i+2\ge R(De)$, we have $\left( De^{r-i+1}\cdot \mathbf {V}_{c}\right) _{P_{t}^{-1}(j)+n/2+1}=1,2^{*}$ or ?. By Eq. (8), we have v confirms to ?, which contradicts with that $v\in \mathcal {C}$. If $i-2\ge R(En)+2$, then $v_{i-2,j}$ confirms to ?, which contradicts with that $v_{i-1,P_{t}^{-1}(j)}\in \mathcal {A}$.

When the information of $\varDelta X_{i,j}$ is gotten from equation (i) or (ii), we have the similar proofs. Thus the assumption that $\mathcal {C}$ is nonempty is invalid. $\square$

By the proof of Lemma 9, we can see that the internal differences gotten from $\varDelta P$ together with $\varDelta C$ confirm to the form ? when $r\ge R(En)+R(De)+1$. Then we give the proof of Theorem 1.

Fig. 3

Dual structure of $\varepsilon$

Proof

(Proof of Theorem 1) We prove this theorem by negative approach. Assuming that $\varDelta P\rightarrow \varDelta C$ be an r-round ID of $\varepsilon ^{r}$. By Lemma 6, we know that there exists an variable $\varDelta X_{i,j}$ with two unequal values. By Lemmas 7 and 9, these two values must come from $\varDelta P$ and $\varDelta C$, respectively. On one hand, we have that the two values can not confirm to the forms given in Lemma 7.

On the other hand, we have that the two values of $\varDelta X_{i,j}$ should confirm to $(En^{i}\cdot \mathbf {V}_{P})_{n/2+j}$ and $(De^{r-i}\cdot \mathbf {V}_{C})_{n/2+j}$, respectively. If $i>m+1$, we have $(En^{i}\cdot \mathbf {V}_{P})_{n/2+j}=$ ? by Corollary 1. If $i=m+1$, then $r-i\ge m$, which implies that $(En^{i}\cdot \mathbf {V} _{P})_{n/2+j}=1,2^{*}$ or ? and $(De^{r-i}\cdot \mathbf {V} _{C})_{n/2+j}=$$1,2^{*}$ or ? by Corollary 1. If $i\le m$, then we have $r-i\ge m+1$ and $(De^{r-i}\cdot \mathbf {V} _{C})_{n/2+j}=$ ?. It can be seen that the two unequal values of $\varDelta X_{i,j}$ confirm to forms given in Lemma 7, which implies a contradiction. Thus, there is no r-round ID for $\varepsilon$ if $r\ge R(En)+R(De)+1$. $\square$

4.2.2 Upper bound for ZCLH

In [11], Sun et al. gave the definition of dual structure for the Feistel structure.

Definition 3

([11]) Let $\mathcal {F}_{SP}$ be a Feistel structure with SP-type round function. Let $\sigma$ be the operation that exchanges the left and right halves of a state. Then the dual structure $\mathcal {F}_{SP}^{\perp }$ of $\mathcal {F}_{SP}$ is defined as $\sigma \circ \mathcal {F}_{P^{T}S}\circ \sigma$.

It can be verified that if P is a permutation matrix, then $\mathcal {F} _{P^{T}S}$ is equivalent to $\mathcal {F}_{SP^{T}}$. Thus the dual structure of $\varepsilon$ can be represented by the structure $\varepsilon ^{\bot }$ in Fig. 3. Based on the dual structure, Sun et al. proved the following theorem.

Theorem 2

([11]) $a\rightarrow b$ is an r-round ID of $\mathcal {F}_{SP}$ if and only if it is an r-round ZCLH of $\mathcal {F} _{SP}^{\perp }$.

So we know that searching ZCLH of $\varepsilon$ is equivalent to searching ID of $\varepsilon ^{\bot }$. Then based on the theories of Sect. 4.2.1, the upper bound on the rounds of ZCLH for $\varepsilon$ can be gotten.

Fig. 4

Type-2 generalized Feistel structure

4.2.3 Extension of our method

Except for the Feistel$^{*}$-SP structure, our method also applies to some other Feistel structures to prove their security against IDC and ZCLC. Note that if the nonlinear part of a Feistel structure is bijective, we can treat it as an S-box. Thus saccording to Definition 1, we can define the characteristic matrices for any Feistel structures with bijective nonlinear parts. Then we define a special kind of characteristic matrix.

Definition 4

Let M be a characteristic matrix of a Feistel structure. If the number of entry “$\mathbf {s}$” and the number of entry “$\mathbf {1}$” in each column and row are all at most 1, then M is called 1-property matrix.

By the analysis in Sects. 3 and 4.2.1, we know that if the characteristic matrices of a Feistel structure are 1-property matrix, then our method can apply to this kind Feistel structure. For example, the Type-2 generalized Feistel structure [18] in Fig. 4. If we treat its round function as an S-box, then its characteristic matrices are 1-property matrix. Then by our method, we get that the longest ID and ZCLH of this structure will not exceed 10 rounds.

5 Applications to LBlock and TWINE

In this section, we apply our method to block ciphers LBlock and TWINE, respectively. Based on some properties of LBlock and TWINE, tight bounds on the rounds of ID and ZCLH of these two ciphers are given.

5.1 Bounds for LBlock

LBlock is a lightweight block cipher proposed by Wu and Zhang in ACNS’11. The round function of LBlock is given in Fig. 5. According to Definition 1, the encryption and decryption matrices of LBlock are

$$\begin{aligned} En=\left( \begin{array}{ll} P_{1}\cdot (s\cdot P_{0}), &{}\quad P_{1} \\ I, &{} \quad O \end{array} \right) \text { and }De=\left( \begin{array}{rr} O, &{}\quad I \\ P_{1}^{-1}, &{}\quad s\cdot P_{0} \end{array} \right) , \end{aligned}$$

respectively, where

$$\begin{aligned} P_{0}=\left( \begin{array}{llllllll} 0 &{}\quad 1 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 \\ 0 &{}\quad 0 &{}\quad 0 &{}\quad 1 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 \\ 1 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 \\ 0 &{}\quad 0 &{}\quad 1 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 \\ 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 1 &{}\quad 0 &{}\quad 0 \\ 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 1 \\ 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 1 &{}\quad 0 &{}\quad 0 &{}\quad 0 \\ 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 1 &{}\quad 0 \end{array} \right) , P_{1}=\left( \begin{array}{llllllll} 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 1 &{}\quad 0 \\ 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 1 \\ 1 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 \\ 0 &{}\quad 1 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 \\ 0 &{}\quad 0 &{}\quad 1 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 \\ 0 &{}\quad 0 &{}\quad 0 &{}\quad 1 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 \\ 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 1 &{}\quad 0 &{}\quad 0 &{}\quad 0 \\ 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 1 &{}\quad 0 &{}\quad 0 \end{array} \right) . \end{aligned}$$

It can be seen that $P_{1}$ is the matrix representation of the operation “$\ggg 8$”.

Fig. 5

Round function of LBlock

Fig. 6

Dual structure of round function of LBlock

The dual structure of the round function of LBlock is given in Fig. 6. The encryption and decryption matrices of the dual structure are

$$\begin{aligned} En^{\perp }=\left( \begin{array}{ll} O, &{} \quad P_{1} \\ I, &{} \quad s\cdot P_{0}^{-1} \end{array} \right) \text { and }De^{\perp }=\left( \begin{array}{ll} (s\cdot P_{0}^{-1})\cdot P_{1}^{-1}, &{} \quad I \\ P_{1}^{-1}, &{} \quad O \end{array} \right) , \end{aligned}$$

respectively. It can be seen that En, De, $R(En^{\perp })$ and $R(De^{\perp })$ are 1-property matrix. By computation, we have $R(En)=R(De)=R(En^{\perp })=R(De^{\perp })=8$. Thus according to Theorem 1, we know that the rounds of ID and ZCLH of LBlock is upper bounded by 17.

Next, we present some properties of character matrices of LBlock. Based on these properties, tight bounds for ID and ZCLH of LBlock are given.

Let $N_{M}^{j}$ be the number of entries “$\mathbf {0}$” and “$\mathbf {1}$” in the jth row of matrix M. By computation, we have

$$\begin{aligned} \left\{ \begin{array}{l} N_{En^{7}}^{j}=0,N_{En^{7}}^{j+8}=1, \\ N_{De^{7}}^{j}=1,N_{De^{7}}^{j+8}=0, \\ N_{(En^{\perp })^{7}}^{j}=1,N_{(En^{\perp })^{7}}^{j+8}=0, \\ N_{(De^{\perp })^{7}}^{j}=0,N_{(De^{\perp })^{7}}^{j+8}=1, \end{array} \right. \text { for }\,\, 0\le j\le 7. \end{aligned}$$

(9)

By the above observations on characteristic matrices of LBlock, we have the following lemma.

Lemma 10

Let $\mathbf {V}$ be a characteristic vector of LBlock. Let $W_{H}(\mathbf {V})$ be the number of nonzero entries in $\mathbf {V}$. If $W_{H}( \mathbf {V})\ge 3$, then we have $(M^{i}\cdot \mathbf {V})_{j}= ?$ for $i\ge 7$ and $0\le j\le 15$, where M is a characteristic matrix of LBlock.

Proof

According to (9), we know that the number of “$\mathbf {0}$” and “$\mathbf {1}$” in each row of $M^{i}$ is at most 1 for $i\ge 7$. Thus if $W_{H}(\mathbf {V})\ge 3$, then there exist two positions $j_{0}$ and $j_{1}$ in the jth row of $M^{i}$ for $i\ge 7$ such that $(\mathbf {V})_{j_{0}}\ne 0$, $(\mathbf {V})_{j_{1}}\ne 0$ and $(M^{i})_{j,j_{0}}$, $(M^{i})_{j,j_{1}}\in \{\mathbf {s},\mathbf {1}+\mathbf {s},2\mathbf {s}\}$. Since

$$\begin{aligned} (M^{i}\cdot \mathbf {V})_{j}=(M^{i})_{j,j_{0}}\cdot (\mathbf {V} )_{j_{0}}+(M^{i})_{j,j_{1}}\cdot (\mathbf {V})_{j,j_{1}}, \end{aligned}$$

we have $(M^{i}\cdot \mathbf {V})_{j}=?$. $\square$

Based on Lemma 10, we have:

Corollary 4

Let $\mathbf {V}_{P}$ and $\mathbf {V}_{C}$ be the characteristic vectors of $\varDelta P$ and $\varDelta C$, respectively. If $W_{H}(\mathbf {V}_{P})\ge 3$ or $W_{H}(\mathbf {V} _{C})\ge 3$, then the third class information is empty when $r\ge 15$.

Corollary 5

If $W_{H}(\mathbf {V}_{P})\ge 3$ or $W_{H}(\mathbf {V} _{C})\ge 3$, and if $r\ge 15$, then $\varDelta P\rightarrow \varDelta C$ is an r -round possible differential of LBlock.

The proofs of Corollaries 4 and 5 are similar with that of Lemma 9 and Theorem 1, respectively. Then, we give the upper bounds on the rounds of ID and ZCLH for LBlock.

Theorem 3

If $r\ge 15$, then there do not exist r-round ID and ZCLH of LBlock.

Proof

By Corollary 5, we only need to check if there exist 15 -round ID $\varDelta P\rightarrow \varDelta C$ with $W_{H}(\mathbf {V}_{P})<3$ and $W_{H}(\mathbf {V}_{C})<3$. By checking out all these 15-round differentials by the WW-algorithm, there is no 15-round ID. Thus there does not exist r-round ID of LBlock when $r\ge 15$.

Notice that $En^{\perp }$ and $De^{\perp }$ have similar properties with matrices En and De, thus we have the same conclusion for ZCLH. $\square$

Fig. 7

Round function of TWINE

Fig. 8

Dual structure of round function of TWINE

5.2 Bounds for TWINE

TWINE is a lightweight block cipher proposed by Suzaki et al. [13]. The round functions of TWINE adopt an variant of the Type-2 generalized Feistel structure (see Fig. 7). According to Definition 1, the encryption and decryption matrices of round function of TWINE are

$$\begin{aligned} En=\left( \begin{array}{rr} \mathbf {s}\cdot P_{0}, &{} P_{0} \\ P_{1}, &{} O \end{array} \right) , De=\left( \begin{array}{rr} O, &{} P_{1}^{-1} \\ P_{0}^{-1}, &{} \mathbf {s}\cdot P_{1}^{-1} \end{array} \right) , \end{aligned}$$

respectively, where

$$\begin{aligned} P_{0}=\left( \begin{array}{lllllllll} 1 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 \\ 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 1 &{}\quad 0 &{}\quad 0 \\ 0 &{}\quad 1 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 \\ 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 1 &{}\quad 0 &{}\quad 0 &{}\quad 0 \\ 0 &{}\quad 0 &{}\quad 0 &{}\quad 1 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 \\ 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 1 &{}\quad 0 \\ 0 &{}\quad 0 &{}\quad 1 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 \\ 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 1 \end{array} \right) ,P_{1}=\left( \begin{array}{lllllllll} 0 &{}\quad 1 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 \\ 0 &{}\quad 0 &{}\quad 0 &{}\quad 1 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 \\ 1 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 \\ 0 &{}\quad 0 &{}\quad 1 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 \\ 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 1 &{}\quad 0 &{}\quad 0 \\ 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 1 \\ 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 1 &{}\quad 0 &{}\quad 0 &{}\quad 0 \\ 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad 1 &{}\quad 0 \end{array} \right) . \end{aligned}$$

The dual structure of TWINE is given in Fig. 8, and the encryption and decryption matrices of the dual structure are

$$\begin{aligned} En^{\perp }=\left( \begin{array}{rr} O, &{} P_{0} \\ P_{1}, &{} \mathbf {s}\cdot P_{0} \end{array} \right) ,De^{\perp }=\left( \begin{array}{rr} s\cdot P_{1}^{-1}, &{} P_{1}^{-1} \\ P_{0}^{-1}, &{} O \end{array} \right) , \end{aligned}$$

respectively. By computation, we have

$$\begin{aligned} \left\{ \begin{array}{l} R(En)=R(De)=R(En^{\perp })=R(De^{\perp })=8, \\ N_{En^{7}}^{2j}=0,N_{En^{7}}^{2j+1}=1, \\ N_{De^{7}}^{2j}=1,N_{De^{7}}^{2j+1}=0, \\ N_{(En^{\perp })^{7}}^{2j}=1,N_{(En^{\perp })^{7}}^{2j+1}=0, \\ N_{(De^{\perp })^{7}}^{2j}=0,N_{(De^{\perp })^{7}}^{2j+1}=1, \end{array} \right. \text { for }0\le j\le 7. \end{aligned}$$

Similar with the analysis in Sect. 5.1, we have:

Theorem 4

There do not exist r-round ID or ZCLH of TWINE if $r\ge 15$.

6 Conclusion

In this paper, we studied the security of the Feistel$^{*}$-SP structure. Upper bounds on the rounds of ID and ZCLH of this structure are given. Moreover, we showed that our method also apply to some generalized Feistel structures, such as the Type-2 generalized Feistel structure. As applications of our method, we proved that there do not exist 15-round ID and ZCLH for LBlock and TWINE. In our future work, we will focus on the security for more generic Feistel-SP structures.