Ein ahnungsloser Passwort-Cracking-Server: Kombination von Hellman-Tabellen und PIR-Protokollen

Inhaltsverzeichnis

• 1. Einleitung
• 2. Grundlagen
  • 2.1 Hash-Umkehr-Tabellen
  • 2.2 Privater Informationsabruf (Private Information Retrieval)
• 3. Lösungsübersicht
• 4. Technische Details & Algorithmus-Konstruktion
• 5. PIR-Protokolle & Komplexitätsanalyse
• 6. Experimentelle Ergebnisse
• 7. Fazit & Ausblick
• 8. Originalanalyse & Expertenkommentar
• 9. Technische Details & Mathematische Formulierung
• 10. Analyse-Rahmen & Fallstudie
• 11. Zukünftige Anwendungen & Richtungen
• 12. Referenzen

1. Einleitung

Dieses Papier behandelt eine kritische Datenschutz-Herausforderung in offensiven Sicherheitsoperationen: Das Durchführen von Passwort-Cracking über einen Drittanbieter-Server, ohne die Ziel-Hashes preiszugeben. Das Szenario betrifft einen Penetrationstester mit begrenzten lokalen Ressourcen (z.B. einem Smartphone), der große, vorberechnete Hash-Tabellen (wie Rainbow- oder Hellman-Tabellen) abfragen muss, die remote gehostet werden. Das Kernproblem ist die Konstruktion eines ahnungslosen Passwort-Cracking-Servers, bei dem der Server nicht erfahren kann, welche Passwort-Hash-Paare der Client zu knacken versucht, und so die operative Geheimhaltung bewahrt wird.

2. Grundlagen

2.1 Hash-Umkehr-Tabellen

Passwortsysteme speichern oft kryptografische Hashes. Angreifer verwenden vorberechnete Tabellen, um diese Hashes umzukehren. Wichtige Methoden sind:

• Hellman-Tabellen (1980): Ein Zeit-Speicher-Kompromiss, der Ketten aus Hashes und Passwörtern verwendet und nur Kettenstart- und -endpunkte speichert.
• Rivests Distinguished Points (1982): Eine Optimierung, die spezielle "ausgezeichnete" Hash-Werte als Kettenendpunkte verwendet, um Nachschlagevorgänge zu reduzieren.
• Rainbow-Tabellen (Oeschlin, 2003): Verwendet bei jedem Kettenschritt eine andere Reduktionsfunktion, ist im Allgemeinen schneller, aber für das vorgeschlagene PIR-basierte Abfragemodell weniger geeignet.

Das Papier argumentiert, dass Hellman-Tabellen (oder Varianten mit Distinguished Points) für diese spezifische Anwendung besser mit PIR-Protokollen kompatibel sind als Rainbow-Tabellen.

2.2 Privater Informationsabruf (Private Information Retrieval)

Private Information Retrieval (PIR) ermöglicht es einem Client, ein Element aus einer Datenbank abzurufen, ohne dass der Server erfährt, auf welches Element zugegriffen wurde. Für eine einzelne Datenbank, die einen n-Bit-String enthält, umfasst ein PIR-Schema:

1. Abfragegenerierung (Client)
2. Abfrageübertragung
3. Abfrageverarbeitung (Server)
4. Antwortübertragung
5. Antwortdekodierung (Client)

Die Komplexität wird gemessen als $O_C$ (Client-Verarbeitung), $O_S$ (Server-Verarbeitung) und $O_T$ (Übertragung). Eine grundlegende untere Schranke ist, dass $O_S$ mindestens $O(n)$ betragen muss, um Privatsphäre zu gewährleisten, was bedeutet, dass der Server Arbeit proportional zur Datenbankgröße leisten muss.

3. Lösungsübersicht

Die vorgeschlagene Lösung kombiniert auf clevere Weise Hellman-Tabellen (oder Distinguished-Point-Tabellen) mit einem Single-Database-PIR-Protokoll. Der Server speichert die vorberechneten Cracking-Tabellen. Wenn ein Client einen Hash knacken möchte, verwendet er eine PIR-Abfrage, um privat die notwendigen Informationen von den spezifischen Positionen in den Hellman-Tabellen abzurufen, die potenziellen Kettenübereinstimmungen entsprechen, ohne die Nachschlageindizes preiszugeben.

4. Technische Details & Algorithmus-Konstruktion

