Improved Generic Attacks on Unbalanced Feistel Schemes with Expanding Functions

From Bauman National Library
This page was last modified on 9 August 2016, at 12:51.
Improved Generic Attacks on Unbalanced Feistel Schemes with Expanding Functions
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 bits to bits with . From a practical point of view, an interesting property of these schemes is that since and 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 , and then we have generalized these improved attacks for all . 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 to is to use Feistel schemes with rounds built with round functions . 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 and the functions are from to .


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 operations: for 5 rounds, an attack in operations is given in [6] and for 3 or 4 rounds an attack in 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 and when the round functions are from bits to 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 and when the round functions are from bits to 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 bits to bits than a random function of bits to 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 where our complexity is slightly greater than in 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 , 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 still gives the best possible attacks. We also provide simulation results for.

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 . 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 and introduce some useful notations. is a Feistel scheme of rounds that produces a permutation from bits to bits. At each round , we denote by the round function from bits to bits. is defined as , where each function is defined from to . On some input , produces an output denoted by by going through rounds. At round , the first bits of the round entry are called . We can notice that . We compute and obtain bits. Those bits are xored to the last bits of the round entry and the result is rotated by bits.

The first round is represented on Figure 1 below:

First Round.PNG

We have

More generally, we can express the recursively:

After rounds , the output can be expressed by using the introduced values :

We don’t need another notation, but for a better understanding we introduce a notation for the intermediate values. After round , we obtain . So we have , and for all and .

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 -tuple of distinct points , and we counthow many -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 -tuples that match the conditions is more important for a scheme than for a random permutation. We introduce more definition. After rounds, we define “horizontal equalities” on part of the output as and . Let . “Vertical equalities” on part are given by , , . We also define “differential equalities” on part by , , . 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 ). This may imply that other equalities will be satisfied with probability 1. On the input and output variables we will always have 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.

Fig2.PNG

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 scheme. See Table 1.


Table 1. attack
(раунд)
0
1
2
3
4
5
6

The "" in this table means that there are horizontal equalities or conditions. The "" 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: (number of input conditions), (number of internal conditions), (number of output conditions). If a -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 -tuple will be greater for a permutation.



Example: CPA-1 attack on 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 . In the next sections a complete analysis will be given for more general parameters. This attack is the one described in Table 1 with and so . 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 such that and the first bits of are 0. So, we will generate exactly messages.

Lemma 1
Therefore there are 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 possibilities. For the second we have only possibilities because and are imposed by the first message. For the third point we have again possibilities, and then we have no choice for the last point. Therefore there are 4-tuple of points that satisfy all the input conditions.


For a scheme, each of these tuple will satisfy at random the 4 internal conditions with a probability equal to . 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 complexity and messages. This is better than the found in [3]. To find this complexity we can also use Table 3 with , , и . 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 and 1000 атак, attacks, we were able to distinguish 575 schemes from a random permutation, so the percentage of success is about 57,5%.

Fig3.PNG

Generation of all possible attacks for 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 . First we choose a value for , then we increase the value of , 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 and .

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 vertical conditions, because it leads to a collision between the points, i.e. and .
  • In the same round, it’s not possible to have horizontal conditions, because it also lead to a collision between the points, i.e. and и .

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: .
  2. There must be less internal conditions than output conditions: .
  3. If then 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 attack given in section 2.2. The equations are: , , , . We have 4 equations and 5 variables , , , , . 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 scheme, and 20 attacks with a CPA-1 complexity equal to .

All possible attacks are given in an extended version of this paper. In the next sections, we generalize for any the best attacks (KPA and CPA-1) obtained for .

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

TWO Attacks

The TWO attack consists in using plaintext/ciphertexts pairs and in counting the number of couples of these pairs that satisfy the relations between the input and output variables. We then compare with where is the number of couples of pairs for a random permutation instead of . The attack is successful, i.e. we are able to distinguish from a random permutation if the difference is much larger than the standard deviation and than the standard deviation , where denotes the expectancy function. These attacks give the best attacks from round to . 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:

... ... ... ...
Round ... ... Round ... ...

Thus, , , . Here denotes the conditions on the input variables. . The number of vertical conditions on the input variables is . denotes the number of conditions on the internal variables. We use for horizontal conditions and for vertical conditions. Similarly, and denote respectively the number of conditions and the number of vertical conditions on the output variables. Then the number of rounds is given by . When 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 than with a random permutation. Here this gives the condition: . 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 and the number of variables is . Thus we get the condition: . The complexity of such an attack is . This implies , i.e. .


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:

... ... ... ...
Round ... ... Round ... ...

Thus, , , . The number of horizontal conditions on the input variables is denoted by . The number of rounds is given . The condition is equivalent to . For R2 attacks, it is easy to check that the number of equations is given by , and the number of variables is . Thus we get the condition: . The complexity of such an attack is . This implies , i.e. . .

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:

... ... ... ...
Round ... ... Round ... ...

and , ,

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

