[Next] [Up] [Previous] [Index]

The Inner Structure of the Feistel Round

Many block ciphers are built upon a structure called the Feistel round, named after Horst Feistel of IBM, who originated this structure for the block cipher LUCIFER.

The block of data to be enciphered is divided into two halves, and in a Feistel round, only one half is changed, by being XORed with a function of the other half. Since the other half isn't changed, it is still available after the round is over; thus, even if the function of that half used to XOR with the half that is changed is not invertible, the round is still invertible.

Thus, one could make some horrible programming error in implementing the f-function in a Feistel cipher, and the result would still "work" for sending and receiving messages, even if the resulting cipher was not secure. This is not necessarily a good thing.

It also means that the direct data path from plaintext to cipher only includes XORs, instead of actually going *through* an S-box whose inverse is then needed for decryption. Just on general principles, this tended to make some people nervous, at least in the early days of DES.

For an extremely scaled-down version of a Feistel cipher, I have produced a complete table of what it does for every possible key.

But first, let us examine for comparison the tableaux for some simpler operations.

For modulo-16 addition, we get what resembles a Vigenère tableau:

    0 1 2 3 4 5 6 7 8 9 A B C D E F
    -------------------------------
0 | 0 1 2 3 4 5 6 7 8 9 A B C D E F
1 | 1 2 3 4 5 6 7 8 9 A B C D E F 0
2 | 2 3 4 5 6 7 8 9 A B C D E F 0 1
3 | 3 4 5 6 7 8 9 A B C D E F 0 1 2
4 | 4 5 6 7 8 9 A B C D E F 0 1 2 3
5 | 5 6 7 8 9 A B C D E F 0 1 2 3 4
6 | 6 7 8 9 A B C D E F 0 1 2 3 4 5
7 | 7 8 9 A B C D E F 0 1 2 3 4 5 6
8 | 8 9 A B C D E F 0 1 2 3 4 5 6 7
9 | 9 A B C D E F 0 1 2 3 4 5 6 7 8
A | A B C D E F 0 1 2 3 4 5 6 7 8 9
B | B C D E F 0 1 2 3 4 5 6 7 8 9 A
C | C D E F 0 1 2 3 4 5 6 7 8 9 A B
D | D E F 0 1 2 3 4 5 6 7 8 9 A B C
E | E F 0 1 2 3 4 5 6 7 8 9 A B C D
F | F 0 1 2 3 4 5 6 7 8 9 A B C D E

And here is the table for the XOR operation.

    0 1 2 3 4 5 6 7 8 9 A B C D E F
    -------------------------------
0 | 0 1 2 3 4 5 6 7 8 9 A B C D E F
1 | 1 0 3 2 5 4 7 6 9 8 B A D C F E
2 | 2 3 0 1 6 7 4 5 A B 8 9 E F C D
3 | 3 2 1 0 7 6 5 4 B A 9 8 F E D C
4 | 4 5 6 7 0 1 2 3 C D E F 8 9 A B
5 | 5 4 7 6 1 0 3 2 D C F E 9 8 B A
6 | 6 7 4 5 2 3 0 1 E F C D A B 8 9
7 | 7 6 5 4 3 2 1 0 F E D C B A 9 8
8 | 8 9 A B C D E F 0 1 2 3 4 5 6 7
9 | 9 8 B A D C F E 1 0 3 2 5 4 7 6
A | A B 8 9 E F C D 2 3 0 1 6 7 4 5
B | B A 9 8 F E D C 3 2 1 0 7 6 5 4
C | C D E F 8 9 A B 4 5 6 7 0 1 2 3
D | D C F E 9 8 B A 5 4 7 6 1 0 3 2
E | E F C D A B 8 9 6 7 4 5 2 3 0 1
F | F E D C B A 9 8 7 6 5 4 3 2 1 0

