About: Linear CryptAnalysis
The Technique
In cryptography, linear cryptanalysis is a form of cryptanalysis like we have spoken about before, apart from the hacker will be searching for a special case , an Affine Cipher , which is a more general substitution of the original cipher “key” but unlocks the data none the less.
Attacks have been developed for block ciphers and stream ciphers. Linear cryptanalysis is one of two widely applicable attacks on block ciphers and for differential cryptanalysis using multiple key diff’s of differentiation tables much like rainbow tables or, a dns database, actually - just a TINY bit more sophisticated!
History
Mitsuru Matsui discovoered linear cryptanalysis methodology , who first applied the technique to the FEAL cipher (Matsui and Yamahgishi) in 1992. Matsui published an attack on the DES algorotihm also, as mentioned in a previous azio.org article:what is DES and 3DES.
Matsui was able to make the first experimental cryptanalysis of a cipher in 1993 and 1994. The attack on DES is not practicle , requiring 243 known plaintexts (lookup/rainbow table). 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 now expected from new cipher designs.
Resources
Azio’s Computer Log » What Is DES and 3DES? said,
October 20, 2006 @ 4:48 am
[...] Best public cryptanalysis: DES is now considered insecure because a brute force attack is possible (see EFF DES cracker). As of 2004, the best analytical attack is linear cryptanalysis, which requires 243 known plaintexts and has a time complexity of 239-43 (Junod, 2001); under a chosen-plaintext assumption, the data complexity can be reduced by a factor of four (Knudsen and Mathiassen, 2000). [...]