Markov attacco (probabilistico) — Operazione completa

Documento di riferimento del progetto Time2Crack

Recipienti: sviluppatori, ricercatori di sicurezza, utenti avanzati

Contenuto

1. Panoramica

Markov Attack è un metodo di cracking password probabilità e statistica Invece di testare tutte le combinazioni possibili in ordine alfabetico — come fa la forza grezza — ordina i candidati dal più probabile almeno, concentrando lo sforzo di calcolo in cui le password umane sono effettivamente situati.

2. Sfondo storico e accademico

2.1 Origini

L'applicazione dei canali di Markov al cracking password è prima delle pubblicazioni accademiche formali. I professionisti della sicurezza offensivi hanno usato modelli simili dal 2000, ma la formalizzazione rigorosa risale principalmente al 2010.

2.2 Ente di riferimento

La formazione del modello Markov si basa su database di password da perdite di dati note:

• RockYou (2009) : 14,3 milioni di password semplici — corpo di riferimento universale

Questi corpus rivelano l'effettiva distribuzione statistica delle password umane, che differisce radicalmente da una distribuzione uniforme.

3. Fondazioni matematiche: Catena di Markov

3.1 Definizione formale

Markov catena di ordine # su un alfabeto # Personaggi precedenti:

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

Per le password, di solito include 95 caratteri ASCII stampabili (26 caso inferiore + 26 caso superiore + 10 cifre + 33 simboli).

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")

Ordine 5 cattura contesti come "dopo "passw", il follow-up più probabile è "o" — informazioni inaccessibili a un modello di ordine 1.

3.2 La matrice di transizione

Per un ordine di 1 su 95 caratteri, la matrice di transizione è dimensione 95 × 95 = 9,025 ingressi. Per ordine 5, va a 955 × 95 = ~7.7 × 1010 input teorici — ma la maggior parte dell'ordine n-grams 5 non appare mai nei dati reali.

3.3 probabilità di log e selezione

Per evitare sovraccarichi galleggianti su 8+-carattere password (probabilità dell'ordine di 10−20), gli strumenti funzionano probabilità di log :

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

Questo valore è punteggio Markov I candidati sono generati in ordine descrescente di punteggio, cioè il più probabile almeno probabile.

3.4 Perché ordinare 5?

La ricerca empirica (Dürmuth 2015, confermata da Ma et al. 2012) mostra che:

4. Architettura di un cracktool di Markov

4.1 Componenti principali

┌─────────────────────────────────────────────────────────────┐
│                    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 Integrazione con Hashcat

L'attuazione più diffusa in pratica è tramite Modalità Hashcat stdin (-a 0 con un generatore esterno) o tramite moduli Python come statsgen (dal toolkit PACK):

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

Strumenti dedicati come OM (Apri Markov Estimator di Next password) genera direttamente liste di candidati ordinati.

5. Fase 1 — Corpo di formazione vera password

5.1. Estrazione di n-grammi

Per ogni password nel corpus, tutti i n-grammi vengono estratti (con un marcatore di avvio). ^ e la fine $)

Esempio con "ciao" (ordine 2):

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

Esempio con "P@ss1!" (ordine 2):

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

5.2 Contabilità e standardizzazione

Per ogni contesto (n-1 caratteri precedenti), vengono conteggiati e normalizzati gli eventi di ciascun personaggio seguente:

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

Queste distribuzioni rivelano le abitudini del linguaggio umano: dopo "pa", la gente scrive massicciamente "s" (password, pass, pablo...).

Smoothing

Il problema dei n-grammi non osservati: se "xq" non appare mai nel corpus, P(c)xq) = 0 per qualsiasi c — che blocca la generazione.

Smoothing permette anche al modello di generare candidati fuori dal corpo di formazione — cruciale per coprire le password leggermente nuove.

5.4 Cosa impara il modello

Dopo l'allenamento su RockYou, un modello di 5 ordini Markov interiorizza modelli come:

6. Fase 2 — Generazione ordinata dei candidati

6.1 Il problema dell'enumerazione del punteggio

