Impossible differential cryptanalysis
From Wikipedia, the free encyclopedia
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 at various intermediate states of the algorithm.
Lars Knudsen was apparently 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 coined the name "impossible differentials" and used them to break 31 out of 32 rounds of the NSA-designed cipher Skipjack. This development led noted 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, including IDEA, Khufu and Khafre, E2, variants of Serpent, MARS, Twofish, Rijndael, CRYPTON, Zodiac, Hierocrypt-3, TEA, XTEA, Mini-AES, ARIA, Camellia, and SHACAL-2.
In 1999 the developers of the attack presented a new 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."
[edit] References
- Lars Knudsen (1998-02-21). "DEAL - A 128-bit Block Cipher" (PDF/PostScript). Technical report no. 151. Department of Informatics, University of Bergen, Norway. Retrieved on 2007-02-27.
- Bruce Schneier (1998-09-15), "Impossible Cryptanalysis and Skipjack", Crypto-Gram Newsletter
- Orr Dunkelman (1999-03). "An Analysis of Serpent-p and Serpent-p-ns" (PDF/PostScript). Rump session, 2nd AES Candidate Conference, Rome: NIST. Retrieved on 2007-02-27.
- E. Biham, A. Biryukov, A. Shamir (1999-03). "Miss in the Middle Attacks on IDEA, Khufu and Khafre" (gzipped PostScript). 6th International Workshop on Fast Software Encryption (FSE 1999): 124-138, Rome: Springer-Verlag. Retrieved on 2007-02-14.
- E. Biham, A. Biryukov, A. Shamir (1999-05). "Cryptanalysis of Skipjack Reduced to 31 Rounds using Impossible Differentials" (PDF/PostScript). Advances in Cryptology - EUROCRYPT '99: 12-23, Prague: Springer-Verlag. Retrieved on 2007-02-13.
- Kazumaro Aoki, Masayuki Kanda (1999). "Search for Impossible Differential of E2" (PDF/PostScript). Retrieved on 2007-02-27.
- Eli Biham, Vladimir Furman (2000-04). "Impossible Differential on 8-Round MARS' Core" (PDF/PostScript). 3rd AES Candidate Conference: 186-194. Retrieved on 2007-02-27.
- Eli Biham, Vladimir Furman (2000-12). "Improved Impossible Differentials on Twofish" (PDF/PostScript). INDOCRYPT 2000: 80-92, Calcutta: Springer-Verlag. Retrieved on 2007-02-27.
- Deukjo Hong, Jaechul Sung, Shiho Moriai, Sangjin Lee, and Jongin Lim (2001-04). "Impossible Differential Cryptanalysis of Zodiac" (PDF). 8th International Workshop on Fast Software Encryption (FSE 2001): 300-311, Yokohama: Springer-Verlag. Retrieved on 2006-12-30.
- Jung Hee Cheon, MunJu Kim, and Kwangjo Kim (2001-09). "Impossible Differential Cryptanalysis of Hierocrypt-3 Reduced to 3 Rounds" (PDF). Proceedings of 2nd NESSIE Workshop. Retrieved on 2007-02-27.
- Jung Hee Cheon, MunJu Kim, Kwangjo Kim, Jung-Yeun Lee, and SungWoo Kang (2001-12-26). "Improved Impossible Differential Cryptanalysis of Rijndael and Crypton" (PDF/PostScript). 4th International Conference on Information Security and Cryptology (ICISC 2001): 39-49, Seoul: Springer-Verlag. Retrieved on 2007-02-27.
- Dukjae Moon, Kyungdeok Hwang, Wonil Lee, Sangjin Lee, AND Jongin Lim (2002-02). "Impossible Differential Cryptanalysis of Reduced Round XTEA and TEA" (PDF). 9th International Workshop on Fast Software Encryption (FSE 2002): 49-60, Leuven: Springer-Verlag. Retrieved on 2007-02-27.
- Raphael Chung-Wei Phan (2003-10). "Impossible Differential Cryptanalysis of Mini-AES" (PDF). Cryptologia XXVII (4): 283-292. Retrieved on 2007-02-27.
- Wenling Wu, Wentao Zhang, and Dengguo Feng (2006). "Impossible Differential Cryptanalysis of ARIA and Camellia" (PDF). Retrieved on 2007-02-27.
 |
This cryptography-related article is a stub. You can help Wikipedia by expanding it. |
