Atak Markova (probabilistyczny) - kompleksowa operacja

Dokument referencyjny projektu Time2Crack

Odbiorcy: deweloperzy, badacze bezpieczeństwa, zaawansowani użytkownicy

Spis treści

1. Przegląd

Markov Attack to metoda łamania haseł probabilistyczne i statystyczne Zamiast testować wszystkie możliwe kombinacje w porządku alfabetycznym - tak jak robi to surowa siła - sortuje kandydatów przynajmniej z najbardziej prawdopodobnych, koncentrując wysiłek obliczeniowy, w którym faktycznie znajdują się ludzkie hasła.

2. Tło historyczne i akademickie

2.1 Początki

Zastosowanie kanałów Markova do łamania haseł jest wcześniej niż formalne publikacje akademickie. Ofensywni specjaliści bezpieczeństwa stosowali podobne modele od 2000 roku, ale rygorystyczna formalizacja pochodzi głównie z 2010 roku.

2.2 Organ referencyjny

Szkolenie modelu Markov opiera się na bazach haseł ze znanych wycieków danych:

• RockYou (2009) : 14.3 mln prostych haseł - uniwersalny korpus odniesienia

Korpus ten ujawnia rzeczywisty statystyczny rozkład haseł ludzkich, który różni się radykalnie od jednolitego rozkładu.

3. Podstawy matematyczne: łańcuchy Markova

3.1 Definicja formalna

Łańcuch zamówień Markov k na alfabecie k Poprzednie znaki:

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

Dla haseł zazwyczaj zawiera 95 znaków ASCII (26 znaków dolnych + 26 znaków górnych + 10 cyfr + 33).

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

Zamówienie 5 rejestruje konteksty takie jak "po" passw ", najbardziej prawdopodobnym następstwem jest" o "- informacje niedostępne dla modelu zlecenia 1.

3.2 Matryca przejściowa

Dla rzędu 1 przez 95 znaków macierz przejściowa jest wielkości 95 × 95 = 9,025 wejśćDla porządku 5, to idzie do 955 × 95 = ~ 7,7 × 1010 teoretycznych wejść - ale większość zamówień n- grams 5 nigdy nie pojawia się w rzeczywistych danych. Wdrożenia używać pustych struktur danych (próby, hash maps) do przechowywania tylko obserwowane n- grams.

3.3 Prawdopodobieństwo i sortowanie dziennika

Aby uniknąć płynących przekroczeń na 8 + -znaków haseł (prawdopodobieństwa rzędu 10 − 20), narzędzia pracują w prawdopodobieństwo logowania :

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

Ta wartość jest wynik Markov Kandydaci są generowani w porządku malejącym wyniku, tj. co najmniej prawdopodobne.

3.4 Dlaczego Zamówienie 5?

Badania empiryczne (Dürmuth 2015, potwierdzone przez Ma et al. 2012) pokazują, że:

4. Architektura narzędzia tnącego Markov

4.1 Główne elementy

┌─────────────────────────────────────────────────────────────┐
│                    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 Integracja z Hashcatem

Najbardziej rozpowszechnione wdrażanie w praktyce jest poprzez Tryb Hashcat stdin (-a 0 z zewnętrznym generatorem) lub za pośrednictwem modułów Pythona jako statsgen (z zestawu narzędzi PACK):

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

Dedykowane narzędzia, takie jak OMEN (Open Markov Estimator of Next haseł) bezpośrednio generuje listy posortowanych kandydatów.

5. Faza 1 - Ciało prawdziwego szkolenia hasła

5.1. Ekstrakcja n-gramów

Dla każdego hasła w korpusie, wszystkie n-gramy są ekstrahowane (z markerem startowym). ^ i koniec $):

Przykład "hello" (kolejność 2):

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

Przykład "P @ ss1!" (kolejność 2):

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

5.2 Liczenie i normalizacja

Dla każdego kontekstu (n-1 poprzednich znaków), zdarzenia każdego następującego znaku są liczone i normalizowane:

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

Te dystrybucje ujawniają ludzkie nawyki językowe: po "pa", ludzie piszą masywnie "s" (hasło, pass, pablo...).

Wygładzanie

Problem nieużywanych n-gramów: jeśli "xq" nigdy nie pojawia się w korpusie, P (c) xq) = 0 dla każdego c - który blokuje generację.

Wygładzanie pozwala również modelowi na generowanie kandydatów z korpusu szkoleniowego - co jest kluczowe dla pokrycia nieco nowych haseł.

5.4 Co model uczy

