Brute Force (engl. "Rohe 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 potentiellen 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. Mancher Brute-Force-Angriff bedient sich außerdem auch einer Wortliste, in welcher besonders häufig vorkommende Passwörter enthalten sind, um schneller Treffer erzielen zu können.

Neben dem Durchprobieren mittels Software kann auch das manuelle Durchprobieren von Passwörtern als Brute-Force-Angriff bezeichnet werden. Desweiteren 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.

Siehe auch: Kryptoanalyse

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 riesigen 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.

In dem strategischen Spiel Go ist die Brute-Force-Methode unabhängig von der zukünftigen Entwicklung der Hardware zum Scheitern verurteilt.