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

References

edit
  1. ^ Lars Knudsen (February 21, 1998). "DEAL - A 128-bit Block Cipher". Technical report no. 151. Department of Informatics, University of Bergen, Norway. Retrieved 2015-05-28. {{cite journal}}: Cite journal requires |journal= (help)
  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. 6th International Workshop on Fast Software Encryption (FSE 1999). Rome: Springer-Verlag. pp. 124–138. Archived from the original (gzipped PostScript) on 2011-05-15. Retrieved 2007-02-14.

Further reading

edit

📚 Artikel Terkait di Wikipedia

Differential cryptanalysis

Differential cryptanalysis is a general form of cryptanalysis applicable primarily to block ciphers, but also to stream ciphers and cryptographic hash

Cryptanalysis

Davies' attack Differential cryptanalysis Harvest now, decrypt later Impossible differential cryptanalysis Improbable differential cryptanalysis Integral cryptanalysis

Skipjack (cipher)

than exhaustive search) within months using impossible differential cryptanalysis. A truncated differential attack was also published against 28 rounds

Block cipher

growing catalog of attacks: truncated differential cryptanalysis, partial differential cryptanalysis, integral cryptanalysis, which encompasses square and integral

Zodiac (cipher)

introduced by SHARK. Zodiac is theoretically vulnerable to impossible differential cryptanalysis, which can recover a 128-bit key in 2119 encryptions. Zodiac

Alex Biryukov

LEX, as well as the cryptanalysis of numerous cryptographic primitives. In 1998, he developed impossible differential cryptanalysis together with Eli Biham

Truncated differential cryptanalysis

In cryptography, truncated differential cryptanalysis is a generalization of differential cryptanalysis, an attack against block ciphers. Lars Knudsen

Eli Biham

under Adi Shamir Attacking all triple modes of operation. Impossible differential cryptanalysis - joint work with Adi Shamir and Alex Biryukov Breaking