Ataque de Markov (probabilístico) — Operación integral

Documento de referencia del proyecto Time2Crack

Recipientes: desarrolladores, investigadores de seguridad, usuarios avanzados

Índice

1. Sinopsis

Markov Attack es un método de craqueo de contraseña probabilística y estadística que genera candidatos con base en las frecuencias observadas de transición entre caracteres en contraseñas humanas reales. En lugar de probar todas las combinaciones posibles en orden alfabético —como lo hace la fuerza cruda— clasifica a candidatos de los más probables al menos, concentrando el esfuerzo de cálculo donde se encuentran las contraseñas humanas.

2. Antecedentes históricos y académicos

2.1 Origen

La aplicación de los canales de Markov a la grieta de contraseñas es anterior a las publicaciones académicas formales. Los profesionales de seguridad ofensivos utilizaron modelos similares desde los años 2000, pero la formalización rigurosa data principalmente de los años 2010.

2.2 Cuerpo de referencia

La formación del modelo Markov se basa en bases de datos de contraseña de las filtraciones de datos conocidas:

• RockYou (2009) : 14.3 millones de contraseñas simples - corpus de referencia universal

Este corpus revela la distribución estadística real de contraseñas humanas, que difiere radicalmente de una distribución uniforme.

3. Fundaciones Matemáticas: Cadenas de Markov

3.1 Definición formal

Markov cadena de orden k sobre un alfabeto k Anteriores caracteres:

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

Para contraseñas, generalmente incluye 95 caracteres ASCII imprimibles (26 mayúsculas + 26 mayú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")

Orden 5 captura contextos como "después de "pasar", el seguimiento más probable es "o" — información inaccesible a un modelo de orden 1.

3.2 La matriz de transición

Para un orden de 1 sobre 95 caracteres, la matriz de transición es tamaño 95 × 95 = 9.025 entradas. Para la Orden 5, va a 955 × 95 = ~7.7 × 1010 insumos teóricos — pero la mayoría del orden n-gramas 5 nunca aparecen en los datos reales. Las implementaciones utilizan estructuras de datos huecos (tries, mapas de hash) para almacenar sólo n-gramas observados.

3.3 Probabilidad y clasificación de registros

Para evitar sobrecostos flotantes en contraseñas de 8+ caracteres (probabilidades del orden de 10-20), las herramientas funcionan en Log probabilities :

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

Este valor es el puntuación Markov Los candidatos se generan en orden descendente de puntuación, es decir, lo más probable al menos.

3.4 ¿Por qué la Orden 5?

La investigación empírica (Dürmuth 2015, confirmada por Ma et al. 2012) muestra que:

4. Arquitectura de un cracktool Markov

4.1 Componentes principales

┌─────────────────────────────────────────────────────────────┐
│                    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 Integración con Hashcat

La aplicación más generalizada en la práctica es a través de la Modo Stdin Hashcat (G)-a 0 con un generador externo) o a través de módulos Python como statsgen (del kit de herramientas PACK):

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

Herramientas dedicadas como OMEN (Open Markov Estimator of Next passwords) genera directamente listas de candidatos ordenados.

5. Fase 1 - Cuerpo de formación de contraseña real

5.1. Extracción de n-gramos

Para cada contraseña en el cuerpo, todos los n-gramos se extraen (con un marcador de inicio). ^ y fin $)

Ejemplo con "hola" (orden 2):

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

Ejemplo con "P@ss1!" (orden 2):

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

5.2 Contabilidad y estandarización

Para cada contexto (n-1 caracteres anteriores), las ocurrencias de cada personaje siguiente se cuentan y se normalizan:

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

Estas distribuciones revelan hábitos de lenguaje humano: después de "pa", la gente escribe masivamente "s" (password, pass, pablo...).

Momento

El problema de los n-gramas no observados: si "xq" nunca aparece en el corpus, P(c)xq) = 0 para cualquier c — que bloquea la generación. Las técnicas de lijado más utilizadas:

Smoothing también permite que el modelo genere candidatos fuera del cuerpo de formación — crucial para cubrir contraseñas ligeramente nuevas.

5.4 Lo que el modelo aprende

