Markov-aanval (probabilistisch)

Projectreferentiedocument Time2Crack

Ontvangers: ontwikkelaars, security onderzoekers, geavanceerde gebruikers

Inhoud

1. Overzicht

Markov Attack is een wachtwoord kraken methode probabilistisch en statistisch die kandidaten genereert door te vertrouwen op de waargenomen frequenties van overgang tussen tekens in echte menselijke wachtwoorden. In plaats van het testen van alle mogelijke combinaties in alfabetische volgorde en zoals de ruwe kracht doet . . het sorteert kandidaten van de meest waarschijnlijke tenminste, concentreren van de berekening inspanning waar menselijke wachtwoorden daadwerkelijk zijn gevestigd.

2. Historische en academische achtergrond

2.1 Oorsprong

De toepassing van Markov's kanalen op wachtwoord kraken is eerder dan formele academische publicaties. Offensive security beoefenaars gebruikt soortgelijke modellen sinds de jaren 2000, maar strenge formalisering dateert voornamelijk uit de 2010s.

2.2 Referentieorgaan

Modeltraining Markov is gebaseerd op wachtwoorddatabases van bekende datalekken:

• RockYou (2009) : 14,3 miljoen gewone wachtwoorden, universele referentie corpus

Deze corpus onthullen de feitelijke statistische verdeling van menselijke wachtwoorden, die radicaal verschilt van een uniforme verdeling.

3. Wiskundige stichtingen: de kettingen van Markov

3.1 Formele definitie

Markov-volgordeketen k op een alfabet k Vorige tekens:

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

Voor wachtwoorden omvat het meestal 95 afdrukbare ASCII-tekens (26 kleine letters + 26 hoofdletters + 10 cijfers + 33 symbolen).

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 vangt contexten zoals "na "passw," de meest waarschijnlijke follow-up is "o" informatie ontoegankelijk voor een ordermodel 1.

3.2 De overgangsmatrix

Voor een orde van 1 op 95 karakters is de overgangsmatrix grootte 95 × 95 = 9,025 inputs. Voor Orde 5 gaat het naar 955 × 95 = ~7,7 × 1010 theoretische inputs Implementaties gebruiken holle datastructuren (tries, hash maps) om alleen waargenomen n-grams op te slaan.

3.3 Log waarschijnlijkheid en sorteren

Om drijvende overschrijdingen op 8+-karakter wachtwoorden (waarschijnlijkheden van de orde van 10−20) te voorkomen, werken de gereedschappen in log waarschijnlijkheden :

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

Deze waarde is de score Markov Kandidaten worden gegenereerd in afnemende volgorde van score, d.w.z. de meest waarschijnlijke ten minste waarschijnlijk.

3.4 Waarom Bestel 5?

Uit empirisch onderzoek (Dürmuth 2015, bevestigd door Ma et al. 2012) blijkt dat:

4. Architectuur van een Markov cracktool

4.1 Belangrijkste onderdelen

┌─────────────────────────────────────────────────────────────┐
│                    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 Integratie met Hashcat

De meest voorkomende uitvoering in de praktijk is via de Hashcat-stdinmodus (-a 0 met een externe generator) of via Python-modules als statsgen (van de PACK toolkit):

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

Specifieke hulpmiddelen zoals VROUWEN (Open Markov Estimator van Next wachtwoorden) direct genereren lijsten van gesorteerde kandidaten.

5. Fase 1

5.1. Extractie van n-grams

Voor elk wachtwoord in het corpus worden alle n-grams uitgepakt (met een startmarkering). ^ en eindigen $) :

Voorbeeld met "hallo" (orde 2):

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

Voorbeeld met "P@ss1!" (orde 2:

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

5.2 Telling en normalisatie

Voor elke context (n-1 vorige tekens) worden de gebeurtenissen van elk volgende teken geteld en genormaliseerd:

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

Deze verdelingen onthullen menselijke taalgewoonten: na "pa" schrijven mensen massaal "s" (wachtwoord, pass, pablo...).

Gladmaken

Het probleem van ongeobserveerde n-grams: als "xq" nooit verschijnt in het corpus, P(c)xq) = 0 voor elke c

Smoothing maakt het model ook mogelijk om kandidaten uit de training te genereren .. cruciaal om iets nieuwe wachtwoorden te dekken.

5.4 Wat het model leert

Na training op RockYou, een Markov 5-orde model internaliseert patronen als:

6. Fase 2

6.1 Het probleem van de opsomming van scores

