Ataque de Markov (probabilístico) — Operação global

Documento de referência do projeto Time2Crack

Destinatários: desenvolvedores, pesquisadores de segurança, usuários avançados

Índice

Resumo

Markov Attack é um método de quebra de senha probabilística e estatística Em vez de testar todas as combinações possíveis em ordem alfabética — como faz a força bruta — classifica os candidatos dos mais prováveis, concentrando o esforço de cálculo onde as senhas humanas estão realmente localizadas.

2. Antecedentes históricos e acadêmicos

2.1 Origens

A aplicação dos canais de Markov para quebra de senhas é anterior às publicações acadêmicas formais. Profissionais de segurança ofensivos usaram modelos semelhantes desde os anos 2000, mas datam de formalização rigorosa principalmente a partir dos anos 2010.

2.2 Organismo de referência

O treinamento do modelo de Markov é baseado em bases de dados de senha de vazamentos de dados conhecidos:

• RockYou (2009) 14,3 milhões de senhas simples — corpus universal de referência

Esses corpus revelam a distribuição estatística real das senhas humanas, que difere radicalmente de uma distribuição uniforme.

3. Fundações Matemáticas: Correntes de Markov

3.1 Definição formal

Cadeia de ordem Markov k num alfabeto k Caracteres anteriores:

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

Para senhas, geralmente inclui 95 caracteres ASCII imprimíveis (26 minúsculas + 26 maiúsculas + 10 dígitos + 33 símbolos).

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

A ordem 5 captura contextos como "após "passw", o seguimento mais provável é "o" — informação inacessível a um modelo de ordem 1.

3.2 A matriz de transição

Para uma ordem de 1 sobre 95 caracteres, a matriz de transição é tamanho 95 × 95 = 9,025 entradasPara a Ordem 5, vai para 955 × 95 = ~7.7 × 1010 inputs teóricos — mas a maioria dos n-gramas de ordem 5 nunca aparece nos dados reais.

3.3 Probabilidade de log e ordenação

Para evitar sobreposições flutuantes em senhas de 8 caracteres (probabilidades da ordem de 10-20), as ferramentas funcionam em probabilidades de log :

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

Este valor é o pontuação Markov Os candidatos são gerados em ordem decrescente de pontuação, ou seja, o mais provável, pelo menos.

3.4 Por que a Ordem 5?

Pesquisa empírica (Dürmuth 2015, confirmada por Ma et al. 2012) mostra que:

4. Arquitetura de um cracktool de Markov

4.1 Principais componentes

┌─────────────────────────────────────────────────────────────┐
│                    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 Integração com Hashcat

A implementação mais generalizada na prática é através da Hashcat stdin mode (-a 0 com um gerador externo) ou através de módulos Python como statsgen (do kit de ferramentas 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

Ferramentas dedicadas como OMEN (Open Markov Estimator of Next passwords) gera diretamente listas de candidatos ordenados.

5. Fase 1 — Corpo de treino de senha real

5.1. Extração de n-gramas

Para cada senha no corpus, todos os n-gramas são extraídos (com um marcador inicial). ^ e fim $) :

Exemplo com "olá" (ordem 2):

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

Exemplo com "P@ss1!" (ordem 2):

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

5.2 Contagem e normalização

Para cada contexto (n-1 caracteres anteriores), as ocorrências de cada caractere a seguir são contadas e normalizadas:

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

Essas distribuições revelam hábitos de linguagem humana: depois de "pa", as pessoas escrevem maciçamente "s" (senha, passe, pablo...).

Suavização

O problema de n-gramas não observados: se "xq" nunca aparece no corpus, P(c)xq) = 0 para qualquer c — que bloqueia a geração. As técnicas de suavização mais utilizadas:

A suavização também permite que o modelo gere candidatos fora do corpus de treinamento — crucial para cobrir senhas ligeiramente novas.

5.4 O que o modelo aprende

Depois de treinar no RockYou, um modelo de 5-ordem Markov internaliza padrões como:

6. Fase 2 — Geração ordenada de candidatos

6.1 O problema da enumeração da pontuação

