Markov attack (probabilistic) — Comprehensive operation

Project reference document Time2Crack

Recipients: developers, security researchers, advanced users

Contents

1. Overview

Markov Attack is a password cracking method probabilistic and statistical which generates candidates by relying on the observed frequencies of transition between characters in real human passwords. Instead of testing all possible combinations in alphabetical order — as the raw force does — it sorts candidates from the most probable at least, concentrating the calculation effort where human passwords are actually located.

2. Historical and academic background

2.1 Origins

The application of Markov's channels to password cracking is earlier than formal academic publications. Offensive security practitioners used similar models since the 2000s, but rigorous formalization dates mainly from the 2010s.

2.2 Reference body

Markov model training is based on password databases from known data leaks:

• RockYou (2009) : 14.3 million plain passwords — universal reference corpus

These corpus reveal the actual statistical distribution of human passwords, which differs radically from a uniform distribution.

3. Mathematical Foundations: Markov's Chains

3.1 Formal definition

Markov chain of order k on an alphabet k Previous characters:

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

For passwords, it usually includes 95 printable ASCII characters (26 lower case + 26 upper case + 10 digits + 33 symbols).

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

Order 5 captures contexts like "after "passw", the most likely follow-up is "o" — information inaccessible to an order model 1.

3.2 The transition matrix

For an order of 1 over 95 characters, the transition matrix is size 95 × 95 = 9,025 inputs. For Order 5, it goes to 955 × 95 = ~7.7 × 1010 theoretical inputs — but the majority of order n-grams 5 never appear in the actual data. Implementations use hollow data structures (tries, hash maps) to store only observed n-grams.

3.3 Log probability and sorting

To avoid floating overruns on 8+-character passwords (probabilities of the order of 10−20), the tools work in log probabilities :

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

This value is the score Markov Candidates are generated in descending order of score, i.e. the most likely at least likely.

3.4 Why Order 5?

Empirical research (Dürmuth 2015, confirmed by Ma et al. 2012) shows that:

4. Architecture of a Markov cracktool

4.1 Main components

┌─────────────────────────────────────────────────────────────┐
│                    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 Integration with Hashcat

The most widespread implementation in practice is via the Hashcat stdin mode (-a 0 with an external generator) or via Python modules as statsgen (from the PACK toolkit):

# 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

Dedicated tools like OMEN (Open Markov Estimator of Next passwords) directly generate lists of sorted candidates.

5. Phase 1 — Body of real password training

5.1. Extraction of n-grams

For each password in the corpus, all n-grams are extracted (with a start marker). ^ and end $) :

Example with "hello" (order 2):

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

Example with "P@ss1!" (order 2):

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

5.2 Counting and standardization

For each context (n-1 previous characters), the occurrences of each following character are counted and normalized:

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

These distributions reveal human language habits: after "pa", people write massively "s" (password, pass, pablo...).

Smoothing

The problem of unobserved n-grams: if "xq" never appears in the corpus, P(c)xq) = 0 for any c — which blocks the generation. The most used smoothing techniques:

Smoothing also allows the model to generate candidates out of the training corpus — crucial to cover slightly new passwords.

5.4 What the model learns

After training on RockYou, a Markov 5-order model internalizes patterns like:

6. Phase 2 — Orderly generation of candidates

6.1 The problem of score enumeration

Generating candidates in descending order of probability Markov is a non-trivial problem. We cannot simply calculate the probabilities of all possible candidates (948 x 6 × 1015 for 8 tanks) and then sort them out.

The solution: Heuristic search with priority tail The algorithm is similar to Dijkstra:

This approach ensures an approximately decreasing sorting without memorizing the entire space.

6.2. Threshold threshold

To avoid generating billions of improbable candidates, a Minimum score below which a partial candidate is eliminated (sladding).

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

Threshold is a critical parameter: too high → you miss passwords at the limit; too low → you generate too many candidates and slow down the attack.

6.3 Length management

Markov models are trained and generally operate by fixed lengthA typical attack:

Length distribution in RockYou: 8 tanks = 24%, 7 tanks = 21%, 9 tanks = 12%, 6 tanks = 10%...

7. Reducing Research Space: The Key to Effectiveness

7.1 Empirical quantification (Dürmuth 2015)

For a password of 8 characters with the complete alphabet (94 tanks):

The difference between "reduced space" and "typical human space" can be explained by the fact that real human passwords are concentrated in top-k% most likely Depending on the model.

7.2 Why Humans Are Predictable

The predictability factors used by Markov:

7.3 The case of keyboard patterns

Keyboard sequences (qwerty, asdf, zxcv, 1234, azerty...) are particularly vulnerable.

In Time2Crack (current version), this distinction is no longer a fixed bearing. The Markov v2 model incorporates kbPat as a signal in a rank estimator (markovExpectedGuesses) then interpole continuously between "human-like" and "random-like" regimes.

8. Notable Variations and Implementations

8.1 OMEN (Open Markov Estimator of Next passwords)

OMEN uses a discretisation of probabilities in whole levels to accelerate the generation:

This approach elegantly solves the problem of orderly enumeration without expensive priority tail.

8.2 OMEN+

Extension of OMEN with:

Reported performance: +15 to +20% cracked passwords vs original OMEN with equal budget.

8.3 Statsgen / PACK (Password Analysis and Cracking Kit)

8.4 JohnTheRipper — Markov Mode

John TheRipper integrates a native Markov mode (developed by Samuele Giovanni Tonon):

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

Parameter --markov-threshold (0-400): controls the cut-off threshold. 150 = recommended standard parameter.

JtR Markov mode uses pre-calculated statistics stored in files .mkv (markov stats files) generated by calcstat.

8.5 Markov Hybrid Models

These hybridizations are used in professional cracking configurations to maximize CPU/GPU budget coverage.

8.6 Modern Language Models (LLM/LSTM) — successors to Markov

LSTM and Transformer networks can be seen as generalizations of Markov channels:

PassGAN (2017), FLA (2019), PassBERT (2022) surpassed classic Markov models by 20-30% in crack rates on modern corpus.

9. Behaviour against different types of passwords

9.1 Passwords from natural words

9.2 Words with leetspeak substitutions

9.3 Words with digital suffix

9.4 Given names and proper names

9.5 Pass words of apparent random structure but mnemotechnic

9.6 Keyboard Patterns

9.7 Really Random Passwords

9.8 Passphrases

10. Integration into Time2Crack: Modelling and Parameters

General logic of calculation (v2)

Time2Crack now models Markov in expected rank (rank-based) rather than with fixed reduction factors.

Calculation line:

10.2 Unicode Tokenization and Calibrated Profile by Language

The Markov v2 model uses Unicode classes (\p{L}, \p{N}, otherwise symbol) and a calibrated profile per language (loaded since data/markov-calibration.json, with internal fallback).

The profile contains:

10.3. Continuous interpolation (end of steep thresholds)

The old model used bearings (0.003 / 0.006 / 0.25 / 0.9). The v2 model replaces this logic with continuous interpolation between:

Random weight is a continuous function of the length, tank and strength of human signals, thus avoiding artificial discontinuities.

10.4 Confidence and applicability score

Time2Crack Scoring Model (function annotateScenarioApplicability()) allocates to 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 Adjustment HF

With Markov v2, the structural signals are already integrated into the estimated rank. The HF adjustment is therefore neutral for Markov in order to avoid double counting.

10.6 Priority in the tiebreak

When multiple attacks give similar times (< 1ms of difference), Time2Crack chooses the most relevant according to a semantic priority:

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

Markov is a useful complement attack that exploits statistical regularities. It takes precedence over gross force for passwords with human structure, but gives precedence to dictionary and hybrid attacks that are more direct.

10.7 Ultra-weak case

For ultra-low passwords (detected by isWeakPassword()), Markov uses a time based on a minimum rank (weakGuessTime) rather than a fixed constant:

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

Reasoning: an ultra-low password (password, 123456, qwerty...) is in the top-100 absolute Markov space — it will be tested first, the accuracy of the calculation is irrelevant.

11. Comparison with other probabilistic attacks

11.1 Markov vs PCFG

11.2 Markov vs. Rule-Based Attack

11.3 Markov vs Neural Networks (PassGAN, LSTM)

11.4 Global positioning

In a professional cracking workflow, the typical order is:

Markov is often the background line front brute force: it effectively covers human passwords that have escaped more targeted attacks.

12. Limits of the Markov Attack

12.1 Dependence on the body of training

The model is as good as its corpus. A corpus dominated by English passwords (RockYou, LinkedIn) misunderstands regularities:

12.2 Long-range interpositional independence

A Markov 5 model sees no more than 5 characters. For a password of 12 characters, it cannot correlate the 12th character with the 1st. A passphrase like "stargate2004!" has a global structure ("word + year +!") that Markov perceives locally but not globally — PCFG is better here.

12.3 Insensitivity to compositional structures

"HorseStapleBattery" (initial majusculum + 3 concatenated words) is difficult for Markov because inter-word transitions (e→S, e→B) are unexpected. The combinator attack or PCFG is better suited.

12.4 Random password ineffectiveness

A password generated by /dev/urandom with 12+ alphanumeric characters has no structure exploitable by Markov. The attack time Markov converges to the raw force.

12.5 Sensitivity to updated password policy

If an organization has imposed strict rules (length ≥ 16, mandatory 1 capital + 1 digit + 1 symbol), the resulting passwords may have a different distribution of the training corpus — reducing the effectiveness of the model.

13. Effective defences

13.1 What completely neutralizes Markov

13.2 Which greatly reduces the effectiveness of Markov

13.3 What does not defend against Markov

13.4 Final recommendation

The most effective defence against Markov (and any probabilistic attack) is toeliminate any foreseeable human structure, which amounts to delegating password creation to a secure random generator.

14. References

Academics (peer-reviewed)

Open source implementations

Sources of corpus

Web sources cited in the Time2Crack application