Brute-Force-Attacke

1. Einführung

Es gibt viele verschiedene Angriffstechniken auf IT-Systeme. Eine davon ist die sogenannte Brute-Force-Attacke. Hierbei handelt es sich um einen sehr naiven und intellektuell nicht sonderlich anspruchsvollen Angriff, bei dem einfach alle Möglichkeiten für ein Passwort oder Schlüssel nacheinander ausprobiert werden. Der Begriff bedeutet übersetzt so viel wie "rohe Gewalt", was auch zur grundlegenden Vorgehenweise dieser Methode passt, nämlich mit roher Gewalt eine Verschlüsselung in die Knie zwingen.
Mit Passwortcrackern wie Hashcat lassen sich Brute-Force-Angriffe sehr leicht realisieren.

2. Das Kerckhoffsche Prinzip

Brute-Force-Angriffe werden auf Passwörter bzw. verschlüsselte Informationen durchgeführt. Nach dem dem Kerckhoffschen Prinzip soll die Sicherheit eines Kryptosystems einzig und allein von der Sicherheit bzw. Geheimhaltung der Schlüssel abhängig sein, d. h. für die gängigen Verschlüsselungsverfahren sind die Algorithmen, mit denen Informationen ver- und entschlüsselt werden, bekannt. Umso wichtiger ist es, dass man durch Ausprobieren nicht einfach den Schlüssel erraten kann, wodurch dann unbefugtes Ver- und Entschlüsseln möglich wäre, da in den Kryptosystemen, die das Prinzip nach Kerckhoff berücksichtigen, die Algorithmen ja bekannt sind.
Doch wie kann man sich vor Brute-Force-Angriffen schützen? Nun, das ist schon wieder ein eigenes Thema für sich, zu dem ich einen separaten Artikel schreiben werde. Hier soll es jetzt erstmal um eine Schutzmöglichkeit gehen, die man recht schnell einsieht: Die Mächtigkeit des Schlüsselraums. Was ist damit gemeint? Ein Kryptosystem besteht aus einer Menge an Schlüsseln, die sogenannte Schlüsselmenge \(\mathcal{S}\) bzw. der Schlüsselraum. Je mächtiger diese Schlüsselmenge ist, d. h. je mehr Schlüssel es theoretisch gibt, desto besser ist man vor Brute-Force-Attacken geschützt. Wir reden hier nicht von \(100\) oder \(1000\), sondern von \(10^{20}\) Schlüsseln und mehr. Moderne Rechner sind nämlich durchaus in der Lage (je nach Kryptogsystem) mehrere hunderttausend Schlüssel pro Sekunde berechnen und testen zu können. Vor diesem Hintergrund ist ein Kryptosystem, in dem nur \(10000\) verschiedene Schlüssel existieren, mehr als schwach.
Wenn du an den Schutz deines Bankkontos denkst, dann wird dir vermutlich schnell klar, dass ein PIN aus vier Ziffern von \(0\) bis \(9\) recht wenige Möglichkeiten ergibt, denn für jede der vier Stellen gibt es nur \(10\) Möglichkeiten und somit insgesamt nur $$ 10\cdot 10\cdot 10\cdot 10 = 10^4=10000 $$ Möglichkeiten. Wenn ein Computer all diese Möglichkeiten ausprobieren würde, wäre er in nicht mal 100ms (wenn nicht sogar noch schneller) fertig. Selbstverständlich haben Banken, um solchen Angriffen vorzubeugen, eine Brute-Force-Sperre eingebaut, die nach drei Falscheingaben die Karte sperrt. Das wiederum sorgt an anderer Stelle für Probleme, auf die wir in einem anderen Artikel eingehen werden. Wir gehen im Folgenden davon aus, dass ein Angreifer unendlich viele Versuche hat, um in ein System einzudringen oder eine Verschlüsselung zu knacken.

3. Schlüsselräume berechnen

