# Improved Generic Attacks on Unbalanced Feistel Schemes with Expanding Functions

 Improved Generic Attacks on Unbalanced Feistel Schemes with Expanding Functions 120px Authors Emmanuel Volte[@: 1], Valerie Nachef[@: 2], and Jacques Patarin[@: 3] Published ? Web site ? Download original

Abstract. “Generic” Unbalanced Feistel Schemes with Expanding Functions are Unbalanced Feistel Schemes with truly random internal round functions from ${\displaystyle n}$ bits to ${\displaystyle (k-1)n}$ bits with ${\displaystyle k \geq 3}$. From a practical point of view, an interesting property of these schemes is that since ${\displaystyle n < (k-1)}$ and ${\displaystyle n}$ can be small (8 bits for example), it is often possible to store these truly random functions in order to design efficient schemes (example: CRUNCH cf [1]). Attacks on these generic schemes were studied in [2] and [3]. As pointed in [2] and [3], there are surprisingly much more possibilities for these attacks than for generic balanced Feistel schemes or generic unbalanced Feistel schemes with contracting functions. In fact, this large number of attack possibilities makes the analysis difficult. In this paper, we shall methodically analyze again these attacks. We have created a computer program that systematically analyze all the possible attacks and detect the most efficient ones. We have detected a condition on the internal variables that was not clearly analyzed in [3], and we have found many new improved attacks by a systematic study of all the “rectangle attacks” when ${\displaystyle k\leq7}$, and then we have generalized these improved attacks for all ${\displaystyle k}$. Many simulations on our improved attacks have also been done and they confirm our theoretical analysis.

Key words: Unbalanced Feistel permutations, pseudo-random permutations, generic attacks on encryption schemes, Block ciphers.

## Introduction

A classical way to construct permutation ${\displaystyle \{0,1\}^N}$ to ${\displaystyle \{0,1\}^N}$ is to use Feistel schemes with ${\displaystyle d}$ rounds built with round functions ${\displaystyle f_{1},...,f_{d}}$. In order to get “Random Feistel Scheme”, these round functions need to be randomly chosen. “Generic attacks” on these schemes are attacks that are valid for most of the round functions.

Definition 1
The most usual Feistel schemes are when ${\displaystyle N=2n}$ and the functions ${\displaystyle f_{i}}$ are from ${\displaystyle \{0,1\}^N}$ to ${\displaystyle \{0,1\}^N}$.

Such schemes are called “balanced Feistel Schemes” and they have been studied a lot since the famous paper by M.Luby и C.Rackoff [4]. Many results have been obtained on the security of such classical Feistel schemes (see [5] for an overview of these results). When the number of rounds is lower than 5, we know attacks with less than ${\displaystyle 2^N=2^{2n}}$ operations: for 5 rounds, an attack in ${\displaystyle O(2^n)}$ operations is given in [6] and for 3 or 4 rounds an attack in ${\displaystyle \sqrt{2^n}}$ is given in [7], [8]. When the functions are permutations, similar attacks for 5 rounds are given in [9] and [10]. Therefore, for security, at least 6 rounds are recommended, i.e. each bit will be changed at least 3 times.

Definition 2
When ${\displaystyle N=kn}$ and when the round functions are from ${\displaystyle (k-1)n}$ bits to ${\displaystyle n}$ bits, we obtain what is called an “Unbalanced Feistel Scheme with contracting functions”.

In [5] M.Naor и O.Reingold give security when for the first and the last rounds pairwise independent functions are used instead of random contracting functions. In [11] security proofs for these schemes are also proved. At Asiacrypt 2006 ([12]) generic attacks on such schemes have been studied.

Definition 3
When ${\displaystyle N=kn}$ and when the round functions are from ${\displaystyle n}$ bits to ${\displaystyle (k-1)n}$ bits, we obtain what is called an “Unbalanced Feistel Scheme with expanding functions”, also called “complete target heavy unbalanced Feistel networks”.

Generic attacks on Unbalanced Feistel Schemes with expanding functions is the theme of this paper. One advantage of these schemes is that it requires much less memory to store a random function of ${\displaystyle n}$ bits to ${\displaystyle (k-1)n}$ bits than a random function of ${\displaystyle (k-1)n}$ bits to ${\displaystyle n}$ bits. Unbalanced Feistel Schemes with expanding functions together with the Xor of random permutations have been used in the construction of the hash function CRUNCH for the cryptographic hash algorithm competition organized by NIST in 2008 (cf [13]). Our results give a lower bound for the number of rounds used to construct this hash function.

Other kinds of Feistel Schemes are used for well known block ciphers. For example, BEAR and LION [14] - are two block ciphers which employ both expanding and contracting unbalanced Feistel networks. The AES-candidate MARS is also using a similar structure.

Attacks on Unbalanced Feistel Schemes with expanding functions have been previously studied by C.S. Jutla [2] and improved attacks were given in [3]. However some of the attacks presented in <[3] need too many conditions on the internal variables. These attacks work, but with weak keys. In this paper, we make a systematic study of the equations between the internal variables to avoid unlikely collisions on the round functions. Thus we get additional conditions. Nevertheless, with more conditions, we show that it is still possible to attack the same number of rounds as in [3]. In Known Plaintext Attacks (KPA), we obtain the same complexity except for ${\displaystyle d=3k-1}$ where our complexity is slightly greater than in ${\displaystyle 2^N=2^{2n}}$ but we do not have too many conditions on the internal variables. For Non-Adaptive Chosen Plaintext Attacks (CPA-1), we give a general method to obtain CPA-1 from KPA. Then we get complexities that are, most of the time, better than the ones in [3]. We also show that the best CPA-1 are not derived from the best KPA. For ${\displaystyle k \leq 7}$, we have generated all the possible attacks, thus the attacks presented here are the best possible attacks. We believe that the generalization of these attacks for any ${\displaystyle k}$ still gives the best possible attacks. We also provide simulation results for${\displaystyle k=3}$.

The paper is organized as follows. First we introduce some notation and definitions. Then we give an overview of the attacks. In Section 4, we show how we have generated all the possible attacks for ${\displaystyle k \leq 7}$. In Section 5, we introduce the different kinds of attacks we will used. These attacks named TWO, R1, R2, R3 and R4 generalize the attacks of [3]. Then in Section 6, we present R1, R2 KPA attacks. In Section 7, we show how to get CPA-1 from KPA. In Section 8, we study R1 and R2 CPA-1 and we give the results of our simulations. Finally, all the results are summarized in Section 9.

## Notation

### Unbalanced Feistel Schemes Notation

We first describe Unbalanced Feistel Scheme with Expanding Functions ${\displaystyle F_{k}^{d}}$ and introduce some useful notations. ${\displaystyle F_{k}^{d}}$ is a Feistel scheme of ${\displaystyle d}$ rounds that produces a permutation from ${\displaystyle kn}$ bits to ${\displaystyle kn}$ bits. At each round ${\displaystyle j}$, we denote by ${\displaystyle f_{1}}$ the round function from ${\displaystyle n}$ bits to ${\displaystyle (k-1)n}$ bits. ${\displaystyle f_{j}}$ is defined as ${\displaystyle f_{j}=(f_{j}^{(1)},f_{j}^{(2)},...,f_{j}^{(k-1)})}$, where each function ${\displaystyle f_{k}^{i}}$ is defined from ${\displaystyle \{0,1\}^n}$ to ${\displaystyle \{0,1\}^n}$. On some input ${\displaystyle [I_{1},I_{2},...,I_{k}]}$, ${\displaystyle F_{k}^{d}}$ produces an output denoted by ${\displaystyle [S_{1},S_{2},...,S_{k}]}$ by going through ${\displaystyle d}$ rounds. At round ${\displaystyle j}$, the first ${\displaystyle n}$bits of the round entry are called ${\displaystyle X^{j-1}}$. We can notice that ${\displaystyle I_{1}=X^{0}}$. We compute ${\displaystyle f_{j}(X^{j-1})}$ and obtain ${\displaystyle (k-1)n}$ bits. Those bits are xored to the ${\displaystyle (k-1)n}$ last bits of the round entry and the result is rotated by ${\displaystyle n}$ bits.

The first round is represented on Figure 1 below:

We have

${\displaystyle X^{0}=I_{1}}$

${\displaystyle X^{1}=I_{2} \oplus f_{1}^{(1)}(I_{1}) }$

${\displaystyle X^{2}=I_{3} \oplus f_{1}^{(2)}(I_{1}) \oplus f_{2}^{(1)}(X^{1})}$

