Der Brute-Force-Angriff

Dies ist immer noch der aussichtsreichste Angriff gegen DES. Man probiert alle Schlüssel durch, d.h. bei 56 Bit sind das 72.000.000.000.000.000 oder auch 72 Billiarden. Für sämtliche Schlüssel muß der Geheimtext dechiffriert und auf sinnvollen Klartext untersucht werden. Das Beispiel der EFF zeigt aber, daß eine solche vollständige Suche keineswegs unmöglich ist. Es ist eher eine Sache des Geldes.

Eine praktikable Brute-Force Methode ist das

Time-Memory-Tradeoff

Diese Methode wurde bereits 1980 von Hellmann entwickelt. Es ist ein allgemeines kryptanalytisches Verfahren. Die Idee ist, nicht alle möglichen Geheimtexte eines Klartextes, der häfig vorkommt, abzuspeichern, sondern nur einen kleinen Teil davon. Der Rest soll während der Analyse berechnet werden.

Gegeben:

Ein häufiger Klartextblock P (z.B. acht Nullen)
Der zugehörige Geheimtextblock C (abgehört)
Eine Projektion R, die 64 Bit auf 56 Bit projeziert.
Diese Projektion kann vor dem Verfahren frei gewählt werden

Wir definieren eine Abbildung f(S)=R(E(S,P)). E(S,P) soll dabei die Verschlüsselung von P mittels dem Schlüssel S sein. Wir suchen alle S mit f(S) = R(C). Solch ein S kann bereits der Schlüssel sein, muss es aber nicht, da acht Bits dabei nicht getestet wurden.

Die Suche nach S gestalten wir wie folgt: Wähle zufällig m Schlüssel S(1), ..., S(m) aus. Auf jedes dieser S(i) wenden wir t-mal die Abbildung f an. Wir berechnen also eine Tabelle mit t+1 Spalten und m-Zeilen. Merken wir uns alle Spalten, so haben wir nichts gewonnen. Also gehen wir wie folgt vor:

Tabelle berechnen, nur erste und letzte Spalte speichern
R(C) in letzter Spalte suchen
wenn nicht gefunden, f(R(C)) in letzter Spalte suchen
wenn wieder nicht gefunden, f(f(R(C))) in letzter Spalte suchen
...
wenn gefunden, berechne entsprechenden Tabelleneintrag (z.B. im Falle, daß R(C) in der letzten Spalte war, nehme Eintrag derselben Zeile, aber eine Spalte davor)

Dieses Verfahren führt nicht sicher zum Ziel, aber bei hinreichend großen t, m fast sicher. Außerdem können falsche Alarme auftreten. Als Richtschnur für t und m schlug Hellmann eine Million parallel berechneter Tabellen mit jeweils 100.000 Zeilen und 1 Million Schritten pro Zeile vor. Das könnte maximal 100 Billiarden Werte abdecken. Der Schlüsselraum ist aber nur 78 Billiarden groß.