Po treningu na RockYou model 5-rzędowy Markov internalizuje wzorce takie jak:

6. Etap 2 - Porządnie generowanie kandydatów

6.1 Problem wyliczenia punktów

Nie możemy po prostu obliczyć prawdopodobieństwa wszystkich możliwych kandydatów (948 x 6 × 1015 dla 8 czołgów), a następnie uporządkować je.

Roztwór: Heuristyczne poszukiwania z priorytetowym ogonem Algorytm jest podobny do Dijkstry:

Podejście to zapewnia w przybliżeniu malejące sortowanie bez zapamiętywania całej przestrzeni.

Progi progowe

Aby uniknąć generowania miliardów nieprawdopodobnych kandydatów, Minimalny wynik poniżej którego eliminowany jest częściowy kandydat (ukośnik).

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

Próg jest krytycznym parametrem: zbyt wysoki → można przegapić hasła na granicy; zbyt niski → można wygenerować zbyt wiele kandydatów i spowolnić atak.

6.3 Zarządzanie długością

Modele Markov są szkolone i ogólnie działają o stałej długościTypowy atak:

Rozkład długości w RockYou: 8 zbiorników = 24%, 7 zbiorników = 21%, 9 zbiorników = 12%, 6 zbiorników = 10%...

7. Zmniejszenie przestrzeni badawczej: klucz do skuteczności

7.1 Obliczenie empiryczne (Dürmuth 2015)

Hasło 8 znaków z pełnym alfabetem (94 zbiorniki):

Różnica między "zredukowaną przestrzenią" a "typową przestrzenią ludzką" może być wyjaśniona faktem, że prawdziwe ludzkie hasła są skoncentrowane w top- k% najprawdopodobniej W zależności od modelu.

7.2 Dlaczego ludzie są przewidywalni

Czynniki przewidywalności stosowane przez Markova:

7.3 Przypadek szablonów klawiatury

Sekwencje klawiatury (qwerty, asdf, zxcv, 1234, azerty...) są szczególnie narażone.

W Time2Crack (wersja bieżąca) rozróżnienie to nie jest już stałe łożysko. Model Markov v2 zawiera kbPat jako sygnał w estymatorze rankingu (markovExpectedGuesses) następnie bezustannie interpole między "ludzkimi" i "losowymi" reżimami.

8. Notowalne zmiany i implementacje

8.1 OMEN (Open Markov Estimator kolejnych haseł)

OMEN wykorzystuje dyskrecjonalizację prawdopodobieństwa w poziomy całkowite przyspieszenie generacji:

Podejście to elegancko rozwiązuje problem uporządkowanego wyliczania bez kosztownego priorytetowego ogona.

8.2 OMEN +

Rozszerzenie OMEN o:

Zgłoszone wyniki: + 15 do + 20% pęknięte hasła vs oryginalne OMEN z równym budżetem.

8.3 Statsgen / PACK (analiza haseł i zestaw do łamania)

8.4 JohnTheRipper - tryb Markov

John TheRipper integruje Tryb rodzimy Markov (opracowany przez Samuele Giovanni Tonon):

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

Parametr --markov-threshold (0- 400): kontroluje próg odcięcia. 150 = zalecany parametr standardowy.

Tryb JtR Markov wykorzystuje wstępnie obliczone statystyki przechowywane w plikach .mkv (pliki statystyk markov) generowane przez calcstat.

8.5 Modele hybrydowe Markov

Te hybrydyzacje są wykorzystywane w profesjonalnych konfiguracjach krakingu do maksymalizacji pokrycia budżetu CPU / GPU.

8.6 Nowoczesne modele językowe (LLM / LSTM) - następcy Markova

Sieci LSTM i Transformer można postrzegać jako uogólnienia kanałów Markov:

PassGAN (2017), FLA (2019), PassBERT (2022) przekroczył klasyczne modele Markov o 20- 30% w skali crack na nowoczesnych ciałach.

9. Zachowanie przed różnymi rodzajami haseł

9.1 Hasła z słów naturalnych

9.2 Słowa z podstawieniem leetspeak

9.3 Słowa z przyrostkiem cyfrowym

9.4 Nazwy i nazwy właściwe

9.5 Przemijające słowa o pozornej strukturze losowej, ale mnemoternic

9.6 Wzory klawiatury

9.7 Naprawdę przypadkowe hasła

9.8 Passphrases

10. Integracja z Time2Crack: Modelowanie i Parametry

Ogólna logika obliczeń (v2)

Time2Crack teraz modele Markov w spodziewany stopień (oparte na rankach), a nie na stałych współczynnikach redukcji.