${\displaystyle X^{3}=I_{4} \oplus f_{1}^{(3)}(I_{1}) \oplus f_{2}^{(1)}(X^{1}) \oplus f_{3}^{(1)}(X^{2})}$

More generally, we can express the ${\displaystyle X^{j}}$ recursively:

${\displaystyle \forall \xi < k, X^{\xi }=I_{\xi +1} \bigoplus_{i=1}^{\xi }f_{i}^{\xi -i+1}(X^{i-1})}$

${\displaystyle \forall \xi \geq 0, X^{k+ \xi }=X^{\xi} \bigoplus_{i=2}^{k}f_{\xi + i}^{k -i+1}(X^{\xi + i-1})}$

After ${\displaystyle d}$ rounds ${\displaystyle d \geq k+1}$, the output ${\displaystyle [S_{1},S_{2},...,S_{k}]}$ can be expressed by using the introduced values ${\displaystyle X^{j}}$:

${\displaystyle S_{k}=X^{d-1}}$

${\displaystyle S_{k-1}=X^{d-2} \oplus f_{d}^{(k-1)}(X^{d-1}) }$

${\displaystyle ...}$

${\displaystyle S_{\xi}=X^{d-1-k-\xi } \bigoplus_{i=d-k+\xi }^{d-1} f_{i+1}^{(\xi +d-i-1)}(X^{i})}$

${\displaystyle ...}$

${\displaystyle S_{1}=X^{d-k} \bigoplus_{i=d-k+1 }^{d-1} f_{i+1}^{(d-i)}(X^{i})}$

We don’t need another notation, but for a better understanding we introduce a notation for the intermediate values. After round ${\displaystyle p}$, we obtain ${\displaystyle [M_{1}^{p},M_{2}^{p},...,M_{k}^{p}]}$. So we have ${\displaystyle M_{1}^{p}=X^{p}}$, and for all ${\displaystyle i\in \{1,2,...,k\}}$ ${\displaystyle M_{i}^{0}=I_{i}}$ and ${\displaystyle M_{i}^{d}=S_{i}}$.

### Differential Attack Notation

Our attacks use sets of points. A point is a plaintext/ciphertext pair. The total number of points gives us the complexity of the attack. From the set of points we extract all the ${\displaystyle \varphi}$-tuple of distinct points ${\displaystyle P(1), P(2), ..., P(\varphi)}$, and we counthow many ${\displaystyle \varphi}$-tuple verify some equalities (see Figure 2 for an example).

Now, we can describe an attack with a differential path. With the path we can explain why the number of ${\displaystyle \varphi}$-tuples that match the conditions is more important for a ${\displaystyle F_{k}^{d}}$ scheme than for a random permutation. We introduce more definition. After ${\displaystyle p}$ rounds, we define “horizontal equalities” on part ${\displaystyle {M_i}}$ of the output ${\displaystyle M}$ as ${\displaystyle M_{i}^{p}(1)=M_{i}^{p}(3)=...=M_{i}^{p}(\varphi-1)}$ and ${\displaystyle M_{i}^{p}(2)=M_{i}^{p}(4)=...=M_{i}^{p}(\varphi)}$. Let ${\displaystyle \ell = \frac{\varphi}{2}-1}$ . “Vertical equalities” on part ${\displaystyle M_{i}}$ are given by ${\displaystyle \forall_j}$, ${\displaystyle 0\le j\le\ell}$, ${\displaystyle M_{i}^{p}(2j+1)= M_{i}^{p}(2j+2)}$. We also define “differential equalities” on part ${\displaystyle M_{i}}$ by ${\displaystyle \forall_j}$, ${\displaystyle 0\le j\le\ell-1}$, ${\displaystyle M_{i}^{p}(2j+1)\oplus M_{i}^{p}(2j+2)= M_{i}^{p}(2j+3)\oplus M_{i}^{p}(2j+4)}$. Notice that when we have the differential equalities, in order to get the horizontal equalities, it is enough to have the first sequence of equalities, and for the vertical equalities, it is enough to get only the first one. When we impose some equalities, we call them conditions (they are satisfied with probability ${\displaystyle \frac{1}{2^n}}$). This may imply that other equalities will be satisfied with probability 1. On the input and output variables we will always have ${\displaystyle \ell }$ differential conditions and either horizontal or vertical conditions. On the internal variables, we will get horizontal or vertical equalities and moreover we will impose more vertical or horizontal conditions.

We need to always have differential equalities. When we impose new conditions on the internal variables, we must check that we do not add too many of them.

We now give an example with an attack over the ${\displaystyle F_{3}^{6}}$ scheme. See Table 1.

 ${\displaystyle i}$(раунд) ${\displaystyle M_{1}^{i}(2j+1)\oplus M_{1}^{i}(2j+2)}$ ${\displaystyle M_{2}^{i}(2j+1)\oplus M_{2}^{i}(2j+2)}$ ${\displaystyle M_{3}^{i}(2j+1)\oplus M_{3}^{i}(2j+2)}$ 0 ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \Delta_1}$ 1 ${\displaystyle 0}$ ${\displaystyle \Delta_1}$ ${\displaystyle 0}$ 2 ${\displaystyle \centerdot\Delta_1}$ ${\displaystyle \centerdot 0}$ ${\displaystyle 0}$ 3 ${\displaystyle \centerdot\Delta_2}$ ${\displaystyle \Delta_3}$ ${\displaystyle \centerdot\Delta_1}$ 4 ${\displaystyle 0}$ ${\displaystyle \centerdot 0}$ ${\displaystyle \centerdot\Delta_2}$ 5 ${\displaystyle 0}$ ${\displaystyle \Delta_2}$ ${\displaystyle 0}$ 6 ${\displaystyle \Delta_2}$ ${\displaystyle 0}$ ${\displaystyle 0}$

The "${\displaystyle \centerdot}$" in this table means that there are horizontal equalities or conditions. The "${\displaystyle 0}$" in the table means that there are vertical equalities or conditions. This notation will be used for any attack. We can count the total number of conditions for the different part: ${\displaystyle n_{I}=3\ell+2}$ (number of input conditions), ${\displaystyle n_{X}=2\ell+2}$ (number of internal conditions), ${\displaystyle n_{S}=3\ell+2}$ (number of output conditions). If a ${\displaystyle \varphi}$-tuple follow the path, i.e. if it satisfies both the input and the internal conditions, then it will verify the output conditions. But there exist other ways to verify both these output conditions and the input conditions. So, we can prove that the number of ${\displaystyle \varphi}$-tuple will be greater for a ${\displaystyle F_k^d}$ permutation.

## Example: CPA-1 attack on ${\displaystyle F_{3}^{6}}$Example: CPA-1 attack on F 3 6 {\displaystyle F {3}^{6}}

We present here a first example where we have obtained a new and better attack than previously known for ${\displaystyle F_{3}^{6}}$. In the next sections a complete analysis will be given for more general parameters. This attack is the one described in Table 1 with ${\displaystyle \varphi = 4}$ and so ${\displaystyle \ell = 1}$. Figure 3 illustrates this attack. It explains the terms of horizontal and vertical equalities. Moreover, conditions are represented by a solid edge and equalities that are automatically satisfied by a dotted edge.

We will generate all the possible messages ${\displaystyle [I_{1}, I_{2}, I_{3}]}$ such that ${\displaystyle I_{1} = 0}$ and the first ${\displaystyle n/2}$ bits of ${\displaystyle I_{2}}$ are 0. So, we will generate exactly ${\displaystyle m = 2^{3n/2}}$ messages.

Lemma 1
Therefore there are ${\displaystyle m^{2} \times 2^{n} = 2^{4n}}$ 4-tuple of points that satisfy all the input conditions.
Proof
How many 4-tuple of points will verify the input conditions? For the first message we have ${\displaystyle m}$ possibilities. For the second we have only ${\displaystyle 2^{n}}$ possibilities because ${\displaystyle I_{1}}$ and ${\displaystyle I_{2}}$ are imposed by the first message. For the third point we have again ${\displaystyle m}$ possibilities, and then we have no choice for the last point. Therefore there are ${\displaystyle m^{2} \times 2^{n} = 2^{4n}}$ 4-tuple of points that satisfy all the input conditions.