Generando candidati in ordine decrescente di probabilità Markov è un problema non banale. Non possiamo semplicemente calcolare le probabilità di tutti i candidati possibili (948 x 6 × 1015 per 8 serbatoi) e poi ordinare fuori.

La soluzione: Ricerca euristica con coda prioritaria L'algoritmo è simile a Dijkstra:

Questo approccio garantisce una selezione approssimativamente decrescente senza memorizzare l'intero spazio.

6.2. Soglia di soglia

Per evitare di generare miliardi di candidati improbabili, un Punteggio minimo sotto il quale viene eliminato un candidato parziale (sladding).

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

Threshold è un parametro critico: troppo alto → si perde password al limite; troppo basso → si genera troppi candidati e rallentare l'attacco.

6.3 Gestione della lunghezza

I modelli Markov sono formati e generalmente funzionano per lunghezza fissaUn attacco tipico:

Distribuzione di lunghezza in RockYou: 8 serbatoi = 24%, 7 serbatoi = 21%, 9 serbatoi = 12%, 6 serbatoi = 10%...

7. Ridurre lo spazio di ricerca: La chiave per l'efficacia

7.1 Quantificazione empirica (Dürmuth 2015)

Per una password di 8 caratteri con l'alfabeto completo (94 serbatoi):

La differenza tra "spazio ridotto" e "spazio umano fisico" può essere spiegata dal fatto che le password umane reali sono concentrate in top-k% molto probabilmente A seconda del modello.

7.2 Perché gli esseri umani sono prevedibili

I fattori di prevedibilità utilizzati da Markov:

7.3 Il caso dei modelli di tastiera

Le sequenze di tastiera (qwerty, asdf, zxcv, 1234, azerty...) sono particolarmente vulnerabili.

In Time2Crack (versione corrente), questa distinzione non è più un cuscinetto fisso. kbPat come segnale in un estimatore di rango (markovExpectedGuesses) poi interpolare continuamente tra regimi "umano-come" e "a forma di casualità".

8. Notevoli variazioni e implementazioni

8.1 OMEN (Aperto Markov Estimatore delle prossime password)

OMEN utilizza una discretizzazione delle probabilità in livelli interi per accelerare la generazione:

Questo approccio risolve elegantemente il problema dell'enumerazione ordinata senza coda di priorità costosa.

8.2 OMEN+

Estensione di OMEN con:

Prestazioni segnalate: +15 - +20% password screpolate vs OMEN originale con pari budget.

8.3 Statsgen / PACK (Password Analysis and Cracking Kit)

8.4 JohnTheRipper — Modalità Markov

John TheRipper integra un modalità nativo Markov (sviluppato da Samuele Giovanni Tonon):

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

Parametro --markov-threshold (0-400): controlla la soglia di taglio. 150 = parametro standard raccomandato.

La modalità JtR Markov utilizza statistiche precalcolate memorizzate nei file .mkv (file di statistiche di Markov) generato da calcStare.

8.5 Modelli ibridi Markov

Queste ibridazioni sono utilizzate nelle configurazioni professionali di cracking per massimizzare la copertura di budget CPU/GPU.

8.6 Modelli linguistici moderni (LLM/LSTM) — successori di Markov

Le reti LSTM e Transformer possono essere viste come generalizzazioni dei canali Markov:

PassGAN (2017), FLA (2019), PassBERT (2022) ha superato i classici modelli Markov del 20-30% in tassi di crepa sul corpus moderno.

9. Comportamento contro diversi tipi di password

9.1 Password da parole naturali

9.2 Parole con leetspeak sostituzioni

9.3 Parole con suffisso digitale

9.4 Nomi e nomi appropriati

9.5 Passare parole di apparente struttura casuale ma mnemotechnic

9.6 Modelli di tastiera

9.7 password davvero casuali

9.8 Passphras

10. Integrazione in Time2Crack: Modellazione e parametri

logica generale del calcolo (v2)

Time2Crack ora modelli Markov in atteso rango (basato in franchigia) piuttosto che con fattori di riduzione fissi.

Linea di calcolo:

10.2 Tokenizzazione Unicode e profilo calibrato per lingua

