PESrank : Estimation en ligne de la devinabilité des mots de passe via l'estimation de rang multidimensionnelle

1. Introduction

Cet article présente PESrank, un nouvel estimateur de robustesse de mot de passe conçu pour modéliser précisément le comportement d'un craqueur de mots de passe puissant en calculant le rang d'un mot de passe dans un ordre de vraisemblance optimal. Il répond au besoin critique d'un retour rapide, précis et explicable sur la robustesse des mots de passe dans les systèmes en ligne.

1.1. Contexte

Malgré leurs vulnérabilités, les mots de passe textuels restent la méthode d'authentification dominante. Les estimateurs heuristiques courants (par exemple, les règles LUDS) sont imprécis. Les estimateurs basés sur le craquage utilisant des modèles de Markov, des PCFG ou des réseaux neuronaux offrent une meilleure précision, mais souffrent souvent de temps d'entraînement longs ou d'un manque de performance en temps réel et d'explicabilité.

1.2. Contributions

Les contributions clés de PESrank sont l'application novatrice d'un cadre d'estimation de rang issu de la cryptanalyse par canaux auxiliaires aux mots de passe, permettant une estimation de rang en moins d'une seconde sans énumération, des temps d'entraînement considérablement plus courts, une personnalisation efficace du modèle sans réentraînement, et une explicabilité inhérente pour le retour utilisateur.

2. La méthodologie PESrank

PESrank reformule l'estimation de la robustesse d'un mot de passe comme un problème d'estimation de rang multidimensionnelle, s'inspirant des techniques d'analyse d'attaques par canaux auxiliaires utilisées en cryptographie.

2.1. Représentation multidimensionnelle du mot de passe

Un mot de passe est décomposé en un point dans un espace de recherche à d dimensions. Les dimensions représentent des attributs indépendants comme le mot de base (par exemple, "password"), les modèles de capitalisation (par exemple, "Password"), les ajouts de suffixe (par exemple, "password123") ou les transformations leet-speak (par exemple, "p@ssw0rd"). La distribution de probabilité pour chaque dimension est apprise séparément à partir de jeux de données de mots de passe.

2.2. Cadre d'estimation du rang

Au lieu d'énumérer tous les mots de passe possibles, PESrank estime le rang d'une combinaison de mot de passe spécifique en calculant le nombre de combinaisons de mots de passe qui sont plus probables (c'est-à-dire qui ont une probabilité conjointe plus élevée) que le mot de passe donné. Cela est analogue à l'estimation du rang d'une clé de chiffrement dans une attaque par canal auxiliaire.

3. Implémentation technique & Modèle mathématique

3.1. Algorithme central et formule

Le cœur de PESrank implique le calcul de la probabilité conjointe d'un mot de passe représenté par un vecteur de valeurs de dimension $\vec{x} = (x_1, x_2, ..., x_d)$. En supposant que les dimensions sont indépendantes (une simplification pour l'efficacité), la probabilité est : $$P(\vec{x}) = \prod_{i=1}^{d} P_i(x_i)$$ où $P_i(x_i)$ est la probabilité de la valeur $x_i$ dans la dimension $i$, apprise à partir des données d'entraînement. Le rang $R(\vec{x})$ est estimé en sommant les probabilités de tous les vecteurs $\vec{y}$ où $P(\vec{y}) > P(\vec{x})$. Des algorithmes efficaces issus de la littérature sur les canaux auxiliaires, comme l'approche par bornage, sont utilisés pour calculer des bornes supérieures et inférieures serrées pour cette somme sans énumération complète.

3.2. Explicabilité et personnalisation

Le modèle multidimensionnel est intrinsèquement explicable. Le système peut indiquer quelles dimensions (par exemple, "un mot de base très courant" ou "un suffixe prévisible comme '123'") contribuent le plus significativement au faible rang (haute devinabilité) d'un mot de passe. La personnalisation (par exemple, intégrer le nom d'un utilisateur ou son année de naissance comme mot de base interdit) peut être réalisée en ajustant dynamiquement la probabilité $P_i(x_i)$ pour les dimensions pertinentes à une valeur proche de zéro, affectant instantanément les calculs de rang sans réentraînement du modèle.