For a ${\displaystyle F_{3}^{6}}$ scheme, each of these tuple will satisfy at random the 4 internal conditions with a probability equal to ${\displaystyle 1/2^{4n}}$. So, the expected number of 4-tuples that satisfy also the output conditions will be approximatively 1. Since there are 5 output conditions, the expected number of 4-tuple that satisfy the input conditions and the output conditions will be much lower for a random permutation. So, this CPA-1 attack will succeed with a high probability. We have found here a CPA-1 attack with ${\displaystyle O(2^{3n/2})}$ complexity and ${\displaystyle O(2^{3n/2})}$ messages. This is better than the ${\displaystyle O(2^{5n/3})}$ found in [3]. To find this complexity we can also use Table 3 with ${\displaystyle r=2}$, ${\displaystyle n_{X} = 4}$, ${\displaystyle \ell= 1}$ и ${\displaystyle k = 3}$. Moreover we have checked that all the other path conditions are verified (see Section 4) and this attack has been simulated by computer. For example, with ${\displaystyle n = 10}$ and 1000 атак, attacks, we were able to distinguish 575 ${\displaystyle F_{3}^{6}}$ schemes from a random permutation, so the percentage of success is about 57,5%.

## Generation of all possible attacks for ${\displaystyle k \le 7}$Generation of all possible attacks for k ≤ 7 {\displaystyle k \le 7}

In this section we describe the way we generate all the possible attacks for ${\displaystyle k \le 7}$. First we choose a value for ${\displaystyle k}$, then we increase the value of ${\displaystyle d}$, until we find no possible attacks. All the attacks (or sometimes only the best attacks when the number is too much important) are put in a specific file corresponding to the values of ${\displaystyle k}$ and ${\displaystyle d}$.

To find an attack, we need to construct all the differential paths. There are two constraints for this construction:

• In the same round, it’s not possible to have ${\displaystyle k}$ vertical conditions, because it leads to a collision between the points, i.e. ${\displaystyle P(1)=P(3)=...=P(\varphi-1)}$ and ${\displaystyle P(2)=P(4)=...=P(\varphi)}$.
• In the same round, it’s not possible to have ${\displaystyle k}$ horizontal conditions, because it also lead to a collision between the points, i.e. ${\displaystyle P(1) = P(2)}$ and ${\displaystyle P(3) = P(4)}$ и ${\displaystyle ...P(\varphi-1)=P(\varphi)}$.

When the path is constructed, we look if the attack is valid. To be valid, an attack must overcome five constraints.

1. The complexity of the attack must be smaller than the total number of possible messages: ${\displaystyle \frac{n_{I}+n_{X}}{2\ell+2} \le k}$.
2. There must be less internal conditions than output conditions: ${\displaystyle n_{X}\le n_{S}}$.
3. If ${\displaystyle n_{X} = n_{S}}$ then ${\displaystyle n_{S}}$ must be different from the number of final consecutive vertical conditions in the output conditions. If not, it is easy to prove that the output conditions are completely equivalent to the internal conditions. So, the output conditions will not happen more often than for a random permutation.
4. The number of equalities inside the path must be smaller than the number of variables included in them. Moreover we do not consider equalities when a variable occurs only once for all the equalities. Let us take an example. The ${\displaystyle F_{3}^{6}}$ attack given in section 2.2. The equations are: ${\displaystyle f^{(1)}_{3}(X_{2}\oplus \delta_{1})\oplus f^{(1)}_{3} (X_{2}) = \delta_{2}}$, ${\displaystyle f^{(2)}_{3} (X_{2}\oplus \delta_{1}) \oplus f^{(2)}_{3} (X_{2}) = \delta_{3}}$, ${\displaystyle f^{(1)}_{4} (X_{3}\oplus \delta_{2}) \oplus f^{(1)}_{4} (X_{3}) = \delta_{3}}$, ${\displaystyle f^{(2)}_{4} (X_{3} \oplus \delta_{2}) \oplus f^{(2)}_{4} (X_{3}) = \delta_{1}}$. We have 4 equations and 5 variables ${\displaystyle X_{2}}$, ${\displaystyle \delta_{1}}$, ${\displaystyle \delta_{2}}$, ${\displaystyle \delta_{3} }$, ${\displaystyle X_{3}}$. All the variables are used at least in 2 equalities, so we cannot simplify
5. There is no bottleneck in the equalities, i.e. any subset of equalities must have a greater number of variables. If it is not the case, the attack will only work with very particular functions (weak keys). This last point is very difficult to carry out without the help of a computer.

Finally, all the possible attacks are sorted in function of their complexity (KPA or CPA-1). For example there is 71 different attacks on the ${\displaystyle F_{}^{}}$ scheme, and 20 attacks with a CPA-1 complexity equal to ${\displaystyle 2^{3n/2}}$.

All possible attacks are given in an extended version of this paper. In the next sections, we generalize for any ${\displaystyle k}$ the best attacks (KPA and CPA-1) obtained for ${\displaystyle k \le 7}$.

## Different kinds of attacks: TWO, R1, R2, R3 and R4

### TWO Attacks

The TWO attack consists in using ${\displaystyle m}$ plaintext/ciphertexts pairs and in counting the number ${\displaystyle N_{F_{k}^{d}}}$ of couples of these pairs that satisfy the relations between the input and output variables. We then compare ${\displaystyle N_{F_{k}^{d}}}$ with ${\displaystyle N_{perm}}$ where ${\displaystyle N_{perm}}$ is the number of couples of pairs for a random permutation instead of ${\displaystyle F_{k}^{d}}$. The attack is successful, i.e. we are able to distinguish ${\displaystyle F_{k}^{d}}$ from a random permutation if the difference ${\displaystyle \mid E(N_{F_{k}^{d}})-E(N_{perm}) \mid}$ is much larger than the standard deviation ${\displaystyle \sigma_{perm}}$ and than the standard deviation ${\displaystyle \sigma_{ F_{k}^{d}}}$, where ${\displaystyle E}$ denotes the expectancy function. These attacks give the best attacks from ${\displaystyle 1}$ round to ${\displaystyle k+2}$. rounds. They are studied in [3]. Their complexity is summarized in Section 9.

### R1 Attacks

Here we have vertical conditions on the input and output variables. These attacks are more general than the attacks named R1 in [3] since we allow more vertical conditions on the input and output variables. These attacks were first described by Jutla [2]. With our differential notation, we have:

 ${\displaystyle I_1}$ ... ${\displaystyle I_r}$ ${\displaystyle I_{r+1}}$ ... ${\displaystyle I_{k}}$ ${\displaystyle S_1}$ ... ${\displaystyle S_{k-v}}$ ${\displaystyle S_{k-v+1}}$ ... ${\displaystyle S_k}$ Round ${\displaystyle 0}$ ${\displaystyle 0}$ ... ${\displaystyle 0}$ ${\displaystyle \Delta^0_{r+1}}$ ... ${\displaystyle \Delta^0_k}$ Round ${\displaystyle d}$ ${\displaystyle \Delta^d_1}$ ... ${\displaystyle \Delta^d_{r-v}}$ ${\displaystyle 0}$ ... ${\displaystyle 0}$

Thus, ${\displaystyle n_{I}=k\ell+r}$, ${\displaystyle n_{X}=t\ell+w}$, ${\displaystyle n_{S}=k\ell+v}$. Here ${\displaystyle n_{I}}$ denotes the conditions on the input variables. ${\displaystyle \ell=\frac{\varphi}{2}-1}$. The number of vertical conditions on the input variables is ${\displaystyle r}$. ${\displaystyle n_{X}}$ denotes the number of conditions on the internal variables. We use ${\displaystyle t}$ for horizontal conditions and ${\displaystyle w}$ for vertical conditions. Similarly, ${\displaystyle n_{S}}$ and ${\displaystyle v}$ denote respectively the number of conditions and the number of vertical conditions on the output variables. Then the number of rounds is given by ${\displaystyle r+t+w}$. When ${\displaystyle n_{X} \le n_{S}}$ we can easily obtain a sufficient condition of success (without computing the standard deviation), since in that case we will have for most permutation about 2 times more solutions with ${\displaystyle F_{k}^{d}}$ than with a random permutation. Here this gives the condition: ${\displaystyle (k-t)\ell \ge w-v}$. In order to avoid weak keys, the number of equations with the internal variables must be smaller than or equal to the number of internal variables. This condition was not always satisfied in [3]. For R1 attacks, it is easy to check that the number of equations is given by ${\displaystyle t(k-1)}$ and the number of variables is ${\displaystyle k(t+1)-r-w}$. Thus we get the condition: ${\displaystyle r+w \le t+k}$. The complexity of such an attack is ${\displaystyle 2^{\frac{n_{I}+n_{X}}{\varphi}n}}$. This implies ${\displaystyle \frac{n_{I}+n_{X}}{\varphi} \le k}$, i.e. ${\displaystyle \frac{(k+t)\ell+r+w}{2\ell+2} \le k}$.

