Linear Cryptanalysis

Linear Cryptanalysis

A more recent development is linear cryptanalysis, described in [MATS93]. This attack is based on finding linear approximations to describe the transformations performed in DES. This method can find a DES key given 2⁴³ known plaintexts, as compared to 2⁴⁷ chosen plaintexts for differential cryptanalysis. Although this is a minor improvement, because it may be easier to acquire known plaintext rather than chosen plaintext, it still leaves linear cryptanalysis infeasible as an attack on DES. So far, little work has been done by other groups to validate the linear cryptanalytic approach.

We now give a brief summary of the principle on which linear cryptanalysis is based. For a cipher with n-bit plaintext and ciphertext blocks and an m-bit key, let the plaintext block be labeled P[1], ... P[n], the cipher text block C[1], ... C[n], and the key K[1], ... K[m]. Then define

A[i, j, ..., k] = A[i] A[j] ... A[k]

The objective of linear cryptanalysis is to find an effective linear equation of the form:

P[a₁, a₂, ..., a_a] C[b₁, b₂, ..., b_b] = K[g₁, g₂, ..., g_c]

(where x = 0 or 1; 1 a, b n, 1 c m, and where the a, b and g terms represent fixed, unique bit locations) that holds with probability p 0.5. The further p is from 0.5, the more effective the equation. Once a proposed relation is determined, the procedure is to compute the results of the left-hand side of the preceding equation for a large number of plaintext-ciphertext pairs. If the result is 0 more than half the time, assume K[g₁, g₂, ..., g_c] = 0. If it is 1 most of the time, assume K[g₁, g₂, ..., g_c] = 1. This gives us a linear equation on the key bits. Try to get more such relations so that we can solve for the key bits. Because we are dealing with linear equations, the problem can be approached one round of the cipher at a time, with the results combined.