View source for Differential-linear attack

{{Short description|Form of cryptanalysis}}
Introduced by [[Biography:Martin Hellman|Martin Hellman]] and Susan K. Langford in 1994, the '''differential-linear''' attack is a mix of both [[Linear cryptanalysis|linear cryptanalysis]] and [[Differential cryptanalysis|differential cryptanalysis]].

The attack utilises a differential characteristic over part of the cipher with a probability of 1 (for a few rounds—this probability would be much lower for the whole cipher). The rounds immediately following the differential characteristic have a linear approximation defined, and we expect that for each chosen plaintext pair, the probability of the linear approximation holding for one chosen plaintext but not the other will be lower for the correct key. Hellman and Langford have shown that this attack can recover 10 key bits of an 8-round [[Engineering:Data Encryption Standard|DES]] with only 512 chosen plaintexts and an 80% chance of success.

The attack was generalised by Eli Biham et al. to use differential characteristics with probability less than 1. Besides DES, it has been applied to FEAL, IDEA, [[Software:Serpent (cipher)|Serpent]], Camellia, and even the [[Stream cipher|stream cipher]] Phelix.

==References==
* {{ cite journal
     | author = Johan Borst
     | title = Differential-Linear Cryptanalysis of IDEA
     | date = February 1997
     | citeseerx = 10.1.1.49.5084
 }}
* {{ cite conference
     | author = Johan Borst, Lars R. Knudsen, Vincent Rijmen
     | title = Two Attacks on Reduced IDEA
     | conference = Advances in Cryptology – EUROCRYPT '97
     | pages = 1–13
     | publisher = [[Physics:Springer-Verlag|Springer-Verlag]]
     |date=May 1997
     | location = Konstanz
     | url = http://www.cosic.esat.kuleuven.be/publications/article-155.pdf
     | access-date = 2007-03-08 }}
* {{ cite conference
     |author1=Eli Biham |author2=Orr Dunkelman |author3=Nathan Keller | title=Enhancing Differential-Linear Cryptanalysis
     | conference= Advances in Cryptology, proceeding of ASIACRYPT 2002, [[Lecture Notes in Computer Science]] 2501
     | pages = 254–266
     | publisher = Springer-Verlag
     |date=December 2002
     | location = Queenstown, New Zealand
     | url = http://www.cs.haifa.ac.il/~orrd/crypt/diff-lin.pdf
     | format = PDF/gzipped PostScript
     | access-date = 2006-12-07 }}
* {{ cite conference
     | author = Eli Biham, Orr Dunkelman, Nathan Keller
     | title = Differential-Linear Cryptanalysis of Serpent
     | conference = 10th International Workshop on Fast Software Encryption (FSE '03)
     | pages = 9–21
     | publisher = Springer-Verlag
     |date=February 2003
     | location = Lund
     | url = http://citeseer.ist.psu.edu/698845.html
     | format = PDF/PostScript
     | access-date = 2007-03-08 }}
* {{cite conference
     | author = Hongjun Wu, Bart Preneel
     | title = Differential-Linear Attacks against the Stream Cipher Phelix
     | conference = 14th International Workshop on Fast Software Encryption (FSE '07)
     | publisher = Springer-Verlag
     | date = December 12, 2006
     | location = [[Place:Luxembourg City|Luxembourg City]]
     | url = http://www.ecrypt.eu.org/stream/papersdir/2006/056.pdf
     | access-date = 2007-03-08
     | archive-date = 2008-08-20
     | archive-url = https://web.archive.org/web/20080820065036/http://www.ecrypt.eu.org/stream/papersdir/2006/056.pdf
     | url-status = dead
     }}
* {{ cite conference
     | author = Eli Biham, Orr Dunkelman, Nathan Keller
     | title = A New Attack on 6-round IDEA
     | conference = 14th International Workshop on Fast Software Encryption (FSE '07)
     | publisher = Springer-Verlag
     | date = December 12, 2006
     | location = [[Place:Luxembourg City|Luxembourg City]]}}

{{cryptography navbox | block}}

[[Category:Cryptographic attacks]]

{{Sourceattribution|Differential-linear attack}}