Impossible differential cryptanalysis

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 noted 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, 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.

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

  1. ^ Lars Knudsen (February 21, 1998) (PDF/PostScript). DEAL - A 128-bit Block Cipher. Technical report no. 151. Department of Informatics, University of Bergen, Norway. http://www2.mat.dtu.dk/people/Lars.R.Knudsen/newblock.html. Retrieved 2007-02-27. 
  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. http://www.schneier.com/crypto-gram-9809.html#impossible. 
  6. ^ 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. pp.124–138. http://www.wisdom.weizmann.ac.il/~albi/fse99idea.ps.gz. Retrieved 2007-02-14. 

Further reading

v · d · e Block ciphers (security summary)
Common
algorithms
Less common
algorithms
Camellia · CAST-128 · IDEA · RC2 · RC5 · SEED · Skipjack · TEA · XTEA
Other
algorithms
3-Way · ABC · Akelarre · Anubis · ARIA · BaseKing · BassOmatic · BATON · BEAR and LION · CAST-256 · 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 · LOKI97 · LOKI89/91 · Lucifer · M6 · M8 · MacGuffin · Madryga · MAGENTA · MARS · Mercy · MESH · MISTY1 · MMB · MULTI2 · MultiSwap · New Data Seal · NewDES · Nimbus · NOEKEON · NUSH · Q · RC6 · REDOC · Red Pike · S-1 · SAFER · SAVILLE · SC2000 · SHACAL · SHARK · SMS4 · Spectr-H64 · Square · SXAL/MBAL · Threefish · Treyfer · UES · Xenon · xmx · XXTEA · Zodiac
Design
Attack
(cryptanalysis)
Brute force · Linear · Differential (Impossible · Truncated) · Integral · Boomerang · Mod n · Related-key · Slide · Rotational · Timing · XSL
Standardization
Misc
v · d · e Cryptography

Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Differential cryptanalysis — is a general form of cryptanalysis applicable primarily to block ciphers, but also to stream ciphers and cryptographic hash functions. In the broadest sense, it is the study of how differences in an input can affect the resultant difference at… …   Wikipedia

  • Cryptanalysis — Close up of the rotors in a Fialka cipher machine Cryptanalysis (from the Greek kryptós, hidden , and analýein, to loosen or to untie ) is the study of methods for obtaining the meaning of encrypted information, without access to the secret… …   Wikipedia

  • Differential-linear attack — Introduced by Martin Hellman and Susan K. Langford in 1994, the differential linear attack is a mix of both linear cryptanalysis and differential cryptanalysis. The attack utilises a differential characteristic over part of the cipher with a… …   Wikipedia

  • Differential equations of addition — In cryptography, differential equations of addition (DEA) are one of the most basic equations related to differential cryptanalysis that mix additions over two different groups (e.g. addition modulo 232 and addition over GF(2)) and where input… …   Wikipedia

  • Mod n cryptanalysis — In cryptography, mod n cryptanalysis is an attack applicable to block and stream ciphers. It is a form of partitioning cryptanalysis that exploits unevenness in how the cipher operates over equivalence classes (congruence classes) modulo n. The… …   Wikipedia

  • Cipher security summary — This article summarizes publicly known attacks against ciphers. Note that not all entries may be up to date. Table color key No known successful attacks Theoretical break Attack demonstrated in practice The Best attack column lists the complexity …   Wikipedia

  • Block cipher — In cryptography, a block cipher is a symmetric key cipher operating on fixed length groups of bits, called blocks, with an unvarying transformation. A block cipher encryption algorithm might take (for example) a 128 bit block of plaintext as… …   Wikipedia

  • Блочный шифр — Общая схема работы блочного шифра Блочный шифр  разновидность симметричного шифра …   Википедия

  • Skipjack (cipher) — Infobox block cipher name = Skipjack designers = NSA publish date = 1998 (declassifed) key size = 80 bits block size = 64 bits structure = unbalanced Feistel network rounds = 32 cryptanalysis = 31 rounds are susceptible to impossible differential …   Wikipedia

  • CLEFIA — General Designers Sony First published 2007 Cipher detail Key sizes 128, 192, or 256 bits Block sizes 128 bits Structure …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”