Diese Kryptanalyse ist 1993 von Matsui entwickelt worden. Um die Vorgehensweise im Fall des DES zu betrachten, müssen wir uns erst mit sogenannten linearen Verfahren beschäftigen.
Wir betrachten {0,1} als Körper, wobei XOR die Addition sein soll und AND die Multiplikation. Blockverfahren, die nur lineare Ausdrücke in den Klartext- und Schlüsselbits darstellen, können somit durch Lösung eines Gleichungssystem entschlüsselt werden. Solche Verfahren sind also hochempfindlich gegenüber Klartextanalysen.
Vertauschungen, Permutationen und XOR-Verknüpfungen sowie Projektionen und Injektionen lassen sich durch lineare Abbildungen darstellen. Da das DES-Verfahren ohne die S-Boxen nur aus solchen Operationen bestehen würde, kann man die S-Boxen zu Recht als das nicht-lineare Element in diesem Verfahren betrachten.
Die Idee der linearen Kryptanalyse im Fall von DES ist, linear zu approximieren. Da man auf {0, 1} keine vernünftige Norm definieren kann, die den Begriff lineare Approximation legitimieren würde - die einzigen denkbaren Abstände sind ja nur null und eins - , greift man wieder auf statistische Mittel zurück.
Man versucht einige Gleichungen mit Wahrscheinlichkeiten zu belegen. Angenommen, es existiere eine Gleichung: r(17) XOR c(3) = s(26) mit einer Wahrscheinlichkeit weit abweichend von 50 Prozent. Dann kann man mit statistischen Mitteln das Schlüsselbit s(26) bei hinreichend großer Menge von Daten sicher bestimmen. Aufgrund der Menge an Feistelrunden ist ein solcher Angriff auf DES leider auf eine Datenmenge von 1000 TByte angewiesen.
Mit geschickteren Ansätzen, indem man sich auf weniger als 16 Runden DES zurückzieht und den Rest mit Brute-Force erledigt, sind "nur noch" 2 hoch 43 bekannte Klartexte notwendig. Also sind nur noch ungefähr 70 TByte Daten zu analysieren.
Um die Praxistauglichkeit dieses Verfahrens zu verdeutlichen, wollen wir eine kleine Rechnung anstellen. Wenn jemand DES-chiffrierte Daten, bei Verwendung desselben Schlüssels, über eine 32 M-Bit/s schnelle Standleitung sendet, dann braucht ein Angreifer nur gut ein halbes Jahr mithören. Anschließend läßt er seine acht Power-Macs noch eventuell 20 Tage rechnen und schon besitzt er den Schlüssel.
Weder die differentielle Kryptanalyse noch die lineare Kryptanalyse sind derzeit in der Lage DES-chiffrierte Daten in angemessener Geschwindigkeit in der Realität zu dechiffrieren. Allein der Brute-Force Angriff verspricht wirklich einen praxisnahen Erfolg. Dies geht allein auf den zu kleinen Schlüsselraum zurück. Das war offenbar auch schon 1976 klar.