Kryptologie Die Exhaustionsmethode

a7Hzq .#5r< kÜ\as TâÆK$ ûj(Ö2 ñw%h: Úk{4R f~`z8 ¤˜Æ+Ô „&¢Dø

Auch genannt Ausschöpfungsmethode, vollständige Schlüsselsuche, brute force attack, Holzhammermethode. Besonders erfolgreich bei Verschiebechiffren.

Prinzipiell kann die Exhaustionsmethode auf jede Chiffre angewendet werden! [s. u.]

Vorgehen: Unter den Geheimtext werden die Klartexte für alle möglichen Schlüssel geschrieben - bei einer Verschiebechiffre wird einfach unter jedem Buchstaben das Alphabet hochgezählt. Der richtige Klartext springt ins Auge.

Beispiel

FDHVDU
GEIWEV
HFJXFW
IGKYGX
JHLZHY
KIMAIZ
LJNBJA
MKOCKB
NLPDLC
OMQEMD
PNRFNE
QOSGOF
RPTHPG
SQUIQH
TRVJRI
USWKSJ
VTXLTK
WUYMUL
XVZNVM
YWAOWN
ZXBPXO
AYCQYP
BZDRZQ
CAESAR
DBFTBS
ECGUCT

Der einzig mögliche sinnvolle Klartext ist CAESAR. Der Schlüssel ist also (Verschiebung um) 3.

Praktische Durchführung

Es werden einige senkrechte Streifen [Papierstreifen oder Holzstäbe] angefertigt, auf denen jeweils das Alphabet zweimal untereinander in senkrechter Anordnung steht. Diese werden nebeneinander gelegt und so gegeneinander verschoben, dass ein Stück des Geheimtextes in einer Zeile steht. In einer anderen Zeile steht dann das entsprechende Stück des Klartextes [Bild].

Bei waagerechter Anordnung sähe das etwa so aus:

                     |
                ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ
                  ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ
              ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ
ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ
                  ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ
 ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ
                     |

Und hier ein Streifen zum (hinreichend häufigen) Ausdrucken und Ausschneiden [PDF].

Frage: Warum kann man im zweiten Alphabet das Z weglassen?

Lehren aus der Kryptoanalyse

1. Verschiebechiffren sind immer lösbar, sobald der Text aus einigen wenigen Buchstaben besteht - zumindest wenn das Alphabet nicht sehr groß ist und wenn, wie wir hier gesehen haben, die sinnvollen Texte nur einen kleinen Teil aller Zeichenketten ausmachen, wenn die Sprache also »dünn« ist. Später wird dies durch »hohe Redundanz« oder »geringe Entropie/Informationsdichte« der Sprache präzisiert.
   
   
2. Erste Idee zur Verstärkung der Verschlüsselung:

   eine große effektive Schlüssellänge verwenden.

   Bei XOR wäre das etwa eine große Blocklänge l. Nimmt man etwa Festplattensektoren zu 512 Byte = 4096 Bit, also l = 4096, so ist die Exhaustionsmethode sicher nicht durchführbar - es gibt 2⁴⁰⁹⁶ verschiedene Schlüssel. Trotzdem ist dieses Verfahren nicht sicher.

Dennoch wird diese Primitiv-Verschlüsselung mit XOR immer wieder neu erfunden und sogar in kommerziellen Sicherheitssystemen vertrieben.

Zur letzen Bemerkung siehe auch

• Jeff Zamora: ActiveSync 2.x allows unauthorized access to your NT password.

Allgemeines Verfahren der Exhausionsmethode

Die Exhaustion (vollständige Schlüsselsuche) ist ein kryptoanalytisches Verfahren, das gegen jede Chiffre anwendbar ist: Es werden einfach alle Schlüssel in irgendeiner Reihenfolge durchprobiert, bis der passende Schlüssel gefunden ist; man erkennt das daran, dass der entstandene Klartext tatsächlich verständlich ist.

Voraussetzung für den Erfolg ist, dass die Klartext-Sprache so viel Redundanz hat, dass »sinnvolle« Texte gegenüber rein zufälligen Zeichenketten sehr selten sind. In der Regel gibt es, wenn der Text mindestens so lang ist wie die »Eindeutigkeitsdistanz« der Chiffre, genau eine sinnvolle Lösung; siehe später.

Das praktische Vorgehen bei der Exhaustion ist also:

1. Nimm den nächsten Schlüssel, dechiffriere probeweise das Anfangsstück des Geheimtextes.
2. Falls sinnvoller Text entsteht (z. B. nach einem statistischen Kriterium, dechiffriere probeweise ein weiteres Stück usw., bis ans Ende des Textes. Wird dieses dabei erreicht, merke den Schlüssel als mögliche Lösung.
3. Falls kein sinnvoller Text entsteht, gehe zum nächsten Schlüssel.