Here is the table for the permutations produced by the successive positions of a 16-contact rotor wired by the interval method. As the rows represent the successive positions of the rotor, their number is first subtracted from the input, then the rotor substitution is performed, and then that number is added to the result. Hence, the diagonals running down from left to right show the normal sequence (0, 1, 2, 3, 4, ... D, E, F) with some starting point.

    0 1 2 3 4 5 6 7 8 9 A B C D E F
    -------------------------------
0 | 1 C 7 F B 8 6 4 E 0 3 D A 5 2 9
1 | A 2 D 8 0 C 9 7 5 F 1 4 E B 6 3
2 | 4 B 3 E 9 1 D A 8 6 0 2 5 F C 7
3 | 8 5 C 4 F A 2 E B 9 7 1 3 6 0 D
4 | E 9 6 D 5 0 B 3 F C A 8 2 4 7 1
5 | 2 F A 7 E 6 1 C 4 0 D B 9 3 5 8
6 | 9 3 0 B 8 F 7 2 D 5 1 E C A 4 6
7 | 7 A 4 1 C 9 0 8 3 E 6 2 F D B 5
8 | 6 8 B 5 2 D A 1 9 4 F 7 3 0 E C
9 | D 7 9 C 6 3 E B 2 A 5 0 8 4 1 F
A | 0 E 8 A D 7 4 F C 3 B 6 1 9 5 2
B | 3 1 F 9 B E 8 5 0 D 4 C 7 2 A 6
C | 7 4 2 0 A C F 9 6 1 E 5 D 8 3 B
D | C 8 5 3 1 B D 0 A 7 2 F 6 E 9 4
E | 5 D 9 6 4 2 C E 1 B 8 3 0 7 F A
F | B 6 E A 7 5 3 D F 2 C 9 4 1 8 0

Such a tableau is referred to as a Friedman square. From the property of its diagonals, a method analogous to symmetry of position can be derived for use in the late stages of cracking a rotor cipher. Since the position, and value, of corresponding equivalents in different rows changes with each row, however, this only works if one knows the displacement between the two alphabets being compared, which is unlike the case for conventional symmetry of position. Since in rotor machines, rotors usually move one step at a time, and in the same direction, this condition can be met.

And here is the tableau for a Feistel round, which, for this example, is two rounds of a cipher that operates on four bit values with the S-box (3,1,0,2) as the f-function. In this table, the columns represent the plaintext input, and the rows represent the four-bit value which is the concatenation of the two two-bit subkeys for the two rounds (which are XORed with the input to the S-box, following DES). I am using in-place Feistel rounds, and the first round uses the left half of the block as the input to the f-function.

    0 1 2 3 4 5 6 7 8 9 A B C D E F
    -------------------------------
0 | B 2 5 C 1 8 F 6 4 D A 3 E 7 0 9
1 | 3 A D 4 9 0 7 E C 5 2 B 6 F 8 1
2 | 7 E 9 0 D 4 3 A 8 1 6 F 2 B C 5
3 | F 6 1 8 5 C B 2 0 9 E 7 A 3 4 D
4 | 5 C B 2 F 6 1 8 A 3 4 D 0 9 E 7
5 | D 4 3 A 7 E 9 0 2 B C 5 8 1 6 F
6 | 9 0 7 E 3 A D 4 6 F 8 1 C 5 2 B
7 | 1 8 F 6 B 2 5 C E 7 0 9 4 D A 3
8 | C 5 2 B 6 F 8 1 3 A D 4 9 0 7 E
9 | 4 D A 3 E 7 0 9 B 2 5 C 1 8 F 6
A | 0 9 E 7 A 3 4 D F 6 1 8 5 C B 2
B | 8 1 6 F 2 B C 5 7 E 9 0 D 4 3 A
C | 2 B C 5 8 1 6 F D 4 3 A 7 E 9 0
D | A 3 4 D 0 9 E 7 5 C B 2 F 6 1 8
E | E 7 0 9 4 D A 3 1 8 F 6 B 2 5 C
F | 6 F 8 1 C 5 2 B 9 0 7 E 3 A D 4