Het genereren van kandidaten in dalende volgorde van waarschijnlijkheid Markov is een niet-triviaal probleem. We kunnen niet gewoon de waarschijnlijkheid van alle mogelijke kandidaten (948 x 6 × 1015 voor 8 tanks) berekenen en ze vervolgens uitzoeken.

De oplossing: Heuristische zoektocht met prioriteit staart Het algoritme lijkt op Dijkstra:

Deze aanpak zorgt voor een ongeveer afnemende sortering zonder de hele ruimte te onthouden.

6.2. Drempeldrempel

Om te voorkomen dat miljarden onwaarschijnlijke kandidaten, een Minimumscore waaronder een gedeeltelijke kandidaat wordt uitgeschakeld (sladen).

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

Drempelwaarde is een kritische parameter: te hoog → je mist wachtwoorden aan de limiet; te laag → je genereert te veel kandidaten en vertraagt de aanval.

6.3 Duurbeheer

Markov modellen zijn opgeleid en werken over het algemeen door vaste lengteEen typische aanval:

Lengteverdeling in RockYou: 8 tanks = 24%, 7 tanks = 21%, 9 tanks = 12%, 6 tanks = 10%...

7. Het verminderen van onderzoeksruimte: de sleutel tot effectiviteit

7.1 Empirische kwantificering (Dürmuth 2015)

Voor een wachtwoord van 8 tekens met het volledige alfabet (94 tanks):

Het verschil tussen "gereduceerde ruimte" en "typische menselijke ruimte" kan worden verklaard door het feit dat echte menselijke wachtwoorden geconcentreerd zijn in top-k% waarschijnlijk Afhankelijk van het model.

7.2 Waarom mensen voorspelbaar zijn

De door Markov gebruikte voorspelbaarheidsfactoren:

7.3 Het geval van toetsenbordpatronen

Toetsenbordsequenties (qwerty, asdf, zxcv, 1234, azerty...) zijn bijzonder kwetsbaar.

In Time2Crack (huidige versie) is dit onderscheid niet langer een vaste lager. kbPat als signaal in een rangschatting (markovExpectedGuesses) vervolgens voortdurend interpoleren tussen "mens-achtige" en "random-achtige" regimes.

8. Opmerkelijke variaties en implementaties

8.1 VROUWEN (Open Markov Estimator van Volgende wachtwoorden)

VROUWEN maken gebruik van een discretie van waarschijnlijkheden in hele niveaus om de generatie te versnellen:

Deze aanpak lost het probleem van een ordelijke opsomming zonder dure prioritaire staart elegant op.

8.2 VROUWEN+

Uitbreiding van vrouwen met:

Gerapporteerde prestaties: +15 tot +20% gebarsten wachtwoorden vs originele VROUWEN met gelijk budget.

8.3 Statsgen / PACK (Wachtwoordanalyse en kraken Kit)

8,4 JohnTheRipper Markov-modus

John TheRipper integreert een native Markov-modus (ontwikkeld door Samuel Giovanni Tonon):

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

Parameter --markov-threshold (0-400): regelt de afkapdrempel. 150 = aanbevolen standaardparameter.

JtR Markov-modus maakt gebruik van vooraf berekende statistieken opgeslagen in bestanden .mkv (markov statistieken bestanden) gegenereerd door calcstat.

8.5 Markov hybride modellen

Deze hybridisaties worden gebruikt in professionele kraakconfiguraties om CPU/GPU budget dekking te maximaliseren.

8.6 Moderne taalmodellen (LLM/L URL)

LSTM en Transformer netwerken kunnen worden gezien als generalisaties van Markov kanalen:

PassGAN (2017), FLA (2019), PassBERT (2022) overtrof de klassieke Markov modellen met 20-30% in cracksnelheden op het moderne corpus.

9. Gedrag tegen verschillende soorten wachtwoorden

9.1 Wachtwoorden uit natuurlijke woorden

9.2 Woorden met leetspeak substituties

9.3 Woorden met digitaal achtervoegsel

9.4 Voornamen en juiste namen

9.5 Pass woorden van schijnbare willekeurige structuur maar mnemotechnische

9.6 Toetsenbordpatronen

9.7 Echt willekeurige wachtwoorden

9,8 Wachtwoordzinnen

10. Integratie in Time2Crack: Modellering en Parameters

Algemene berekeningslogica (v2)

Time2Crack nu modellen Markov in verwachte rang (rank-based) in plaats van met vaste reductiefactoren.

Berekeningslijn:

10.2 Unicode Tokenization en gekalibreerd profiel per taal

