cryptography Cryptography, or cryptology (from "hidden, secret"; and ''graphein'', "to write", or ''-logy, -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of Adversary (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 a ...

for

block cipher In cryptography, a block cipher is a deterministic algorithm that operates on fixed-length groups of bits, called ''blocks''. Block ciphers are the elementary building blocks of many cryptographic protocols. They are ubiquitous in the storage a ...

s. While ordinary differential cryptanalysis tracks differences that propagate through the cipher with greater than expected

probability Probability is a branch of mathematics and statistics concerning events and numerical descriptions of how likely they are to occur. The probability of an event is a number between 0 and 1; the larger the probability, the more likely an e ...

, impossible differential cryptanalysis exploits differences that are impossible (having probability 0) at some intermediate

state State most commonly refers to: * State (polity), a centralized political organization that regulates law and society within a territory **Sovereign state, a sovereign polity in international law, commonly referred to as a country **Nation state, a ...

of the cipher algorithm.

Lars Knudsen Lars Ramkilde Knudsen (born 21 February 1962) is a Denmark, Danish researcher in cryptography, particularly interested in the design and cryptanalysis, analysis of block ciphers, cryptographic hash function, hash functions and message authentic ...

appears to be the first to use a form of this attack, in the 1998 paper where he introduced his AES candidate,

DEAL In cryptography, DEAL (Data Encryption Algorithm with Larger blocks) is a symmetric block cipher derived from the Data Encryption Standard (DES). Its design was presented by Lars Knudsen at the SAC conference in 1997, and submitted as a proposa ...

. 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: * Cryptography, the practice and study of hiding information * Cryptocurrency, a type of digital currency based on cryptography Crypto or krypto may also refer to: Cryptography * Cryptanalysis, the study of methods f ...

'98, in which

Eli Biham Eli Biham () is an Israeli cryptographer and cryptanalyst who is a professor at the Technion - Israel Institute of Technology Computer Science department. From 2008 to 2013, Biham was the dean of the Technion Computer Science department, afte ...

Alex Biryukov Alex Biryukov () is a cryptographer, currently a full professor at the University of Luxembourg. Biography His notable work includes the design of the stream cipher LEX, as well as the cryptanalysis of numerous cryptographic primitives. In 1998, ...

, and

Adi Shamir Adi Shamir (; born July 6, 1952) is an Israeli cryptographer and inventor. He is a co-inventor of the Rivest–Shamir–Adleman (RSA) algorithm (along with Ron Rivest and Len Adleman), a co-inventor of the Feige–Fiat–Shamir identification sc ...

introduced the name "impossible differential" and used the technique to break 4.5 out of 8.5 rounds of

IDEA In philosophy and in common usage, an idea (from the Greek word: ἰδέα (idea), meaning 'a form, or a pattern') is the results of thought. Also in philosophy, ideas can also be mental representational images of some object. Many philosophe ...

and 31 out of 32 rounds of the

NSA The National Security Agency (NSA) is an intelligence agency of the United States Department of Defense, under the authority of the director of national intelligence (DNI). The NSA is responsible for global monitoring, collection, and proces ...

-designed cipher Skipjack. This development led cryptographer

Bruce Schneier Bruce Schneier (; born January 15, 1963) is an American cryptographer, computer security professional, privacy specialist, and writer. Schneier is an Adjunct Lecturer in Public Policy at the Harvard Kennedy School and a Fellow at the Berkman ...

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 In cryptography, Khufu and Khafre are two block ciphers designed by Ralph Merkle in 1989 while working at Xerox's Palo Alto Research Center. Along with Snefru, a cryptographic hash function, the ciphers were named after the Egyptian Pharaohs Kh ...

, E2, variants of Serpent,

MARS Mars is the fourth planet from the Sun. It is also known as the "Red Planet", because of its orange-red appearance. Mars is a desert-like rocky planet with a tenuous carbon dioxide () atmosphere. At the average surface level the atmosph ...

Twofish In cryptography, Twofish is a symmetric key block cipher with a block size of 128 bits and key sizes up to 256 bits. It was one of the five finalists of the Advanced Encryption Standard contest, but it was not selected for standardization. Two ...

Rijndael The Advanced Encryption Standard (AES), also known by its original name Rijndael (), is a specification for the encryption of electronic data established by the U.S. National Institute of Standards and Technology (NIST) in 2001. AES is a variant ...

(AES), CRYPTON,

Zodiac The zodiac is a belt-shaped region of the sky that extends approximately 8° north and south celestial latitude of the ecliptic – the apparent path of the Sun across the celestial sphere over the course of the year. Within this zodiac ...

, Hierocrypt-3,

TEA Tea is an aromatic beverage prepared by pouring hot or boiling water over cured or fresh leaves of '' Camellia sinensis'', an evergreen shrub native to East Asia which probably originated in the borderlands of south-western China and nor ...

, XTEA, Mini-AES,

ARIA In music, an aria (, ; : , ; ''arias'' in common usage; diminutive form: arietta, ; : ariette; in English simply air (music), air) is a self-contained piece for one voice, with or without instrument (music), instrumental or orchestral accompan ...

Camellia ''Camellia'' (pronounced or ) is a genus of flowering plants in the family Theaceae. They are found in tropical and subtropical areas in East Asia, eastern and South Asia, southern Asia, from the Himalayas east to Japan and Indonesia. There are ...

, and

SHACAL-2 SHACAL-1 (originally simply SHACAL) is a 160-bit block cipher based on SHA-1, and supports keys from 128-bit to 512-bit. SHACAL-2 is a 256-bit block cipher based upon the larger hash function SHA-256. Both SHACAL-1 and SHACAL-2 were selected fo ...

. 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