SOPG: Suchbasierte geordnete Passwortgenerierung für autoregressive neuronale Netze

Inhaltsverzeichnis

1. Einleitung

Passwörter bleiben die am weitesten verbreitete Methode zur Benutzerauthentifizierung. Folglich ist das Erraten von Passwörtern eine kritische Komponente der Cybersicherheitsforschung, die sowohl offensive Sicherheitstests (Cracking) als auch defensive Stärkebewertungen untermauert. Traditionelle Methoden, von regelbasierter Enumeration bis hin zu statistischen Modellen wie Markov-Ketten und PCFG, weisen inhärente Grenzen in Effizienz und Diversität auf. Das Aufkommen von Deep Learning, insbesondere autoregressiver neuronaler Netze, versprach einen Paradigmenwechsel. Ein kritischer Engpass blieb jedoch bestehen: die Standardmethode der zufälligen Stichprobenziehung bei der Generierung. Dies führt zu doppelten Passwörtern und, noch schädlicher, zu einer zufälligen Generierungsreihenfolge, die Angreifer zwingt, umfangreiche, ineffiziente Listen zu durchsuchen. Dieses Papier stellt SOPG (Search-Based Ordered Password Generation) vor, eine neuartige Methode, die darauf ausgelegt ist, autoregressive Passwort-Erratungsmodelle dazu zu bringen, Passwörter in annähernd absteigender Wahrscheinlichkeitsreihenfolge zu generieren und dadurch die Angriffseffizienz dramatisch zu steigern.

2. Hintergrund & Verwandte Arbeiten

2.1 Evolution der Passwort-Erratung

Die Passwort-Erratung hat sich in verschiedenen Phasen entwickelt. Frühe Methoden stützten sich auf Wörterbuchangriffe und manuell erstellte Mangling-Regeln (z.B. John the Ripper), die heuristisch und erfahrungsabhängig waren. Die Verbreitung von großangelegten Passwortlecks (z.B. RockYou im Jahr 2009) ermöglichte datengesteuerte, statistische Ansätze. Das Markov-Modell (Weir et al., 2009) und die Probabilistische Kontextfreie Grammatik (PCFG) (Ma et al., 2014) boten einen systematischeren, wahrscheinlichkeitsbasierten Rahmen für die Generierung, obwohl sie Gefahr liefen, zu überanpassen, und nicht in der Lage waren, komplexe, langreichweitige Abhängigkeiten in Passwortstrukturen zu modellieren.

2.2 Ansätze mit neuronalen Netzen

Deep-Learning-Modelle, insbesondere Generative Adversarial Networks (GANs) wie PassGAN (Hitaj et al., 2017) und autoregressive Modelle wie solche, die auf LSTM- oder GPT-Architekturen basieren, lernen die Wahrscheinlichkeitsverteilung von Passwörtern direkt aus Daten. Sie können hochgradig vielfältige und realistische Passwörter generieren. Typischerweise verwenden sie jedoch zufällige Stichprobenziehung (z.B. multinomiale Stichprobenziehung) aus der gelernten Verteilung bei jedem Generierungsschritt. Dieser grundlegende Prozess ist unabhängig vom globalen Ranking vollständiger Passwortwahrscheinlichkeiten, was zu den Ineffizienzen führt, die SOPG zu lösen versucht.

3. Die SOPG-Methode

3.1 Kernkonzept

SOPG formuliert die Passwortgenerierung von einem stochastischen Stichprobenproblem zu einem gelenkten Suchproblem um. Anstatt zufällig das nächste Zeichen auszuwählen, setzt es einen Suchalgorithmus (wahrscheinlich eine Variante der Beam Search oder der Best-First-Search) ein, um den Raum möglicher Passwortfortsetzungen zu erkunden, wobei Pfade priorisiert werden, die zu vollständigen Passwörtern mit höherer geschätzter Wahrscheinlichkeit führen. Das Ziel ist, die Passwortliste in einer Reihenfolge auszugeben, die einer echten absteigenden Sortierung nach $P(Passwort|Modell)$ nahekommt.

3.2 Suchalgorithmus

