World Library  
Flag as Inappropriate
Email this Article

Impossible differential cryptanalysis

Article Id: WHEBN0003329225
Reproduction Date:

Title: Impossible differential cryptanalysis  
Author: World Heritage Encyclopedia
Language: English
Subject: Zodiac (cipher), KASUMI, Skipjack (cipher), Khufu and Khafre, Block cipher
Collection: Cryptographic Attacks
Publisher: World Heritage Encyclopedia

Impossible differential cryptanalysis

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

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."[6]


  1. ^ Lars Knudsen (February 21, 1998). "DEAL - A 128-bit Block Cipher" (PDF). Technical report no. 151. Department of Informatics,  
  2. ^ Shamir, A. (August 25, 1998) Impossible differential attacks. CRYPTO '98 rump session (video at Google Video—uses Flash)
  3. ^ Biryukov, A. (August 25, 1998) Miss-in-the-middle attacks on IDEA. CRYPTO '98 rump session (video at Google Video—uses Flash)
  4. ^ Biham, E. (August 25, 1998) Impossible cryptanalysis of Skipjack. CRYPTO '98 rump session (video at Google Video—uses Flash)
  5. ^ Bruce Schneier (September 15, 1998). "Impossible Cryptanalysis and Skipjack". Crypto-Gram Newsletter. 
  6. ^ E. Biham, A. Biryukov, A. Shamir (March 1999). Miss in the Middle Attacks on IDEA, Khufu and Khafre ( 

Further reading

  • E. Biham, A. Biryukov, A. Shamir (May 1999). Cryptanalysis of Skipjack Reduced to 31 Rounds using Impossible Differentials (PDF/PostScript). Advances in Cryptology -  
  • Kazumaro Aoki, Masayuki Kanda (1999). "Search for Impossible Differential of E2" (PDF/PostScript). Retrieved 2007-02-27. 
  • Eli Biham,  
  • Eli Biham, Vladimir Furman (December 2000). Improved Impossible Differentials on Twofish (PDF/PostScript).  
  • Deukjo Hong, Jaechul Sung, Shiho Moriai, Sangjin Lee, and Jongin Lim (April 2001). Impossible Differential Cryptanalysis of Zodiac (PDF). 8th International Workshop on Fast Software Encryption (FSE 2001).  
  • Raphael C.-W. Phan and Mohammad Umar Siddiqi (July 2001). "Generalised Impossible Differentials of Advanced Encryption Standard" (PDF).  
  • Jung Hee Cheon, MunJu Kim, Kwangjo Kim, Jung-Yeun Lee, and SungWoo Kang (December 26, 2001). Improved Impossible Differential Cryptanalysis of Rijndael and Crypton. 4th International Conference on Information Security and Cryptology (ICISC 2001).  
  • Dukjae Moon, Kyungdeok Hwang, Wonil Lee, Sangjin Lee, AND Jongin Lim (February 2002). Impossible Differential Cryptanalysis of Reduced Round XTEA and TEA (PDF). 9th International Workshop on Fast Software Encryption (FSE 2002).  
  • Raphael C.-W. Phan (May 2002). "Classes of Impossible Differentials of Advanced Encryption Standard" (PDF).  
  • Raphael C.-W. Phan (October 2003). "Impossible Differential Cryptanalysis of Mini-AES" (PDF).  
  • Raphael C.-W. Phan (July 2004). "Impossible Differential Cryptanalysis of 7-round AES". Information Processing Letters 91 (1): pp. 29–32.  
  • Wenling Wu, Wentao Zhang, and Dengguo Feng (2006). "Impossible Differential Cryptanalysis of ARIA and Camellia" (PDF). Retrieved 2007-02-27. 
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.