### R2 Attacks

Here we have horizontal conditions on the input variables and vertical conditions on the output variables. Again these attacks are more general than the attacks named R2 in [3] since we allow more horizontal conditions on the input variables and more vertical conditions on the output variables. We have:

 ${\displaystyle I_1}$ ... ${\displaystyle I_u}$ ${\displaystyle I_{u+1}}$ ... ${\displaystyle I_{k}}$ ${\displaystyle S_1}$ ... ${\displaystyle S_{k-v}}$ ${\displaystyle S_{k-v+1}}$ ... ${\displaystyle S_k}$ Round ${\displaystyle 0}$ ${\displaystyle \centerdot\Delta^0_1}$ ... ${\displaystyle \centerdot\Delta^0_u}$ ${\displaystyle \Delta^0_{u+1}}$ ... ${\displaystyle \Delta^0_k}$ Round ${\displaystyle d}$ ${\displaystyle \Delta^d_1}$ ... ${\displaystyle \Delta^d_{k-v}}$ ${\displaystyle 0}$ ... ${\displaystyle 0}$

Thus, ${\displaystyle n_{I}=(k+r)\ell}$, ${\displaystyle n_{X}=t\ell+w}$, ${\displaystyle n_{S}=k\ell+v}$. The number of horizontal conditions on the input variables is denoted by ${\displaystyle u}$. The number of rounds is given ${\displaystyle u+t+w}$. The condition ${\displaystyle n_{X} \le n_{S}}$ is equivalent to ${\displaystyle (k-t)\ell \ge w-v}$. For R2 attacks, it is easy to check that the number of equations is given by ${\displaystyle (t+1)(k-1)}$, and the number of variables is ${\displaystyle k(t+2)-w}$. Thus we get the condition: ${\displaystyle w \le t+k+1}$. The complexity of such an attack is ${\displaystyle 2^{\frac{n_{I}+n_{X}}{\varphi}n}}$. This implies ${\displaystyle \frac{n_{I}+n_{X}}{\varphi} \le k}$, i.e. . ${\displaystyle \frac{(k+t+u)\ell+w}{2\ell+2} \le k}$.

### R3 and R4 Attacks

We describe briefly, R3 and R4 attacks. It is easy to get the number of rounds and the conditions on the number of equations and variables. For R3 attacks, we have vertical conditions on the input variables and horizontal conditions on the output variables. This gives:

 ${\displaystyle I_1}$ ... ${\displaystyle I_r}$ ${\displaystyle I_{r+1}}$ ... ${\displaystyle I_{k}}$ ${\displaystyle S_1}$ ... ${\displaystyle S_{k-s}}$ ${\displaystyle S_{k-s+1}}$ ... ${\displaystyle S_k}$ Round ${\displaystyle 0}$ ${\displaystyle 0}$ ... ${\displaystyle 0}$ ${\displaystyle \Delta^0_{r+1}}$ ... ${\displaystyle \Delta^0_k}$ Round ${\displaystyle d}$ ${\displaystyle \Delta^d_1}$ ... ${\displaystyle \Delta^d_{k-s}}$ ${\displaystyle \centerdot\Delta^{d}_{k-s+1}}$ ... ${\displaystyle \centerdot\Delta^d_k}$

and ${\displaystyle n_{I}=k\ell+r}$, ${\displaystyle n_{X}=t\ell+w}$, ${\displaystyle n_{S}=(k+s)\ell}$

For R4 attacks, we have horizontal conditions on the input and output variables. This gives:

 ${\displaystyle I_1}$ ... ${\displaystyle I_u}$ ${\displaystyle I_{u+1}}$ ... ${\displaystyle I_{k}}$ ${\displaystyle S_1}$ ... ${\displaystyle S_{k-s}}$ ${\displaystyle S_{k-s+1}}$ ... ${\displaystyle S_k}$ Round ${\displaystyle 0}$ ${\displaystyle \centerdot\Delta^0_1}$ ... ${\displaystyle \centerdot\Delta^0_u}$ ${\displaystyle \Delta^0_{u+1}}$ ... ${\displaystyle \Delta^0_k}$ Round ${\displaystyle d}$ ${\displaystyle \Delta^d_1}$ ... ${\displaystyle \Delta^d_{k-s}}$ ${\displaystyle \centerdot\Delta^{d}_{k-s+1}}$ ... ${\displaystyle \centerdot\Delta^d_k}$

and ${\displaystyle n_{I}=(k+u)\ell}$, ${\displaystyle n_{X}=t\ell+w}$, ${\displaystyle n_{S}=(k+s)\ell}$

## Best KPA attacks: R1, R2

In this section we describe the best attacks we have found. As mentioned before, we know that for ${\displaystyle k \le 7}$, they are the best possible attacks. We will mostly describe one example of R2 attacks since for any round there are many possible R2 attacks that give the best complexity. It can be noticed that in KPA, there is a symmetry between R2 and R3 attacks. Thus there always exist R2 and R3 attacks with the same complexity. Sometimes, it is also possible to have R1 attacks. Most of the time, R4 attacks are worse. We give attacks from ${\displaystyle k+3}$ rounds to ${\displaystyle 3k-1}$ rounds since from ${\displaystyle 1}$ to ${\displaystyle k+2}$ rounds, TWO attacks are most of the time better and they are described in [3]. In all our attacks, it is easily checked that the conditions given in the previous section are satisfied. Moreover, we always look for attacks where the number of points is minimum. Our best R2 KPA attacks are summarized in Table 2:

Remarks:

1. We have the following R1 attacks:
 ${\displaystyle d}$ values ${\displaystyle n_I}$ ${\displaystyle n_X}$ ${\displaystyle n_S}$ ${\displaystyle \ell }$ Complexity ${\displaystyle k+2q\in[k+3, 2k-2]}$ ${\displaystyle (2k-1)\ell}$ ${\displaystyle q\ell+q+1}$ ${\displaystyle k\ell+q+1}$ ${\displaystyle 1}$ ${\displaystyle 2^{\frac{k+d}{4}n}}$ ${\displaystyle k+2q+1\in[k+3, 2k-2]}$ ${\displaystyle (2k-1)\ell}$ ${\displaystyle q\ell+q+2}$ ${\displaystyle k\ell+q+2}$ ${\displaystyle 1}$ ${\displaystyle 2^{\frac{k+d}{4}n}}$ ${\displaystyle k+2q\in[2k-1, 3k-2]}$ ${\displaystyle (2k-1)\ell}$ ${\displaystyle (q-[\frac{k-1}{2}])\ell+q+[\frac{k+1}{2}]}$ ${\displaystyle k\ell+k-1}$ ${\displaystyle 1}$ ${\displaystyle 2^{\frac{k+d}{4}n}}$ ${\displaystyle k+2q+1\in[2k-1, 3k-2]}$ ${\displaystyle (2k-1)\ell}$ ${\displaystyle (q-[\frac{k-3}{2}])\ell+q+[\frac{k+1}{2}]}$ ${\displaystyle k\ell+k-1}$ ${\displaystyle 1}$ ${\displaystyle 2^{\frac{k+d}{4}n}}$ ${\displaystyle 3k-1}$ ${\displaystyle k\ell+\ell}$ ${\displaystyle k\ell+2k-1}$ ${\displaystyle k\ell+k-1}$ ${\displaystyle k}$ ${\displaystyle 2^{k-\frac{1}{2k+2}n}}$
(a) When ${\displaystyle k+3 \le d \le 2k-2}$ and ${\displaystyle d=k+2q}$, we set

${\displaystyle n_{I}=k\ell+k-1}$, ${\displaystyle n_{X}=q\ell+q+1}$, ${\displaystyle n_{S}=k\ell+q+1}$

It is possible to choose ${\displaystyle \ell=1}$ and the complexity is also ${\displaystyle 2^{\frac{k+d}{4}n}}$.

(b) When ${\displaystyle 2k-1 \le d \le 3k-2}$ and ${\displaystyle d=k+2q}$, we set

${\displaystyle n_{I}=k\ell+2}$, ${\displaystyle n_{X}=q\ell+k+q-2}$, ${\displaystyle n_{S}=k\ell+k-1}$

The complexity is still ${\displaystyle 2^{\frac{k+d}{4}n}}$, but ${\displaystyle \ell }$ is greater than ${\displaystyle 1}$.