Después de entrenar en RockYou, un modelo Markov de 5 órdenes interioriza patrones como:

6. Fase 2 - Generación ordenada de candidatos

6.1 El problema de la enumeración de la puntuación

Generar candidatos en orden descendente de probabilidad Markov es un problema no-trivial. No podemos simplemente calcular las probabilidades de todos los candidatos posibles (948 x 6 × 1015 para 8 tanques) y luego ordenarlos.

La solución: Búsqueda heurística con cola prioritaria El algoritmo es similar a Dijkstra:

Este enfoque garantiza una clasificación aproximadamente decreciente sin memorizar todo el espacio.

6.2. umbral del umbral

Para evitar generar miles de millones de candidatos improbables, Puntuación mínima debajo del cual se elimina un candidato parcial (esclavamiento).

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

Threshold es un parámetro crítico: demasiado alto → se pierde contraseñas en el límite; demasiado bajo → se generan demasiados candidatos y ralentizar el ataque.

Gestión de la longitud

Los modelos Markov están entrenados y generalmente funcionan por longitud fijaUn ataque típico:

Distribución de longitud en RockYou: 8 tanques = 24%, 7 tanques = 21%, 9 tanques = 12%, 6 tanques = 10%...

7. Reducing Research Space: The Key to Effectiveness

7.1 Cuantificación empírica (Dürmuth 2015)

Para una contraseña de 8 caracteres con el alfabeto completo (94 tanques):

La diferencia entre "espacio reducido" y "espacio humano típico" se explica por el hecho de que las contraseñas humanas reales se concentran en lo más probable Según el modelo.

7.2 Por qué los humanos son predecibles

Los factores de previsibilidad utilizados por Markov:

7.3 El caso de los patrones de teclado

Las secuencias de teclado (qwerty, asdf, zxcv, 1234, azerty...) son particularmente vulnerables.

En Time2Crack (versión actual), esta distinción ya no es un rodamiento fijo. kbPat como señal en un estimador de rango (markovExpectedGuesses) entonces interponer continuamente entre regímenes "humanos" y "como el aleatorio".

8. Variaciones e implementaciones notables

8.1 OMEN (Open Markov Estimator of Next passwords)

OMEN utiliza una discretización de probabilidades niveles completos para acelerar la generación:

Este enfoque resuelve elegantemente el problema de la enumeración ordenada sin una cola de prioridad costosa.

8.2 OMEN+

Extension of OMEN with:

Rendimiento informado: +15 a +20% contraseñas cracked vs original OMEN con presupuesto igual.

8.3 Statsgen / PACK (Password Analysis and Cracking Kit)

8.4 JohnTheRipper — Modo Markov

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

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

Parámetro --markov-threshold (0-400): controla el umbral de corte. 150 = parámetro estándar recomendado.

El modo JtR Markov utiliza estadísticas precalculadas almacenadas en archivos .mkv (archivos de estadísticas de Markov) generados por calcstat.

8.5 Modelos híbridos Markov

Estas hibridaciones se utilizan en configuraciones profesionales de cracking para maximizar la cobertura presupuestaria de CPU/GPU.

8.6 Modelos de lenguaje moderno (LLM/LSTM) — sucesores de Markov

Las redes LSTM y Transformer se pueden ver como generalizaciones de los canales Markov:

PassGAN (2017), FLA (2019), PassBERT (2022) superó los modelos clásicos de Markov en un 20-30% en las tasas de crack en el corpus moderno.

9. Comportamiento contra diferentes tipos de contraseñas

9.1 Contraseñas de palabras naturales

9.2 Palabras con sustituciones de palanca

9.3 Palabras con sufijo digital

9.4 Nombres y nombres adecuados

9.5 Paso palabras de aparente estructura aleatoria pero mnemotécnica

9.6 Pautas de teclado

9.7 Contraseñas aleatorias de verdad

9.8 Frases

10. Integración en Time2Crack: Modelado y Parámetros

Lógica general del cálculo (v2)

Time2Crack ahora modelos Markov en rango previsto (basado en barra) en lugar de con factores de reducción fijos.

Línea de cálculo:

10.2 Unicode Tokenization and Calibrated Profile by Language

