L'attaque Markov (probabiliste) — Fonctionnement exhaustif

Document de référence pour le projet Time2Crack

Destinataires : développeurs, chercheurs en sécurité, utilisateurs avancés

Table des matières

1. Vue d'ensemble

L'attaque Markov est une méthode de cracking de mots de passe probabiliste et statistique qui génère des candidats en s'appuyant sur les fréquences observées de transition entre caractères dans des mots de passe humains réels. Au lieu de tester toutes les combinaisons possibles dans l'ordre alphabétique — comme le fait la force brute —, elle trie les candidats du plus probable au moins probable, concentrant l'effort de calcul là où les mots de passe humains se trouvent réellement.

2. Contexte historique et académique

2.1 Origines

L'application des chaînes de Markov au cracking de mots de passe est antérieure aux publications académiques formelles. Les praticiens de la sécurité offensive utilisaient des modèles similaires dès les années 2000, mais la formalisation rigoureuse date principalement des années 2010.

2.2 Corpus de référence

L'entraînement des modèles Markov repose sur des bases de données de mots de passe issus de fuites de données connues :

• RockYou (2009) : 14,3 millions de mots de passe en clair — corpus de référence universel

Ces corpus révèlent la distribution statistique réelle des mots de passe humains, qui diffère radicalement d'une distribution uniforme.

3. Fondements mathématiques : les chaînes de Markov

3.1 Définition formelle

Une chaîne de Markov d'ordre k sur un alphabet Σ modélise la probabilité de chaque caractère en fonction des k caractères précédents :

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

Pour les mots de passe, Σ comprend généralement les 95 caractères ASCII imprimables (26 minuscules + 26 majuscules + 10 chiffres + 33 symboles).

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

L'ordre 5 capture des contextes comme « après "passw", la suite la plus probable est "o" » — information inaccessible à un modèle d'ordre 1.

3.2 La matrice de transition

Pour un ordre 1 sur 95 caractères, la matrice de transition est de taille 95 × 95 = 9 025 entrées. Pour l'ordre 5, elle passe à 95⁵ × 95 = ~7,7 × 10¹⁰ entrées théoriques — mais la majorité des n-grammes d'ordre 5 n'apparaissent jamais dans les données réelles. Les implémentations utilisent des structures de données creuses (tries, hash maps) pour ne stocker que les n-grammes observés.

3.3 Probabilité logarithmique et tri