1. In [2] Jutla gave a R1 attack on ${\displaystyle 3k-3}$ rounds but the complexity that we obtain with a R2 attack here is better. It is possible to perform a R1 attack on ${\displaystyle 3k - 2}$ rounds just by adding a vertical condition on the input variables to the attack on ${\displaystyle 3k - 3}$ rounds and the we obtain the same complexity as the one we get with a R2 attack. Due to the conditions between the number of equations and internal variables, it is not possible to use the same idea for ${\displaystyle 3k-1}$ rounds. In this last case, we have R2 (and of course R3) attacks.

## Way to transform KPA Attacks into CPA-1 Attacks

We have analyzed all the possible situations and we are now able to present formulas that give us directly the CPA complexity depending on the initial conditions. We call ${\displaystyle u}$ the number of horizontal conditions, ${\displaystyle r}$ the number of vertical condition and ${\displaystyle \delta = \mid u-r \mid }$. So we can distinguish four cases:

1. ${\displaystyle u=0}$: ${\displaystyle \underbrace{0 0 ... 0}_\text{r”0”} \Delta_1 ... \Delta_{k-r}}$
2. ${\displaystyle r=0}$: ${\displaystyle \overbrace{\centerdot\Delta_1 \centerdot\Delta_2 ... \centerdot\Delta_u}^\text{u”.”} \Delta_{u+1} ... \Delta_{k-r}}$
3. ${\displaystyle u \le r}$: ${\displaystyle \underbrace{ \overbrace{\centerdot 0 \centerdot 0 ... \centerdot 0}^\text{u”.”} \overbrace{0 ... 0}^\text{ d = r - u } }_\text{r”0”} \Delta_1 ... \Delta_{k-r} }$
4. ${\displaystyle u \ge r}$: ${\displaystyle \overbrace{ \underbrace{\centerdot 0 \centerdot 0 ... \centerdot 0}_\text{r”0”} \underbrace{\centerdot\Delta_1 \centerdot\Delta_2 ... \centerdot\Delta_\delta}_\text{d = u - r} }^\text{u”.”} \Delta_{\delta+1} ... \Delta_{k-r} }$
 Conditions ${\displaystyle \log_{2^n}{(CPA)}}$ ${\displaystyle u=0}$ ${\displaystyle r}$ vertical conditions ${\displaystyle \frac{n_X}{\ell+2}\le k-r}$ ${\displaystyle \frac{n_X}{\ell+2}}$ ${\displaystyle \frac{n_X}{\ell+2}\le k-r}$ ${\displaystyle \frac{n_{X}-k+r}{\ell+1}}$ ${\displaystyle r=0}$ ${\displaystyle u}$ horizontal conditions ${\displaystyle \frac{n_X}{\ell+2}\le k-u}$ ${\displaystyle \frac{n_X}{\ell+2}}$ ${\displaystyle \frac{n_X}{\ell+2}\le k-u}$ ${\displaystyle \frac{n_{X}-\ell(k-u)}{2}}$ ${\displaystyle r \ne0 }$ и ${\displaystyle u \ne 0}$ ${\displaystyle u}$ horizontal conditions and ${\displaystyle r}$ vertical conditions ${\displaystyle u \le r}$ ${\displaystyle (\ell+2)(k-r)>n_X}$ ${\displaystyle \frac{n_X}{\ell+2}}$ ${\displaystyle (\ell+2)(k-r)+(\ell+1)\delta>n_X}$ and ${\displaystyle (\ell+2)(k-r)\le n_X}$ ${\displaystyle \frac{n_{X}-k+r}{\ell+1}}$ ${\displaystyle (\ell+2)(k-r)+(\ell+1)\delta \le n_X }$ ${\displaystyle n_{X}-k+r-\ell(k-u)}$ ${\displaystyle u > r}$ ${\displaystyle (\ell+2)(k-u)>n_X }$ ${\displaystyle \frac{n_X}{\ell+2}}$ ${\displaystyle (\ell+2)(k-u)+2\delta>n_X}$ and ${\displaystyle (\ell+2)(k-u)\le n_X}$ ${\displaystyle \frac{n_{X}-\ell(k-u)}{2}}$ ${\displaystyle (\ell+2)(k-u)+2\delta \le n_X }$ ${\displaystyle n_{X}-k+r-\ell(k-u)}$

We can notice that the best CPA-1 attacks do not always come from the best KPA attacks. Nevertheless, if we want to express the CPA complexity with the KPA complexity, we can use the following formula: ${\displaystyle \log_{2n} (KPA) = \frac{r+(u+k)\ell + n_{X}}{2\ell + 2}}$.

Theorem 1
For all the CPA-1 Attacks we found, we prove that the best choice is to keep the first bits constant and generate all the possible messages with the same first bits.
Proof
Let’s show how we prove it for Case 1. The best way to choose messages is to keep some of the bits constant (for example equal to zero) and consider all the possible combination for the other bits. We call ${\displaystyle b}$ the number of varying bits among the first ${\displaystyle rn}$ bits, and we call ${\displaystyle \beta }$ the number of varying bits among the last ${\displaystyle (k-r)n}$ bits. So we have ${\displaystyle 0 \le b \le rn}$ and ${\displaystyle 0 \le \beta \le (k-r)n}$, and this allow us to generate ${\displaystyle 2^{b+ \beta}}$ points (plaintext/cyphertext pair). Now we count how many ${\displaystyle \varphi}$-tuple ${\displaystyle M^{0}(1), ..., M^{0}(\varphi)}$ of points will verify the input conditions. For ${\displaystyle M^{0}(1)}$ we have ${\displaystyle 2^{b+ \beta}}$ possibilities, for ${\displaystyle M^{0}(2)}$ only ${\displaystyle 2^{\beta}-1 \approx 2^{\beta}}$ possibilities, because the first ${\displaystyle rn}$ bits are imposed by ${\displaystyle M^{0}(1)}$. For ${\displaystyle M^{0}(3)}$ we have again ${\displaystyle 2^{b+ \beta} - 2 \approx 2^{b+ \beta}}$ possibilities. For ${\displaystyle M^{0}(4)}$ only one possibility: ${\displaystyle M^{0}(4) = M^{0}(3) \oplus (M^{0}(1) \oplus M^{0}(2))}$. We continue like this until we reach the last two points. For ${\displaystyle M^{0}(\varphi - 1)}$ we have again almost ${\displaystyle 2^{b+ \beta}}$ possibilities, and for ${\displaystyle M^{0}(\varphi)}$ only one possibility. So, the total number of ${\displaystyle \varphi}$-tuple is ${\displaystyle (2^{b+ \beta})^{\varphi /2} \times 2^{\beta} = 2^{(b+ \beta) \ell+1)+\beta}}$. The complexity of the CPA-1 is equal to ${\displaystyle 2^{b+ \beta}}$. We want this number to be as small as possible, and at the same time we want to generate a maximum of ${\displaystyle \varphi}$-tuples that satisfy the input conditions. So, we want to have ${\displaystyle \beta }$ as large as possible. Each ${\displaystyle \varphi}$-tuples has a probability equal to ${\displaystyle 1/2^{n_{X} \cdot n} }$ to satisfy the internal conditions. In order to have a reasonable chance to realize these conditions, we must have ${\displaystyle (b+ \beta)(\ell+1)+\beta = n_{X} \cdot n}$. If ${\displaystyle b=0 }$ we get ${\displaystyle \beta = \frac{n_{X}}{\ell+1}n }$. But this is possible only if ${\displaystyle \beta \le (k-r)n }$, i.e. if ${\displaystyle \frac{n_{X}}{\ell+1} \le k-r }$. If we have ${\displaystyle \frac{n_{X}}{\ell+1} > k-r }$, then we must take the maximum possible value for ${\displaystyle \beta }$: ${\displaystyle \beta=(k-r)n}$ and that gives us a CPA-1 complexity equal to ${\displaystyle 2^{b+ \beta}=2^{\frac{n_{X}-k+r}{\ell+1}n}}$.

All the cases are summarized in Table 3.

## Best CPA-1 Attacks: R1, R2. Simulation

### CPA-1 attacks

