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]

References

↑ Lars Knudsen (February 21, 1998). "DEAL - A 128-bit Block Cipher" (PDF). Technical report no. 151. Department of Informatics, University of Bergen, Norway. Retrieved 2015-05-28.
↑ Shamir, A. (August 25, 1998) Impossible differential attacks. CRYPTO '98 rump session (video at Google Video—uses Flash)
↑ Biryukov, A. (August 25, 1998) Miss-in-the-middle attacks on IDEA. CRYPTO '98 rump session (video at Google Video—uses Flash)
↑ Biham, E. (August 25, 1998) Impossible cryptanalysis of Skipjack. CRYPTO '98 rump session (video at Google Video—uses Flash)
↑ Bruce Schneier (September 15, 1998). "Impossible Cryptanalysis and Skipjack". Crypto-Gram Newsletter.
↑ E. Biham, A. Biryukov, A. Shamir (March 1999). Miss in the Middle Attacks on IDEA, Khufu and Khafre (gzipped PostScript). 6th International Workshop on Fast Software Encryption (FSE 1999). Rome: Springer-Verlag. pp. 124–138. Retrieved 2007-02-14.

Orr Dunkelman (March 1999). An Analysis of Serpent-p and Serpent-p-ns (PDF/PostScript). Rump session, 2nd AES Candidate Conference. Rome: NIST. Retrieved 2007-02-27.
E. Biham, A. Biryukov, A. Shamir (May 1999). Cryptanalysis of Skipjack Reduced to 31 Rounds using Impossible Differentials (PDF/PostScript). Advances in Cryptology - EUROCRYPT '99. Prague: Springer-Verlag. pp. 12–23. Retrieved 2007-02-13.
Kazumaro Aoki, Masayuki Kanda (1999). "Search for Impossible Differential of E2" (PDF/PostScript). Retrieved 2007-02-27.
Eli Biham, Vladimir Furman (April 2000). Impossible Differential on 8-Round MARS' Core (PDF/PostScript). 3rd AES Candidate Conference. pp. 186–194. Retrieved 2007-02-27.
Eli Biham, Vladimir Furman (December 2000). Improved Impossible Differentials on Twofish (PDF/PostScript). INDOCRYPT 2000. Calcutta: Springer-Verlag. pp. 80–92. Retrieved 2007-02-27.
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). Yokohama: Springer-Verlag. pp. 300–311. Retrieved 2006-12-30.
Raphael C.-W. Phan and Mohammad Umar Siddiqi (July 2001). "Generalised Impossible Differentials of Advanced Encryption Standard" (PDF). Electronics Letters 37 (14): pp. 896–898. doi:10.1049/el:20010619. Retrieved 2007-07-17.
Jung Hee Cheon, MunJu Kim, and Kwangjo Kim (September 2001). Impossible Differential Cryptanalysis of Hierocrypt-3 Reduced to 3 Rounds (PDF). Proceedings of 2nd NESSIE Workshop. Retrieved 2007-02-27.
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). Seoul: Springer-Verlag. pp. 39–49. CiteSeerX: 10.1.1.15.9966. |access-date= requires |url= (help)
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). Leuven: Springer-Verlag. pp. 49–60. Retrieved 2007-02-27.
Raphael C.-W. Phan (May 2002). "Classes of Impossible Differentials of Advanced Encryption Standard" (PDF). Electronics Letters 38 (11): pp. 508–510. doi:10.1049/el:20020347. Retrieved 2007-07-17.
Raphael C.-W. Phan (October 2003). "Impossible Differential Cryptanalysis of Mini-AES" (PDF). Cryptologia. XXVII (4): pp. 283–292. doi:10.1080/0161-110391891964. ISSN 0161-1194. Archived from the original (PDF) on 2007-09-26. Retrieved 2007-02-27.
Raphael C.-W. Phan (July 2004). "Impossible Differential Cryptanalysis of 7-round AES". Information Processing Letters 91 (1): pp. 29–32. doi:10.1016/j.ipl.2004.03.006. Retrieved 2007-07-19.
Wenling Wu, Wentao Zhang, and Dengguo Feng (2006). "Impossible Differential Cryptanalysis of ARIA and Camellia" (PDF). Retrieved 2007-02-27.

Block ciphers (security summary)

Common algorithms	AES Blowfish DES (Internal Mechanics, Triple DES) Serpent Twofish

Less common algorithms	Camellia CAST-128 IDEA RC2 RC5 SEED ARIA Skipjack TEA XTEA

Other algorithms	3-Way Akelarre Anubis BaseKing BassOmatic BATON BEAR and LION CAST-256 Chiasmus CIKS-1 CIPHERUNICORN-A CIPHERUNICORN-E CLEFIA CMEA Cobra COCONUT98 Crab Cryptomeria/C2 CRYPTON CS-Cipher DEAL DES-X DFC E2 FEAL FEA-M FROG G-DES GOST Grand Cru Hasty Pudding cipher Hierocrypt ICE IDEA NXT Intel Cascade Cipher Iraqi KASUMI KeeLoq KHAZAD Khufu and Khafre KN-Cipher Ladder-DES Libelle LOKI (97, 89/91) Lucifer M6 M8 MacGuffin Madryga MAGENTA MARS Mercy MESH MISTY1 MMB MULTI2 MultiSwap New Data Seal NewDES Nimbus NOEKEON NUSH PRESENT Q RC6 REDOC Red Pike S-1 SAFER SAVILLE SC2000 SHACAL SHARK Simon SMS4 Speck Spectr-H64 Square SXAL/MBAL Threefish Treyfer UES Xenon xmx XXTEA Zodiac

Design	Feistel network Key schedule Lai-Massey scheme Product cipher S-box P-box SPN Avalanche effect Block size Key size Key whitening (Whitening transformation)

Attack (cryptanalysis)	Brute-force (EFF DES cracker) MITM (Biclique attack, 3-subset MITM attack) Linear (Piling-up lemma) Differential (Impossible Truncated Higher-order) Differential-linear Distinguishing (Known-key) Integral/Square Boomerang Mod n Related-key Slide Rotational Timing XSL Interpolation Partitioning Davies' Rebound Weak key Tau Chi-square Time/memory/data tradeoff

Standardization	AES process CRYPTREC NESSIE

Utilization	Initialization vector Mode of operation Padding

Cryptography

History of cryptography Cryptanalysis Outline of cryptography

Symmetric-key algorithm Block cipher Stream cipher Public-key cryptography Cryptographic hash function Message authentication code Random numbers Steganography

Portal

This article is issued from Wikipedia - version of the Saturday, December 12, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Impossible differential cryptanalysis

References

Further reading