# Linear cryptanalysis

﻿
Linear cryptanalysis

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). 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). The attack on DES is not generally practical, requiring 243 known plaintexts.

A variety of refinements to the attack have been suggested, including using multiple linear approximations or incorporating non-linear expressions. Evidence of security against linear cryptanalysis is usually expected of new cipher designs.

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 plaintext-ciphertext 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 exclusive-or (XOR) operation. For example, the following equation states that 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.$

For a real cipher, it should not be possible to create such equations that hold all or none of the time. 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 are not expected to hold all the time, 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 substitution-permutation network, analysis is concentrated primarily on the S-boxes, the only nonlinear part of the cipher (i.e. the operation of an S-box cannot be encoded in a linear equation). For small enough S-boxes, it is possible to enumerate every possible linear equation relating the S-box's input and output bits, calculate their biases and choose the best ones. Linear approximations for S-boxes 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 piling-up 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_\left\{i_1\right\} oplus P_\left\{i_2\right\} oplus cdots oplus C_\left\{j_1\right\} oplus C_\left\{j_2\right\} oplus cdots = K_\left\{k_1\right\} oplus K_\left\{k_2\right\} oplus cdots$

we can then apply a straightforward algorithm (Matsui's Algorithm 2), using known plaintext-ciphertext 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 right-hand side (referred to as a "partial key"), count how many times the approximation holds true over all the known plaintext-ciphertext pairs; call this count "T". The partial key whose "T" has the greatest absolute difference from half the number of plaintext-ciphertext 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. It is important to note that 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.

ee also

* Piling-up lemma
* Differential cryptanalysis

References

* cite conference
author = Matsui, M. and Yamagishi, A
title = A new method for known plaintext attack of FEAL cipher
booktitle = Advances in Cryptology - EUROCRYPT 1992

* cite conference
author = Matsui, M
title = Linear cryptanalysis method for DES cipher
booktitle = Advances in Cryptology - EUROCRYPT 1993
url = http://homes.esat.kuleuven.be/~abiryuko/Cryptan/matsui_des.PDF
format = PDF
accessdate = 2007-02-22

* cite conference
author = Matsui, M
title = The first experimental cryptanalysis of the data encryption standard
booktitle = Advances in Cryptology - CRYPTO 1994

* [http://www.engr.mun.ca/~howard/Research/Papers/ldc_tutorial.html A tutorial on linear (and differential) cryptanalysis of block ciphers]

Wikimedia Foundation. 2010.

### Look at other dictionaries:

• Cryptanalysis — Close up of the rotors in a Fialka cipher machine Cryptanalysis (from the Greek kryptós, hidden , and analýein, to loosen or to untie ) is the study of methods for obtaining the meaning of encrypted information, without access to the secret… …   Wikipedia

• Linear (disambiguation) — Definition: The word linear comes from the Latin word linearis, which means created by lines. Usage in mathematics: * Linear, a property; * Linear code; * Linear equation; * Linear function; * Linear programming, a type of optimization problem; * …   Wikipedia

• Cryptanalysis of TIA's Common Cryptographic Algorithms — In 1992, the TR 45 working group within the Telecommunications Industry Association (TIA) developed a standard for integration of cryptographic technology into tomorrow s digital cellular systems [TIA92] , which has been updated at least once… …   Wikipedia

• Linear feedback shift register — [ xor gate provides feedback to the register that shifts bits from left to right. The maximal sequence consists of every possible state except the 0000 state.] A linear feedback shift register (LFSR) is a shift register whose input bit is a… …   Wikipedia

• 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… …   Wikipedia

• Partitioning cryptanalysis — In cryptography, partitioning cryptanalysis is a form of cryptanalysis for block ciphers. Developed by Carlo Harpes in 1995, the attack is a generalization of linear cryptanalysis. Harpes originally replaced the bit sums (affine transformations)… …   Wikipedia

• Differential-linear attack — Introduced by Martin Hellman and Susan K. Langford in 1994, the differential linear attack is a mix of both linear cryptanalysis and differential cryptanalysis. The attack utilises a differential characteristic over part of the cipher with a… …   Wikipedia

• Mod n cryptanalysis — In cryptography, mod n cryptanalysis is an attack applicable to block and stream ciphers. It is a form of partitioning cryptanalysis that exploits unevenness in how the cipher operates over equivalence classes (congruence classes) modulo n. The… …   Wikipedia

• Impossible differential cryptanalysis — In cryptography, impossible differential cryptanalysis is a form of differential cryptanalysis for block ciphers. While ordinary differential cryptanalysis tracks differences that propagate through the cipher with greater than expected… …   Wikipedia

• Decision Linear assumption — The Decision Linear (DLIN) assumption is a mathematical assumption used in elliptic curve cryptography. In particular, the DLIN assumption is useful in settings where the decisional Diffie–Hellman assumption does not hold (as is often the case in …   Wikipedia