Brute-Force-Methode

Die Brute-Force-Methode (von englisch brute force ‚rohe Gewalt‘) bzw. Methode der rohen Gewalt, auch Exhaustionsmethode (kurz Exhaustion von lateinisch exhaurire ‚ausschöpfen‘), ist eine Lösungsmethode für Probleme aus den Bereichen Informatik, Kryptologie und Spieltheorie, die auf dem Ausprobieren aller möglichen (oder zumindest vieler möglicher) Fälle beruht. Sowohl der Begriff erschöpfende Suche (engl. exhaustive search), als auch vollständige Suche sind in Gebrauch.

Informatik

Für viele Probleme in der Informatik sind keine effizienten Algorithmen bekannt. Der natürlichste und einfachste Ansatz zu einer algorithmischen Lösung eines Problems besteht darin, alle potenziellen Lösungen durchzuprobieren, bis die richtige gefunden ist. Diese Methode nennt man „Brute-Force-Suche“ (englisch brute-force search).

Die Brute-Force-Suche ist einfach zu implementieren und dazu bestimmt, die korrekte Lösung zu finden. Allerdings steigt der Aufwand an Rechenoperationen proportional zur Anzahl der zu probierenden möglichen Lösungen, wobei die Anzahl dieser möglichen Lösungen mit zunehmendem Umfang der Probleme häufig exponentiell rasch wächst.

In manchen Fällen existieren Methoden, um das Laufzeitverhalten zu optimieren. Möchte man etwa ein vierwalziges Zahlenschloss lösen und probiert hierbei die Codeworte in natürlicher Reihenfolge aus, so müsste man beim Wechsel von Codewort 0999 auf Codewort 1000 vier Walzen bewegen. Wenn man jedoch mit Gray-Codes arbeitet (nach 0999 folgt 1999), muss pro Versuch stets nur eine Walze bewegt werden.

Ein wichtiger Anwendungsbereich findet sich in der Computersicherheit. Ein oft angeführtes Anwendungsbeispiel für die Brute-Force-Methode ist hier das Brechen oder umgangssprachlich „Knacken“ von Passwörtern.

Oft sind Passwörter mit Hilfe von kryptographischen Hashfunktionen verschlüsselt. Eine direkte Berechnung des Passworts aus dem Hashwert ist praktisch nicht möglich. Ein Cracker kann jedoch die Hashwerte vieler Passwörter berechnen. Stimmt ein Wert mit dem Wert des hinterlegten Passwortes überein, hat er das (oder ein anderes, zufällig passendes) Passwort gefunden. Brute Force bedeutet hier also simples Ausprobieren von möglichen Passwörtern. Vordefinierte Hashlisten häufig verwendeter Passwörter nennt man Rainbow Tables.

Aus dem oben genannten Zusammenhang zwischen Umfang des Problems und Anzahl der benötigten Rechenoperationen lässt sich für das Beispiel des „Passwortknackens“ der Schluss ziehen, dass mit steigender Passwortlänge oder steigender Anzahl an möglicherweise im Passwort vorhandenen Zeichen (Alphabet ohne Zahlen, mit Zahlen, mit Sonderzeichen) der Aufwand der Brute-Force-Methode schnell ansteigt. Die Methode ist in der Praxis häufig erfolgreich, da die meisten Benutzer kurze und einfache, damit unsichere Passwörter verwenden. Mit entsprechenden Werkzeugen können schon auf handelsüblichen Mittelklasse-Computern Millionen Passwörter je Sekunde ausprobiert werden.

Wird die Anzahl der auszuprobierenden Passwörter durch Reduktion der Möglichkeiten auf Einträge aus einem „Wörterbuch“ (oder Zusammensetzungen derer) eingeschränkt, spricht man auch von einem Wörterbuchangriff (englisch dictionary attack). Es gibt spezielle Wortlisten, die in Passwörtern übliche Begriffe enthalten.

Aufgrund der schnell steigenden Rechenleistung heutiger Rechner können diese zunehmend mehr Möglichkeiten pro Zeiteinheit durchprobieren. Somit sind immer längere Passwörter oder solche aus einer größeren Vielzahl an verwendeten Zeichen für einen ausreichenden Schutz gegen die Brute-Force-Methode erforderlich.

Gegenmaßnahmen beinhalten unter anderem die Verwendung von Key-Stretching oder Salts. Beim Key-Stretching wird durch Iteration eines Hashes (PBKDF2) oder durch komplizierte Vorbereitungsmaßnahmen für die Ausführung eines Algorithmus (bcrypt) die Rechenzeit zur Berechnung des finalen Hashwertes vergrößert oder durch intensiven Speichergebrauch die Ausführung auf schnellen ASICs oder FPGAs, die beide nur über vernachlässigbaren Speicher verfügen, verhindert (scrypt). Der Salt, der mit dem Passwort konkateniert wird, dient dazu, die Erstellung von Rainbow-Tables durch Vergrößerung des Urbildbereichs zu verhindern. Der Schlüssel wird also durch gewisse Methoden „gestreckt“, sodass ein Passwort mit geringerer Komplexität mit Key-Stretching dennoch rechenäquivalent zu einem komplexeren Passwort ohne Key-Stretching wird.

