In cryptography

Cryptography

Cryptography is the practice and study of techniques for secure communication in the presence of third parties...

, impossible differential cryptanalysis is a form of differential cryptanalysis

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 an input can affect the resultant difference at the output...

 for block cipher

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 a 128-bit block of plaintext as input, and output a corresponding 128-bit block of ciphertext...

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

Probability

Probability is ordinarily used to describe an attitude of mind towards some proposition of whose truth we arenot certain. The proposition of interest is usually of the form "Will a specific event occur?" The attitude of mind is of the form "How certain are we that the event will occur?" The...

, impossible differential cryptanalysis exploits differences that are impossible

Impossible

Impossible or Impossibility may refer to:-Law:* Impossibility, a valid legal excuse for non-performance of duties under a contract* Impossibility defense - a legal defense against criminal charges-Fictional characters:...

 (having probability 0) at some intermediate state

State (computer science)

In computer science and automata theory, a state is a unique configuration of information in a program or machine. It is a concept that occasionally extends into some forms of systems programming such as lexers and parsers....

 of the cipher algorithm.

Lars Knudsen

Lars Knudsen

Lars Ramkilde Knudsen is a Danish researcher in cryptography, particularly interested in the design and analysis of block ciphers, hash functions and message authentication codes .-Academic:...

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

Advanced Encryption Standard process

The Advanced Encryption Standard , the block cipher ratified as a standard by National Institute of Standards and Technology of the United States , was chosen using a process markedly more open and transparent than its predecessor, the aging Data Encryption Standard...

, DEAL

DEAL

In cryptography, DEAL is a block cipher derived from the Data Encryption Standard . The design was proposed in a report by Lars Knudsen in 1998, and was submitted to the AES contest by Richard Outerbridge .DEAL is a Feistel network which uses DES as the...

. The first presentation to attract the attention of the cryptographic community was later the same year at the rump session of CRYPTO

Crypto

-Cryptography and cryptanalysis:* Cryptography, the practice and study of hiding information* Cryptanalysis, the study of methods for obtaining the meaning of encrypted information* CRYPTO , an annual cryptographical and cryptoanalytic conference...

 '98, in which Eli Biham

Eli Biham

Eli Biham is an Israeli cryptographer and cryptanalyst, currently a professor at the Technion Israeli Institute of Technology Computer Science department. Starting from October 2008, Biham is the dean of the Technion Computer Science department, after serving for two years as chief of CS graduate...

, Alex Biryukov

Alex Biryukov

Alex Biryukov is a cryptographer, currently an assistant 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 impossible differential cryptanalysis together...

, and Adi Shamir

Adi Shamir

Adi Shamir is an Israeli cryptographer. He is a co-inventor of the RSA algorithm , a co-inventor of the Feige–Fiat–Shamir identification scheme , one of the inventors of differential cryptanalysis and has made numerous contributions to the fields of cryptography and computer...

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

International Data Encryption Algorithm

In cryptography, the International Data Encryption Algorithm is a block cipher designed by James Massey of ETH Zurich and Xuejia Lai and was first described in 1991. As a block cipher, it is also symmetric. The algorithm was intended as a replacement for the Data Encryption Standard[DES]...

 and 31 out of 32 rounds of the NSA

National Security Agency

The National Security Agency/Central Security Service is a cryptologic intelligence agency of the United States Department of Defense responsible for the collection and analysis of foreign communications and foreign signals intelligence, as well as protecting U.S...

-designed cipher Skipjack

Skipjack (cipher)

In cryptography, Skipjack is a block cipher—an algorithm for encryption—developed by the U.S. National Security Agency . Initially classified, it was originally intended for use in the controversial Clipper chip...

. This development led noted cryptographer Bruce Schneier

Bruce Schneier

Bruce Schneier is an American cryptographer, computer security specialist, and writer. He is the author of several books on general security topics, computer security and cryptography, and is the founder and chief technology officer of BT Managed Security Solutions, formerly Counterpane Internet...

 to speculate that the NSA had no previous knowledge of impossible differential cryptanalysis. The technique has since been applied to many other ciphers, including IDEA

International Data Encryption Algorithm

In cryptography, the International Data Encryption Algorithm is a block cipher designed by James Massey of ETH Zurich and Xuejia Lai and was first described in 1991. As a block cipher, it is also symmetric. The algorithm was intended as a replacement for the Data Encryption Standard[DES]...

, Khufu and Khafre

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

, E2

E2 (cipher)

In cryptography, E2 is a block cipher which was created in 1998 by NTT and submitted to the AES competition.Like other AES candidates, E2 operates on blocks of 128 bits, using a key of 128, 192, or 256 bits. It uses a 12-round Feistel network...

, variants of Serpent

Serpent (cipher)

Serpent is a symmetric key block cipher which was a finalist in the Advanced Encryption Standard contest, where it came second to Rijndael. Serpent was designed by Ross Anderson, Eli Biham, and Lars Knudsen....

, MARS, Twofish

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 was not selected for standardisation...

, Rijndael, CRYPTON

CRYPTON

In cryptography, CRYPTON is a block cipher submitted as a candidate for the Advanced Encryption Standard . It is very efficient in hardware implementations and was designed by Chae Hoon Lim of Future Systems Inc....

, Zodiac

Zodiac (cipher)

In cryptography, Zodiac is a block cipher designed in 2000 by Chang-Hyi Lee for the Korean firm SoftForum.Zodiac uses a 16-round Feistel network structure with key whitening. The round function uses only XORs and S-box lookups...

, Hierocrypt-3, TEA

Tiny Encryption Algorithm

In cryptography, the Tiny Encryption Algorithm is a block cipher notable for its simplicity of description and implementation, typically a few lines of code...

, XTEA

XTEA

In cryptography, XTEA is a block cipher designed to correct weaknesses in TEA. The cipher's designers were David Wheeler and Roger Needham of the Cambridge Computer Laboratory, and the algorithm was presented in an unpublished technical report in 1997...

, Mini-AES, ARIA

ARIA (cipher)

In cryptography, ARIA is a block cipher designed in 2003 by a large group of South Korean researchers. In 2004, the Korean Agency for Technology and Standards selected it as a standard cryptographic technique....

, Camellia

Camellia (cipher)

In cryptography, Camellia is a 128-bit block cipher jointly developed by Mitsubishi and NTT. The cipher has been approved for use by the ISO/IEC, the European Union's NESSIE project and the Japanese CRYPTREC project...

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