Gerando candidatos em ordem decrescente de probabilidade Markov é um problema não trivial. Nós não podemos simplesmente calcular as probabilidades de todos os candidatos possíveis (948 x 6 × 1015 para 8 tanques) e, em seguida, ordená-los.

A solução: Busca heurística com cauda prioritária O algoritmo é semelhante ao Dijkstra:

Esta abordagem garante uma classificação aproximadamente decrescente sem memorizar todo o espaço.

6.2. Limiar

Para evitar gerar bilhões de candidatos improváveis, a Pontuação mínima abaixo do qual um candidato parcial é eliminado (slading).

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

Limiar é um parâmetro crítico: muito alto → você perde senhas no limite; muito baixo → você gera muitos candidatos e retarda o ataque.

6. 3 Gestão do comprimento

Os modelos Markov são treinados e geralmente operam por comprimento fixoUm ataque típico:

Distribuição de comprimento em RockYou: 8 tanques = 24%, 7 tanques = 21%, 9 tanques = 12%, 6 tanques = 10%...

7. Redução do espaço de pesquisa: a chave para a eficácia

7.1 Quantificação empírica (Dürmuth 2015)

Para uma senha de 8 caracteres com o alfabeto completo (94 tanques):

A diferença entre "espaço reduzido" e "espaço humano típico" pode ser explicada pelo fato de que as senhas humanas reais estão concentradas em topo- k% mais provável Dependendo do modelo.

7.2 Por que os humanos são previsíveis

Os factores de previsibilidade utilizados por Markov:

7.3 O caso dos padrões de teclado

As sequências de teclado (qwerty, asdf, zxcv, 1234, azerty...) são particularmente vulneráveis.

No Time2Crack (versão atual), esta distinção não é mais um rolamento fixo. kbPat como sinal num estimador de classificação (markovExpectedGuesses) então interpolo continuamente entre regimes "humanos" e "leandom-like".

8. Variações e implementações notáveis

8.1 OMEN (Estimador de Markov Aberto das Próximas Senhas)

A OMEN utiliza uma discretização das probabilidades em níveis inteiros acelerar a geração:

Esta abordagem elegantemente resolve o problema da enumeração ordenada sem cauda de prioridade cara.

8.2 OMEN+

Extensão do OMEN com:

Desempenho relatado: +15 a +20% senhas rachadas vs original OMEN com orçamento igual.

8.3 Statsgen / PACK (Análise de Senha e Kit de Cracking)

8.4 JohnTheRipper — Modo Markov

John TheRipper integra modo Markov nativo (desenvolvido por Samuele Giovanni Tonon):

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

Parâmetro --markov-threshold (0-400): controla o limiar de corte. 150 = parâmetro padrão recomendado.

O modo JtR Markov usa estatísticas pré- calculadas armazenadas em arquivos .mkv (arquivos de estatísticas de marcov) gerados por calcstat.

8.5 Modelos híbridos de Markov

Essas hibridizações são usadas em configurações de cracking profissional para maximizar a cobertura de orçamento da CPU/GPU.

8.6 Modelos de linguagem modernos (LLM/LSTM) — sucessores de Markov

As redes LSTM e Transformer podem ser vistas como generalizações de canais Markov:

PassGAN (2017), FLA (2019), PassBERT (2022) superou os modelos clássicos de Markov em 20-30% nas taxas de crack no corpus moderno.

9. Comportamento contra diferentes tipos de senhas

9.1 Senhas de palavras naturais

9.2 Palavras com substituições de leetspeak

9.3 Palavras com sufixo digital

9.4 Nomes e nomes próprios

9.5 Passe palavras de estrutura aleatória aparente mas mnemotechnic

9.6 Padrões de teclado

9.7 Senhas Realmente Aleatórias

9. 8 Frases- senhas

10. Integração em Time2Crack: Modelação e Parâmetros

Lógica geral de cálculo (v2)

Time2Crack agora modelos Markov em classificação esperada (rank-based) em vez de com fatores de redução fixos.

Linha de cálculo:

10.2 Tokenization Unicode e perfil calibrado por idioma

