Hill Climbing Methode

Siehe auch: Brute Force-Attacke, Häufigkeitsverteilung

"Hill Climbing" lässt sich mit "Bergsteigen" übersetzen und so werden die Algorithmen, die diese Methode benutzen, auch als "Bergsteigeralgorithmus" bezeichnet. Den Namen hat diese Kryptoanalyse-Methode daher, dass man die Funktionsweise mit der Erklimmung eines Berggipfels versinnbildlichen kann: Wie ein Bergsteiger den Weg zum Gipfel über Aufs und Abs findet, so findet ein Hill Climbing-Algorithmus das richtige Schlüsselwort bzw. den Klartext auch nach einer Abfolge von Aufs und Abs.

Dazu braucht es einen Beurteilungsmechanismus, ob man den Gipfel schon erreicht hat. Das geschieht dadurch, dass man den mit dem gerade benutzten Schlüssel das Chiffrat entschlüsselt und den daraus resultierten vermeintlichen Klartext auf Plausibilität überprüft. Das geschieht meist durch Zählung von Tri-, Tetra- oder Pentagrammen und Vergleich der Ergebnisse mit der Häufigkeitsverteilung dieser in einer natürlichen Sprache, welche ein charakteristisches, statistisches Muster aufweist.

Die jeweilige Übereinstimmung bzw. die "Fitness" wird mit einer Punktzahl ("Score") ausgedrückt. Je höher der Score, desto näher ist man dem Gipfel, also an der Lösung.

Anstatt nun stumpf wie bei einer Brute Force-Attacke alle möglichen Schlüsselkombinationen auszuprobieren, bedient man sich einer Optimierung, die aus der Analogie zum Bergsteigen kommt: "Zum Gipfel geht es immer aufwärts". Das heißt: Wenn der Score bei einer bestimmten Änderung des Schlüssels höher wird, dann befinden wir uns wahrscheinlich auf dem richtigen Weg, denn es geht aufwärts.

Wie beim Bergsteigen geht es natürlich nicht immer nur aufwärts, sondern wir müssen auch mal ein Tal durchschreiten, um dann wieder aufwärts gehen zu können und vielleicht einen noch höheren Bergkamm erreichen zu können. Diese Optimierungsmethode spart viele unnötige Wege und damit viel Zeit und sie erlaubt es, Chiffre zu brechen, die mit der Brute-Force-Methode "ewig" dauern würden.

Andererseits können wir uns bei unserem Aufstieg auch nie ganz sicher sein, den maximal höchsten Gipfel ("globales Maximum") bereits erreicht zu haben. Es könnte immer noch einen höheren Gipfel geben als den gegenwärtig erreichten ("lokales Maximum"). Denn bei der Kryptoanalyse steckt unser Bergsteiger sozusagen im dichten Nebel und kann nur einen Schritt voraus sehen und machen. Dafür kann er in Nullkommanichts wieder an einer ursprünglich gegangenen Punkt zurück, an dem er schon einmal war, um von dort in eine andere Richtung weiter zu machen.

Man muss für den Score also einen Grenzwert ("Gipfelhöhe") festlegen, ab dem die Chiffre als gelöst gilt oder eben eine gewisse Zeit, in der sich kein neuer Gipfelerfolg einstellte.

Dann erstellt man eine Liste der vielleicht 20 höchsten Gipfel, abwärts sortiert nach dem Score mit errechnetem Klartext und Schlüssel und zeigt diese Auswahl an, damit ein Mensch den Klartext bzw. den Schlüssel identifizieren kann.

Eine Kleinigkeit gibt es aber für die Hill Climbing-Methode zu bedenken: Sie funktioniert nicht mit modernen Chiffren wie zum Beispiel DES oder AES. Die sind nämlich von Haus aus schon darauf ausgelegt, dass die Änderung nur eines Zeichens / Bytes im Schlüssel das nachfolgende Chiffrat komplett anders aussehen zu lassen, sie also Choas schaffen. DES realisiert das durch ein Feistel-Netzwerk, AES durch eine Substitutions-Permutations-Netzwerk.

Die Hill Climbing-Methode benötigt aber eine Chiffre, bei der sich nicht viel ändert, wenn sich nur ein Schlüsselbuchstabe ändert, damit sie auch die beiden Einzel-Schritte, die sie auf ihrem Weg tat, miteinander vergleichen und beurteilen kann, ob der letzte Schritt auf- oder abwärts führte. Alle klassischen (nicht computerbasierten) Substitutions-Chiffren bis hin zu den Chiffriermaschinen sind anfällig für die Hill Climbing-Methode, dies schließt die Enigma nicht aus.

Ein Hill Climbing-Algorithmus muss zudem auf die jeweilige Chiffre zugeschnitten sein, denn er muss wiederholt:

• Einen möglichen Schlüssel generieren
• Das Chiffrat mit diesem Schlüssel dechiffrieren
• Das Resultat mit statistischen Methoden mit einem Score bewerten
• Auf das zuvor definierte Abbruchkriterium prüfen
• Die nächste geeignete Manipulation des Schlüssels nach einer Selektionsstrategie festlegen

Der Verschlüsselungsalgorithmus und ggf. der Bewertungsalgorithmus muss also Teil des Ganzen sein und deshalb gibt es auch nicht den einen allgemeingültigen Hill Climbing Solver. Aber vieles davon wäre auch für einen Brute-Force-Angriff vonnöten und die Hill Climbing-Methode spart demgegenüber enorm viel Rechenzeit, weil es nur ein Bruchteil der Schlüssel durchprobiert, nämlich den jeweils vielversprechendsten.

Die Hill Climbing-Methode lässt sich auch gut parallelisieren, programmiertechnisch zum Beispiel durch mehrere Threads, die mehrere CPU-Kerne auslasten. Einfach indem man die virtuellen Bergsteiger an unterschiedlichen Positionen los klettern lässt, respektive pro Thread mit einem anderen Schlüsselkandidaten startet.

Hill-Climbing lässt sich auch für Tranpositionen anwenden, solange die Bedingungen erfüllt sind: 1. Es ist möglich, nur kleine Änderungen am Schlüssel vorzunehmen, dann dann nur eine kleine Änderung des Chiffrats zur Folge haben und 2. Man muss eine geeignete Bewertungsfunktion entwickeln können. Dies wäre zum Beispiel bei einem vollständigen Spaltentausch der Fall: man könnte den Schlüssel, die Spaltenreihenfolge geringfügig ändern, indem man nur 2 Zahlen der Reihenfolge vertauscht und man könnte das Resultat der Entschlüsselung durch Vergleich der Häufigkeit von Tri-, Tetra- oder Pentagrammen überprüfen. Bei der unvollständigen Spaltentausch-Chiffre wird die Sache ein wenig kniffliger, weil allein dies nicht immer ausreicht. Dann muss die Bewertungsfunktion noch weitere Überprüfungen enthalten. Tipps zur Vorgehensweise finden sich im Artikel Brechen von Transpositions-Chiffren.

Quellen, Literaturverweise und weiterführende Links