Slide attack

The slide attack 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. 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 attack was first described by David Wagner and Alex Biryukov. Bruce Schneier first suggested the term "slide attack" to them, and they used it in their 1999 paper describing the attack.

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 idea of the slide attack has roots in a paper published by Edna Grossman and Bryant Tuckerman in an IBM Technical Report in 1977. Grossman and Tuckerman demonstrated the attack on a weak block cipher named New Data Seal (NDS). The attack relied on the fact that the cipher has identical subkeys in each round, so the cipher had a cyclic key schedule with a cycle of only one key, which makes it an early version of the slide attack. 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 actual attack

First, to introduce some notation. In this section 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 permutationfunctions, "F". This "F" function may consist of more than one roundof 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 willappear at least once in "F".

The next step is to collect 2^{n/2} plaintext-ciphertext pairs. Depending onthe characteristics of the cipher fewer may suffice, but by the birthday paradox no more than 2^{n/2} should be needed. These pairs, which denoted as (P,C) are then used to find a slid pair which denoted (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 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 itsname.

The process of finding a slid pair is somewhat different for each cipherbut follows the same basic scheme. One uses the fact that it is relativelyeasy to extract the key from just one iteration of "F". Choose any pair ofplaintext-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, this is a slid pair; otherwise move on to the next pair.

With 2^{n/2} 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 positivescan 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 ofplaintext-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) the search is for a P_0=(R_0, L_0 igoplus F(R_0,K)). This reduces the possible paired messages from 2^ndown to 2^{n/2} (since half the message is fixed) and so at most 2^{n/4} plaintext-ciphertext pairs are needed in order to find a slid-pair.

References

* cite paper
author = E.K. Grossman and B. Tuckerman
title = Analysis of a Feistel-like cipher weakened by having no rotating key
publisher = IBM Thomas J. Watson Research Report RC 6375
year = 1977

* cite book
author = Henry Beker and Fred Piper
title = Cipher Systems: The Protection of Communications
publisher = John Wiley & Sons
year = 1982
pages = pp.263–267
isbn = 0-471-89192-4
(contains a summary of the paper by Grossman and Tuckerman)
* cite conference
author = Alex Biryukov and David Wagner
title = Slide Attacks
booktitle = 6th International Workshop on Fast Software Encryption (FSE '99)
pages = pp.245–259
publisher = Springer-Verlag
date = March 1999
location = Rome
url = http://citeseer.ist.psu.edu/190677.html
format = PDF/PostScript
accessdate = 2007-09-03

* cite conference
author = Alex Biryukov and David Wagner
title = Advanced Slide Attacks
booktitle = Advances in Cryptology, Proceedings of EUROCRYPT 2000
pages = pp.589–606
publisher = Springer-Verlag
date = May 2000
location = Bruges
url = http://citeseer.ist.psu.edu/303568.html
format = PDF/PostScript
accessdate = 2007-09-03

* cite conference
author = S. Furuya
title = Slide Attacks with a Known-Plaintext Cryptanalysis
booktitle = 4th International Conference on Information Security and Cryptology (ICISC 2001)
pages = pp.214–225
publisher = Springer-Verlag
date = December 2001
location = Seoul
url = http://register.itfind.or.kr/Report01/200401/IITA/IITA-0763-017/IITA-0763-017.pdf
format = PDF
accessdate = 2007-09-03

* cite journal
author = Eli Biham
title = New Types of Cryptanalytic Attacks Using Related Keys
journal = Journal of Cryptology
volume = 7
issue = 4
issn = 0933-2790
pages = pp.229–246
year = 1994
url = http://citeseer.ist.psu.edu/biham94new.html
format = PDF/PostScript
accessdate = 2007-09-03

* cite paper
author = M. Ciet, G. Piret, J. Quisquater
title = Related-Key and Slide Attacks: Analysis, Connections, and Improvements
year = 2002
url = http://citeseer.ist.psu.edu/560898.html
format = PDF/PostScript
accessdate = 2007-09-04


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Correlation attack — In cryptography, correlation attacks are a class of known plaintext attacks for breaking stream ciphers whose keystream is generated by combining the output of several linear feedback shift registers (called LFSRs for the rest of this article)… …   Wikipedia

  • Meet-in-the-middle attack — Not to be confused with man in the middle attack. The meet in the middle attack is a cryptographic attack which, like the birthday attack, makes use of a space time tradeoff. While the birthday attack attempts to find two values in the domain of… …   Wikipedia

  • Differential-linear attack — Introduced by Martin Hellman and Susan K. Langford in 1994, the differential linear attack is a mix of both linear cryptanalysis and differential cryptanalysis. The attack utilises a differential characteristic over part of the cipher with a… …   Wikipedia

  • Cryptanalysis — Close up of the rotors in a Fialka cipher machine Cryptanalysis (from the Greek kryptós, hidden , and analýein, to loosen or to untie ) is the study of methods for obtaining the meaning of encrypted information, without access to the secret… …   Wikipedia

  • DES-X — In cryptography, DES X (or DESX) is a variant on the DES (Data Encryption Standard) block cipher intended to increase the complexity of a brute force attack using a technique called key whitening. The original DES algorithm was specified in 1976… …   Wikipedia

  • Spectr-H64 — Infobox block cipher name = Spectr H64 designers = N.D. Goots, A.A. Moldovyan and N.A. Moldovyan publish date = 2001 derived from = derived to = CIKS 1 related to = key size = 256 bits block size = 64 bits structure = Feistel like network rounds …   Wikipedia

  • Блочный шифр — Общая схема работы блочного шифра Блочный шифр  разновидность симметричного шифра …   Википедия

  • New Data Seal — General First published 1975 Derived from Lucifer Cipher detail Key sizes 2048 bits Block sizes 128 bits Structure …   Wikipedia

  • Treyfer — Infobox block cipher name = Treyfer designers = Gideon Yuval publish date = 1997 derived from = derived to = related to = key size = 64 bits block size = 64 bits structure = rounds = 32 cryptanalysis = A slide attack using 232 known plaintexts… …   Wikipedia

  • M6 (cipher) — Infobox block cipher name = M6 designers = Hitachi publish date = 1997 derived from = derived to = M8 related to = key size = 40 64 bits block size = 64 bits structure = Feistel network rounds = 10 cryptanalysis = Mod n cryptanalysis: 1 known… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”