In dem vorangegangenen Beispiel mit den PINs hast du bereits gesehen, wie man den Schutz eines Kryptosystems vor einem Brute-Force-Angriff berechnen kann, nämlich indem man mithilfe der Kombinatorik die Anzahl an Möglichkeiten theoretisch berechnet. In meiner Bachelorarbeit habe ich eine eigene Metrik entworfen, mit der man die Sicherheit von Authentifizierungsverfahren bestimmen kann. Eine Kenngröße war dabei auch die Mächtigkeit des Schlüsselsraums. Wir werden uns nun für einige dieser Authentifizierungsverfahren, die alle wissensbasiert sind (d. h. man muss eine Geheiminformation erinnern), die Mächtigkeit der Schlüsselräume berechnen.
Für Seins-basierte Authentifizierungsverfahren (wie etwa Fingerabdrücke oder Retina-Muster) ist es ohne tiefgreifende biologische Grundkenntnisse nicht ohne weiteres möglich, die Mächtigkeit des Schlüsselraums theoretisch zu berechnen. Es gibt aber enorm viele Möglichkeiten, wodurch Brute-Force-Angriffe hier mehr oder weniger chancenlos sind. Es sei denn, es liegen einem weitere Informationen über das Opfer vor (wie etwa Teile eines Fingerabdrucks oder sehr scharfe Aufnahmen der Augen). Ein Angriff, bei dem nicht nur mit "roher Gewalt" ausprobiert wird, sondern bei dem verschiedene Faktoren intelligent berücksichtigt und kombiniert werden, fällt dann eher in die Kategorie "Guessing-Angriff". Wenn man den Schlüsselraum durch Kombinieren reduziert hat, wendet man auf die übriggebliebenen Schlüssel aber dann wieder eine Brute-Force-Attacke an.
Dazu mal ein praktisches Beispiel: Stelle dir vor, du stehst am Geldautomaten und hinter dir sieht jemand zufällig im Vorbeigehen, wie du die letzte Ziffer deines PINs eintippst (z. B. die \(0\)). Wenn diese Person nun eine Brute-Force-Attacke für deinen PIN durchführen wollen würde, müsste sie statt \(10000\) nur noch $$ 10\cdot 10\cdot 10=1000 $$ Möglichkeiten ausprobieren! Der Schlüsselraum hat sich also durch Bekanntwerden von nur einer einzigen Stelle um den Faktor \(10\) reduziert. Das ist problematisch und ein weiteres Argument dafür, dass der PIN für das, was er eigentlich schützen soll, mehr als schwach ist. Interessant würde es werden, wenn der PIN nicht von der Bank vorgegeben werden würde, sondern vom Anwender selbst festgelegt werden könnte. Dann könnte man durch Wissen über den Besitzer der Bankkarte eine derart hohe Schlüsselraumreduktion vornehmen, sodass nur noch eine handvoll PIN übrig bliebe. Die verbliebenen Möglichkeiten müssen dann allerdings trotzdem per Brute-Force durchprobiert werden.

3.1 Passwörter

Bei Passwörtern gibt es zwei Größen, aus denen man die Anzahl des Schlüsselraums berechnen kann, nämlich die Anzahl möglicher Zeichen \(n\) und die Länge des Passworts \(k\). Insgesamt ergeben sich, weil es sich dabei um eine Variation mit Wiederholung handelt $$ n^k $$ verschiedene Passwörter. In der Praxis können bis zu \(95\) Zeichen für ein Passwort erlaubt sein. Damit hätte man $$ 95^k $$ Möglichkeiten, um ein \(k-\)stelliges Passwort zu bilden. Wenn die erlaubte Passwortlänge zwischen \(6\) und \(15\) Zeichen liegt, dann gibt es $$ \sum\limits_{k=6}^{15}{95^k}=468219860267835848668171500000 $$ Passwörter. Das sind schon sehr viele! In der Praxis kann man diesen Schlüsselraum aber deutlich reduzieren, da Menschen sehr faul sind, was die Wahl starker Passwörter angeht.

Die Reduktion des Schlüsselraums ist das wohl größte Problem, da man dadurch ein auf den ersten Moment nicht in hinreichend kurzer Zeit knackbares Problem, auf eines reduziert, das sich sehr leicht knacken lässt. In SAP-Systemen werden Teile eines Passworts z. B. redundant gespeichert, was einen zweistufigen Brute-Force-Angriff ermöglicht. #Ich habe dir dazu einen Artikel auf meiner Webseite in der Videobeschreibung verlinkt#

