Brute-Force-Methode

Brute Force bzw. Methode der rohen Gewalt ist der Fachbegriff für eine Lösungsmethode schwerer Probleme aus dem Bereich der Informatik und der Spieltheorie, die auf dem Ausprobieren aller (oder zumindest eines erheblichen Teils der in Frage kommenden) Varianten beruht.

Informatik

Für viele Probleme gibt es in der Informatik keine effizienten Algorithmen. Der natürlichste und einfachste Ansatz zur algorithmischen Lösung eines Problems besteht dann darin, einfach alle potenziellen Lösungen durchzuprobieren. Diese Methode nennt man "Brute Force".

Bekannt ist diese Methode vor allem im Bereich der Computersicherheit. Klassisches Anwendungsbeispiel für Brute-Force-Attacken ist das Knacken von verschlüsselten Passwortlisten, welche in der Regel aus Hash-Werten bestehen, bei welchen die Verschlüsselung nicht mehr rückgängig gemacht werden kann. Brute Force bedeutet hier dann simples Ausprobieren verschiedener Passwortmöglichkeiten. Versuche werden generiert, auf die gleiche Weise verschlüsselt und bei Gleichheit der beiden Hashes ist das Passwort gefunden. Dieses Verfahren ist deshalb sehr rechenintensiv und lohnt sich nur in den wenigsten Fällen, solange keine zu schwachen Passwörter vergeben wurden, daher meist die zweite Wahl nach einem Wörterbuchangriff (engl. "Dictionary Attack").

Des Weiteren gibt es Software, um Brute-Force-Angriffe via Internet auf Dienste wie FTP durchzuführen.

Der vielseitigen Anwendbarkeit, insbesondere gegen Internetdienste, steht der immense Zeitaufwand gegenüber, weshalb mit zunehmender Rechenleistung immer längere Hash-Werte für einen ausreichenden Schutz benötigt werden.

Spieltheorie

In der Spieltheorie bezeichnet man mit der Brute-Force-Methode eine Strategie, in der der Variantenbaum bis zu einer gewissen Tiefe vollständig 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; damit setzt die Hardware dieser Methode eine natürliche Grenze.

Die Brute-Force-Methode kann mit den verschiedensten Methoden verfeinert werden, was durch das genannte exponentielle Wachstum zu erheblichen Verbesserungen führen kann. Eine sehr übliche Verbesserung ist die Alpha-Beta-Suche: ist ein Zug in einer bestimmten Tiefe durch einen gewissen Gegenzug widerlegt, dann ist es nutzlos, nach noch besseren Widerlegungen zu suchen.

Eine andere übliche Methode ist, ab einer gewissen Tiefe nur noch "forcierende" Züge zu betrachten. Im Schach wären dies etwa Schachgebote oder Schlagzüge.

Kryptoanalyse

Bei der Kryptoanalyse werden alle möglichen Schlüssel nacheinander durchprobiert. Die Reihenfolge wird gegebenenfalls nach der Wahrscheinlichkeit ausgewählt. Diese Methode ist auch bei modernen Verschlüsselungsverfahren sinnvoll, wenn von der Verwendung eines relativ schwachen Passwortes ausgegangen werden kann.