Die Konstruktion konzentriert sich auf die Anpassung von Hellman-Tabellen für PIR. Eine Hellman-Tabelle wird durch eine kryptografische Hash-Funktion $H$ und eine Reduktionsfunktion $R$ definiert. Eine Kette beginnt mit einem Klartext $SP_i$ und berechnet iterativ: $X_0 = SP_i$, $X_{j+1} = H(R(X_j))$, wobei nur $(SP_i, EP_i)$ gespeichert wird, wobei $EP_i$ der Endwert nach $t$ Schritten ist. Um einen Hash $h$ zu prüfen, berechnet der Client eine Kette der Länge $t$, beginnend mit $h$, und prüft bei jedem Schritt, ob der Zwischenwert mit einem gespeicherten Endpunkt übereinstimmt. Das PIR-Protokoll wird verwendet, um diese Endpunktvergleiche privat aus der Tabelle des Servers abzurufen.

5. PIR-Protokolle & Komplexitätsanalyse

Das Papier analysiert den Rechen- und Kommunikationsaufwand. Unter Verwendung eines standardmäßigen Computational-PIR-Protokolls (z.B. basierend auf der Annahme quadratischer Reste) skaliert die Server-Verarbeitungskosten $O_S$ mit der Tabellengröße. Die Client-Kosten $O_C$ und die Kommunikation $O_T$ sind deutlich niedriger, aber nicht trivial. Die Analyse zeigt, dass PIR zwar Overhead im Vergleich zu einer Klartextabfrage einführt, dies jedoch der notwendige Preis für starke Abfrage-Privatsphäre ist. Die Wahl von Hellman- gegenüber Rainbow-Tabellen wird hier gerechtfertigt, da Rainbow-Tabellen das Prüfen mehrerer Spalten mit unterschiedlichen Reduktionsfunktionen erfordern, was zu mehr PIR-Abfragen und höheren Gesamtkosten führt.

6. Experimentelle Ergebnisse

Ein Prototyp wurde in Python implementiert. Die Experimente demonstrierten die Machbarkeit des Ansatzes. Wichtige Metriken waren:

• Abfragezeit: Die End-to-End-Zeit für einen ahnungslosen Cracking-Versuch, unter Berücksichtigung von PIR-Berechnung und Kommunikationslatenz.
• Serverlast: Die Rechenlast auf dem Server pro Abfrage, die die theoretische $O(n)$-Schranke bestätigt.
• Erfolgsrate: Die Wahrscheinlichkeit, einen Hash bei gegebener Tabellenabdeckung erfolgreich zu knacken, die mit den Standard-Hellman-Tabellen-Erfolgswahrscheinlichkeiten übereinstimmt.

Die Ergebnisse bestätigten, dass das System funktioniert, hoben jedoch den Leistungskompromiss hervor: Privatsphäre hat den Preis erhöhter Serverberechnung pro Abfrage im Vergleich zu einem nicht-privaten Dienst.

7. Fazit & Ausblick

Das Papier demonstriert erfolgreich eine neuartige Architektur für einen ahnungslosen Passwort-Cracking-Server. Zukünftige Arbeitsrichtungen umfassen:

• Erforschung effizienterer PIR-Protokolle, um $O_S$ und $O_T$ zu reduzieren.
• Untersuchung der Verwendung von Trusted Execution Environments (TEEs) wie Intel SGX als Alternative oder Ergänzung zu kryptografischem PIR.
• Erweiterung des Modells auf verteilte oder Multi-Server-PIR-Umgebungen, um die Leistung potenziell zu verbessern.

8. Originalanalyse & Expertenkommentar

Kernaussage: Dieses Papier geht es nicht darum, Passwörter schneller zu knacken; es geht darum, sie leiser zu knacken. Die Autoren haben eine eklatante operative Lücke in der offensiven Sicherheit identifiziert: den digitalen Fußabdruck. Wenn ein Red-Teamer einen Cloud-basierten Cracking-Dienst abfragt, sind diese Abfragemetadaten ein Risiko. Diese Arbeit schlägt vor, die Absicht selbst mit PIR zu verschlüsseln und den Server "ahnungslos" zu machen. Es ist ein klassisches Beispiel für die Anwendung fortgeschrittener kryptografischer Theorie (PIR) auf ein hartes, reales Infosec-Problem. Die Bedeutung ist vergleichbar mit den Datenschutzüberlegungen bei Model-Inversion-Angriffen oder Membership-Inference-Angriffen auf Machine-Learning-APIs, bei denen die Abfrage selbst sensible Informationen preisgeben kann.