In this section, we describe the best CPA-1 that we have obtained. Again for ${\displaystyle k \le 7}$ we know that we have the best possible attacks. Except for ${\displaystyle 3k-1}$ rounds, we obtain a better complexity than in [3]. . The best CPA-1 are generally R2 attacks. Sometimes R1 attacks exist with the same complexity. It is interesting to note that the best CPA-1 do not come from the best KPA. We will use the study of CPA-1 made in Section 7. We will describe CPA-1 for ${\displaystyle k+3 \le d \le 3k-1}$ since for ${\displaystyle d \le k+2}$, the best attacks are the TWO attacks given in [3]. Again we will give an example of such an attack for each round. We notice that for the same conditions on the input and output variables, we can find several attacks: the horizontal and vertical conditions on the internal variables can be displayed differently inside the attack, but we must respect the conditions between the number of equations and variables at each step of the attack. An example is given at the end of this section. Our best R2 CPA-1 attacks are summarized in the following table:

 ${\displaystyle d}$ values ${\displaystyle n_I}$ ${\displaystyle n_X}$ ${\displaystyle n_S}$ ${\displaystyle \ell }$ Complexity ${\displaystyle k+3}$ ${\displaystyle k\ell+(k-1)\ell}$ ${\displaystyle \ell+3}$ ${\displaystyle k\ell+1}$ ${\displaystyle 1}$ ${\displaystyle 2^{\frac{3n}{2}}}$ ${\displaystyle k+4}$ ${\displaystyle k\ell+(k-2)\ell }$ ${\displaystyle 2\ell+4}$ ${\displaystyle k\ell+2}$ ${\displaystyle 1}$ ${\displaystyle 2^{2n}}$ ${\displaystyle k+5}$ ${\displaystyle k\ell+(k-2)\ell }$ ${\displaystyle 2\ell+5 }$ ${\displaystyle k\ell+2}$ ${\displaystyle 1}$ ${\displaystyle 2^{\frac{5n}{2} }}$ ${\displaystyle k+2q\in[k+6, 3k-4]}$ ${\displaystyle k\ell+(k-q)\ell }$ ${\displaystyle (q-1)\ell+2q+1}$ ${\displaystyle k\ell+1}$ ${\displaystyle q-1}$ ${\displaystyle 2^{\frac{q^{2}+2}{q+1}n}}$ ${\displaystyle k+2q+1\in[k+7, 3k-5]}$ ${\displaystyle k\ell+(k-q)\ell }$ ${\displaystyle (q-1)\ell+2q+2}$ ${\displaystyle k\ell+1}$ ${\displaystyle q-1}$ ${\displaystyle 2^{k-\frac{q^{2}+3}{q+1}n}}$ ${\displaystyle 3k-3}$ ${\displaystyle k\ell+\ell }$ ${\displaystyle (k-2)\ell+2k-2}$ ${\displaystyle k\ell+1}$ ${\displaystyle k-1}$ ${\displaystyle 2^{\frac{(k-1)k }{k+1}n}}$ ${\displaystyle 3k-2}$ ${\displaystyle k\ell+(k-1)\ell }$ ${\displaystyle (k-[\frac{k}{2}])\ell+2k-[\frac{k-1}{2}]}$ ${\displaystyle k\ell+k-1}$ ${\displaystyle 1}$ ${\displaystyle 2^{(k-1)n}}$ ${\displaystyle 3k-1}$ ${\displaystyle k\ell+\ell }$ ${\displaystyle (k-1)\ell+2k-1}$ ${\displaystyle k\ell+k-1}$ ${\displaystyle k}$ ${\displaystyle 2^{(k-\frac{1}{2})n}}$

Remark. For ${\displaystyle d=k+3}$, ${\displaystyle k+4}$, ${\displaystyle k+5}$ and ${\displaystyle 3k-2}$, there exist R1 attacks with the same complexity and the same number of points.

### Overview of the R2 CPA-1 Attack on ${\displaystyle F_{k}^{3k-1}}$Overview of the R2 CPA-1 Attack on F k 3 k − 1 {\displaystyle F {k}^{3k-1}}

We did a simulation of our best CPA-1 Attack. The input and output conditions were the following:

 ${\displaystyle I_1}$ ${\displaystyle I_2}$ ... ${\displaystyle I_k}$ ${\displaystyle S_1}$ ${\displaystyle S_2}$ ... ${\displaystyle S_k}$ Round ${\displaystyle 0}$ ${\displaystyle \centerdot\Delta^0_1}$ ${\displaystyle \Delta^0_2}$ ... ${\displaystyle \Delta^0_k}$ Round ${\displaystyle d}$ ${\displaystyle \Delta^d_1}$ ${\displaystyle 0}$ ... ${\displaystyle 0}$

Several different differential paths match with these input and output conditions. For example let’s see all the R2 path for the ${\displaystyle F_{3}^{8}}$ and ${\displaystyle F_{4}^{11}}$ permutations. See Table 5 and Table 9 in Appendix A.

Table 5. All the paths for the R2 attack against ${\displaystyle F^8_3}$, ${\displaystyle \varphi=8}$
Path 1:
 0 ${\displaystyle \centerdot \Delta_1}$ ${\displaystyle \Delta_2}$ ${\displaystyle \Delta_3}$ 1 ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \centerdot \Delta_1}$ 2 ${\displaystyle 0}$ ${\displaystyle \Delta_1}$ ${\displaystyle 0}$ 3 ${\displaystyle \centerdot \Delta_1}$ ${\displaystyle 0}$ ${\displaystyle 0}$ 4 ${\displaystyle 0}$ ${\displaystyle \Delta_4}$ ${\displaystyle \centerdot \Delta_1}$ 5 ${\displaystyle \centerdot \Delta_4}$ ${\displaystyle \Delta_1}$ ${\displaystyle 0}$ 6 ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \centerdot \Delta_4}$ 7 ${\displaystyle 0}$ ${\displaystyle \Delta_4}$ ${\displaystyle 0}$ 8 ${\displaystyle \Delta_4}$ ${\displaystyle 0}$ ${\displaystyle 0}$
Path 2:
 0 ${\displaystyle \centerdot \Delta_1}$ ${\displaystyle \Delta_2}$ ${\displaystyle \Delta_3}$ 1 ${\displaystyle 0}$ ${\displaystyle \Delta_4}$ ${\displaystyle \centerdot \Delta_1}$ 2 ${\displaystyle \centerdot \Delta_4}$ ${\displaystyle \Delta_1}$ ${\displaystyle 0}$ 3 ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \centerdot \Delta_4}$ 4 ${\displaystyle 0}$ ${\displaystyle \Delta_4}$ ${\displaystyle 0}$ 5 ${\displaystyle \centerdot \Delta_4}$ ${\displaystyle 0}$ ${\displaystyle 0}$ 6 ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \centerdot \Delta_4}$ 7 ${\displaystyle 0}$ ${\displaystyle \Delta_4}$ ${\displaystyle 0}$ 8 ${\displaystyle \Delta_4}$ ${\displaystyle 0}$ ${\displaystyle 0}$

