L'attaque PCFG — 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

  • Vue d'ensemble
  • Contexte historique et académique
  • Fondements : grammaire structurelle des mots de passe
  • Apprentissage du modèle PCFG
  • Génération ordonnée des candidats
  • Pourquoi PCFG casse des secrets à entropie apparente élevée
  • Implémentation dans Time2Crack : addPCFGAttacks()
  • Fonction pcfgKeyspace() et hypothèses
  • Gestion numérique : soft cap (remplacement du cap dur)
  • Calibration haute fidélité
  • Benchmarks et ordres de grandeur
  • Exemples concrets
  • Limites de l'attaque PCFG
  • Défenses efficaces
  • Références bibliographiques

    • 1. Vue d'ensemble

    PCFG (Probabilistic Context-Free Grammar) modélise la structure des mots de passe en segments typés (lettres, chiffres, symboles), puis génère les candidats les plus probables en priorité.

    2. Contexte historique et académique

    Les travaux de Weir et al. (2009) ont établi PCFG comme une méthode majeure de cracking probabiliste, souvent supérieure aux approches purement dictionnaire à budget égal sur des corpus humains.

    3. Fondements : grammaire structurelle des mots de passe

    Exemple :

    Le modèle apprend que certains schémas (L8D2, L6D4) sont fréquents, d'autres rares.

    4. Apprentissage du modèle PCFG

  • Segmenter les mots de passe en classes.
  • Estimer la probabilité des squelettes.
  • Estimer la probabilité des tokens dans chaque slot.

    • 5. Génération ordonnée des candidats

    PCFG produit d'abord les dérivations à probabilité élevée. Cette priorisation est la source principale de son efficacité.

    6. Pourquoi PCFG casse des secrets à entropie apparente élevée

    Une chaîne peut sembler forte en entropy brute tout en étant très prévisible structurellement (mot + chiffres + symbole). PCFG exploite cette prévisibilité.

    7. Implémentation dans Time2Crack : addPCFGAttacks()

    Time2Crack calcule un budget via pcfgKeyspace(pw) puis convertit en temps avec budgetTime(...).

    Catégorie: cat: "pcfg", note: nPCFGDetected.

    8. Fonction pcfgKeyspace() et hypothèses

    Le modèle interne approxime les dimensions lexicales, numériques et symboliques, puis borne le keyspace pour rester réaliste en usage interactif.

    Composants principaux :

  • composante lettres (wordGuesses),
  • composante chiffres (10^digitLen),
  • composante symboles (32^symbolCount),
  • facteur de variantes structurelles.

    • Le budget PCFG est ensuite converti en temps via budgetTime(pcfgGuesses, rate).

    9. Gestion numérique : soft cap (remplacement du cap dur)

    Time2Crack utilise désormais un soft cap pour éviter les plateaux artificiels causés par un cap dur unique.

    9.1 Ancienne approche (cap dur)

    Un Math.min(..., cap) écrase toutes les valeurs au-dessus du cap en une même constante. Cela supprime la hiérarchie entre cas "difficiles" et "très difficiles".

    9.2 Nouvelle approche (soft cap)

    Le modèle applique une compression continue :

  • linéaire sous un point de coude (knee),
  • compression progressive au-dessus,
  • asymptote vers un maximum numérique (max).

    • Formule utilisée :

    soft = knee + (max - knee) * (1 - exp(-(raw - knee)/(max - knee))) pour raw > knee.

    Sinon soft = raw.

    9.3 Paramètres actuels (app.js)

  • PCFGSOFTCAPKNEE = 1e14
  • PCFGMAXGUESSES = 1e18

    • Effet : stabilité numérique conservée sans rupture brutale ni perte totale de différenciation.

    10. Calibration haute fidélité

    Avec PCFG v2, les signaux structurels sont déjà intégrés dans l'estimation de rang (pcfgKeyspace). L'ajustement HF est donc neutre pour éviter le double comptage.

    11. Benchmarks et ordres de grandeur

    Sur hash rapides, les structures courantes tombent très vite.

    Sur KDF lents, l'ordre PCFG reste avantageux mais le coût par tentative reste déterminant.

    12. Exemples concrets

  • Password123 : cible idéale PCFG.
  • xQ7$vP2!mL9@ : faible compatibilité PCFG.

    • 13. Limites de l'attaque PCFG

  • dépendance au corpus d'entraînement,
  • faibles performances sur aléatoire réel,
  • complexité de calibration linguistique multi-domaines,
  • la v1 du modèle reste une approximation de ranking PCFG (pas une grammaire entraînée en ligne).

    • 14. Défenses efficaces

  • Éviter les structures habituelles (Word+Digits+Symbol).
  • Utiliser des secrets générés aléatoirement.
  • KDF robustes + MFA.

    • 15. Références bibliographiques

  • Weir et al. (2009). IEEE S&P.
  • Ma et al. (2014). IEEE S&P.
  • Wheeler, D. (2016). USENIX Security.