Linear cryptanalysis

From Free net encyclopedia

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 two widely applicable attacks on block ciphers; the other being differential cryptanalysis.

The discovery of linear cryptanalysis 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 2⁴³ 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.

See also

• Piling-up lemma

References

• Matsui, M and Yamagishi, A, (1992). A new method for known plaintext attack of FEAL cipher. EUROCRYPT 1992.
• Matsui, M. (1993). Linear cryptanalysis method for DES cipher. EUROCRYPT 1993.
• Matsui, M. (1994). The first experimental cryptanalysis of the data encryption standard. CRYPTO 1994.

External links

• A tutorial on linear (and differential) cryptanalysis of block ciphers
• Linear cryptanalysis: a literature survey

Block ciphers edit

Algorithms: 3-Way | AES | Akelarre | Anubis | Blowfish | Camellia | CAST-128 | CAST-256 | CMEA | CS-Cipher | DEAL | DES | DES-X | FEAL | FOX | FROG | G-DES | GOST | ICE | IDEA | Iraqi | KASUMI | KHAZAD | Khufu and Khafre | Libelle | LOKI89/91 | LOKI97 | Lucifer | MacGuffin | Madryga | MAGENTA | MARS | MISTY1 | MMB | NewDES | Noekeon | RC2 | RC5 | RC6 | REDOC | Red Pike | S-1 | SAFER | SEED | Serpent | SHACAL | SHARK | Skipjack | SMS4 | Square | TEA | Triple DES | Twofish | XTEA

Design: Feistel network | Key schedule | Product cipher | S-box | SPN   Attacks: Brute force | Linear / Differential cryptanalysis | Mod n | Related key | XSL   Standardization: AES process | CRYPTREC | NESSIE   Misc: Avalanche effect | Block size | IV | Key size | Modes of operation | Piling-up lemma | Weak key

fr:Cryptanalyse linéaire