In cryptography, linear cryptanalysis is a general form of cryptanalysis based on finding affine approximations to the action of a cipher. Attacks have been developed for block ciphers and stream ciphers. Linear cryptanalysis is one of the two most widely used attacks on block ciphers; the other being differential cryptanalysis.
The discovery is attributed to Mitsuru Matsui, who first applied the technique to the FEAL cipher (Matsui and Yamagishi, 1992).^{[1]} Subsequently, Matsui published an attack on the Data Encryption Standard (DES), eventually leading to the first experimental cryptanalysis of the cipher reported in the open community (Matsui, 1993; 1994).^{[2]}^{[3]} The attack on DES is not generally practical, requiring 2^{47} known plaintexts.^{[3]}
A variety of refinements to the attack have been suggested, including using multiple linear approximations or incorporating nonlinear expressions, leading to a generalized partitioning cryptanalysis. Evidence of security against linear cryptanalysis is usually expected of new cipher designs.
Contents

Overview 1

Constructing linear equations 1.1

Deriving key bits 1.2

See also 2

References 3

External links 4

Further reading 5
Overview
There are two parts to linear cryptanalysis. The first is to construct linear equations relating plaintext, ciphertext and key bits that have a high bias; that is, whose probabilities of holding (over the space of all possible values of their variables) are as close as possible to 0 or 1. The second is to use these linear equations in conjunction with known plaintextciphertext pairs to derive key bits.
Constructing linear equations
For the purposes of linear cryptanalysis, a linear equation expresses the equality of two expressions which consist of binary variables combined with the exclusiveor (XOR) operation. For example, the following equation, from a hypothetical cipher, states the XOR sum of the first and third plaintext bits (as in a block cipher's block) and the first ciphertext bit is equal to the second bit of the key:
P_1 \oplus P_3 \oplus C_1 = K_2.
In an ideal cipher, any linear equation relating plaintext, ciphertext and key bits would hold with probability 1/2. Since the equations dealt with in linear cryptanalysis will vary in probability, they are more accurately referred to as linear approximations.
The procedure for constructing approximations is different for each cipher. In the most basic type of block cipher, a substitutionpermutation network, analysis is concentrated primarily on the Sboxes, the only nonlinear part of the cipher (i.e. the operation of an Sbox cannot be encoded in a linear equation). For small enough Sboxes, it is possible to enumerate every possible linear equation relating the Sbox's input and output bits, calculate their biases and choose the best ones. Linear approximations for Sboxes then must be combined with the cipher's other actions, such as permutation and key mixing, to arrive at linear approximations for the entire cipher. The pilingup lemma is a useful tool for this combination step. There are also techniques for iteratively improving linear approximations (Matsui 1994).
Deriving key bits
Having obtained a linear approximation of the form:
P_{i_1} \oplus P_{i_2} \oplus \cdots \oplus C_{j_1} \oplus C_{j_2} \oplus \cdots = K_{k_1} \oplus K_{k_2} \oplus \cdots
we can then apply a straightforward algorithm (Matsui's Algorithm 2), using known plaintextciphertext pairs, to guess at the values of the key bits involved in the approximation.
For each set of values of the key bits on the righthand side (referred to as a partial key), count how many times the approximation holds true over all the known plaintextciphertext pairs; call this count T. The partial key whose T has the greatest absolute difference from half the number of plaintextciphertext pairs is designated as the most likely set of values for those key bits. This is because it is assumed that the correct partial key will cause the approximation to hold with a high bias. The magnitude of the bias is significant here, as opposed to the magnitude of the probability itself.
This procedure can be repeated with other linear approximations, obtaining guesses at values of key bits, until the number of unknown key bits is low enough that they can be attacked with brute force.
See also
References

^ Matsui, M. and Yamagishi, A. "Advances in Cryptology 

^ Matsui, M. "Advances in Cryptology 

^ ^{a} ^{b} Matsui, M. "Advances in Cryptology  EUROCRYPT 1993" (
External links

A tutorial on linear (and differential) cryptanalysis of block ciphers

"Improving the Time Complexity of Matsui's Linear Cryptanalysis", improves the complexity thanks to the Fast Fourier Transform
Further reading

Linear Cryptanalysis of DES

A Tutorial on Linear and Differential Cryptanalysis

Linear Cryptanalysis Demo


Common
algorithms



Less common
algorithms



Other
algorithms



Design



Attack
(cryptanalysis)



Standardization



Utilization







This article was sourced from Creative Commons AttributionShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, EGovernment Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a nonprofit organization.