characteristics of the cipher fewer may suffice, but by the birthday problem no more than should be needed. These pairs, which denoted as are then used to find a slid pair which is denoted . A slid pair has the property that and that . Once a slid pair is identified, 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 a message after one application of the function F. It is ’slid’ over one encryption round and this is where the attack gets its 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. Choose any pair of plaintext-ciphertext pairs, and check to see what the keys corresponding to and are. If these keys match, this is a slid pair; otherwise move on to the next pair. With plaintext-ciphertext pairs one slid pair is expected, along with 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 to 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 a cyclic key schedule. The reason for this is given a the search is for a . This reduces the possible paired messages from down to (since half the message is fixed) and so at most plaintext-ciphertext pairs are needed in order to find a slid pair. References (contains a summary of the paper by Grossman and Tuckerman) Cryptographic attacks