4. Résultats expérimentaux & Performances

4.1. Références de précision et de vitesse

L'implémentation Python a été évaluée de manière approfondie. Les principaux résultats incluent :

Vitesse : Temps de réponse inférieur à la seconde pour l'estimation du rang, même avec un modèle entraîné sur 905 millions de mots de passe.
Précision : Les bornes de rang estimées étaient systématiquement dans un facteur 2 (une marge de 1 bit) du rang réel, démontrant une grande précision.
Temps d'entraînement : Considérablement plus court que les modèles de réseaux neuronaux ou de PCFG complexes, nécessitant des ordres de grandeur de calcul en moins.

Ces métriques soulignent la viabilité pratique pour un déploiement en ligne.

4.2. Déploiement en conditions réelles

PESrank a été intégré à une page d'inscription aux cours universitaires. Il a fourni un retour en temps réel et explicable aux utilisateurs créant des mots de passe, démontrant sa facilité d'utilisation et ses performances sous des conditions de charge réelles. Le retour a aidé à orienter les utilisateurs loin des modèles de mots de passe faibles et prévisibles.

5. Cadre d'analyse & Exemple pratique

Perspective de l'analyste : Idée centrale, Enchaînement logique, Forces & Faiblesses, Perspectives actionnables

Idée centrale : PESrank n'est pas juste une autre amélioration incrémentale des vérificateurs de mots de passe ; c'est un changement de paradigme fondamental. Il transpose avec succès le cadre rigoureux et quantitatif de l'estimation de rang par canal auxiliaire—un pilier de l'évaluation du matériel cryptographique à haut risque—dans le monde désordonné des mots de passe choisis par les humains. Ce passage de la conjecture heuristique à la cryptanalyse probabiliste est un coup de maître. Il traite le craquage de mot de passe non pas comme un problème linguistique ou de reconnaissance de motifs, mais comme un problème de recherche dans un espace de probabilité structuré, s'alignant parfaitement avec le fonctionnement réel des craqueurs modernes comme Hashcat et John the Ripper avec leurs règles de transformation et chaînes de Markov.

Enchaînement logique : La logique est élégamment réductionniste. 1) Déconstruire les mots de passe en caractéristiques orthogonales pertinentes pour le craquage (mots de base, transformations). 2) Apprendre un modèle de probabilité simple pour chaque caractéristique à partir des données de fuites. 3) Reconstruire la devinabilité d'un mot de passe en calculant combien de combinaisons plus probables existent. Cela contourne le besoin de modèles monolithiques et opaques des réseaux neuronaux (comme ceux de [30, 37]) ou des ensembles de règles parfois encombrants des PCFG [41]. L'hypothèse d'indépendance entre les dimensions est son saut simplificateur clé, échangeant une certaine fidélité de modélisation contre des gains massifs en vitesse et explicabilité—un compromis qui semble très favorable en pratique.

Forces & Faiblesses : Ses forces sont redoutables : une vitesse fulgurante et une explicabilité native sont des atouts majeurs pour l'adoption en conditions réelles, répondant aux deux plus gros points faibles des modèles académiques. L'astuce de personnalisation est ingénieuse et pratique. Cependant, une faiblesse critique réside dans l'hypothèse d'indépendance. Bien qu'efficace, elle ignore les corrélations (par exemple, certains modèles de capitalisation sont plus probables avec certains mots de base). Cela pourrait conduire à des inexactitudes de rang pour les mots de passe complexes et corrélés. De plus, sa précision est intrinsèquement liée à la qualité et à l'étendue de ses données d'entraînement pour chaque dimension, une dépendance qu'il partage avec tous les modèles basés sur les données. Il pourrait avoir du mal avec les stratégies de création de mots de passe véritablement nouvelles, non observées dans les fuites passées.

