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

Figure 5-1 A slid pair for a very simple cipher.
When these two pairs of plaintext-ciphertext pairs have this property, we call them a slid pair .
The useful thing about a slid pair is that, if the round function is very weak (like we assume), then we can
find the key very easily from a slid pair, since we have two simple relationships:
Both the plaintext pair ( P, Q ) and the ciphertext pair ( C, D ) give us information that we can use to derive the
key.
Let's move to a practical example of this. Consider the FEAL cipher, with the round function:
If we want to check for a slid pair, the only unknown variables would be the β 's.
This means that for the second step, we get
And if we already know the value of f 2 ,α 2 , α 3 , f 1 , then we can easily calculate β 1 by reversing the S-box and
plugging in the appropriate values.
Similarly, we can use the first step to derive β 0 , since we will know all of the other parts.
Once we know the two β values, we can calculate F(A) and check to see if it matches up with B. If everything
matches up, then we have, in all likelihood, found a slid pair. We then perform the same derivations as above on
the ciphertexts to determine more of the key schedule.
With some luck, finding the slid pair will reveal enough bits of the key to allow brute-forcing the remaining
bits. For example, several bits of the output of the round might be independently modified by portions of the
key material, sometimes by direct XOR, allowing the key bits to be easily derived.
5.4.1 Slide Attacks on Feistel Ciphers
Finding a slid pair with a Feistel cipher is not difficult. After one round of encryption on a Feistel cipher, the
output will have half of the bits the same as the input (the old left half becomes the new right half).
With a known-plaintext attack, we can simply look at the slid pair's plaintexts and ciphertexts to check if
F(P) = Q and F(C) = D. Finding the slid pair is a simple matter of sorting tables of plaintexts and ciphertexts so
that matches can be quickly found.
There is the possibility of a false alarm here, but it is not too significant; on average, we can expect one false
alarm for every real slid pair.
This known-plaintext attack requires about 2 n /2 plaintext-ciphertext pairs (half of the size of the cipher,
which is also the size of the Feistel structure), and about the same amount of work.