General Cryptanalytic Methods - Modern Cryptanalysis: Techniques for Advanced Code Breaking - page 129

For a chosen-plaintext attack, we do a very similar attack. First, we choose a random n /2 bit value, x, for one
of the halves, and then we select 2 n/4 random values for y to form the plaintext ( x , y) (where x is the left half, y
is the right half).
For our second plaintext, we again use a fixed x and generate a value z that is completely random. We gener-
ate another 2 n /4 of these values and store the plaintext ( z , x) (this time, the right half is x, and the left half is z ).
We also calculate the encryptions of both plaintexts to form the pairs and store these pairs in a large table.
With this many pairs, we expect to find about one slid pair.
An individual Feistel round is usually fairly weak; thus, when a slid pair is found using either method, we
can usually expect to get the entire key, or most of it, fairly easily.
5.4.2 Advanced Slide Attacks
One issue with standard slide attacks is that ciphers with two or more rounds of self-similarity tend to make the
attack less practical. Self-similiarity means that the cipher switches between two or more round functions or
keys (or both) every round. To combat a two-round, self-similar cipher with a standard slide attack, we would
have to slide two rounds instead of one, which makes the attack more difficult.
There areafewtricks that canbeusedtocombat these problems [1].Thefirstiscalled the complementation
slide attack . We perform a complementation slide attack by, instead of sliding by two rounds, as we suggested
before, sliding by one.
The change comes in that we will now have to look for a different type of slid pair. Previously, we looked for
a slid pair so that F(P) = Q, but now we want one so that F(P) ⊕ Q = Δ where Δ is not zero.
In these cases, if we find multiple slid pairs, we will always have the same Δ. Therefore, identifying slid
pairs is still fairly easy.
To derive the key, we can analyze the value of Δ. Typically, Δ will be equal to something along the lines of
the XOR of the two round subkeys, giving us a lot of information that can be used to break them (such as by
doing an exhaustive search against half of the bits to derive the rest).
Another property of two-round self-similarity is that the decryption process looks nearly identical to the en-
cryption process: They just start one round off from each other, since they do the rounds in reverse order. We
can use this property in a method called sliding with a twist [1].
The twist is that we will look at the second plaintext-ciphertext pair of the slid pair backwards to look for
the slid pair. The two-round self-similarity will then give us F(P) = D and F(C) = Q, and allow us to derive a
key very similarly to above.
Consider the above case, only with four-round self-similarity (four distinct rounds, perhaps with different
keys used each time). The above complementation attack could be used by sliding two rounds to achieve the
similarity, but this would again be decreasing our effectiveness.
Both methods can be combined, creating a complementation slide with a twist [1]. These two methods
combined will allow us to develop a better attack against that four-round self-similar version.
Essentially, we are looking for a fixed difference, and we are using the second part of the slid pair in reverse
order. This will line up the keys submitted to the Feistel round function as follows (the top is the encryption, the
bottom is the decryption, slid once):
With this slid pair then, all of the differences cancel out except for the K 1 ⊕ K 3 pairs. We then can look for a Δ
of K 1 ⊕ K 3 and use it to derive the key.