Because only two rounds are performed, the last two bits are only changed by being XORed, for any key, with a fixed function of the first two bits, as they are on entry. The first two bits are changed by being XORed, for any key, with a fixed function of the last two bits as they are on exit. This leads to some of the patterns which are visible in the tableau above.

If, instead, we use the right half as the f-function input first, other patterns become visible (still using the first part of the row number as the first subkey):

    0 1 2 3 4 5 6 7 8 9 A B C D E F
    -------------------------------
0 | E 4 1 B 8 2 7 D 5 F A 0 3 9 C 6
1 | C 6 3 9 A 0 5 F 7 D 8 2 1 B E 4
2 | D 7 2 8 B 1 4 E 6 C 9 3 0 A F 5
3 | F 5 0 A 9 3 6 C 4 E B 1 2 8 D 7
4 | 5 F A 0 3 9 C 6 E 4 1 B 8 2 7 D
5 | 7 D 8 2 1 B E 4 C 6 3 9 A 0 5 F
6 | 6 C 9 3 0 A F 5 D 7 2 8 B 1 4 E
7 | 4 E B 1 2 8 D 7 F 5 0 A 9 3 6 C
8 | 3 9 C 6 5 F A 0 8 2 7 D E 4 1 B
9 | 1 B E 4 7 D 8 2 A 0 5 F C 6 3 9
A | 0 A F 5 6 C 9 3 B 1 4 E D 7 2 8
B | 2 8 D 7 4 E B 1 9 3 6 C F 5 0 A
C | 8 2 7 D E 4 1 B 3 9 C 6 5 F A 0
D | A 0 5 F C 6 3 9 1 B E 4 7 D 8 2
E | B 1 4 E D 7 2 8 0 A F 5 6 C 9 3
F | 9 3 6 C F 5 0 A 2 8 D 7 4 E B 1

Note, interestingly, that the columns are also permutations of the hexadecimal digits from 0 to F. This is a consequence of using an invertible f-function, one without an expansion permutation. It is well known that DES with only two rounds would be easy to crack.

Could one throw a curve to a cryptanalyst by exchanging the roles of subkey and plaintext in a two-round Feistel cipher such as this? In other words, can the subkey in this case be produced with a simple formula?

Yes: if we note our S-box as f(x), and its inverse as F(x), and the two halves of the plaintext as p1 and p2, the two halves of the ciphertext as c1 and c2, and the two subkeys as s1 and s2, a two round Feistel cipher becomes:

c2 = p2 XOR f( p1 XOR s1 )
c1 = p1 XOR f( c2 XOR s2 )

To solve for s1 and s2, given both c and p, and having F(x), we first XOR both sides of the equations with p2 and p1 respectively:

c2 XOR p2 = f( p1 XOR s1 )
c1 XOR p1 = f( c2 XOR s2 )

Then, invert f:

F( c2 XOR p2 ) = p1 XOR s1
F( c1 XOR p1 ) = c2 XOR s2

Then, XOR the two sides of the equations by p1 and c2 respectively:

p1 XOR F( c2 XOR p2 ) = s1
c2 XOR F( c1 XOR p1 ) = s2

In other words, with a two-round Feistel cipher, the f-function output is always the plaintext XOR the ciphertext, and so the subkey is found by inverting the f-function, and comparing the result to the input, which is visible in the ciphertext for the second round, and visible in the plaintext for the first round.

With DES, one has four possibilities for the subkey for every nybble, because of the two extra bits due to the expansion permutation. This can be overcome when one just has two rounds to solve. QUADIBLOC, on the other hand, has an invertible f-function, but three subkeys, not just one, go into the f-function.

What would be of concern in connection with the general security of block ciphers would be if one could easily take two known plaintexts, and solve a four-round Feistel cipher by imposing the constraint (essentially, on the result after the second round) that both sets of equations simultaneously have the same subkeys.

Then, if the same process could be repeated and generalized, eight known plaintexts would be sufficient to crack a cipher like DES but without an expansion permutation.