Pour éviter les sous-débordements flottants sur des mots de passe de 8+ caractères (probabilités de l'ordre de 10⁻²⁰), les outils travaillent en log-probabilités :

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

Cette valeur constitue le score Markov du candidat. Les candidats sont générés par ordre décroissant de score, c'est-à-dire du plus probable au moins probable.

3.4 Pourquoi l'ordre 5 ?

Les recherches empiriques (Dürmuth 2015, confirmées par Ma et al. 2012) montrent que :

4. Architecture d'un cracktool Markov

4.1 Composants principaux

┌─────────────────────────────────────────────────────────────┐
│                    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 Intégration avec Hashcat

L'implémentation la plus répandue en pratique est via le mode stdin de Hashcat (-a 0 avec un générateur externe) ou via des modules Python comme statsgen (du toolkit 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

Des outils dédiés comme OMEN (Open Markov Estimator of Next passwords) génèrent directement des listes de candidats triés.

5. Phase 1 — Entraînement sur corpus de mots de passe réels

5.1 Extraction des n-grammes

Pour chaque mot de passe du corpus, on extrait tous les n-grammes (avec un marqueur de début ^ et de fin $) :

Exemple avec "hello" (ordre 2) :

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

Exemple avec "P@ss1!" (ordre 2) :

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

5.2 Comptage et normalisation

Pour chaque contexte (n-1 caractères précédents), on compte les occurrences de chaque caractère suivant, puis on normalise :

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

Ces distributions révèlent les habitudes linguistiques humaines : après "pa", les gens écrivent massivement "s" (password, pass, pablo...).

5.3 Smoothing (lissage)

Le problème des n-grammes non observés : si "xq" n'apparaît jamais dans le corpus, P(c|xq) = 0 pour tout c — ce qui bloque la génération. Les techniques de lissage les plus utilisées :

Le lissage permet aussi au modèle de générer des candidats hors du corpus d'entraînement — crucial pour couvrir des mots de passe légèrement inédits.

5.4 Ce que le modèle apprend

Après entraînement sur RockYou, un modèle Markov d'ordre 5 internalise des patterns comme :

6. Phase 2 — Génération ordonnée de candidats

6.1 Le problème de l'énumération par score

Générer les candidats par ordre décroissant de probabilité Markov est un problème non trivial. On ne peut pas simplement calculer les probabilités de tous les candidats possibles (94⁸ ≈ 6 × 10¹⁵ pour 8 chars) puis les trier.

La solution : recherche heuristique avec priority queue (file de priorité). L'algorithme s'apparente à Dijkstra :

Cette approche garantit un tri approximativement décroissant sans mémoriser l'intégralité de l'espace.

6.2 Seuil de coupure (threshold)

Pour éviter de générer des milliards de candidats improbables, on définit un score minimal en dessous duquel un candidat partiel est éliminé (élagage). Concrètement :

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

Le threshold est un paramètre critique : trop haut → on rate des mots de passe à la limite ; trop bas → on génère trop de candidats et on ralentit l'attaque.

6.3 Gestion des longueurs

Les modèles Markov sont entraînés et opèrent généralement par longueur fixée. Une attaque typique :

La distribution des longueurs dans RockYou : 8 chars = 24 %, 7 chars = 21 %, 9 chars = 12 %, 6 chars = 10 %...

7. Réduction de l'espace de recherche : la clé de l'efficacité

7.1 Quantification empirique (Dürmuth 2015)

Pour un mot de passe de 8 caractères avec l'alphabet complet (94 chars) :

La différence entre "espace réduit" et "espace humain typique" s'explique par le fait que les mots de passe humains réels se concentrent dans les top-k% les plus probables selon le modèle.

7.2 Pourquoi les humains sont prévisibles

Les facteurs de prévisibilité exploités par Markov :

7.3 Le cas des patterns clavier

Les séquences clavier (qwerty, asdf, zxcv, 1234, azerty...) sont particulièrement vulnérables. Pour ces patterns :

Dans Time2Crack (version actuelle), cette distinction n'est plus un palier fixe. Le modèle Markov v2 intègre kbPat comme signal dans un estimateur de rang (markovExpectedGuesses) puis interpole continûment entre régime "human-like" et "random-like".

8. Variantes et implémentations notables

8.1 OMEN (Open Markov Estimator of Next passwords)

OMEN utilise une discrétisation des probabilités en niveaux entiers pour accélérer la génération :

Cette approche résout élégamment le problème de l'énumération ordonnée sans priority queue coûteuse.

8.2 OMEN+

Extension de OMEN avec :

Performance rapportée : +15 à +20 % de mots de passe crackés vs OMEN original à budget égal.

8.3 Statsgen / PACK (Password Analysis and Cracking Kit)

8.4 JohnTheRipper — mode Markov

JohnTheRipper intègre un mode Markov natif (développé par Samuele Giovanni Tonon) :

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

Paramètre --markov-threshold (0-400) : contrôle le seuil de coupure. 150 = paramètre standard recommandé.

Le mode Markov de JtR utilise des statistiques précalculées stockées dans des fichiers .mkv (markov stats files) générés par calcstat.

8.5 Modèles Markov hybrides

Ces hybridations sont utilisées dans des configurations de cracking professionnelles pour maximiser la couverture à budget CPU/GPU fixé.

8.6 Modèles de langage modernes (LLM/LSTM) — successeurs de Markov

Les réseaux LSTM et Transformer peuvent être vus comme des généralisations des chaînes de Markov :

PassGAN (2017), FLA (2019), PassBERT (2022) surpassent les modèles Markov classiques de 20-30 % en taux de crack sur des corpus modernes.

9. Comportement face à différents types de mots de passe

9.1 Mots de passe issus de mots naturels

9.2 Mots avec substituations leetspeak

9.3 Mots avec suffixe numérique

9.4 Prénoms et noms propres

9.5 Mots de passe de structure aléatoire apparente mais mnémotechnique

9.6 Patterns clavier

9.7 Mots de passe véritablement aléatoires

9.8 Passphrases

10. Intégration dans Time2Crack : modélisation et paramètres

10.1 Logique générale de calcul (v2)

Time2Crack modélise désormais Markov en rang attendu (rank-based) plutôt qu'avec des facteurs fixes de réduction.

Pipeline de calcul :

10.2 Tokenisation Unicode et profil calibré par langue

Le modèle Markov v2 utilise des classes Unicode (\p{L}, \p{N}, sinon symbole) et un profil calibré par langue (chargé depuis data/markov-calibration.json, avec fallback interne).

Le profil contient :

10.3 Interpolation continue (fin des seuils abrupts)

L'ancien modèle utilisait des paliers (0.003 / 0.006 / 0.25 / 0.9). Le modèle v2 remplace cette logique par une interpolation continue entre :

Le poids "random" est une fonction continue de la longueur, du charset et de la force des signaux humains, ce qui évite les discontinuités artificielles.

10.4 Score de confiance et d'applicabilité

Le modèle de scoring de Time2Crack (fonction annotateScenarioApplicability()) attribue à 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 Ajustement HF

Avec Markov v2, les signaux structurels sont déjà intégrés dans le rang estimé. L'ajustement HF est donc neutre pour Markov afin d'éviter le double comptage.

10.6 Priorité dans le tiebreak

Quand plusieurs attaques donnent des temps similaires (< 1ms de différence), Time2Crack choisit la plus pertinente selon une priorité sémantique :

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

Markov est une attaque complément utile qui exploite les régularités statistiques. Elle prime sur la force brute pour les mots de passe avec structure humaine, mais cède le pas aux attaques dictionnaire et hybride qui sont plus directes.

10.7 Cas ultra-weak

Pour les mots de passe ultra-faibles (détectés par isWeakPassword()), Markov utilise un temps basé sur un rang minimal (weakGuessTime) plutôt qu'une constante fixe :

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

Raisonnement : un mot de passe ultra-faible (password, 123456, qwerty...) est dans le top-100 absolu de l'espace Markov — il sera testé en premier, la précision du calcul est sans intérêt.

11. Comparaison avec les autres attaques probabilistes

11.1 Markov vs PCFG

11.2 Markov vs Attaque par règles (Rule-based)

11.3 Markov vs Réseaux neuronaux (PassGAN, LSTM)

11.4 Positionnement global

Dans un workflow de cracking professionnel, l'ordre typique est :

Markov est souvent la ligne de fond avant brute force : il couvre efficacement les mots de passe humains qui ont échappé aux attaques plus ciblées.

12. Limites de l'attaque Markov

12.1 Dépendance au corpus d'entraînement

Le modèle est aussi bon que son corpus. Un corpus dominé par les mots de passe anglais (RockYou, LinkedIn) capture mal les régularités :

12.2 Indépendance inter-positions à grande distance

Un modèle Markov d'ordre 5 ne voit pas au-delà de 5 caractères. Pour un mot de passe de 12 caractères, il ne peut pas corréler le 12ème caractère avec le 1er. Une passphrase comme "stargate2004!" a une structure globale ("mot + année + !") que Markov perçoit localement mais pas globalement — PCFG est meilleur ici.

12.3 Insensibilité aux structures compositionnelles

"HorseStapleBattery" (majuscule initiale + 3 mots concaténés) est difficile pour Markov car les transitions inter-mots (e→S, e→B) sont inattendues. L'attaque combinator ou PCFG est mieux adaptée.

12.4 Inefficacité sur mots de passe aléatoires

Un mot de passe généré par /dev/urandom avec 12+ caractères alphanumériques n'a aucune structure exploitable par Markov. Le temps d'attaque Markov converge vers la force brute.

12.5 Sensibilité aux mises à jour de politique de mots de passe

Si une organisation a imposé des règles strictes (longueur ≥ 16, obligatoirement 1 majuscule + 1 chiffre + 1 symbole), les mots de passe résultants peuvent avoir une distribution différente des corpus d'entraînement — réduisant l'efficacité du modèle.

13. Défenses efficaces

13.1 Ce qui neutralise complètement Markov

13.2 Ce qui diminue fortement l'efficacité de Markov

13.3 Ce qui ne défend pas contre Markov

13.4 Recommandation finale

La défense la plus efficace contre Markov (et toute attaque probabiliste) est d'éliminer toute structure humaine prévisible, ce qui revient à déléguer la création de mots de passe à un générateur aléatoire sécurisé.

14. Références bibliographiques

Académiques (peer-reviewed)

Implémentations open source

Sources de corpus

Sources web citées dans l'application Time2Crack