Perspectives actionnables : Pour les équipes de sécurité, le message est clair : abandonnez les vérificateurs LUDS. PESrank démontre qu'un retour précis comme un craqueur et en temps réel est désormais opérationnellement faisable. La voie d'intégration montrée—son intégration dans un portail d'inscription—est un modèle. Pour les chercheurs, l'avenir réside dans les modèles hybrides. Combinez le cadre efficace et explicable de PESrank avec un composant neuronal léger pour modéliser les corrélations inter-dimensionnelles, de la même manière que les modèles de vision comme CycleGAN utilisent des générateurs séparés pour différentes transformations de domaine tout en maintenant une structure cohésive. La prochaine frontière est la personnalisation adaptative qui apprend des suggestions de mots de passe *rejetées* par un utilisateur pour affiner son modèle en temps réel, allant au-delà des listes de blocage statiques.

6. Applications futures & Axes de recherche

Chasse proactive aux menaces : Au-delà des vérificateurs destinés aux utilisateurs, l'algorithme central de PESrank peut analyser les bases de données de mots de passe existantes (avec un hachage approprié) pour identifier et signaler proactivement les comptes avec des mots de passe hautement devinables, permettant des réinitialisations forcées.
Moteurs de personnalisation améliorés : Les systèmes futurs pourraient s'intégrer aux annuaires organisationnels (par exemple, LDAP) pour personnaliser automatiquement le modèle avec les noms des employés, les noms de code de projets et le jargon interne, créant un modèle de menace dynamique et spécifique à l'organisation.
Étalonnage et normalisation : L'approche par estimation de rang fournit une métrique quantitative rigoureuse. Cela pourrait constituer la base de normes d'étalonnage de la robustesse des mots de passe à l'échelle de l'industrie, dépassant les étiquettes vagues de "fort" ou "faible".
Validation croisée des modèles : PESrank pourrait être utilisé comme un filtre "première passe" rapide et explicable, les mots de passe suspects étant signalés pour une analyse plus approfondie par des modèles plus gourmands en calcul (par exemple, RNN), créant une défense à plusieurs niveaux.
Recherche sur l'interdépendance des dimensions : Le principal axe de recherche est l'assouplissement de l'hypothèse d'indépendance. L'exploration de modèles de corrélation légers (par exemple, les réseaux bayésiens sur les dimensions) pourrait améliorer la précision pour les mots de passe complexes sans sacrifier l'avantage central de la vitesse.

7. Références

L. David et A. Wool, "Online Password Guessability via Multi-Dimensional Rank Estimation", arXiv preprint arXiv:1912.02551v2, 2020.
J. Bonneau, "The Science of Guessing: Analyzing an Anonymized Corpus of 70 Million Passwords", IEEE Symposium on Security and Privacy, 2012.
M. Weir, S. Aggarwal, B. de Medeiros et B. Glodek, "Password Cracking Using Probabilistic Context-Free Grammars", IEEE Symposium on Security and Privacy, 2009.
W. Melicher, B. Ur, S. M. Segreti, S. Komanduri, L. Bauer, N. Christin et L. F. Cranor, "Fast, Lean, and Accurate: Modeling Password Guessability Using Neural Networks", USENIX Security Symposium, 2016.
D. Wang, H. Cheng, P. Wang, X. Huang et G. Jian, "A Security Analysis of Honeywords", NDSS, 2018. (Exemple d'analyse rigoureuse liée aux mots de passe)
P. G. Kelley, S. Komanduri, M. L. Mazurek, R. Shay, T. Vidas, L. Bauer, N. Christin, L. F. Cranor et J. Lopez, "Guess Again (and Again and Again): Measuring Password Strength by Simulating Password-Cracking Algorithms", IEEE Symposium on Security and Privacy, 2012.
National Institute of Standards and Technology (NIST), "Digital Identity Guidelines", NIST Special Publication 800-63B, 2017. (Pour le contexte sur les normes d'authentification)