In this case, then, our equations would be (denoting our two plaintexts and ciphertexts by p and P and c and C respectively, and using t and T for the intermediate two-round results, and S for the second set of two subkeys):

s1 = p1 XOR F( t2 XOR p2 ) = P1 XOR F( T2 XOR P2 )   [1]
s2 = t2 XOR F( t1 XOR p1 ) = T2 XOR F( T1 XOR P1 )   [2]
S1 = t1 XOR F( c2 XOR t2 ) = T1 XOR F( C2 XOR T2 )   [3]
S2 = c2 XOR F( c1 XOR t1 ) = C2 XOR F( C1 XOR T1 )   [4]

The number of equations and the number of unknowns is correct for solution. I've labelled the four equations with the numbers from 1 to 4 for the next step.

But while f is invertible, it is also, in the general case, nonlinear. In our reduced-scale example, because we used only a four-element S-box, we can't produce a permutation that is neither linear nor affine, but that ceases to be true as soon as we go to a wider S-box; even one with eight elements that is nonlinear is possible, as used in the cipher 3-Way.

Does a nonlinear S-box prevent us from going further in solving these equations?

Note that with chosen plaintexts and ciphertexts, it should be possible to crack a four-round cipher if we can crack a two-round one directly with a single known plaintext, by a variation of David Wagner's boomerang method; but that method does not generalize to higher number of rounds, and we will therefore not consider it at this stage. However, if we can get to eight rounds before the equations become impractically complex, the boomerang attack would get us the rest of the way.

In the equations above, our problem is that t and T are unknown. What we have to overcome this is that the same key, and hence the same subkeys, are used in both cases.

We can manipulate the equations to get:

t2  = p2 XOR f( p1 XOR P1 XOR F( T2 XOR P2 ) )   [from 1]
    = c2 XOR f( t1 XOR T1 XOR F( C2 XOR T2 ) )   [from 3]
t1  = c1 XOR f( c2 XOR C2 XOR F( C1 XOR T1 ) )   [from 4]
    = p1 XOR f( t2 XOR T2 XOR F( T1 XOR P1 ) )   [from 2]

Does the fact that t1 and T1, and t2 and T2, are separated from each other by F and f prevent us from going further, except by trial-and-error methods, which will become useless as more rounds are added, or can a Feistel cipher fall to this type of analytic attack?

We can certainly substitute for t1 and t2, and also for T1 and T2, since we can reverse the roles of the two known plaintexts and use the same equations, but that doesn't eliminate unknowns; thus, T1 can be expressed as a function of known quantities and t1, but that identity is simply the inverse of the one labelled "from 4" above.

If we apply this inversion to the equations marked "from 3" and "from 2", we do get a set of equations that appears to fit together:

t2  = p2 XOR f( p1 XOR P1 XOR F( T2 XOR P2 ) )
T2  = C2 XOR f( T1 XOR t1 XOR F( c2 XOR t2 ) )
t1  = c1 XOR f( c2 XOR C2 XOR F( C1 XOR T1 ) )
T1  = P1 XOR f( T2 XOR t2 XOR F( t1 XOR p1 ) )

because now, by substituting, we can eliminate t1 and t2, and just obtain two equations in T1 and T2.

These equations are:

T2  = C2 XOR f( T1 XOR c1 XOR f( c2 XOR C2 XOR F( C1 XOR T1 ) ) XOR
                F( c2 XOR p2 XOR f( p1 XOR P1 XOR F( T2 XOR P2 ) ) ) )
T1  = P1 XOR f( T2 XOR p2 XOR f( p1 XOR P1 XOR F( T2 XOR P2 ) ) XOR
                F( c1 XOR f( c2 XOR C2 XOR F( C1 XOR T1 ) ) XOR p1 ) )

And it is at this stage that it appears that further simplification is indeed made impossible if f and F are general S-boxes, and so it appears that Feistel ciphers are safe against a simple attack by algebra.


[Next] [Up] [Previous] [Index]

Next Chapter
Chapter Start
Table of Contents
Main Page