Eine andere Gegenmaßnahme besteht in der Verwendung extrem langer, zufällig generierter Passwörter, die man sich nicht mehr merkt, sondern in einer Kennwortverwaltung hinterlegt. Auf diese Weise reduziert man die Zahl der für Brute Force anfälligen Schwachstellen auf eine einzige, nämlich das Hauptkennwort der Kennwortverwaltung.

In der Praxis werden Brute-Force-Angriffe auch dadurch erschwert, dass die Zahl der Versuche begrenzt ist, und nach einigen erfolglosen Passworteingaben der Zugang gesperrt wird oder weitere Versuche erst nach einer Wartezeit möglich sind. Trotzdem wurde im September 2014 bekannt, dass z. B. Apple in seiner iCloud längere Zeit solche einfachen Maßnahmen nicht implementiert hatte und zumindest einfache Brute-Force-Attacken möglich waren.

Kryptologie

In der Kryptoanalyse, also dem Teilgebiet der Kryptologie, das sich mit der Entzifferung von verschlüsselten Geheimtexten befasst, kann die Methode verwendet werden, um alle möglichen Schlüssel „exhaustiv“, das heißt erschöpfend durchzuprobieren. Man spricht bei dieser vollständigen Schlüsselsuche von einem „Brute-Force-Angriff“ (engl. brute force attack) oder auch von der „Exhaustionsmethode“.

Die Reihenfolge der Probe-Schlüssel wird gegebenenfalls nach ihrer Wahrscheinlichkeit ausgewählt. Dies ist jedoch bei (pseudo)zufällig generierten Schlüsseln wenig hilfreich. Die Schlüssellänge spielt eine entscheidende Rolle: Mit zunehmender Länge des Schlüssels steigt der Umfang des Schlüsselraums, also der Menge aller möglichen Schlüssel, exponentiell an. Es ist hier nach den Regeln der Wahrscheinlichkeit zu erwarten, dass im Mittel die Hälfte aller möglichen Schlüssel des Schlüsselraums ausprobiert werden muss, bis der verwendete Schlüssel gefunden ist.

Angriffe dieser Art auf moderne Verschlüsselungsalgorithmen bei Verwendung ausreichend langer Schlüssel sind in der Praxis aussichtslos, da der erforderliche Rechenaufwand (und damit Zeit- und/oder Kostenaufwand) zu groß wäre. Da die Leistung moderner Hardware immer mehr steigt und sich der Zeitaufwand für das Durchprobieren aller Schlüssel einer bestimmten Länge dadurch erheblich reduziert, muss die minimale Schlüssellänge ausreichend groß gewählt werden, um einen Angriff durch Exhaustion sicher zum Scheitern zu verurteilen.

Spieltheorie

In der Spieltheorie, beispielsweise beim Computerschach, ist die Brute-Force-Methode eine Strategie, in der der Variantenbaum bis zu einer gewissen Tiefe vollständig durchsucht und analysiert wird. Eine Bewertungsfunktion für jede der dabei auftretenden Stellungen dient dabei zur Entscheidungsfindung für den besten Zug.

Der Aufwand für die Brute-Force-Methode wächst exponentiell mit der verwendeten Maximaltiefe der Stellungssuche. Schach wird den endlichen Nullsummenspielen mit perfekter Information zugeordnet. Theoretisch könnte man also ermitteln, ob bei beiderseits perfektem Spiel Weiß oder Schwarz gewinnt oder die Partie remis enden muss. Da die Anzahl der möglichen Varianten jedoch enorm hoch ist, setzt gegenwärtig die jeweilige Leistung der Hardware dieser Methode noch ihre Grenzen.

Die Brute-Force-Methode kann durch unterschiedliche Ansätze verfeinert werden, wodurch erhebliche Verbesserungen erreicht werden können. Ein Beispiel ist die Alpha-Beta-Suche. Dabei wird berücksichtigt, ob beim Schachspiel ein Zug in einer bestimmten Suchtiefe durch einen bestimmten Gegenzug widerlegt werden kann. Wird dies erkannt, dann ist es sinnlos, nach noch besseren Widerlegungen zu suchen. Auf diese Weise kann viel Rechenzeit eingespart werden.

Eine andere Methode ist, ab einer gewissen Tiefe nur noch „forcierte“ Abwicklungen zu betrachten. Im Schach wären dies etwa Schachgebote oder Schlagzüge.

Weblinks

• Zusammenhang von Brute-Force-Attacken und Passwortlängen. In: 1pw.de. Abgerufen am 7. September 2022. 
• Dennis Yurichev: How to create FPGA-based Oracle RDBMS cracker that works in average 30–40 times faster than password crackers on Intel Core Duo 2.