3.2 Android-Mustersperre

Die Android-Mustersperre ist ein Authentifizierungsverfahren, bei dem man nach bestimmten Regeln ein Muster in eine \(3\times 3\) Matrix aus Punkten einzeichnet. Hierfür gibt es 389112 Möglichkeiten. Diese habe ich mit Hilfe eines kleinen Programms ermittelt #das ich dir unten in der Videobeschreibung verlinkt habe. Dort findest du auch eine Datei von mir mit allen möglichen Mustersperren samt Hashwert, der im Android-Telefon hinterlegt ist# Du müsstest im Worst-Case also 389112 verschiedene Muster eingeben, um unbefugten Zugriff auf ein Smartphone zu erhalten. Wenn du für jedes Muster ca. 5 Sekunden für die Eingabe bräuchtest, wären das maximal 23 Tage (am Stück). Durch Shoulder-Surfing und Smudge-Attacks lässt sich der Schlüsselraum für dein Opfer reduzieren. Die Mustersperre ist also alles andere als sicher.

3.3 Emoji-PIN

Der Emoji-PIN ist ein bisher noch nicht in der Praxis eingesetztes Authentifizierungsverfahren, bei dem man aus einer Menge an Emojis vier heraussucht und diese dann (unter Berücksichtigung der Reihenfolge) das Passwort bilden. Dieses Verfahren verbessert die Merkbarkeit von Passwörtern und PINs, da man mit Emojis Emotionen verbinden und Geschichten stricken kann. Wie groß ist der Schlüsselraum für den Emoji-PIN? Gehen wir von \(20\) Emojis aus und einer PIN-Länge von \(4\) aus, dann gibt es für jede der vier Stellen \(20\) verschiedene Möglichkeiten, insgesamt also $$ 20^{4}=160000 $$ Möglichkeiten, was \(16\) mal so viele wie beim PIN, aber dennoch viel zu wenige sind! Die Erhöhung der Zeichenmenge und/oder der Emoji-PIN-Länge senkt die Usability dieses Verfahrens, was wiederum negative Konsequenzen für die Sicherheit hat.

3.4 Cäsar-Verschlüsselung

Nach Julius Cäsar ist ein Verschlüsselungsverfahren benannt, das darauf basiert, dass man jeden Buchstaben einer zu verschlüsselnden Nachricht um eine bestimmte Anzahl an Stellen verschiebt. Heute kennt man diese Cäsar-Verschlüsselung auch unter dem Namen ROT\(_n\)-Verschlüsselung, wobei \(n\) angibt, um wie viele Stellen die Buchstaben verschoben werden. Wenn man am Ende des Alphabets angekommen ist, fängt man einfach wieder vorne an. Man rechnet also modulo der Anzahl an Buchstaben in dem Alphabet. Wenn man z. B. die Nachricht GEHEIMNIS mit ROT-13 verschlüsselt, ergib sich TRURVZAVF.
Wie sicher ist denn die Cäsar- bzw. ROT-Verschlüsselung vor Brute-Force-Attacken? Nun, da wir modulo \(26\) rechnen (also immer wieder vorne im Alphabet anfangen) gibt es nur \(26\) bzw. \(52\) (mit Groß- und Kleinbuchstaben) verschiedene Schlüssel, wobei der Schlüssel \(0\) noch nicht einmal Sinn ergibt (dann erhält man nämlich die identische Nachricht). Außerdem ist die Unterscheidung zwischen Groß- und Kleinbuchstaben auch kaum sicherheitsfördernd, da der Klein- und Großbuchstabe eine fixe Länge voneinander entfernt liegen, d. h. wir können ruhig von \(26\) verschiedenen Schlüsseln ausgehen. Die restlichen Kombinationen bekommt man sehr schnell durch Ausprobieren heraus. Nehmen wir mal an, wir hätten die Geheimbotschaft NSKTWRFYNP gegeben und wüssten, dass sie mit der Cäsar-Verschlüsselung verschlüsselt worden wäre. Dann probieren wir (ab dem Schlüssel \(1\)) systematisch durch und erhalten:
  • MRJSVQEXMO
  • LQIRUPDWLN
  • KPHQTOCVKM
  • JOGPSNBUJL
  • INFORMATIK
