Slide attack

The idea of the slide attack was originally published by Edna Grossman and Bryant Tuckerman in an IBM Technical Report in 1977. It is a form of cryptanalysis designed to deal with the prevailing idea that even weak ciphers can become very strong by increasing the number of rounds, which can ward off a differential attack. Grossman and Tuckerman demonstrated the attack on a weak block cipher named New Data Seal (NDS). A summary of the report, including a description of the NDS block cipher and the attack, is given in Cipher Systems (Beker & Piper, 1982). The term slide attack was coined by David Wagner and Alex Biryukov in 1999.

The slide attack works in such a way as to make the number of rounds in a cipher irrelevant. Rather than looking at the data-randomizing aspects of the block cipher the slide attack works by analyzing the key schedule and exploiting weaknesses in it to break the cipher. The most common one is the keys repeating in a cyclic manner.

The only requirements for a slide attack to work on a cipher is that it can be broken down into multiple rounds of an identical F function. This probably means that it has a cyclic key schedule. The F function must be vulnerable to a known-plaintext attack. The slide attack is closely related to the related-key attack.

The actual attack

First, to introduce some notation. In this section we assume the cipher takes n bit blocks and has a key-schedule using $K_{1}\cdots K_{m}$ as keys of any length.

The slide attack works by breaking the cipher up into identical permutation functions, F. This F function may consist of more than one round of the cipher; it is defined by the key-schedule. For example, if a cipher uses an alternating key schedule where it switches between a $K_{1}$ and $K_{2}$ for each round, the F function would consist of two rounds. Each of the $K_{i}$ will appear at least once in F.

The next step is to collect $2^{n/2}$ plaintext-ciphertext pairs. Depending on the characteristics of the cipher we may need fewer, but, by the birthday paradox, we expect to need no more than $2^{n/2}$. These pairs, which we will denote as $(P,C)$ are then used to find a slid pair which we will denote $(P_{0},C_{0})(P_{1},C_{1})$. A slid pair has the property that $P_{0}=F(P_{1})$ and that $C_{0}=F(C_{1})$. Once we have identified a slid pair, the cipher is broken because of the vulnerability to known-plaintext attacks. The key can easily be extracted from this pairing. The slid pair can be thought to be what happens to your message after one application of the function F. It is ’slid’ over one encryption round and this is where the attack gets it’s name.

The process of finding a slid pair is somewhat different for each cipher but follows the same basic scheme. One uses the fact that it is relatively easy to extract the key from just one iteration of F. You pick any pair of plaintext-ciphertext pairs, $(P_{0},C_{0})(P_{1},C_{1})$ and check to see what the keys corresponding to $P_{0}=F(P_{1})$ and $C_{0}=F(C_{1})$ are. If these keys match, you have found a slid pair, if not you should move on to the next pair.

With $2^{n/2}$ plaintext-ciphertext pairs you should expect to find one slid pair and a small number of false-positives depending on the structure of the cipher. The false positives can be eliminated by using the keys on a different message-ciphertext pair and see if the encryption is correct. The probability that the wrong key will correctly encipher two or more messages is very low for a good cipher.

Sometimes the structure of the cipher greatly reduces the number of plaintext-ciphertext pairs needed, and thus also a large amount of the work. The clearest of these examples is the Feistel cipher using just one key. The reason for this is given a $P=(L_{0},R_{0})$ you must look for a $P_{0}=(R_{0},L_{0}\bigoplus F(R_{0},K))$. This reduces the possible paired messages from $2^{n}$ down to $2^{n/2}$ (since half the message is fixed) and so we will only need to collect at most $2^{n/4}$ plaintext-ciphertext pairs in order to find a slid-pair.

References

• Analysis of a Feistel-like cipher weakened by having no rotating key. E.K.Grossman and B.Tuckerman. IBM Thomas J. Watson Research Report RC 6375, 1977.
• Cipher Systems: The Protection of Communications. Henry Beker and Fred Piper. Northwood Books: London, 1982. (contains a summary of the paper by Grossman and Tuckerman).
• Slide Attacks Alex Biryukov and David Wagner. FSE'99
• Advanced Slide Attacks Alex Biryukov and David Wagner. EUROCRYPT 2000.
• Slide Attacks with a Known-Plaintext Cryptanalysis S. Furuya
• New Types of Cryptanalytic Attacks Using Related Keys Eli Biham
• Related-Key and Slide Attacks: Analysis, Connections and Improvements M. Ciet, G. Piret, J. Quisquater