In
cryptography, impossible differential cryptanalysis is a form of
differential cryptanalysis
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 information input can aff ...
for
block cipher
In cryptography, a block cipher is a deterministic algorithm operating on fixed-length groups of bits, called ''blocks''. Block ciphers are specified cryptographic primitive, elementary components in the design of many cryptographic protocols and ...
s. 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
A deal, or deals may refer to:
Places United States
* Deal, New Jersey, a borough
* Deal, Pennsylvania, an unincorporated community
* Deal Lake, New Jersey
Elsewhere
* Deal Island (Tasmania), Australia
* Deal, Kent, a town in England
* Deal, a ...
. The first presentation to attract the attention of the cryptographic community was later the same year at the rump session of
CRYPTO
Crypto commonly refers to:
* Cryptocurrency, a type of digital currency secured by cryptography and decentralization
* Cryptography, the practice and study of hiding information
Crypto or Krypto may also refer to:
Cryptography
* Cryptanalysis, ...
'98, in which
Eli Biham,
Alex Biryukov Alex Biryukov is a cryptographer, currently a full professor at the University of Luxembourg. His notable work includes the design of the stream cipher LEX, as well as the cryptanalysis of numerous cryptographic primitives. In 1998, he developed imp ...
, and
Adi Shamir introduced the name "impossible differential" and used the technique to break 4.5 out of 8.5 rounds of
IDEA and 31 out of 32 rounds of the
NSA-designed cipher
Skipjack. This development led 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:
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."
References
Further reading
*
*
*
*
*
*
*
*
*
*
*
*
*
*
{{cryptography navbox , block
Cryptographic attacks