Der Schlüssel war also sehr wahrscheinlich die \(5\). \(26\) Schlüssel sind in der heutigen Zeit also ein schlechter Witz. Man könnte für solche monoalphabetischen Kryptosysteme auch weitere Angriffe und Analysen starten (wie etwa den Kasiski-Test), doch dazu in einem anderen Artikel mehr.

3.5 RSA-Kryptosystem

Von allen bisherigen Verfahren ist das RSA-Kryptosystem das mit dem größten Schlüsselraum. Beim RSA-Verfahren wird der Schlüssel nämlich aus zwei Primzahlen gebildet und Euklid wusste bereits, dass es unendlich viele Primzahlen gibt. Dementsprechend ist der Schlüsselraum auch unendlich groß. Allerdings kann man die Brute-Force-Methode auch dazu nutzen, um aus dem öffentlichen Schlüssel den privaten Schlüssel herzuleiten. Das RSA-Verfahren ist nämlich ein asymmetrisches Verschlüsselungsverfahren, bei dem man theoretisch aus dem öffentlichen Schlüssel den geheimen Schlüssel durch systematisches Ausprobieren herleiten kann. Beim RSA-Verfahren würde sich das Ausprobieren auf das Aufspüren der beiden Primzahlen beziehen, aus denen sich der Schlüssel zusammensetzt. Für \(143\) ist das noch recht einfach, denn durch eine einfache Primfaktorzerlegung kommt man schnell auf \(11\) und \(13\), doch es gibt keinen effizienten Algorithmus, mit dem man Primfaktoren für eine Zahl berechnen kann, der auch für Zahlen in hinreichend kurzer Zeit terminiert, die mehrere hundert Stellen lang sind. Das RSA-Verfahren ist somit (wie quasi alle Verschlüsselungsverfahren mit Ausnahme des One-Time-Pads) nur praktisch, aber nicht theoretisch sicher.

3.6 SHA512

Wie schon bei Passwörtern, steigt mit zunehmender Länge die Sicherheit von Hash-Werten. Je weniger Limitationen an ein Passwort gestellt werden, desto größer ist der Schlüsselraum. Beim SHA512 Algorithmus wird eine beliebige Zeichenkette in eine Zeichenkette aus \(128\) Hexadezimalziffern übersetzt. Wie viele verschiedene Hash-Werte gibt es also theoretisch? Es gibt insgesamt \(16\) Hexadezimalziffern, nämlich $$ 0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f $$ Da an jeder der \(128\) Stellen \(16\) verschiedene Ziffern Zeichen möglich sind, gibt es insgesamt $$ 16^{128} $$ verschiedene Hash-Werte. Mal angenommen, wir könnten eine Milliarde Hashwerte pro Sekunde berechnen (was schon astronomisch hoch wäre). Dann würden wir immer noch $$ \frac{16^{128}}{10^9\cdot 60\cdot 60\cdot 24\cdot 365}\approx 4\cdot 10^{137} $$ Jahre brauchen, um alle ermitteln zu können. Von Speichern ist dabei noch gar nicht die Rede. Zum Vergleich: Das Universum ist etwa \(13.8\cdot 10^{9}\) Jahre alt. Man bräuchte also ca. $$ \frac{4\cdot 10^{137}}{13.8\cdot 10^9}\approx 2.9\cdot 10^{127} $$ mal so lange wie das Universum alt ist, um mit einer Milliarde Rechenoperationen pro Sekunde alle Hash-Werte berechnen zu können. Das ist sicher! Das Problem ist auch hier, dass es ausgeklügelte Angriffstechniken gibt, um diese Zahl (auch für andere Hash-Algorithmen) zu reduzieren!

4. Hashes für die Mustersperre

Download
Hashes für die Mustersperre
mustersperre.txt
Text Dokument 18.9 MB