AngriffMarkov(probabilistisch) — Umfassender Betrieb

Referenzdokument des ProjektsTime2Crack

Empfänger: Entwickler, Sicherheitswissenschaftler, Fortgeschrittene

Inhalt

1. Überblick

AngriffMarkovist ein Passwort-Cracking-Verfahren probabilistisch und statistisch die Kandidaten generiert, indem sie sich auf die beobachteten Frequenzen des Übergangs zwischen Zeichen in realen menschlichen Passwörtern verlassen. Statt alle möglichen Kombinationen in alphabetischer Reihenfolge zu testen - wie die Rohkraft tut - sortiert sie Kandidaten aus dem wahrscheinlichsten zumindest, Konzentration der Berechnungsaufwand, wo menschliche Passwörter tatsächlich liegen.

2. Historischer und akademischer Hintergrund

2.1 Ursprung

AnwendungMarkovPasswörter knacken predates formale akademische Publikationen. Offensive Sicherheitspraktizierende verwendet ähnliche Modelle aus den 2000er Jahren, aber strenge Formalisierung stammt hauptsächlich aus den 2010er Jahren.

2.2 Referenzkörper

ModellausbildungMarkovbasierend auf Passwort-Datenbanken von bekannten Datenlecks:

• RockYou (2009) : 14,3 Millionen einfache Passwörter — universelle Referenzkorpus

Diese Korpus zeigen die tatsächliche statistische Verteilung menschlicher Passwörter, die sich radikal von einer einheitlichen Verteilung unterscheidet.

3. Mathematische Grundlagen:Markov

3.1 Formelle Definition

Eine Kette vonMarkovOrdnung k.o. auf einem Alphabet k.o. Vorherige Zeichen:

P(cₙ | c₁c₂...cₙ₋₁) = P(cₙ | cₙ₋ₖ...cₙ₋₁)

Für Passwörter enthält es in der Regel 95 bedruckbare ASCII-Zeichen (26 unteres Gehäuse + 26 oberes Gehäuse + 10 Ziffern + 33 Symbole).

P("password") = P("p") × P("a"|"p") × P("s"|"a") × P("s"|"s") × ...

P("password") = P("p") × P("a"|"p") × P("s"|"pa") × P("s"|"pas")
                × P("w"|"pass") × P("o"|"passw") × P("r"|"passwo")
                × P("d"|"passwor")

Order 5 erfasst Kontexte wie "nach "passw", die wahrscheinlichste Folge ist "o" — Informationen, die für ein Auftragsmodell 1 nicht zugänglich sind.

3.2 Die Übergangsmatrix

Für eine Ordnung von 1 über 95 Zeichen ist die Übergangsmatrix Größe 95 × 95 = 9,025 Eingänge. Für Bestellung 5 geht es 955 × 95 = ~7.7 × 1010 theoretische Eingänge — aber die Mehrheit der Ordnung n-Grammen 5 erscheint nie in den tatsächlichen Daten. Implementierungen verwenden hohle Datenstrukturen (tries, hash maps), um nur beobachtete n-Grammen zu speichern.

3.3 Log-Wahrscheinlichkeit und Sortierung

Um schwimmende Overruns auf 8+-Kennwörtern zu vermeiden (Verbindlichkeiten in der Größenordnung von 10-20), arbeiten die Werkzeuge in log Wahrscheinlichkeiten :

log P("password") = log P("p") + log P("a"|"p") + log P("s"|"a") + ...

Dieser Wert ist ErgebnisMarkov Die Kandidaten werden in absteigender Reihenfolge der Partitur erzeugt, d.h. die wahrscheinlichsten zumindest wahrscheinlich.

3.4 Warum Ordnung 5?

Empirische Forschung (Dürmuth 2015, bestätigt von Ma et al. 2012) zeigt:

4. Architektur eines CrackersMarkov

4.1 Hauptkomponenten

