Department of Computer Science, Institute for Systems Architecture, Chair of Privacy and Data Security Pentestlab — Brute-force-Angriffe dud.inf.tu-dresden.de Stefan Köpsell ([email protected]) Brute-Force — Überblick brute force – rohe Gewalt / Brachialgewalt generelle Idee: • Ausprobieren vieler / aller möglichen Lösungskandidaten Vorteil: • in der Regel einfach umzusetzen Nachteil: • für viele Probleme sehr aufwendig (Laufzeit / Ressourcenverbrauch) Brute-Force — ein Beispiel Problem: Faktorisierung von 𝑛𝑛 ∈ ℕ Brute-Force-Algorithmen: a) für alle brute-force – Durchprobieren teste: ? aller möglichen 𝑖𝑖 ∈ ℕ, 1 < 𝑖𝑖 < 𝑛𝑛 Lösungskandidaten 𝑖𝑖 | 𝑛𝑛  was zählt zu „alle“? b) für alle 𝑛𝑛 teste: ? 𝑖𝑖 ∈ ℕ, 1 < 𝑖𝑖 < 2  Effizienz / Komplexität eines 𝑖𝑖 | 𝑛𝑛 Brute-Force-Algorithmus ein c) für alle mögliches Gütekriterium teste: ? 𝑖𝑖 ∈ ℕ, 1 < 𝑖𝑖 < 𝑛𝑛 𝑖𝑖 | 𝑛𝑛 d) für alle teste: ? 𝑖𝑖 ∈ ℙ, 1 < 𝑖𝑖 < 𝑛𝑛 2 𝑖𝑖 | 𝑛𝑛 𝑥𝑥 + 4𝑥𝑥 = 𝑛𝑛 ? Brute-Force— allgemeine Überlegungen • Problemeigenschaften: • es muß etwas geben, was man Durchprobieren kann • Abbruchkriterium (für Erfolgsfall) notwendig: • Lösung ist überprüfbar • Beispiel: Faktorisierung • IT-System: Systemverhalten • Beispiel: Programmabsturz, erfolgreiche Anmeldung • zeitliche Begrenzung Brute-Force— allgemeine Überlegungen • Strategien bezüglich Durchprobieren: • systematisch / vollständig / deterministisch: • alle Elemente einer endlichen Menge an Hand einer Wohlordnung • “natürliche” / “kanonische” Ordnung • gewichtet beispielsweise an Hand von Auftrittswahrscheinlichkeiten • exhaustive search  Beispiele: - Schlüsselsuche im Bereich Kryptographie - Paßwortsuche • indeterministisch:  Zufall beeinflußt Kandidatenauswahl  ggf. nicht vollständig • fuzzing Randomisierte Algorithmen • randomisierter / stochastischer /probabilistischer Algorithmus: • Zufall beeinflußt Abarbeitung des Algorithmus • Parameterwahl • mehrfache Ausführung kann zu unterschiedlichen Ergebnissen führen • Las-Vegas-Algorithmus: • liefert nie ein falsches Ergebnis • Unterarten: • a) liefert immer richtiges Ergebnis, Laufzeit im worst-case sehr groß • b) Algorithmus liefert kein / Teilmenge der Ergebnisse, Laufzeit beschränkt • Beispiel: Faktorisierung mit zufälliger Faktorenauswahl • Monte-Carlo-Algorithmus: • kann falsches Ergebnis liefern • Schranke für Fehlerwahrscheinlichkeit bestimmbar Fuzzing • ursprüngliche (?) Idee: • 1988 als Teil einer Praktikumsaufgabe am Computer Science Department der Universität von Wisconsin-Madison; Betreuer: Bart Miller: “The goal of this project is to evaluate the robustness of various UNIX utility programs, given an unpredictable input stream. This project has two parts. First, you will build a fuzz generator. This is a program that will output a random character stream. Second, you will take the fuzz generator and use it to attack as many UNIX utilities as possible, with the goal of trying to break them.” [http://pages.cs.wisc.edu/~bart/fuzz/CS736-Projects-f1988.pdf] • Konzept [http://pages.cs.wisc.edu/~bart/fuzz/]:  The input is random. We do not use any model of program behavior, application type, or system description.  Our reliability criteria is simple: if the application crashes or hangs, it is considerd to fail the test, otherwise it passes. Fuzzing • häufig angewendet im Rahmen von Black-Box-Test / Untersuchungen • “intelligentere” Anwendung in White-Box / Gray-Box Situationen möglich • modellgesteuerte Generierung der zufälligen Eingabedaten • abgeleitet von aufgezeichnete Daten (mutation) • aus Protokoll / Programm / Schnittstellenspezifikation • Beispiel: zufällige Eingabedaten mit (korrekt berechneter) Prüfsumme • verwandte Begriffe: Lasttest / Streßtest • fault injection  insbesondere im Hardwarebereich schon früh eingesetzt • Vielzahl an Werkzeugen existiert • Vielfältige Einsatzmöglichkeiten • Robustheits- / “Korrektheits”-Test von Programme • Test von Protokollimplementierung im Netzbereich • Hardwaretests • Sicherheitstest Fuzzing • Ziele: • unmittelbare Erfolg • System zeigt aus Angreifersicht gewünschtes Verhalten • Beispiel: • Umgehung von Zugriffskontrollmechanismen durch Fuzzing von Eingabeparametern • mittelbarer Erfolg • System zeigt Verhalten, daß auf weitere Angriffsmöglichkeiten hindeutet • Beispiel: Systemabsturz  ggf. erfolgreiche Bufferoverflow / Stackoverflow-Angriffe möglich Fuzzing— ein Beispiel Rowhammer • Mark Seaborn, Thomas Dulien: „Exploiting the DRAM rowhammer bug to gain kernel privileges“, März 2015 • basierend auf: Kim et al.: „Flipping Bits in Memory Without Accessing Them: An Experimental Study of DRAM Disturbance Errors“  Bit-Flip in Speicherzelle X durch wiederholten Zugriff auf Speicherzelle Y code1a: mov [a], %eax // copy data to address a mov [b], %ebx // copy data to address b clflush (a) // flush cache for address a clflush (b) // flush cache for address b jmp code1a funktioniert auch mit JavaScript… • • Angriffsszenarien: • Manipulation von “sicherem Code” bei Sandboxing-Verfahren  Ausbruch aus Sandbox • demonstriert für Google Chrome Native Client • Betriebssysteme: Manipulation der Page Table • Read/Write Zugriffs-Beschränkungen • Abbildung virtuelle Adresse  physische Adresse