Linia obliczeniowa:

10.2 Unicode Tokenizacja i kalibrowany profil według języka

Model Markov v2 wykorzystuje klasy Unicode (\p{L}, \p{N}, inaczej symbol) i skalibrowany profil na język (załadowany od data/markov-calibration.json, z wewnętrznymi zapasami).

Profil zawiera:

10.3. Interpolacja ciągła (koniec stromych progów)

Stary model zastosował łożyska (0.003 / 0.006 / 0.25 / 0.9). Model v2 zastępuje tę logikę ciągłą interpolacją pomiędzy:

Losowa waga jest ciągłą funkcją długości, czołgu i wytrzymałości sygnałów ludzkich, unikając w ten sposób sztucznych przerw.

10.4 Ocena zaufania i możliwości zastosowania

Time2Crack Scoring Model (funkcja annotateScenarioApplicability()) przydziela Markovowi:

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

Z Markov v2, sygnały strukturalne są już zintegrowane z szacowaną rangą. Dostosowanie HF jest zatem neutralne dla Markov w celu uniknięcia podwójnego liczenia.

10.6 Priorytet w przerwie

Gdy kilka ataków daje podobne czasy (< 1ms różnicy), Time2Crack wybiera najbardziej istotne zgodnie z semantycznym priorytetem:

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

Markov jest użytecznym atakiem uzupełniającym, który wykorzystuje statystyczną regularność. Ma pierwszeństwo przed siłą brutto dla haseł z ludzką strukturą, ale daje pierwszeństwo słownikowi i atakom hybrydowym, które są bardziej bezpośrednie.

10. 7 Przypadek osłabienia ultradźwięków

Dla ultraniskich haseł (wykryte przez isWeakPassword()), Markov wykorzystuje czas oparty na minimalnej randze (weakGuessTime) raczej niż stała stała:

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

Uzasadnienie: ultraniskie hasło (hasło, 123456, qwerty...) znajduje się w absolut Przestrzeń Markov - będzie najpierw testowany, dokładność obliczeń jest nieistotna.

11. Porównanie z innymi atakami probabilistycznymi

11. 1 Markov vs PCFG

11.2 Markov vs.

11.3 Markov vs Neural Networks (PassGAN, LSTM)

11.4 Globalne pozycjonowanie

W profesjonalnym procesie krakingu typowa kolejność to:

Markov jest często linia tła front brute force: skutecznie obejmuje ludzkie hasła, które uniknęły bardziej ukierunkowanych ataków.

12. Granice ataku Markova

12.1 Zależność od struktury kształcenia

Model jest tak dobry jak jego korpus. Korpus zdominowany przez angielskie hasła (RockYou, LinkedIn) źle rozumie regularność:

12.2 Niezależność międzypozycyjna od długości pasma

Model Markov 5 widzi nie więcej niż 5 znaków. Dla hasła 12 znaków, nie może korelować 12 znaków z 1. Passphrase jak "stargate2004!" ma globalną strukturę ("słowo + rok +!"), że Markov postrzega lokalnie, ale nie globalnie - PCFG jest tu lepiej.

12.3 Niewrażliwość na struktury składu

"HorseStapleBattery" (initial majusculum + 3 concatenated words) jest trudne dla Markova, ponieważ między-słowo przejścia (e → S, e → B) są nieoczekiwane.

12.4 Przypadkowa nieskuteczność hasła

Hasło wygenerowane przez /dev/urandom z 12 + alfanumerycznych znaków nie ma struktury exploitable przez Markov. Czas ataku Markov zbiega się do surowej siły.

12.5 Wrażliwość na uaktualnioną politykę dotyczącą hasła

Jeżeli organizacja nałożyła ścisłe zasady (długość ≥ 16, obowiązkowy 1 kapitał + 1 cyfra + 1 symbol), wynikające z nich hasła mogą mieć inny podział korpusu szkoleniowego - zmniejszając skuteczność modelu.

13. Skuteczna obrona

13.1 Co całkowicie neutralizuje Markova

13.2 Co znacznie zmniejsza skuteczność leku Markov

13.3 Co nie chroni przed Markovem?

13.4 Zalecenie końcowe

Najskuteczniejszą obroną przed Markovem (i każdym atakiem probabilistycznym) jestwyeliminować wszelkie przewidywalne struktury ludzkieCo oznacza przekazanie hasła do bezpiecznego generatora losowego.

14. Odniesienia

Akademika (peer-review)

Wdrażanie otwartego źródła

Źródła ciałka

Źródła internetowe cytowane w aplikacji Time2Crack