┌─────────────────────────────────────────────────────────────┐
│                    OUTIL DE CRACKING MARKOV                 │
├─────────────────┬───────────────────┬───────────────────────┤
│  Phase          │  Composant        │  Rôle                 │
├─────────────────┼───────────────────┼───────────────────────┤
│  Entraînement   │ Corpus Parser     │ Lit les mots de passe │
│                 │ N-gram Counter    │ Compte les transitions│
│                 │ Probability Table │ Normalise en probas   │
│                 │ Model Serializer  │ Sauvegarde le modèle  │
├─────────────────┼───────────────────┼───────────────────────┤
│  Génération     │ Candidate Gen     │ Énumère par score     │
│                 │ Length Controller │ Filtre par longueur   │
│                 │ Threshold Filter  │ Coupe les improbables │
├─────────────────┼───────────────────┼───────────────────────┤
│  Attaque        │ Hash Engine       │ Compare aux cibles    │
│                 │ GPU Interface     │ Hashcat backend       │
└─────────────────┴───────────────────┴───────────────────────┘

4.2 Integration mit Hashcat

Die in der Praxis am weitesten verbreitete Umsetzung ist über Hashcat stdin mode (-a 0 mit einem externen Generator oder über Python-Module als statsgen (aus dem PACK-Toolkit):

# Exemple d'attaque Markov pratique
python statsgen.py rockyou.txt --output markovModell.stats
python maskgen.py markovmodel.stats | hashcat -a 0 -m 1000 targethashes.txt

Dedizierte Werkzeuge wie OMEN (offen)MarkovSchätzung der nächsten Passwörter) direkt erstellen Listen von sortierten Kandidaten.

5. Phase 1 — Aufbau eines echten Passworttrainings

5.1. Extraktion von n-Grammen

Für jedes Passwort im Korpus werden alle n-Grammen extrahiert (mit einem Startmarker). ^ und Ende $)

Beispiel mit "Hallo" (Bestellung 2):

^h, he, el, ll, lo, o$

Beispiel mit "P@ss1!" (Bestellung 2):

^P, P@, @s, ss, s1, 1!, !$

5.2 Zählung und Standardisierung

Für jeden Kontext (n-1 vorherige Zeichen) werden die Vorkommnisse jedes folgenden Zeichens gezählt und normalisiert:

Contexte "pa" → {s: 847, r: 12, t: 8, l: 3, ...}
→ P(s|pa) = 847/870 = 0.973
→ P(r|pa) = 12/870 = 0.014

Diese Verteilungen zeigen menschliche Sprachgewohnheiten: nach "pa", schreiben Menschen massiv "s" (Passwort, Pass, pablo...).

Glätten

Das Problem der unbeobachteten n-Grammen: wenn "xq" nie in den Korpus erscheint, P(c)xq) = 0 für jede c — die die Generation blockiert.

Das Glatteing ermöglicht es dem Modell auch, Kandidaten aus dem Trainingskorpus zu generieren – entscheidend, um leicht neue Passwörter abzudecken.

5.4 Was das Modell lernt

Nach dem Training auf RockYou, ein ModellMarkovBestellen 5 interniert Muster wie:

6. Phase 2 — Ordentliche Kandidatengeneration

6.1 Das Problem der Notenaufzählung

Kandidaten in absteigender Reihenfolge der Wahrscheinlichkeit generierenMarkovWir können nicht einfach die Wahrscheinlichkeiten aller möglichen Kandidaten (948 x 6 × 1015 für 8 Tanks) berechnen und dann aussortieren.

Die Lösung: Heuristische Suche mit Prioritätsschwanz Der Algorithmus ist ähnlich wie Dijkstra:

Dieser Ansatz sorgt für eine annähernd abnehmende Sortierung, ohne den gesamten Raum zu merken.

6.2. Schwellenschwelle

Um zu vermeiden, Milliarden von unwahrscheinlichen Kandidaten zu erzeugen, Mindestpunkt darunter wird ein Teilkandidat eliminiert (Lattung).

Si log P(candidatpartiel) < THRESHOLD → abandon de cette branche

Schwelle ist ein kritischer Parameter: zu hoch → Sie vermissen Passwörter an der Grenze; zu niedrig → Sie generieren zu viele Kandidaten und verlangsamen den Angriff.

6.3 Längenmanagement

ModelleMarkovwerden geschult und im Allgemeinen betrieben durch feste LängeEin typischer Angriff:

Längenverteilung in RockYou: 8 Tanks = 24%, 7 Tanks = 21%, 9 Tanks = 12%, 6 Tanks = 10%...

7. Reducing Research Space: Der Schlüssel zur Effektivität

7.1 Empirische Quantifizierung (Dürmuth 2015)

Für ein Passwort von 8 Zeichen mit dem vollständigen Alphabet (94 Tanks):