Logischer Ablauf: Das Argument ist logisch schlüssig. 1) Bedrohungsmodell definieren: ein nicht vertrauenswürdiger Drittanbieter-Server. 2) Passende kryptografische Primitive auswählen: Single-Database Computational PIR, die einzige praktikable Option für dieses Szenario mit einem einzelnen, nicht kolludierenden Server. 3) Die Cracking-Primitive anpassen: Hellman-Tabellen gegenüber Rainbow-Tabellen wählen, weil ihre Struktur weniger, deterministischere PIR-Abfragen pro Cracking-Versuch erfordert. Dies ist eine entscheidende Engineering-Entscheidung, die tiefes Domänenwissen zeigt. Der Fluss von Problem zu kryptografischem Werkzeug zu Systemintegration ist kohärent.

Stärken & Schwächen: Die größte Stärke ist die Neuartigkeit und direkte Anwendbarkeit. Der Prototyp beweist die Konzepttauglichkeit. Die Schwächen sind jedoch praktischer Natur. Der Leistungs-Overhead von PIR ist enorm. Wie die Autoren anmerken, ist die Serverarbeit $O(n)$. Für große Tabellen (Terabyte) ist dies für einen kommerziellen Dienst prohibitiv. Es ist eine Lösung, die perfekte Privatsphäre über jeden Anschein von Effizienz stellt. Darüber hinaus schützt sie nur die Abfrage. Der Server weiß immer noch, dass der Client eine Cracking-Operation durchführt, was in einigen Rechtsgebieten bereits ausreichen könnte, um Alarm auszulösen. Im Vergleich zu aufkommenden Ansätzen mit vollständiger homomorpher Verschlüsselung (FHE) ist diese PIR-basierte Methode einfacher, aber weit weniger flexibel.

Umsetzbare Erkenntnisse: Für Sicherheitspraktiker ist dies eine Blaupause für hochsichere, datenschutzbewahrende offensive Werkzeuge. Für Forscher eröffnet es eine neue Arbeitsrichtung zu effizientem, nutzbarem PIR. Der unmittelbare nächste Schritt ist ein Benchmark-Vergleich mit einem TEE-basierten Ansatz (z.B. Ausführung der Cracking-Logik in einer SGX-Enklave). Der TEE würde die Berechnung privat mit potenziell weniger Overhead als kryptografisches PIR durchführen, führt jedoch Vertrauen in den Hardware-Hersteller ein. Die langfristige Vision sollte ein Hybridmodell sein: PIR für den initialen, sensibelsten Index-Lookup verwenden und vielleicht vertrauenswürdige Hardware für nachfolgende Schritte, um Vertrauensannahmen und Leistung auszubalancieren. Diese Arbeit zeigt, ähnlich wie das grundlegende CycleGAN-Papier, das kreativ Netzwerke für ungepaarte Bildübersetzung kombinierte, wie die Kombination zweier ausgereifter Technologien (Hellman-Tabellen und PIR) eine neuartige Lösung für ein Nischen- aber wichtiges Problem schaffen kann.

9. Technische Details & Mathematische Formulierung

Der Kern einer Hellman-Kette für eine Hash-Funktion $H$ und Reduktionsfunktion $R$ ist iterativ definiert. Gegeben ein Start-Klartext $P_0$: $$X_0 = P_0$$ $$X_{k+1} = H(R(X_k)) \quad \text{für } k = 0, 1, ..., t-1$$ Der Kettenendpunkt ist $X_t$. Die Tabelle speichert Paare $(P_0, X_t)$. Um einen Hash $h$ umzukehren, berechnet man eine Testkette von $h$: $Y_0 = h$, $Y_1 = H(R(Y_0))$, ..., $Y_t = H(R(Y_{t-1}))$. Bei jedem Schritt $j$ prüft man, ob $R(Y_j)$ ein Distinguished Point ist oder ob $Y_j$ mit einem gespeicherten Endpunkt $X_t$ übereinstimmt, was eine Kettenregeneration zur Findung des Urbilds auslöst. In der PIR-adaptierten Version wird der Abgleich mit der gespeicherten Endpunktliste des Servers über eine PIR-Abfrage auf den Index durchgeführt, der $R(Y_j)$ oder $Y_j$ entspricht.

10. Analyse-Rahmen & Fallstudie