O modelo Markov v2 usa classes Unicode (\p{L}, \p{N}, de outra forma símbolo) e um perfil calibrado por idioma (carregado desde data/markov-calibration.json, com retrocesso interno).

O perfil contém:

10.3. Interpolação contínua (fim dos limiares íngremes)

O modelo antigo usou rolamentos (0.003 / 0,006 / 0.25/ 0.9). O modelo v2 substitui esta lógica por interpolação contínua entre:

O peso aleatório é uma função contínua do comprimento, tanque e força dos sinais humanos, evitando descontinuidades artificiais.

10.4 Pontuação de confiança e aplicabilidade

Modelo de Pontuação Time2Crack (função annotateScenarioApplicability()) atribuições 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 HF de ajustamento

Com Markov v2, os sinais estruturais já estão integrados na classificação estimada. O ajuste HF é, portanto, neutro para Markov, a fim de evitar a dupla contagem.

10.6 Prioridade no empate

Quando vários ataques dão tempos semelhantes (< 1ms de diferença), o Time2Crack escolhe o mais relevante de acordo com uma prioridade semântica:

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

Markov é um ataque de complemento útil que explora regularidades estatísticas. Ele tem precedência sobre a força bruta para senhas com estrutura humana, mas dá precedência a ataques de dicionário e híbridos que são mais diretos.

10.7 Caso ultrafraco

Para senhas ultra- baixas (detectado por isWeakPassword()), Markov usa um tempo baseado em uma classificação mínima (weakGuessTime) em vez de uma constante fixa:

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

Raciocínio: uma senha ultra-low (senha, 123456, qwerty...) está no absoluto superior- 100 Espaço de Markov — será testado primeiro, a precisão do cálculo é irrelevante.

11. Comparação com outros ataques probabilísticos

11, 1 Markov vs PCFG

11.2 Markov vs. Ataque baseado em regras

11. 3 Markov vs Redes Neurais (PassGAN, LSTM)

11.4 Posicionamento global

Em um fluxo de trabalho de cracking profissional, a ordem típica é:

Markov é frequentemente o linha de fundo força bruta frontal: efetivamente cobre senhas humanas que escaparam de ataques mais direcionados.

12. Limites do Ataque de Markov

12.1 Dependência do corpo de formação

O modelo é tão bom quanto seu corpus. Um corpus dominado por senhas inglesas (RockYou, LinkedIn) não entende as regularidades:

12.2 Independência interposicional de longo alcance

Um modelo Markov 5 não vê mais de 5 caracteres. Para uma senha de 12 caracteres, não pode correlacionar o 12o caracter com o 1o. Uma frase-passe como "stargate2004!" tem uma estrutura global ("palavra + ano +!") que Markov percebe localmente, mas não globalmente — PCFG é melhor aqui.

12.3 Insensibilidade às estruturas composicionais

"HorseStapleBattery" (majusculum inicial + 3 palavras concatenadas) é difícil para Markov porque transições inter-palavras (e→S, e→B) são inesperadas. O ataque combinador ou PCFG é mais adequado.

12. 4 Ineficácia da senha aleatória

Uma senha gerada por /dev/urandom com mais de 12 caracteres alfanuméricos não tem estrutura explorável por Markov. O tempo de ataque Markov converge para a força bruta.

12.5 Sensibilidade à política de senhas atualizada

Se uma organização impôs regras rigorosas (comprimento ≥ 16, obrigatório 1 capital + 1 dígito + 1 símbolo), as senhas resultantes podem ter uma distribuição diferente do corpus de formação — reduzindo a eficácia do modelo.

13. Defesas eficazes

13.1 O que neutraliza completamente Markov

13.2 O que reduz consideravelmente a eficácia de Markov

13.3 O que não defende contra Markov

13.4 Recomendação final

A defesa mais eficaz contra Markov (e qualquer ataque probabilístico) éeliminar qualquer estrutura humana previsível, que equivale a delegar a criação de senha para um gerador aleatório seguro.

14. Referências

Acadêmicos (avaliados pelos pares)

Implementação de código aberto

Fontes de corpus

Fontes da Web citadas no aplicativo Time2Crack