Der Unterschied zwischen "reduziertem Raum" und "typischer menschlicher Raum" lässt sich dadurch erklären, dass echte menschliche Passwörter in höchstwahrscheinlich Je nach Modell.

7.2 Warum Menschen vorhersehbar sind

Die vonMarkov:

7.3 Der Fall von Tastaturmustern

Keyboard-Sequenzen (qwerty, asdf, zxcv, 1234, azerty...) sind besonders gefährdet.

InTime2CrackDiese Unterscheidung ist nicht mehr eine feste Ebene.MarkovV2 umfasst kbPat als Signal in einem Rangschätzer (markovExpectedGuesses) dann kontinuierlich zwischen "menschlichen" und "randomähnlichen" Regimen interpolieren.

8. Notable Variationen und Implementierungen

8.1 OMEN (offenMarkovSchätzung der nächsten Passwörter)

OMEN verwendet eine Diskretisierung von Wahrscheinlichkeiten in Insgesamt die Erzeugung beschleunigen:

Dieser Ansatz löst elegant das Problem der ordentlichen Aufzählung ohne teure Priorität Schwanz.

8.2 OMEN+

Erweiterung von OMEN mit:

Gemeldete Leistung: +15 bis +20% gekrackte Passwörter vs original OMEN mit gleichem Budget.

8.3 Statsgen / PACK (Passwortanalyse und Cracking Kit)

8.4 John TheRipper — ModusMarkov

John TheRipper integriert ein ModusMarkovgeb. (entwickelt von Samuele Giovanni Tonon):

john --markov --min-length=6 --max-length=8 hashes.txt

Parameter --markov-threshold (0-400): steuert die Abschaltschwelle. 150 = empfohlener Standardparameter.

ModeMarkovJtR verwendet in Dateien vorkalkulierte Statistiken .mkv (markov stats files) generiert von calcstat.

ModelleMarkovHybriden

Diese Hybridisierungen werden in professionellen Cracking-Konfigurationen verwendet, um die Budgetabdeckung von CPU/GPU zu maximieren.

8.6 Moderne Sprachmodelle (LLM/LSTM) — Nachfolger vonMarkov

LSTM- und Transformer-Netzwerke sind als Verallgemeinerungen derMarkov:

PassGAN (2017), FLA (2019), PassBERT (2022) übertrifft die ModelleMarkovKlassiker von 20-30 % in Rissrate auf moderne corpus.

9. Verhalten gegen verschiedene Arten von Passwörtern

9.1 Passwörter aus natürlichen Wörtern

9.2 Wörter mit Leetspeak-Ersetzungen

9.3 Wörter mit digitalem Suffix

9.4 Vorname und richtige Namen

9.5 Passwörter der scheinbaren zufälligen Struktur, aber mnemotechnic

9.6 Tastatur Muster

9.7 wirklich zufällige Passwörter

9.8 Passphrasen

10. Integration inTime2CrackModellierung und Parameter

Allgemeine Berechnungslogik (v2)

Time2Crackjetzt ModellMarkovin erwartete Rendite (rank-basiert) anstatt mit festen Reduktionsfaktoren.

Berechnungslinie:

10.2 Unicode Tokenization and Calibrated Profile by Language

Das ModellMarkovv2 verwendet Unicode-Klassen (\p{L}, \p{N}, andernfalls Symbol) und ein kalibriertes Profil pro Sprache (belastet seit data/markov-calibration.json, mit internem Rückfall).

Das Profil enthält:

10.3. Kontinuierliche Interpolation (Ende steiler Schwellen)

Das alte Modell verwendet Lager (0.003 / 0.006 / 0.25 / 0.9). Das v2 Modell ersetzt diese Logik durch kontinuierliche Interpolation zwischen:

Zufälliges Gewicht ist eine kontinuierliche Funktion der Länge, des Tanks und der Festigkeit menschlicher Signale, wodurch künstliche Diskontinuitäten vermieden werden.

10.4 Confidence and applicability score

Das Scoring-ModellTime2Crack(Funktion) annotateScenarioApplicability()) ZuweisungenMarkov:

case "markov":
  return context.looksHuman ? 0.76 : 0.34;

case "markov":
  return Number(!!context.looksHuman) + Number(!!context.kbPat)
       + Number(!!context.seq)        + Number(!!context.rep);