Während das PDF-Abstrakt den spezifischen Algorithmus nicht detailliert, deutet das beschriebene Verhalten auf eine Methode hin, die eine Prioritätswarteschlange von Kandidaten-Passwortpräfixen verwaltet. In jedem Schritt erweitert es das vielversprechendste Präfix (höchste kumulative Wahrscheinlichkeit), indem es das neuronale Netz für die Verteilung des nächsten Zeichens abfragt und neue Kandidaten generiert. Durch systematische Erkundung der Hochwahrscheinlichkeitsregionen des Passwortraums zuerst stellt es sicher, dass die wahrscheinlichsten Passwörter früh generiert werden, und vermeidet von Natur aus Duplikate.

3.3 SOPGesGPT-Modell

Die Autoren implementieren ihre Methode auf einer GPT-basierten Architektur und schaffen SOPGesGPT. Das GPT-Modell (z.B. ein reiner Decoder-Transformer) wird auf geleakten Passwortdatensätzen trainiert, um das nächste Zeichen in einer Sequenz vorherzusagen. SOPG wird dann als Generierungs-/Inferenzmethode auf diesem trainierten Modell angewendet und ersetzt die Standard-Stichprobenziehung.

4. Technische Details & Mathematische Formulierung

Ein autoregressives Modell definiert die Wahrscheinlichkeit eines Passworts $\mathbf{x} = (x_1, x_2, ..., x_T)$ als das Produkt der bedingten Wahrscheinlichkeiten: $$P(\mathbf{x}) = \prod_{t=1}^{T} P(x_t | x_1, ..., x_{t-1})$$ wobei $x_t$ das Zeichen an Position $t$ ist und $T$ die Passwortlänge. Standard-Stichprobenziehung wählt $x_t \sim P(\cdot | x_1, ..., x_{t-1})$.

SOPG zielt konzeptionell darauf ab, Sequenzen $\mathbf{x}$ in der Reihenfolge abnehmender $P(\mathbf{x})$ zu finden und auszugeben. Dies kann als ein Kürzester-Pfad-Suchproblem in einem Baum betrachtet werden, wobei Knoten Präfixe sind, Kantenkosten mit $-\log P(x_t | prefix)$ zusammenhängen und das Ziel darin besteht, Pfade (Passwörter) in der Reihenfolge steigender Gesamtkosten (d.h. abnehmender Wahrscheinlichkeit) aufzuzählen. Algorithmen wie Uniform Cost Search (UCS) oder seine beschränkte Variante, Beam Search mit großer Strahlbreite und dynamischem Pruning, können diese annähernde Ordnung erreichen. Der Schlüssel ist, dass die Suchfrontier durch die Wahrscheinlichkeitsbewertung des aktuellen Pfads priorisiert wird.

5. Experimentelle Ergebnisse & Analyse

5.1 Vergleich mit zufälliger Stichprobenziehung

Das Papier präsentiert überzeugende Ergebnisse, die SOPG mit der Standard-Stichprobenziehung auf demselben zugrundeliegenden Modell vergleichen. Wichtige Erkenntnisse:

• Keine Duplikate: SOPG generiert eine eindeutige Liste, während die zufällige Stichprobenziehung viele Wiederholungen produziert und Rechenaufwand verschwendet.
• Überlegene Angriffseffizienz: Um die gleiche Abdeckungsrate (Prozentsatz der in einem Testset geknackten Passwörter) zu erreichen, benötigt SOPG deutlich weniger Modellinferenzen und generiert eine viel kleinere Gesamtliste. Dies führt direkt zu schnellerem Passwort-Cracking in realen Szenarien.

5.2 Vergleich mit dem Stand der Technik

SOPGesGPT wurde gegen wichtige Passwort-Erratungsmodelle verglichen: OMEN (Markov), FLA, PassGAN (GAN), VAEPass (VAE) und das zeitgenössische PassGPT. In einem One-Site-Test:

• Abdeckungsrate: SOPGesGPT erreichte 35,06% und übertraf OMEN um 254%, FLA um 298%, PassGAN um 421%, VAEPass um 380% und PassGPT um 81%.
• Effektive Rate: Das Papier beansprucht auch die Führung in der "effektiven Rate", wahrscheinlich eine Metrik, die sich auf die Qualität oder Trefferquote früh generierter Passwörter bezieht, was SOPGs primäre Stärke ist.

Dies zeigt, dass die Generierungsmethode (SOPG) für die Leistung ebenso kritisch ist wie die Modellarchitektur.