El modelo Markov v2 utiliza clases de Unicode (\p{L}, \p{N}, de otro modo símbolo) y un perfil calibrado por idioma (cargado desde entonces data/markov-calibration.json, con retroceso interno).

El perfil contiene:

10.3 Interpolación continua (fin de umbrales empinados)

El modelo antiguo utiliza rodamientos (0.003 / 0.006 / 0.25 / 0.9). El modelo v2 reemplaza esta lógica con interpolación continua entre:

El peso aleatorio es una función continua de la longitud, el tanque y la fuerza de las señales humanas, evitando así las discontinuidades artificiales.

10.4 Puntaje de confianza y aplicabilidad

Time2Crack Scoring Model (función annotateScenarioApplicability()) asigna 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 Ajuste HF

Con Markov v2, las señales estructurales ya están integradas en el rango estimado. Por lo tanto, el ajuste HF es neutral para Markov con el fin de evitar la doble contabilización.

10.6 Prioridad en el corte de corbatas

Cuando múltiples ataques dan tiempos similares (asignados 1ms de diferencia), Time2Crack elige lo más relevante según una prioridad semántica:

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

Markov es un útil ataque complementario que explota las regularidades estadísticas. Tiene precedencia sobre la fuerza bruta para las contraseñas con estructura humana, pero da precedencia al diccionario y los ataques híbridos que son más directos.

Caso 10.7 Ultra-weak

Para contraseñas ultra-bajo (detectadas por isWeakPassword()), Markov utiliza un tiempo basado en un rango mínimo (weakGuessTime) en lugar de una constante fija:

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

Razonamiento: una contraseña ultra-bajo (password, 123456, qwerty...) está en el top-100 absoluto Espacio Markov — se probará primero, la exactitud del cálculo es irrelevante.

11. Comparación con otros ataques probabilísticos

11.1 Markov vs PCFG

11.2 Markov vs. Rule-Based Attack

11.3 Markov vs Neural Networks (PassGAN, LSTM)

11.4 Posición mundial

En un flujo de trabajo profesional, el orden típico es:

Markov es a menudo el línea de antecedentes fuerza bruta frontal: cubre efectivamente las contraseñas humanas que han escapado a ataques más dirigidos.

12. Límites del ataque de Markov

12.1 Dependencia del cuerpo de capacitación

El modelo es tan bueno como su corpus. Un corpus dominado por contraseñas inglesas (RockYou, LinkedIn) malinterpreta las regularidades:

12.2 Independencia interposicional de largo alcance

Un modelo Markov 5 no ve más de 5 caracteres. Para una contraseña de 12 caracteres, no puede correlacionar el 12o carácter con el 1o. Un passphrase como "stargate2004!" tiene una estructura global ("palabra + año +!") que Markov percibe localmente pero no globalmente — PCFG es mejor aquí.

12.3 Insensibilidad a las estructuras de composición

"HorseStapleBattery" (majusculo inicial + 3 palabras concatenadas) es difícil para Markov porque las transiciones entre palabras (e→S, e→B) son inesperadas.El ataque combinador o PCFG es mejor adecuado.

12.4 Ineficacia de la contraseña aleatoria

Una contraseña generada /dev/urandom con 12 caracteres alfanuméricos no tiene estructura explotable por Markov. El tiempo de ataque Markov converge a la fuerza cruda.

12.5 Sensibilidad de actualizar la política de contraseña

Si una organización ha impuesto reglas estrictas (duración ≥ 16, símbolo obligatorio 1 capital + 1 dígito + 1), las contraseñas resultantes pueden tener una distribución diferente del cuerpo de entrenamiento, reduciendo la eficacia del modelo.

13. Defensas eficaces

13.1 Lo que neutraliza completamente a Markov

13.2 Lo que reduce considerablemente la eficacia de Markov

13.3 Lo que no defiende contra Markov

13.4 Recomendación final

La defensa más efectiva contra Markov (y cualquier ataque probabilístico) eseliminar cualquier estructura humana previsible, lo que equivale a delegar la creación de contraseña a un generador aleatorio seguro.

14. Referencias

Académicos (revisados por los espectadores)

Implementaciones de código abierto

Fuentes del corpus

Fuentes web citadas en la aplicación Time2Crack