10.5 Einstellen HF

mitMarkovv2 sind die Struktursignale bereits in den geschätzten Rang integriert. Die HF-Einstellung ist daher neutral fürMarkovum Doppelzählung zu vermeiden.

10.6 Priorität in der Krawatte

Wenn mehrere Angriffe ähnliche Zeiten geben (< 1ms Differenz),Time2Crackwählt die relevanteste nach semanischer Priorität aus:

const tieBreakPriority = {
  // ...
  markov: 8,    // Statistical n-gram — broad coverage
  // ...
};

Markovist ein nützlicher Komplement-Angriff, der statistische Regelmäßigkeiten ausnutzt. Es hat Vorrang vor der groben Kraft für Passwörter mit menschlicher Struktur, aber gibt Vorrang vor Wörterbuch und Hybrid-Angriffen, die direkter sind.

10.7 Ultra-weak Gehäuse

Für Ultra-Low-Passwörter (entdeckt von isWeakPassword()),MarkovZeit auf Basis eines Mindestplatzes (weakGuessTime) anstatt einer festen Konstante:

if (weak) {
  rows.push({ ..., sec: weakGuessTime(a.rate), note: t("nWeakPassword"), cat: "markov" });
}

Begründung: ein ultra-niedriges Passwort (Passwort, 123456, qwerty...) ist im Top-100 absolut von Outer SpaceMarkov— es wird zunächst geprüft, die Genauigkeit der Berechnung ist irrelevant.

11. Vergleich mit anderen probabilistischen Angriffen

1.1.1MarkovvsPCFG

11.2Markovvs Regelbasierter Angriff

ANHANGMarkovvs Neural-Netzwerke (PassGAN, LSTM)

11.4 Globale Positionierung

In einem professionellen Cracking-Workflow ist die typische Reihenfolge:

Markovoft Hintergrundlinie front brute force: es deckt effektiv menschliche Passwörter, die mehr gezielte Angriffe entkommen.

12. AngriffsbeschränkungenMarkov

12.1 Abhängigkeit vom Ausbildungskörper

Das Modell ist genauso gut wie seine Korpus. Ein Korpus dominiert von englischen Passwörtern (RockYou, LinkedIn) missversteht Regelmäßigkeiten:

12.2 Lange interpositionale Unabhängigkeit

Ein ModellMarkovBestellen 5 sieht nicht mehr als 5 Zeichen. Für ein Passwort von 12 Zeichen kann es das 12. Zeichen nicht mit dem 1. korrelieren. Eine Passphrase wie "stargate2004!" hat eine globale Struktur ("Wort + Jahr +!"), dieMarkovwird lokal wahrgenommen, aber nicht global —PCFGist hier besser.

12.3 Unempfindlichkeit gegenüber kompositorischen Strukturen

"HorseStapleBattery" (initial majusculum + 3 concatenated Wörter) ist schwierig fürMarkovweil die Zwischenwortübergänge (e→S, e→B) unerwartet sind.PCFGist besser geeignet.

12.4 Zufälliges Passwort ineffektivität

Ein Passwort, das von /dev/urandom mit 12+ alphanumerischen Zeichen hat keine Struktur ausgenutztMarkov. Die Zeit des AngriffsMarkovsich mit der brutalen Kraft auseinandersetzen.

12.5 Sensitivität zur aktualisierten Passwortrichtlinie

Hat eine Organisation strenge Regeln auferlegt (Länge ≥ 16, obligatorisches 1 Kapital + 1 Ziffer + 1 Symbol), können die resultierenden Passwörter eine andere Verteilung des Trainingskorpus haben — die Wirksamkeit des Modells zu reduzieren.

13. Wirksame Verteidigung

13.1 Was völlig neutralisiertMarkov

13.2 Dies reduziert die Wirksamkeit derMarkov

13.3 Was verteidigt nicht gegenMarkov

13.4 Schlussempfehlung

Die wirksamste Verteidigung gegenMarkov(und jeder probabilistische Angriff)jede vorhersehbare menschliche Struktur beseitigen, die die Übertragung von Passwort-Erstellung auf einen sicheren Zufallsgenerator.

14. Referenzen

Akademiker (peer-reviewed)

Open Source Implementierungen

Quellen von corpus

Webquellen, die in der Anmeldung genannt werdenTime2Crack