6. Analyse-Rahmenwerk & Fallbeispiel

Rahmenwerk zur Bewertung von Passwort-Erratungsmodellen:

1. Modellarchitektur & Training: Was ist das zugrundeliegende neuronale Netz (GAN, VAE, Autoregressiver Transformer)? Wie wird es trainiert?
2. Generierungsmethode: Wie werden Passwörter aus dem trainierten Modell erzeugt? (z.B. Zufällige Stichprobenziehung, Beam Search, SOPG). Dies ist der Schwerpunkt des Papiers.
3. Ordnung & Effizienz: Erzeugt die Methode Passwörter in einer nützlichen Reihenfolge (absteigende Wahrscheinlichkeit)? Wie ist die Rechen-/Rater-Effizienz?
4. Diversität & Duplikation: Generiert sie neue Passwörter oder viele Duplikate?
5. Benchmark-Leistung: Abdeckungsrate, Effektive Rate und Geschwindigkeit auf Standarddatensätzen (z.B. RockYou).

Fallbeispiel ohne Code: Betrachten Sie zwei Angreifer, Alice und Bob, die dasselbe trainierte GPT-Passwortmodell verwenden. Alice verwendet die Standard-Stichprobenziehung. Bob verwendet SOPG. Um einen Testdatensatz von 1000 Passwörtern zu knacken, müsste Alices Software vielleicht 10 Millionen Rategenerieren, mit 30% Duplikaten, um 350 zu knacken. Bobs SOPG-gesteuerte Software müsste vielleicht nur 1 Million eindeutige Raten in optimaler Reihenfolge generieren, um die gleichen 350 zu knacken. Bobs Angriff ist 10x ressourceneffizienter und wird schneller abgeschlossen.

7. Anwendungsausblick & Zukünftige Richtungen

Unmittelbare Anwendungen:

• Proaktives Testen der Passwortstärke: Sicherheitsteams können SOPG-verbesserte Modelle verwenden, um vorgeschlagene Passwortrichtlinien effizienter zu auditieren, indem sie zuerst die wahrscheinlichsten Angriffsvektoren generieren.
• Forensische Passwortwiederherstellung: Rechtmäßige Passwortwiederherstellungstools können SOPG integrieren, um die Erfolgsquote innerhalb begrenzter Zeit-/Rechenbudgets zu erhöhen.

Zukünftige Forschungsrichtungen:

• Hybridmodelle: Kombination der geordneten Generierung von SOPG mit den Stärken anderer Architekturen (z.B. Integration semantischen Wissens aus großen Sprachmodellen).
• Adaptives/Online-SOPG: Modifikation der Suchstrategie in Echtzeit basierend auf Feedback von Teilergebnissen eines Angriffs.
• Defensive Gegenmaßnahmen: Forschung zu neuen Passwort-Hashing- oder Speichertechniken, die speziell resistent gegen geordnete, wahrscheinlichkeitsgesteuerte Angriffe wie SOPG sind.
• Jenseits von Passwörtern: Anwendung des geordneten Generierungsparadigmas auf andere Sicherheitsdomänen wie die Generierung wahrscheinlicher Phishing-URLs oder Malware-Varianten.

8. Referenzen

1. Weir, M., Aggarwal, S., Medeiros, B., & Glodek, B. (2009). Password Cracking Using Probabilistic Context-Free Grammars. In IEEE Symposium on Security and Privacy.
2. Ma, J., Yang, W., Luo, M., & Li, N. (2014). A Study of Probabilistic Password Models. In IEEE Symposium on Security and Privacy.
3. Hitaj, B., Gasti, P., Ateniese, G., & Perez-Cruz, F. (2017). PassGAN: A Deep Learning Approach for Password Guessing. In International Conference on Applied Cryptography and Network Security.
4. Goodfellow, I., et al. (2014). Generative Adversarial Nets. Advances in Neural Information Processing Systems.
5. Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., & Sutskever, I. (2019). Language Models are Unsupervised Multitask Learners. OpenAI Blog.
6. Melicher, W., et al. (2016). Fast, Lean, and Accurate: Modeling Password Guessability Using Neural Networks. In USENIX Security Symposium.

9. Originalanalyse & Expertenkommentar