... ... ... ...
Round ... ... Round ... ...

and , ,

Best KPA attacks: R1, R2

In this section we describe the best attacks we have found. As mentioned before, we know that for , 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 rounds to rounds since from to 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:
Table 2. Best known KPA on , for any
values Complexity
(a) When and , we set

, ,

It is possible to choose and the complexity is also .

(b) When and , we set

, ,

The complexity is still , but is greater than .

  1. In [2] Jutla gave a R1 attack on rounds but the complexity that we obtain with a R2 attack here is better. It is possible to perform a R1 attack on rounds just by adding a vertical condition on the input variables to the attack on 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 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 the number of horizontal conditions, the number of vertical condition and . So we can distinguish four cases:

  1. :
  2. :
  3. :
  4. :
Table 3. KPA to CPA
Conditions

vertical conditions

horizontal conditions

и

horizontal conditions and vertical conditions

and

and


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: .

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 the number of varying bits among the first bits, and we call the number of varying bits among the last bits. So we have and , and this allow us to generate points (plaintext/cyphertext pair). Now we count how many -tuple of points will verify the input conditions. For we have possibilities, for only possibilities, because the first bits are imposed by . For we have again possibilities. For only one possibility: . We continue like this until we reach the last two points. For we have again almost possibilities, and for only one possibility. So, the total number of -tuple is . The complexity of the CPA-1 is equal to . We want this number to be as small as possible, and at the same time we want to generate a maximum of -tuples that satisfy the input conditions. So, we want to have as large as possible. Each -tuples has a probability equal to to satisfy the internal conditions. In order to have a reasonable chance to realize these conditions, we must have . If we get . But this is possible only if , i.e. if . If we have , then we must take the maximum possible value for : and that gives us a CPA-1 complexity equal to .


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 we know that we have the best possible attacks. Except for 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 since for , 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:

Table 4. Best known CPA-1 on , for any
values Complexity

Remark. For , , and , there exist R1 attacks with the same complexity and the same number of points.

Overview of the R2 CPA-1 Attack on 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:


... ...
Round ... Round ...

Several different differential paths match with these input and output conditions. For example let’s see all the R2 path for the and permutations. See Table 5 and Table 9 in Appendix A.

Table 5. All the paths for the R2 attack against ,
Path 1:
0
1
2
3
4
5
6
7
8
Path 2:
0
1
2
3
4
5
6
7
8

We counted the number of paths for :

3 4 5 6 7
path 2 8 27 89 296


We will see that, the greater 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 scheme. For both schemes, we compute ciphertext/plaintext pairs, by varying only the last 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 -tuple of points match the input and output condition. If we found couples of points that satisfy all these conditions with , we count as if we have found -tuple, because this is the number of -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 , since we have generated all the attacks, these are the best possible attacks.

Table 6. Experimental results for
of success of false alarm iteration
2 3 6 29,09 0,35 100000
2 4 8 61,6 0,06 10000
2 5 10 98,37 0 10000
2 6 12 99,99 0 10000
2 7 14 100 0 1000
2 8 16 100 0 1000
2 9 18 100 0 500
2 10 20 100 0 100
4 3 12 21,15 1,12 10000
4 4 16 42,5 0 1000
4 5 20 93 0 100
4 6 24 100 0 100
6 3 18 8 1,2 500
8 3 24 2 0 100


Then we have generalized the results for and we believe that the attacks presented here are also the best possible attacks. For , we have TWO attacks. For , 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 rounds for example). In CPA-1, the best complexity is given by R2 attacks, and sometimes R1 attacks.


Table 7. Best known TWO and Rectangle attacks on . Details about the parameters in this table: (new) means that we have found a better attack than previously known.
KPA CPA-1
1 1
, TWO 2
, TWO 2
, TWO , TWO
, TWO , TWO
, R2, R3 , R2(new)
, R1, R2, R3 , R2
, R2, R3 , R2


Table 8. Best known TWO and Rectangle attacks on , for any . Details about the parameters in this table: (new) means that we have found a better attack than previously know.
KPA CPA-1
1 1
, TWO 2
, TWO 2
, , TWO 2
, TWO , TWO
, TWO , TWO
, R2, R3 , R2(new)
, R1 R2, R3 , R2(new)
, R2, R3 , R2(new)
.

.

.

.

.

.

.

.

.

, , , R1 R2, R3 , R2(new)
, , , R2, R3 , R2(new)
.

.

.

.

.

.

.

.

.

, R2, R3 , R2(new)
, R1 R2, R3 , R2(new)
, R2, R3, (*) , R2

In these tables,“new” means that the complexity that we obtain is better than the complexity given in [3]. (*) means that for 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 was performed thanks to a computer program and the most efficient ones were selected. Then the generalization for any 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 . This seems to be a memory space problem. Also, in this paper, we did not study attacks with complexity greater than . 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 , there exist 286 attacks on , with the same conditions on the input and output variables). An estimation for any 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 ,

Table 9. All the paths for the R2 attack against ,