We counted the number of paths for ${\displaystyle k \le 7}$:

 ${\displaystyle k}$ 3 4 5 6 7 ${\displaystyle \#}$ path 2 8 27 89 296

We will see that, the greater ${\displaystyle k}$ is, the better the attacks work.

### Experimental results

We did simulations of these CPA-1 attacks. For each simulation, we generate a random Feistel scheme with 20 rounds, and a ${\displaystyle F_{k}^{3k-1}}$ scheme. For both schemes, we compute ${\displaystyle 2^{(k-1/2)n}}$ ciphertext/plaintext pairs, by varying only the last ${\displaystyle (k - 1/2)n}$ bits. After this, we extract all the couples of points that satisfy both input and output conditions. We sort these couples of points in order to count how many ${\displaystyle \varphi}$-tuple of points match the input and output condition. If we found ${\displaystyle q}$ couples of points that satisfy all these conditions with ${\displaystyle q \ge \varphi/2}$ , we count as if we have found ${\displaystyle \frac{q!}{(q-\varphi/2)!}}$ ${\displaystyle \varphi}$-tuple, because this is the number of ${\displaystyle \varphi}$-tuple we can take out these points, by changing the position of the couple of points. Once this is finished, we compare the number found for each permutation. Most of the time, that enables us to distinguish between them. See Table 6.

## Summary of the attacks

In Tables 7 and 8, we give the complexity of the attacks we have found. For ${\displaystyle k \le 7}$, since we have generated all the attacks, these are the best possible attacks.

 ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle kn}$ ${\displaystyle \%}$ of success ${\displaystyle \%}$ of false alarm ${\displaystyle \#}$ iteration 2 3 6 29,09${\displaystyle \%}$ 0,35${\displaystyle \%}$ 100000 2 4 8 61,6${\displaystyle \%}$ 0,06${\displaystyle \%}$ 10000 2 5 10 98,37${\displaystyle \%}$ 0${\displaystyle \%}$ 10000 2 6 12 99,99${\displaystyle \%}$ 0${\displaystyle \%}$ 10000 2 7 14 100${\displaystyle \%}$ 0${\displaystyle \%}$ 1000 2 8 16 100${\displaystyle \%}$ 0${\displaystyle \%}$ 1000 2 9 18 100${\displaystyle \%}$ 0${\displaystyle \%}$ 500 2 10 20 100${\displaystyle \%}$ 0${\displaystyle \%}$ 100 4 3 12 21,15${\displaystyle \%}$ 1,12${\displaystyle \%}$ 10000 4 4 16 42,5${\displaystyle \%}$ 0${\displaystyle \%}$ 1000 4 5 20 93${\displaystyle \%}$ 0${\displaystyle \%}$ 100 4 6 24 100${\displaystyle \%}$ 0${\displaystyle \%}$ 100 6 3 18 8${\displaystyle \%}$ 1,2${\displaystyle \%}$ 500 8 3 24 2${\displaystyle \%}$ 0${\displaystyle \%}$ 100

Then we have generalized the results for ${\displaystyle k > 7}$ and we believe that the attacks presented here are also the best possible attacks. For ${\displaystyle d \le k + 3}$, we have TWO attacks. For ${\displaystyle d \ge k + 3}$, we have rectangle attacks. As mentioned before, in KPA, there are always R2 and R3 attacks that give the best complexity sometimes there is also a R1 attacks (for${\displaystyle 3k - 2}$ rounds for example). In CPA-1, the best complexity is given by R2 attacks, and sometimes R1 attacks.

 KPA CPA-1 ${\displaystyle F_3^1}$ 1 1 ${\displaystyle F_3^2}$ ${\displaystyle 2^{\frac{n}{2}}}$, TWO 2 ${\displaystyle F_3^3}$ ${\displaystyle 2^{n}}$, TWO 2 ${\displaystyle F_3^4}$ ${\displaystyle 2^{\frac{3}{2}n}}$, TWO ${\displaystyle 2^{\frac{n}{2}}}$, TWO ${\displaystyle F_3^5}$ ${\displaystyle 2^{2n}}$, TWO ${\displaystyle 2^{n}}$, TWO ${\displaystyle F_3^6}$ ${\displaystyle 2^{\frac{9}{4}n}}$, R2, R3 ${\displaystyle 2^{\frac{3}{2}n}}$, R2(new) ${\displaystyle F_3^7}$ ${\displaystyle 2^{\frac{5}{2}n}}$, R1, R2, R3 ${\displaystyle 2^{2n}}$, R2 ${\displaystyle F_3^8}$ ${\displaystyle 2^{\frac{23}{8}n}}$, R2, R3 ${\displaystyle 2^{\frac{5}{2}n}}$, R2

 KPA CPA-1 ${\displaystyle F_k^1}$ 1 1 ${\displaystyle F_k^2}$ ${\displaystyle 2^{\frac{n}{2}}}$, TWO 2 ${\displaystyle F_k^3}$ ${\displaystyle 2^{n}}$, TWO 2 ${\displaystyle F_k^d}$, ${\displaystyle 2 \le d \le k}$ ${\displaystyle 2^{\frac{d-1}{2}n}}$, TWO 2 ${\displaystyle F_k^k+1}$ ${\displaystyle 2^{\frac{k}{2}n}}$, TWO ${\displaystyle 2^{\frac{n}{2}}}$, TWO ${\displaystyle F_k^k+2}$ ${\displaystyle 2^{\frac{k+1}{2}n}}$, TWO ${\displaystyle 2^{n}}$, TWO ${\displaystyle F_k^k+3}$ ${\displaystyle 2^{\frac{2k+3}{4}n}}$, R2, R3 ${\displaystyle 2^{\frac{3n}{2}}}$, R2(new) ${\displaystyle F_k^k+4}$ ${\displaystyle 2^{\frac{k+2}{2}n}}$, R1 R2, R3 ${\displaystyle 2^{2n}}$, R2(new) ${\displaystyle F_k^k+5}$ ${\displaystyle 2^{\frac{2k+5}{4}n}}$, R2, R3 ${\displaystyle 2^{\frac{5n}{2}}}$, R2(new) . . . . . . . . . ${\displaystyle F_k^d}$, ${\displaystyle d=k+2q}$, ${\displaystyle 3 \le q \le k-2}$ ${\displaystyle 2^{\frac{d+k}{4}n}}$, R1 R2, R3 ${\displaystyle 2^{\frac{q^{2}+2}{q+1}n}}$, R2(new) ${\displaystyle F_k^d}$, ${\displaystyle d=k+2q+1}$, ${\displaystyle 3 \le q \le k-3}$ ${\displaystyle 2^{\frac{d+k}{4}n}}$, R2, R3 ${\displaystyle 2^{\frac{q^{2}+3}{q+1}n}}$, R2(new) . . . . . . . . . ${\displaystyle F_k^3k-1}$ ${\displaystyle 2^{(k-\frac{3}{4})n}}$, R2, R3 ${\displaystyle 2^{\frac{(k-1)k}{k+1}n}}$, R2(new) ${\displaystyle F_k^3k-2}$ ${\displaystyle 2^{(k-\frac{1}{2})n}}$, R1 R2, R3 ${\displaystyle 2^{(k-1)n}}$, R2(new) ${\displaystyle F_k^3k-3}$ ${\displaystyle 2^{(k-\frac{1}{2k+2})n}}$, R2, R3, (*) ${\displaystyle 2^{(k-\frac{1}{2})n}}$, R2

In these tables,“new” means that the complexity that we obtain is better than the complexity given in [3]. (*) means that for ${\displaystyle 3k-1}$ rounds our complexity is worse than the complexity in [3]. This comes from the fact, as we mentioned earlier, that the conditions between the equations and the internal variables were not all considered in [3].

## Conclusion

In this paper we make a systematic study of rectangle generic attacks on unbalanced Feistel schemes with expanding functions. Although these attacks were already analyzed in [2] and [3], this paper brings many improvements. Generation of all possible rectangle attacks for ${\displaystyle k \le 7}$ was performed thanks to a computer program and the most efficient ones were selected. Then the generalization for any ${\displaystyle k}$ was possible. This gives attacks for which conditions between equations and internal variables are satisfied. This was not detected in [3]. We also provide a complete description of the way to obtain CPA-1 from KPA. This shows how to get the best CPA-1 and we improved the CPA-1 complexity of [3]. Also many simulations confirm our theoretical results.

There are still some open problems. It would be interesting to complete the program in order to generate all the attacks for any ${\displaystyle k}$. This seems to be a memory space problem. Also, in this paper, we did not study attacks with complexity greater than ${\displaystyle kn}$. In that case, we need to attack permutations generators and not only one single permutation. In [3], attacks called “multi-rectangle attacks” were introduced, but so far no significant results have been obtained on these attacks. It might give a new way to study generic attacks on unbalanced Feistel schemes with expanding functions. As we mentioned in Section 3, when we have exactly the same condition on the input and output variables, there are many possible CPA-1 attacks (for ${\displaystyle k = 7}$, there exist 286 attacks on ${\displaystyle F_{7}^{20}}$, with the same conditions on the input and output variables). An estimation for any ${\displaystyle k}$ will strengthen the attack.

## Authors

Cite error: Invalid <references> tag; parameter "group" is allowed only.

Use <references />, or <references group="..." />

## Literature

Cite error: Invalid <references> tag; parameter "group" is allowed only.

Use <references />, or <references group="..." />

## Appendix

Appendix А. All the paths for the R2 attack against ${\displaystyle F_4^{11}}$, ${\displaystyle \varphi = 10}$

 ${\displaystyle 0}$ ${\displaystyle \centerdot\Delta_1}$ ${\displaystyle \Delta_2}$ ${\displaystyle \Delta_3}$ ${\displaystyle \Delta_4}$ ${\displaystyle \centerdot\Delta_1}$ ${\displaystyle \Delta_2}$ ${\displaystyle \Delta_3}$ ${\displaystyle \Delta_4}$ ${\displaystyle \centerdot\Delta_1}$ ${\displaystyle \Delta_2}$ ${\displaystyle \Delta_3}$ ${\displaystyle \Delta_4}$ ${\displaystyle \centerdot\Delta_1}$ ${\displaystyle \Delta_2}$ ${\displaystyle \Delta_3}$ ${\displaystyle \Delta_4}$ ${\displaystyle 1}$ ${\displaystyle 0}$ ${\displaystyle \Delta_5}$ ${\displaystyle \Delta_6}$ ${\displaystyle \centerdot\Delta_1}$ ${\displaystyle 0}$ ${\displaystyle \Delta_5}$ ${\displaystyle \Delta_6}$ ${\displaystyle \centerdot\Delta_1}$ ${\displaystyle 0}$ ${\displaystyle \Delta_5}$ ${\displaystyle \Delta_6}$ ${\displaystyle \centerdot\Delta_1}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \Delta_5}$ ${\displaystyle \centerdot\Delta_6}$ ${\displaystyle 2}$ ${\displaystyle \centerdot\Delta_5}$ ${\displaystyle \Delta_6}$ ${\displaystyle \Delta_1}$ ${\displaystyle 0}$ ${\displaystyle \centerdot\Delta_5}$ ${\displaystyle \Delta_6}$ ${\displaystyle \Delta_1}$ ${\displaystyle 0}$ ${\displaystyle \centerdot\Delta_5}$ ${\displaystyle \Delta_6}$ ${\displaystyle \Delta_1}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \Delta_5}$ ${\displaystyle \Delta_1}$ ${\displaystyle 0}$ ${\displaystyle 3}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \Delta_7}$ ${\displaystyle \centerdot\Delta_5}$ ${\displaystyle 0}$ ${\displaystyle \Delta_7}$ ${\displaystyle \Delta_8}$ ${\displaystyle \centerdot\Delta_5}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \centerdot\Delta_5}$ ${\displaystyle \centerdot\Delta_5}$ ${\displaystyle \Delta_1}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 4}$ ${\displaystyle 0}$ ${\displaystyle \Delta_7}$ ${\displaystyle \Delta_5}$ ${\displaystyle 0}$ ${\displaystyle \centerdot\Delta_7}$ ${\displaystyle \Delta_8}$ ${\displaystyle \Delta_5}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \Delta_5}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \Delta_6}$ ${\displaystyle \Delta_7}$ ${\displaystyle \centerdot\Delta_8}$ ${\displaystyle 5}$ ${\displaystyle \centerdot\Delta_7}$ ${\displaystyle \Delta_5}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \Delta_9}$ ${\displaystyle \centerdot\Delta_7}$ ${\displaystyle 0}$ ${\displaystyle \Delta_5}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \centerdot\Delta_6}$ ${\displaystyle \Delta_7}$ ${\displaystyle \Delta_5}$ ${\displaystyle 0}$ ${\displaystyle 6}$ ${\displaystyle 0}$ ${\displaystyle \Delta_8}$ ${\displaystyle \Delta_9}$ ${\displaystyle \centerdot\Delta_7}$ ${\displaystyle 0}$ ${\displaystyle \Delta_9}$ ${\displaystyle \Delta_7}$ ${\displaystyle 0}$ ${\displaystyle \centerdot\Delta_5}$ ${\displaystyle \centerdot 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \Delta_8}$ ${\displaystyle \Delta_9}$ ${\displaystyle \centerdot\Delta_6}$ ${\displaystyle 7}$ ${\displaystyle \centerdot\Delta_8}$ ${\displaystyle \Delta_9}$ ${\displaystyle \Delta_7}$ ${\displaystyle 0}$ ${\displaystyle \centerdot\Delta_9}$ ${\displaystyle \Delta_7}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \centerdot\Delta_7}$ ${\displaystyle \centerdot\Delta_8}$ ${\displaystyle \Delta_9}$ ${\displaystyle \centerdot\Delta_5}$ ${\displaystyle \centerdot\Delta_8}$ ${\displaystyle \Delta_9}$ ${\displaystyle \Delta_6}$ ${\displaystyle 0}$ ${\displaystyle 8}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \centerdot\Delta_8}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \centerdot\Delta_9}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \centerdot 0}$ ${\displaystyle \centerdot\Delta_7}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \centerdot\Delta_8}$ ${\displaystyle 9}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \Delta_8}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \Delta_9}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \Delta_7}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \Delta_8}$ ${\displaystyle 0}$ ${\displaystyle 10}$ ${\displaystyle 0}$ ${\displaystyle \Delta_8}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \Delta_9}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \Delta_7}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \Delta_8}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 11}$ ${\displaystyle \Delta_8}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \Delta_9}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \Delta_7}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \Delta_8}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \centerdot\Delta_1}$ ${\displaystyle \Delta_2}$ ${\displaystyle \Delta_3}$ ${\displaystyle \Delta_4}$ ${\displaystyle \centerdot\Delta_1}$ ${\displaystyle \Delta_2}$ ${\displaystyle \Delta_3}$ ${\displaystyle \Delta_4}$ ${\displaystyle \centerdot\Delta_1}$ ${\displaystyle \Delta_2}$ ${\displaystyle \Delta_3}$ ${\displaystyle \Delta_4}$ ${\displaystyle \centerdot\Delta_1}$ ${\displaystyle \Delta_2}$ ${\displaystyle \Delta_3}$ ${\displaystyle \Delta_4}$ ${\displaystyle 1}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \centerdot\Delta_1}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \centerdot\Delta_1}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \Delta_5}$ ${\displaystyle \centerdot\Delta_1}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \Delta_5}$ ${\displaystyle \centerdot\Delta_1}$ ${\displaystyle 2}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \Delta_1}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \Delta_1}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \Delta_5}$ ${\displaystyle \Delta_1}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \Delta_5}$ ${\displaystyle \Delta_1}$ ${\displaystyle 0}$ ${\displaystyle 3}$ ${\displaystyle 0}$ ${\displaystyle \Delta_1}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \Delta_1}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \centerdot\Delta_5}$ ${\displaystyle \centerdot\Delta_1}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \centerdot\Delta_5}$ ${\displaystyle \Delta_1}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 4}$ ${\displaystyle \centerdot\Delta_1}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \centerdot\Delta_1}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \centerdot\Delta_6}$ ${\displaystyle \Delta_7}$ ${\displaystyle \Delta_8}$ ${\displaystyle \centerdot\Delta_5}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \Delta_6}$ ${\displaystyle \centerdot\Delta_5}$ ${\displaystyle 5}$ ${\displaystyle \centerdot\Delta_5}$ ${\displaystyle \Delta_6}$ ${\displaystyle \Delta_7}$ ${\displaystyle \centerdot\Delta_1}$ ${\displaystyle 0}$ ${\displaystyle \Delta_5}$ ${\displaystyle \Delta_6}$ ${\displaystyle \centerdot\Delta_1}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \centerdot\Delta_9}$ ${\displaystyle \centerdot\Delta_6}$ ${\displaystyle 0}$ ${\displaystyle \Delta_6}$ ${\displaystyle \Delta_5}$ ${\displaystyle 0}$ ${\displaystyle 6}$ ${\displaystyle 0}$ ${\displaystyle \Delta_8}$ ${\displaystyle \centerdot\Delta_9}$ ${\displaystyle \centerdot\Delta_5}$ ${\displaystyle \centerdot\Delta_5}$ ${\displaystyle \centerdot\Delta_6}$ ${\displaystyle \Delta_1}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \Delta_9}$ ${\displaystyle \Delta_6}$ ${\displaystyle 0}$ ${\displaystyle \centerdot\Delta_6}$ ${\displaystyle \centerdot\Delta_5}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 7}$ ${\displaystyle \centerdot\Delta_8}$ ${\displaystyle \Delta_9}$ ${\displaystyle \Delta_5}$ ${\displaystyle 0}$ ${\displaystyle \centerdot\Delta_7}$ ${\displaystyle \Delta_8}$ ${\displaystyle \Delta_9}$ ${\displaystyle \centerdot\Delta_5}$ ${\displaystyle \centerdot\Delta_9}$ ${\displaystyle \Delta_6}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \centerdot\Delta_7}$ ${\displaystyle \Delta_8}$ ${\displaystyle \Delta_9}$ ${\displaystyle \centerdot\Delta_6}$ ${\displaystyle 8}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \centerdot\Delta_8}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \centerdot\Delta_7}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \centerdot\Delta_9}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \centerdot\Delta_7}$ ${\displaystyle 9}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \Delta_8}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \Delta_7}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \Delta_9}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \Delta_7}$ ${\displaystyle 0}$ ${\displaystyle 10}$ ${\displaystyle 0}$ ${\displaystyle \Delta_8}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \Delta_7}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \Delta_9}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \Delta_7}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 11}$ ${\displaystyle \Delta_8}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \Delta_7}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle \Delta_9}$