Il modello Markov v2 utilizza le classi Unicode (\p{L}♪ \p{N}, altrimenti simbolo) e un profilo calibrato per lingua (caricato da data/markov-calibration.json, con ricaduta interna).

Il profilo contiene:

10.3. Interpolazione continua (fine delle soglie ripide)

Il vecchio modello utilizzato cuscinetti (0.003 / 0.006 / 0.25 / 0.9). Il modello v2 sostituisce questa logica con interpolazione continua tra:

Il peso casuale è una funzione continua della lunghezza, del serbatoio e della forza dei segnali umani, evitando così le discontinuità artificiali.

10.4 Punteggio di fiducia e applicabilità

Time2Crack modello di punteggio (funzione annotateScenarioApplicability()) assegna a 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 Regolazione HF

Con Markov v2, i segnali strutturali sono già integrati nel rango stimato. La regolazione HF è quindi neutrale per Markov al fine di evitare doppio conteggio.

10.6 Priorità al tiebreak

Quando più attacchi danno tempi simili (± 1ms di differenza), Time2Crack sceglie il più rilevante secondo una priorità semantica:

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

Markov è un utile attacco di complemento che sfrutta le regolarità statistiche. Ha la precedenza sulla forza lorda per le password con la struttura umana, ma dà la precedenza a attacchi dizionario e ibridi che sono più diretti.

10.7 Ultra-weak caso

Per le password ultra-basse (detected by isWeakPassword()), Markov utilizza un tempo basato su un grado minimo (weakGuessTime) piuttosto che una costante fissa:

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

Ragione: una password ultra-bassa (password, 123456, qwerty...) è nella top-100 assoluto Markov spazio — sarà testato prima, l'accuratezza del calcolo è irrilevante.

11. Confronto con altri attacchi probabilistici

11.1 Markov vs PCFG

11.2 Markov vs. Attacco basato sulla regola

11.3 Markov vs Neural Networks (PassGAN, LSTM)

11.4 Posizionamento globale

In un flusso di lavoro professionale di cracking, l'ordine tipico è:

Markov è spesso sfondo linea forza bruta anteriore: copre efficacemente le password umane che sono sfuggiti più attacchi mirati.

12. Limiti dell'attacco di Markov

12.1 Dipendenza dal corpo della formazione

Un corpus dominato dalle password inglesi (RockYou, LinkedIn) interpreta le regolarità:

12.2 indipendenza interposizionale a lungo raggio

Un modello Markov 5 non vede più di 5 caratteri. Per una password di 12 caratteri, non può correlare il 12 ° carattere con il 1 °. Un passphrase come "stargate2004!" ha una struttura globale ("parola + anno +!") che Markov percepisce localmente ma non globalmente — PCFG è migliore qui.

12.3 Insensibilità alle strutture compositive

"HorseStapleBattery" (majusculum iniziale + 3 parole concatenate) è difficile per Markov perché transizioni inter-parole (e→S, e→B) sono inaspettate. L'attacco combinatore o PCFG è più adatto.

12.4 Inefficacia della password casuale

Una password generata da /dev/urandom con 12+ caratteri alfanumerici non ha struttura sfruttabile da Markov. Il tempo di attacco Markov converge alla forza cruda.

12.5 Sensibilità alla politica di password aggiornata

Se un'organizzazione ha imposto regole severe (lunghezza ≥ 16, obbligatoria 1 capitale + 1 cifra + 1 simbolo), le password risultanti possono avere una distribuzione diversa del corpo di formazione — riducendo l'efficacia del modello.

13. Efficace difesa

13.1 Ciò che neutralizza completamente Markov

13.2 Che riduce notevolmente l'efficacia di Markov

13.3 Che cosa non difende contro Markov

13.4 Raccomandazione finale

La difesa più efficace contro Markov (e qualsiasi attacco probabile) è quella dieliminare qualsiasi struttura umana prevedibile, che equivale a delegare la creazione di password a un generatore casuale sicuro.

14. Riferimenti

Academics (peer-reviewed)

Esecuzioni open source

Fonti di corpus

Fonti web citate nell'applicazione Time2Crack