In cryptography, impossible differential cryptanalysis is a form of differential cryptanalysis for block ciphers. 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 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 AES candidate, DEAL. 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" and used the technique to break 4.5 out of 8.5 rounds of IDEA and 31 out of 32 rounds of the NSA-designed cipher Skipjack. This development led cryptographer Bruce Schneier to speculate that the NSA had no previous knowledge of impossible differential cryptanalysis. The technique has since been applied to many other ciphers: Khufu and Khafre, E2, variants of Serpent, MARS, Twofish, Rijndael (AES), CRYPTON, Zodiac, Hierocrypt-3, TEA, XTEA, Mini-AES, ARIA, Camellia, and SHACAL-2.[citation needed]

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."

Further reading

  • Orr Dunkelman (March 1999). (PDF/PostScript). Rump session, 2nd AES Candidate Conference. Rome: NIST.
  • E. Biham; A. Biryukov; A. Shamir (May 1999). (PDF/PostScript). Advances in Cryptology – EUROCRYPT '99. Prague: Springer-Verlag. pp. 12–23.
  • Kazumaro Aoki; Masayuki Kanda (1999). (PDF/PostScript). {{cite journal}}:Cite journal requires |journal= (help)
  • Eli Biham, Vladimir Furman (April 2000). (PDF/PostScript). 3rd AES Candidate Conference. pp. 186–194.
  • Eli Biham; Vladimir Furman (December 2000). (PDF/PostScript). INDOCRYPT 2000. Calcutta: Springer-Verlag. pp. 80–92.
  • Deukjo Hong; Jaechul Sung; Shiho Moriai; Sangjin Lee; Jongin Lim (April 2001). . 8th International Workshop on Fast Software Encryption (FSE 2001). Yokohama: Springer-Verlag. pp. 300–311. Archived from (PDF) on 2007-12-13.
  • Raphael C.-W. Phan; Mohammad Umar Siddiqi (July 2001). "Generalised Impossible Differentials of Advanced Encryption Standard". Electronics Letters. 37 (14): 896–898. Bibcode:. doi:.
  • Jung Hee Cheon, MunJu Kim, and Kwangjo Kim (September 2001). (PDF). Proceedings of 2nd NESSIE Workshop.{{cite conference}}: CS1 maint: multiple names: authors list (link)
  • Jung Hee Cheon; MunJu Kim; Kwangjo Kim; Jung-Yeun Lee; SungWoo Kang (December 26, 2001). Improved Impossible Differential Cryptanalysis of Rijndael and Crypton. 4th International Conference on Information Security and Cryptology (ICISC 2001). Seoul: Springer-Verlag. pp. 39–49. CiteSeerX .
  • Dukjae Moon; Kyungdeok Hwang; Wonil Lee; Sangjin Lee; AND Jongin Lim (February 2002). (PDF). 9th International Workshop on Fast Software Encryption (FSE 2002). Leuven: Springer-Verlag. pp. 49–60.
  • Raphael C.-W. Phan (May 2002). "Classes of Impossible Differentials of Advanced Encryption Standard". Electronics Letters. 38 (11): 508–510. Bibcode:. doi:.
  • Raphael C.-W. Phan (October 2003). (PDF). Cryptologia. XXVII (4): 283–292. doi:. ISSN . S2CID . Archived from (PDF) on 2007-09-26.
  • Raphael C.-W. Phan (July 2004). . Information Processing Letters. 91 (1): 29–32. doi:.
  • Wenling Wu; Wentao Zhang; Dengguo Feng (2006). (PDF). {{cite journal}}:Cite journal requires |journal= (help)