Fallstudie: Sicheres Penetration Testing as a Service (PTaaS)
Stellen Sie sich eine Cloud-basierte PTaaS-Plattform vor, die Passwort-Audits anbietet. Ein Kundenunternehmen lädt eine Liste von Passwort-Hashes aus dem eigenen System für ein Sicherheitsaudit hoch. Bei einem Standarddienst erfährt der Cloud-Anbieter, welchen spezifischen Hashes die Passwörter des Unternehmens entsprechen – ein potenzieller Datenschutzverstoß. Unter Verwendung des ahnungslosen Server-Frameworks:

1. Das Auditing-Tool des Clients verarbeitet jeden Ziel-Hash $h$ vor.
2. Für jedes $h$ berechnet es lokal die notwendigen Indizes $i_1, i_2, ... i_k$ in die Hellman-Tabellen des Anbieters.
3. Es verwendet ein PIR-Protokoll, um verschlüsselte Abfragen für diese Indizes zu generieren, und sendet sie an den PTaaS-Server.
4. Der Server verarbeitet alle Abfragen (führt Arbeit auf seiner gesamten Datenbank aus) und gibt verschlüsselte Datenblöcke zurück.
5. Der Client entschlüsselt die Antworten und verarbeitet sie lokal, um zu sehen, ob Kettenübereinstimmungen gefunden wurden, und stellt so Klartext-Passwörter wieder her.

Während dieses gesamten Prozesses sieht der PTaaS-Anbieter nur verschlüsselte, zufällig aussehende Abfragen und erfährt nichts darüber, welche Hashes der Client getestet hat, und bewahrt so die Vertraulichkeit des internen Passwortsatzes des Kunden.

11. Zukünftige Anwendungen & Richtungen

Die Prinzipien dieser Forschung gehen über Passwort-Cracking hinaus:

• Datenschutzbewahrende Threat-Intelligence-Abfragen: Abfragen von Indikatoren für Kompromittierung (IOCs) aus einer gemeinsamen Datenbank, ohne die eigenen Assets preiszugeben.
• Vertraulicher DNA-Sequenzabgleich: Ein Krankenhaus könnte eine Genomdatenbank nach Krankheitsmarkern abfragen, ohne das vollständige Genom des Patienten preiszugeben.
• Private Filterung in der Log-Analyse: Durchsuchen gemeinsamer Sicherheitslogs nach Angriffsmustern, ohne die spezifischen Muster preiszugeben, für die die eigene Organisation anfällig ist.
• Die Konvergenz mit Vollständiger Homomorpher Verschlüsselung (FHE) ist eine Schlüsselrichtung. Während PIR das Zugriffsmuster verbirgt, könnte FHE es dem Server ermöglichen, die gesamte Cracking-Berechnung auf verschlüsselten Daten durchzuführen und nur ein verschlüsseltes Ergebnis zurückzugeben. Projekte wie Microsofts SEAL und OpenFHE machen dies praktikabler.
• Die Integration mit Differential Privacy könnte eine Ebene statistischer Privatsphäre hinzufügen und sicherstellen, dass selbst der Erfolg oder Misserfolg einer Abfrage nicht zu viele Informationen preisgibt.

12. Referenzen

1. Calvo, A., Futoransky, A., & Sarraute, C. (2013). An Oblivious Password Cracking Server. arXiv preprint arXiv:1307.8186.
2. Hellman, M. (1980). A cryptanalytic time-memory trade-off. IEEE Transactions on Information Theory, 26(4), 401-406.
3. Rivest, R. L. (1982). How to reuse a "write-once" memory. (MIT Laboratory for Computer Science Technical Report).
4. Oechslin, P. (2003). Making a faster cryptanalytic time-memory trade-off. Advances in Cryptology - CRYPTO 2003 (pp. 617-630). Springer.
5. Chor, B., Goldreich, O., Kushilevitz, E., & Sudan, M. (1995). Private information retrieval. Proceedings of IEEE 36th Annual Symposium on Foundations of Computer Science (pp. 41-50). IEEE.
6. Zhu, J. Y., Park, T., Isola, P., & Efros, A. A. (2017). Unpaired image-to-image translation using cycle-consistent adversarial networks. Proceedings of the IEEE international conference on computer vision (pp. 2223-2232). (Zitiert als analoges Beispiel kreativer Technologiekombination).
7. Microsoft Research. (o.J.). Microsoft SEAL (Simple Encrypted Arithmetic Library). Abgerufen von https://www.microsoft.com/en-us/research/project/microsoft-seal/