Het Markov v2 model maakt gebruik van Unicode klassen (\p{L}, \p{N}, anderszins symbool) en een gekalibreerd profiel per taal (geladen sinds data/markov-calibration.json, met interne terugval).

Het profiel bevat:

10.3. Continue interpolatie (eind van steile drempels)

Het oude model gebruikte lagers (0,03 / 0,006 / 0,25 / 0,9). Het v2 model vervangt deze logica door continue interpolatie tussen:

Willekeurig gewicht is een continue functie van de lengte, tank en sterkte van menselijke signalen, waardoor kunstmatige onderbrekingen worden vermeden.

10.4 Vertrouwen en toepasbaarheid score

Time2Crack Scoring Model (functie annotateScenarioApplicability()) wordt toegewezen aan Markov:

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 HF aanpassing

Bij Markov v2 zijn de structurele signalen al geïntegreerd in de geschatte rang. De HF-aanpassing is daarom neutraal voor Markov om dubbeltelling te voorkomen.

10.6 Prioriteit in de tiebreak

Wanneer meerdere aanvallen vergelijkbare tijden (< 1ms van verschil) geven, Time2Crack kiest de meest relevante volgens een semantische prioriteit:

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

Markov is een nuttige aanvulling aanval die gebruik maakt van statistische regulariteiten. Het heeft voorrang op bruto kracht voor wachtwoorden met menselijke structuur, maar geeft voorrang aan woordenboek en hybride aanvallen die meer direct zijn.

10.7 Ultra zwakke zaak

Voor ultra-lage wachtwoorden (gedetecteerd door isWeakPassword()), gebruikt Markov een tijd gebaseerd op een minimum rang (weakGuessTime) in plaats van een vaste constante:

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

Reden: een ultra-laag wachtwoord (wachtwoord, 123456, qwerty...) is in de top-100 absoluut Markov ruimte

11. Vergelijking met andere probabilistische aanvallen

11,1 Markov vs PCFG

11.2 Markov vs. Regelgebonden aanval

11.3 Markov vs Neural Networks (PassGAN, LSTM)

11.4 Algemene positionering

In een professionele kraken workflow is de typische volgorde:

Markov is vaak de achtergrondregel front brute kracht: het dekt effectief menselijke wachtwoorden die ontsnapt zijn aan meer gerichte aanvallen.

12. Grenzen van de Markov aanval

12.1 Afhankelijkheid van de opleiding

Het model is zo goed als zijn corpus. Een corpus gedomineerd door Engelse wachtwoorden (RockYou, LinkedIn) begrijpt de regelmaat verkeerd:

12.2 Langeafstandsonafhankelijkheid

Een Markov 5 model ziet niet meer dan 5 tekens. Voor een wachtwoord van 12 tekens, kan het niet correleren het 12e karakter met de 1e. Een wachtwoordzin zoals "stargate2004!" heeft een globale structuur ("woord + jaar +!") die Markov ziet lokaal, maar niet wereldwijd is PCFG beter hier.

12.3 Ongevoeligheid voor samenstellingsstructuren

"HorseStapleBatttery" (eerste majusculum + 3 samengevoegde woorden) is moeilijk voor Markov omdat inter-woord overgangen (e→S, e→B) zijn onverwacht. De combinator aanval of PCFG is beter geschikt.

12.4 Willekeurig wachtwoord ineffectiviteit

Een wachtwoord gegenereerd door /dev/urandom met 12+ alfanumerieke tekens heeft geen structuur die Markov kan exploiteren. De aanvalstijd Markov convergeert naar de ruwe kracht.

12.5 Gevoeligheid voor bijgewerkt wachtwoordbeleid

Als een organisatie strenge regels heeft opgelegd (lengte ≥ 16, verplicht 1 kapitaal + 1 cijfer + 1 symbool), kunnen de resulterende wachtwoorden een andere verdeling van de opleiding hebben . .

13. Doeltreffende verdediging

13.1 Wat Markov volledig neutraliseert

13.2 Wat de effectiviteit van Markov sterk vermindert

13.3 Wat niet verdedigt tegen Markov

13.4 Slotaanbeveling

De meest effectieve verdediging tegen Markov (en elke probabilistische aanval) is omelke te verwachten menselijke structuur elimineren, wat neerkomt op het delegeren van wachtwoorden aan een veilige willekeurige generator.

14.

Academici (peer-reviewed)

Open source implementaties

Bronnen van corpus

Webbronnen geciteerd in de Time2Crack-toepassing