Linear and Differential Cryptanalysis

The two most significant attacks against symmetric-key block ciphers are known as linear cryptanalysis and differential cryptanalysis. Both cryptanalysis techniques arose as theoretical attacks on the Data Encryption Standard (DES), which has since been superseded by the Advanced Encryption Standard (AES). Differential cryptanalysis is a method which analyzes the effect of particular differences in plaintext pairs on the differences of the corresponding ciphertext pairs. It is a chosen plaintext attack, which is where an attacker selects inputs and examines the outputs in an attempt to figure out the key. Differential cryptanalysis seeks to exploit a scenario where a particular output occurs given a particular input difference. The differences can be exploited to assign probabilities to potential keys and to even locate the most probable key.

Inspired by Eli Biham and Adi Shamir’s differential cryptanalysis a few years prior, Mitsuru Matsui introduced linear cryptanalysis to the world in 1993 at the cryptography research conference EUROCRYPT. In his work, Linear Cryptanalysis Method for DES Cipher, Matsui shows several new approaches to known plaintext attacks. A known plaintext attack is premised on the attacker holding information on a set of plaintext and the corresponding ciphertext. The purpose of linear cryptanalysis is to obtain a linear approximate expression of a target cipher algorithm. This attack method attempts to create a statistical linear path between the input and output bits of each S-Box.  Linear cryptanalysis was the first known plaintext attack on the full 16-round DES cipher, rendering it breakable faster than an exhaustive key search.