Exhaustive Suche

Exhaustive Suche

Die Brute-Force-Methode (engl. für „Methode der rohen Gewalt“), auch Exhaustionsmethode (von lat. exhaurire = ausschöpfen), ist eine Lösungsmethode für Probleme aus den Bereichen Informatik, Kryptologie und Spieltheorie, die auf dem Ausprobieren aller (oder zumindest vieler) möglichen Fälle beruht.

Inhaltsverzeichnis

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, einfach alle potenziellen Lösungen durchzuprobieren, bis die richtige gefunden ist. Diese Methode nennt man „Brute-Force-Suche“ (engl. „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 steigendem Umfang der Probleme exponentiell ansteigt.

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

Oft sind Passwörter als kryptographische Hash-Funktionen verschlüsselt. Eine Berechnung des Passworts aus dem Hash-Wert ist praktisch nicht möglich. Ein „Cracker“ kann jedoch die Hash-Werte vieler Passwörter berechnen. Stimmt ein Wert mit dem Wert des hinterlegten Passwortes überein, hat er das (oder ein passendes) Passwort gefunden. Brute Force bedeutet hier also simples Ausprobieren von möglichen Passwörtern. Vordefinierte Hash-Listen häufig verwendeter Passwörter nennt man "Rainbow Table".

Aus dem oben genannten Zusammenhang zwischen Umfang des Problemes und 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) die Aufwändigkeit des Brute-Forcens schnell ansteigt. Die Methode ist in der Praxis häufig erfolgreich, da die meisten Benutzer kurze und einfache, damit unsichere, Passwörter verwenden. Schon auf einem handelsüblichen Mittelklasse-Computer können etwa 15 bis 25 Millionen Passwörter pro Sekunde ausprobiert werden (Stand 2008).

Wird die Anzahl der auszuprobierenden Passwörter durch Reduktion der Möglichkeiten auf Einträge aus einem „Wörterbuch“ (bzw. Zusammensetzungen derer) eingeschränkt, spricht man auch von einem Wörterbuchangriff (engl. „dictionary attack“).

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.

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, exponential 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ären. Da die Leistung moderner Hardware immer mehr steigt und dadurch der Zeitaufwand für das Durchprobieren aller Schlüssel einer bestimmten Länge erheblich reduziert, muss die minimale Schlüssellänge periodisch vergrößert werden, um weiterhin Sicherheit gewährleisten zu können.

Spieltheorie

In der Spieltheorie, beispielsweise beim Computer-Schach, 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. Damit setzt auch hier die jeweilige Qualität der Hardware dieser Methode eine bestimmte Grenze.

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


Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Visuelle Suche — Die Merkmalsintegrationstheorie (im Original Feature Integration Theory) von Anne Treisman (1980) ist eine Theorie, die die menschliche Objekterkennung mithilfe visueller Aufmerksamkeit erklärt. Den Ausgangspunkt für Treismans Ansichten stellt… …   Deutsch Wikipedia

  • Schlüssellänge — Die Schlüssellänge ist eine wichtige Eigenschaft kryptographischer Verfahren und bezeichnet ein logarithmisches Maß für die Anzahl der verschiedenen möglichen Schlüssel des Verfahrens. Inhaltsverzeichnis 1 Definition 2 Bedeutung für die… …   Deutsch Wikipedia

  • Eieraufgabe des Brahmagupta — Die Eieraufgabe des Brahmagupta[1], im Englischen auch als Egg Basket Problem[2] bekannt, ist eine als Anwendungsproblem eingekleidete zahlentheoretische Aufgabe. Hierbei erfüllt die Anzahl der Eier in einem Korb eine Reihe von Bedingungen,… …   Deutsch Wikipedia

  • Feature Integration Theory — Die Merkmalsintegrationstheorie (im Original Feature Integration Theory) von Anne Treisman (1980) ist eine Theorie, die die menschliche Objekterkennung mithilfe visueller Aufmerksamkeit erklärt. Den Ausgangspunkt für Treismans Ansichten stellt… …   Deutsch Wikipedia

  • Merkmalsintegrationstheorie — Die Merkmalsintegrationstheorie (im Original Feature Integration Theory) von Anne Treisman (1980) ist eine Theorie, die die menschliche Objekterkennung mithilfe visueller Aufmerksamkeit erklärt. Den Ausgangspunkt für Treismans Ansichten stellt… …   Deutsch Wikipedia

  • Pop-Out-Effekt — Die Merkmalsintegrationstheorie (im Original Feature Integration Theory) von Anne Treisman (1980) ist eine Theorie, die die menschliche Objekterkennung mithilfe visueller Aufmerksamkeit erklärt. Den Ausgangspunkt für Treismans Ansichten stellt… …   Deutsch Wikipedia

  • Brute-Force-Methode — Die Brute Force Methode (von engl. brute force = rohe Gewalt) bzw. Methode der rohen Gewalt, auch Exhaustionsmethode (von lat. exhaurire = ausschöpfen), ist eine Lösungsmethode für Probleme aus den Bereichen Informatik, Kryptologie und… …   Deutsch Wikipedia

  • Mondseer Fragmente — Rekonstruktion des Fragments NB12799B Mt.13,39 53 althochdeutsch Die Mondseer Fragmente (oder Monseer Fragmente, früher auch Wiener Fragmente, auf Englisch Monsee Fragments) sind eine Sammlung von christlichen Texten, die aus dem Westen des… …   Deutsch Wikipedia

  • Monseer Fragmente — handgeschriebene Replik des rekonstruierten Originaltextes von Matthäus Kapitel 13 Vers 15 bis 24 Die Mondseer Fragmente (früher auch Monseer Fragmente oder Wiener Fragmente, auf Englisch monsee fragments) sind eine Sammlung von christlichen… …   Deutsch Wikipedia

  • History of Vietnam — The history of Vietnam begins around 2,700 years ago. Successive dynasties based in China ruled Vietnam directly for most of the period from 111 BC until 938 when Vietnam regained its independence.cite book |last=Kenny |first=Henry J. |year=2002… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”