View source for Impossible differential cryptanalysis

{{short description|Form of differential cryptanalysis for block ciphers that exploits differences that cannot occur}}
In [[cryptography]], '''impossible differential cryptanalysis''' is a form of [[differential cryptanalysis]] for [[block cipher]]s. While ordinary differential cryptanalysis tracks differences that propagate through the cipher with greater than expected [[probability]], impossible differential cryptanalysis exploits differences that are impossible (having probability 0) at some intermediate [[state (computer science)|state]] of the cipher algorithm.

[[Lars Knudsen]] appears to be the first to use a form of this attack, in the 1998 paper where he introduced his [[Advanced Encryption Standard process|AES candidate]], [[DEAL]].<ref>{{ cite journal
| author = Lars Knudsen | title = DEAL - A 128-bit Block Cipher | version = Technical report no. 151
| publisher = Department of Informatics, [[University of Bergen]], Norway | date = February 21, 1998 | url =  http://www2.mat.dtu.dk/people/Lars.R.Knudsen/papers/deal.pdf.gz | access-date = 2015-05-28 }}</ref> The first presentation to attract the attention of the cryptographic community was later the same year at the rump session of [[CRYPTO]] '98, in which [[Eli Biham]], [[Alex Biryukov]], and [[Adi Shamir]] introduced the name "impossible differential"<ref>Shamir, A. (August 25, 1998) [http://video.google.com/videoplay?docid=1283860161748060032&hl=en Impossible differential attacks.] CRYPTO '98 rump session (video at [[Google Video]]&mdash;uses [[Adobe Flash|Flash]])</ref> and used the technique to break 4.5 out of 8.5 rounds of [[International Data Encryption Algorithm|IDEA]]<ref>Biryukov, A. (August 25, 1998) [http://video.google.com/videoplay?docid=-5370812042739937841&hl=en Miss-in-the-middle attacks on IDEA.] CRYPTO '98 rump session (video at Google Video&mdash;uses Flash)</ref> and 31 out of 32 rounds of the [[National Security Agency|NSA]]-designed cipher [[Skipjack (cipher)|Skipjack]].<ref>Biham, E. (August 25, 1998) [http://video.google.com/videoplay?docid=-312957337727284112&hl=en Impossible cryptanalysis of Skipjack.] CRYPTO '98 rump session (video at Google Video&mdash;uses Flash)</ref> This development led cryptographer [[Bruce Schneier]] to speculate that the NSA had no previous knowledge of impossible differential cryptanalysis.<ref>{{ Cite journal | author = Bruce Schneier | title = Impossible Cryptanalysis and Skipjack | journal = Crypto-Gram Newsletter | date = September 15, 1998 | url = https://www.schneier.com/crypto-gram-9809.html#impossible }}</ref> The technique has since been applied to many other ciphers: [[Khufu and Khafre]], [[E2 (cipher)|E2]], variants of [[Serpent (cipher)|Serpent]], [[MARS (cryptography)|MARS]], [[Twofish]], [[Rijndael]] (AES), [[CRYPTON]], [[Zodiac (cipher)|Zodiac]], [[Hierocrypt-3]], [[Tiny Encryption Algorithm|TEA]], [[XTEA]], [[Mini-AES]], [[ARIA (cipher)|ARIA]], [[Camellia (cipher)|Camellia]], and [[SHACAL-2]].{{citation needed|date=June 2020}}

Biham, Biryukov and Shamir also presented a relatively efficient specialized method for finding impossible differentials that they called a ''miss-in-the-middle'' attack. This consists of finding "two events with probability one, whose conditions cannot be met together."<ref>{{ cite conference | author1 = E. Biham | author2 = A. Biryukov | author3 = A. Shamir | title = Miss in the Middle Attacks on IDEA, Khufu and Khafre | conference = 6th International Workshop on [[Fast Software Encryption]] (FSE 1999) | pages = 124–138 | publisher = [[Springer-Verlag]] | date = March 1999 | location = Rome | url = http://www.wisdom.weizmann.ac.il/~albi/fse99idea.ps.gz | format = [[gzip]]ped PostScript | access-date = 2007-02-14 | url-status = dead | archive-url = https://web.archive.org/web/20110515085818/http://www.wisdom.weizmann.ac.il/~albi/fse99idea.ps.gz | archive-date = 2011-05-15 }}</ref>

==References==
{{Reflist|30em}}

==Further reading==
* {{ cite conference
     | author = Orr Dunkelman
     | title = An Analysis of Serpent-p and Serpent-p-ns
     | conference = Rump session, 2nd AES Candidate Conference
     | publisher = [[NIST]]
     |date=March 1999
     | location = [[Rome]]
     | url = http://citeseer.ist.psu.edu/284484.html
     | format = PDF/PostScript
     | access-date = 2007-02-27 | author-link = Orr Dunkelman
 }}
* {{ cite conference
     |author1=E. Biham |author2=A. Biryukov |author3=A. Shamir | title = Cryptanalysis of Skipjack Reduced to 31 Rounds using Impossible Differentials
     | conference = Advances in Cryptology – [[EUROCRYPT]] '99
     | pages = 12–23
     | publisher = Springer-Verlag
     | date=May 1999
     | location = [[Prague]]
     | url = http://citeseer.ist.psu.edu/old/46276.html
     | format = PDF/PostScript
     | access-date = 2007-02-13 }}
* {{ cite journal
     |author1=Kazumaro Aoki |author2=Masayuki Kanda | title = Search for Impossible Differential of E2
     | year = 1999
     | url = http://citeseer.ist.psu.edu/315996.html
     | format = PDF/PostScript
     | access-date = 2007-02-27 }}
* {{ cite conference
     | author = Eli Biham, [[Vladimir Furman]]
     | title = Impossible Differential on 8-Round MARS' Core
     | conference = 3rd AES Candidate Conference
     | pages = 186–194
     | date=April 2000
     | url = http://citeseer.ist.psu.edu/biham00impossible.html
     | format = PDF/PostScript
     | access-date = 2007-02-27 }}
* {{ cite conference
     |author1=Eli Biham |author2=Vladimir Furman | title = Improved Impossible Differentials on Twofish
     | conference = [[INDOCRYPT]] 2000
     | pages = 80–92
     | publisher = Springer-Verlag
     | date=December 2000
     | location = [[Calcutta]]
     | url = http://citeseer.ist.psu.edu/339990.html
     | format = PDF/PostScript
     | access-date = 2007-02-27 }}
* {{cite conference
     | author1 = Deukjo Hong
     | author2 = Jaechul Sung
     | author3 = Shiho Moriai
     | author4 = Sangjin Lee
     | author5 = Jongin Lim
     | title = Impossible Differential Cryptanalysis of Zodiac
     | conference = 8th International Workshop on Fast Software Encryption (FSE 2001)
     | pages = 300–311
     | publisher = Springer-Verlag
     | date = April 2001
     | location = [[Yokohama]]
     | url = http://www.mathmagic.cn/Crypt1998-2003/bibs/2355/23550300.htm
     | format = PDF
     | access-date = 2006-12-30
     | archive-url = https://web.archive.org/web/20071213222753/http://www.mathmagic.cn/Crypt1998-2003/bibs/2355/23550300.htm
     | archive-date = 2007-12-13
     | url-status = dead
     }}
*  {{ cite journal
     |author1=Raphael C.-W. Phan |author2=Mohammad Umar Siddiqi | title = Generalised Impossible Differentials of Advanced Encryption Standard
     | journal = [[Electronics Letters]]
     | volume = 37
     | issue = 14
     | pages = 896–898
     | date=July 2001
     | doi = 10.1049/el:20010619 |bibcode=2001ElL....37..896P }}
* {{ cite conference
     | author = [[Cheon Jung-Hee|Jung Hee Cheon]], MunJu Kim, and Kwangjo Kim
     | title = Impossible Differential Cryptanalysis of Hierocrypt-3 Reduced to 3 Rounds
     | conference = Proceedings of 2nd [[NESSIE]] Workshop
     | date=September 2001
     | url = https://docs.google.com/viewer?a=v&pid=explorer&chrome=true&srcid=0B7u7lZfHbsZyNWQ0OGIzYjAtMjE0ZC00NTU4LTk2YTAtYjJlOWI4YzUwZDY5&hl=en
     | format = PDF
     | access-date = 2007-02-27 }}
* {{ cite conference
     |author1=Jung Hee Cheon |author2=MunJu Kim |author3=Kwangjo Kim |author4=Jung-Yeun Lee |author5=SungWoo Kang | title = Improved Impossible Differential Cryptanalysis of Rijndael and Crypton
     | conference = 4th International Conference on Information Security and Cryptology (ICISC 2001)
     | pages = 39–49
     | publisher = Springer-Verlag
     | date = December 26, 2001
     | location = [[Seoul]]
     | citeseerx = 10.1.1.15.9966
     }}
* {{cite conference
     | author1 = Dukjae Moon
     | author2 = Kyungdeok Hwang
     | author3 = Wonil Lee
     | author4 = Sangjin Lee
     | author5 = AND Jongin Lim
     | title = Impossible Differential Cryptanalysis of Reduced Round XTEA and TEA
     | conference = 9th International Workshop on Fast Software Encryption (FSE 2002)
     | pages = 49–60
     | publisher = Springer-Verlag
     | date = February 2002
     | location = [[Leuven]]
     | url = https://iacr.org/archive/fse2002/23650050/23650050.pdf
     | access-date = 2007-02-27
     }}
*  {{ cite journal
     | author = Raphael C.-W. Phan 
     | title = Classes of Impossible Differentials of Advanced Encryption Standard
     | journal = [[Electronics Letters]]
     | volume = 38
     | issue = 11
     | pages = 508–510
     | date=May 2002
     | doi = 10.1049/el:20020347 | bibcode = 2002ElL....38..508P
 }}
* {{ cite journal
     | author = Raphael C.-W. Phan
     | title = Impossible Differential Cryptanalysis of Mini-AES 
     | journal = [[Cryptologia]]
     | volume = XXVII
     | issue = 4
     | issn = 0161-1194
     | pages = 283–292
     | date=October 2003
     | url = http://www.geocities.com/dearphael/ImpMiniAES.pdf
     | access-date = 2007-02-27 |archive-url=https://web.archive.org/web/20070926205539/http://www.geocities.com/dearphael/ImpMiniAES.pdf|archive-date=2007-09-26
     | doi=10.1080/0161-110391891964| s2cid = 2658902 
 }}
* {{ cite journal
     | author = Raphael C.-W. Phan
     | title = Impossible Differential Cryptanalysis of 7-round AES 
     | journal = Information Processing Letters
     | volume = 91
     | issue = 1
     | pages = 29–32
     | date=July 2004
     | url = http://www.informatik.uni-trier.de/~ley/db/journals/ipl/ipl91.html
     | access-date = 2007-07-19
     | doi = 10.1016/j.ipl.2004.03.006 }}
* {{ cite journal
     |author1=Wenling Wu |author2=Wentao Zhang |author3=Dengguo Feng | title = Impossible Differential Cryptanalysis of ARIA and Camellia
     | year = 2006
     | url = http://eprint.iacr.org/2006/350
     | format = PDF
     | access-date = 2007-02-27 }}

{{cryptography navbox | block}}

[[Category:Cryptographic attacks]]