Après avoir lu diverses ressources sur la force des mots de passe, j'essaie de créer un algorithme qui fournira une estimation approximative de la quantité d'entropie d'un mot de passe.

J'essaie de créer un algorithme aussi complet que possible. À ce stade, je n'ai qu'un pseudocode, mais l'algorithme couvre les éléments suivants:

• longueur du mot de passe
• caractères répétés
• modèles (logique)
• différents espaces de caractères (LC, UC, numérique, spécial, étendu)
• attaques par dictionnaire

Il ne couvre PAS les éléments suivants, et DEVRAIT le couvrir BIEN (mais pas parfaitement):

• ordre (les mots de passe peuvent être strictement ordonnés par la sortie de cet algorithme)
• motifs (spatiaux)

Quelqu'un peut-il donner un aperçu de la faiblesse de cet algorithme? Plus précisément, quelqu'un peut-il penser à des situations où le fait de fournir un mot de passe à l'algorithme surestimerait sa force? Les sous-estimations sont moins problématiques.

L'algorithme:

// the password to test
password = ?
length = length(password)

// unique character counts from password (duplicates discarded)
uqlca = number of unique lowercase alphabetic characters in password
uquca = number of uppercase alphabetic characters
uqd   = number of unique digits
uqsp  = number of unique special characters (anything with a key on the keyboard)
uqxc  = number of unique special special characters (alt codes, extended-ascii stuff)

// algorithm parameters, total sizes of alphabet spaces
Nlca = total possible number of lowercase letters (26)
Nuca = total uppercase letters (26)
Nd   = total digits (10)
Nsp  = total special characters (32 or something)
Nxc  = total extended ascii characters that dont fit into other categorys (idk, 50?)

// algorithm parameters, pw strength growth rates as percentages (per character)
flca = entropy growth factor for lowercase letters (.25 is probably a good value)
fuca = EGF for uppercase letters (.4 is probably good)
fd   = EGF for digits (.4 is probably good)
fsp  = EGF for special chars (.5 is probably good)
fxc  = EGF for extended ascii chars (.75 is probably good)

// repetition factors.  few unique letters == low factor, many unique == high
rflca = (1 - (1 - flca) ^ uqlca)
rfuca = (1 - (1 - fuca) ^ uquca)
rfd   = (1 - (1 - fd  ) ^ uqd  )
rfsp  = (1 - (1 - fsp ) ^ uqsp )
rfxc  = (1 - (1 - fxc ) ^ uqxc )

// digit strengths
strength =
( rflca * Nlca + 
  rfuca * Nuca +
  rfd   * Nd   +
  rfsp  * Nsp  +
  rfxc  * Nxc    ) ^ length

entropybits = log_base_2(strength)

Quelques entrées et leurs sorties entropy_bits souhaitées et réelles:

INPUT           DESIRED        ACTUAL
aaa             very pathetic  8.1
aaaaaaaaa       pathetic       24.7
abcdefghi       weak           31.2
H0ley$Mol3y_    strong         72.2
s^fU¬5ü;y34G<   wtf            88.9
[a^36]*         pathetic       97.2
[a^20]A[a^15]*  strong         146.8
xkcd1**         medium         79.3
xkcd2**         wtf            160.5

* these 2 passwords use shortened notation, where [a^N] expands to N a's.
** xkcd1 = "Tr0ub4dor&3", xkcd2 = "correct horse battery staple"

L'algorithme se rend compte (correctement) que l'augmentation de la taille de l'alphabet (même d'un chiffre) renforce considérablement les mots de passe longs, comme le montre la différence d'entropie_bits pour les 6e et 7e mots de passe, qui consistent tous deux en 36 a, mais le 21e du second est capitalisé. Cependant, ils ne tiennent pas compte du fait qu'avoir un mot de passe de 36 a n'est pas une bonne idée, il est facilement cassé avec un pirate de mot de passe faible (et toute personne qui vous regarde taper le verra) et l'algorithme ne reflète pas cela .

Il reflète cependant le fait que xkcd1 est un mot de passe faible par rapport à xkcd2, malgré une densité de complexité plus élevée (est-ce même une chose?).

Comment puis-je améliorer cet algorithme?

Addendum 1

Les attaques par dictionnaire et les attaques basées sur des modèles semblent être la grande chose, donc je vais essayer de les résoudre.

Je pourrais effectuer une recherche complète par le mot de passe des mots d'une liste de mots et remplacer les mots par des jetons uniques aux mots qu'ils représentent. Les jetons de mots seraient alors traités comme des caractères et auraient leur propre système de poids, et ajouteraient leurs propres poids au mot de passe. J'aurais besoin de quelques nouveaux paramètres d'algorithme (je les appellerai lw, Nw ~ = 2 ^ 11, fw ~ = .5 et rfw) et je prendrais en compte le poids dans le mot de passe comme je le ferais pour n'importe quel autre poids.

Cette recherche de mots pourrait être spécialement modifiée pour correspondre à la fois aux lettres minuscules et majuscules ainsi qu'aux substitutions de caractères courantes, comme celle de E avec 3. Si je n'ajoutais pas de poids supplémentaire à ces mots correspondants, l'algorithme sous-estimerait un peu leur force ou deux par mot, ce qui est OK. Sinon, une règle générale serait, pour chaque correspondance de caractère non parfaite, donner au mot un bit bonus.

Je pourrais ensuite effectuer des vérifications de modèle simples, telles que des recherches de séries de caractères répétés et des tests dérivés (prendre la différence entre chaque caractère), qui identifieraient des modèles tels que 'aaaaa' et '12345', et remplacer chaque modèle détecté par un modèle jeton, unique au motif et à la longueur. Les paramètres algorithmiques (en particulier, l'entropie par motif) pourraient être générés à la volée en fonction du motif.

À ce stade, je prendrais la longueur du mot de passe. Chaque jeton de mot et jeton de motif compterait comme un caractère; chaque jeton remplacerait les caractères qu'ils représentaient symboliquement.

J'ai créé une sorte de notation de modèle, mais elle comprend la longueur du modèle l, l'ordre des modèles o et l'élément de base b. Ces informations pourraient être utilisées pour calculer un poids arbitraire pour chaque modèle. Je ferais quelque chose de mieux dans le code réel.

Exemple modifié:

Password:          1234kitty$$$$$herpderp
Tokenized:         1 2 3 4 k i t t y $ $ $ $ $ h e r p d e r p
Words Filtered:    1 2 3 4 @W5783 $ $ $ $ $ @W9001 @W9002
Patterns Filtered: @P[l=4,o=1,b='1'] @W5783 @P[l=5,o=0,b='$'] @W9001 @W9002

Breakdown:         3 small, unique words and 2 patterns
Entropy:           about 45 bits, as per modified algorithm

Password:          correcthorsebatterystaple
Tokenized:         c o r r e c t h o r s e b a t t e r y s t a p l e
Words Filtered:    @W6783 @W7923 @W1535 @W2285

Breakdown:         4 small, unique words and no patterns
Entropy:           43 bits, as per modified algorithm

La sémantique exacte de la façon dont l'entropie est calculée à partir des modèles est à discuter. Je pensais à quelque chose comme:

entropy(b) * l * (o + 1) // o will be either zero or one

L'algorithme modifié trouverait des défauts et réduirait la force de chaque mot de passe dans le tableau d'origine, à l'exception de s^fU¬5ü;y34G<, qui ne contient aucun mot ni motif.

L'annexe A à la p46 du NIST SP 800-63 parle du travail de Claude Shannon , qui estime l'entropie des mots de passe en utilisant un certain nombre de bits. En effet, c'est le document que le dessin animé XKCD utilise pour calculer les bits d'entropie. Plus précisément:

• l'entropie du premier caractère est prise à 4 bits;
• l'entropie des 7 caractères suivants est de 2 bits par caractère; cela correspond à peu près à l'estimation de Shannon selon laquelle «lorsque l'on considère des effets statistiques ne dépassant pas plus de 8 lettres, l'entropie est d'environ 2,3 bits par caractère;»
• pour le 9ème au 20ème caractère, l'entropie est supposée être de 1,5 bits par caractère;
• pour les caractères 21 et supérieurs, l'entropie est considérée comme étant de 1 bit par caractère;
• Un «bonus» de 6 bits d'entropie est attribué à une règle de composition qui requiert à la fois des majuscules et des caractères non alphabétiques. Cela force l'utilisation de ces caractères, mais dans de nombreux cas, ces caractères n'apparaîtront qu'au début ou à la fin du mot de passe, et cela réduit quelque peu l'espace de recherche total, de sorte que l'avantage est probablement modeste et presque indépendant de la longueur du mot de passe;
• Un bonus jusqu'à 6 bits d'entropie est ajouté pour une vérification approfondie du dictionnaire. Si l'attaquant connaît le dictionnaire, il peut éviter de tester ces mots de passe et pourra de toute façon deviner une grande partie du dictionnaire, qui sera cependant le mot de passe sélectionné le plus probable en l'absence de règle de dictionnaire. L'hypothèse est que la plupart des avantages de l'entropie de devinettes pour un test de dictionnaire reviennent à des mots de passe relativement courts, car tout mot de passe long qui peut être mémorisé doit nécessairement être une «phrase de passe» composée de mots de dictionnaire, de sorte que le bonus tombe à zéro à 20 personnages.

L'idée est qu'un système d'authentification choisirait certains niveaux d'entropie comme seuils. Par exemple, 10 bits peuvent être faibles, 20 moyens et 30 forts (nombres choisis arbitrairement à titre d'exemple, pas de recommandation). Malheureusement, le document ne recommande pas de tels seuils, probablement parce que la puissance de calcul disponible pour la force brute ou pour deviner les mots de passe augmente avec le temps:

Au lieu d'imposer un ensemble de règles spécifiques arbitraires, un système d'authentification peut classer les mots de passe des utilisateurs, en utilisant les règles énoncées ci-dessus, et accepter ceux qui répondent à une norme d'entropie minimale. Par exemple, supposons que des mots de passe avec au moins 24 bits d'entropie soient requis. Nous pouvons calculer l'estimation d'entropie de «IamtheCapitanofthePina4» en observant que la chaîne a 23 caractères et satisferait une règle de composition nécessitant des majuscules et des caractères non alphabétiques.

Cela peut ou non être ce que vous recherchez, mais ce n'est pas un mauvais point de référence, si rien d'autre.

[Modifier: ajouté ce qui suit.]

L'article intitulé Testing Metrics for Password Creation Policies by Attacking Large Sets of Revealed Passwords (par Matt Weir, Sudhir Aggarwal, Michael Collins et Henry Stern) a démontré que le modèle de Shannon, décrit ci-dessus, n'est pas un modèle précis d'entropie pour les mots de passe générés par l'homme. Je recommanderais de consulter la «Section 5 Génération de nouvelles politiques de création de mots de passe» pour des propositions plus précises.

Consultez le code source de KeePass au bas de cette page . La QualityEstimationclasse implémente un algorithme plutôt sympa qui semble être en ligne avec ce que vous cherchez à mettre en place. Mes résultats se présentent comme tels:

aaa                              8
aaaaaaaaa                        9
abcdefghi                       18
H0ley$Mol3y_                    73
s^fU¬5ü;y34G<                   99
[a^36]*                         10
[a^20]A[a^15]*                  18
Tr0ub4dor&3                     66
correct horse battery staple    98

Tu demandes

Plus précisément, quelqu'un peut-il penser à des situations où le fait de fournir un mot de passe à l'algorithme surestimerait sa force?

Mais vous avez un exemple dans la question. De par sa conception, xkcd2 a environ 44 bits d'entropie, mais votre estimation est de 160,5 bits.

Quelqu'un peut-il donner un aperçu de la faiblesse de cet algorithme? Plus précisément, quelqu'un peut-il penser à des situations où l'introduction d'un mot de passe dans l'algorithme surestimerait sa force?

Vous en avez fait allusion dans le préambule (attaques par dictionnaire, etc.). Essentiellement, l'attaquant peut deviner un certain nombre de pratiques courantes, ce qui réduit considérablement l'espace de recherche. Je suis presque sûr que votre algorithme "surestimera" les éléments suivants:

• partout
• Partout
• Partout1

Le mot de passe est assez long, mais il est trivialement craquable car le mot d'origine apparaît dans un dictionnaire de base, et les modifications sont considérées comme assez courantes pour faire partie de toute attaque décente par dictionnaire. Les conversions classiques de lettres -> nombres (par exemple 3v3rywh3r3) devraient également être considérées comme assez faibles, et vous devriez les pénaliser.

Dans une moindre mesure, d'autres mots de passe de dérangement peuvent être ceux qui ont des schémas évidents, tels que:

• abcdefghijklmnop
• abcde12345

Bien que ceux-ci soient probablement moins susceptibles d'être ciblés dans de véritables attaques par dictionnaire, ils souffrent de problèmes similaires à ceux de votre exemple "aaaaa ...".

Je ne sais pas si les expressions de mot de passe sont actuellement ciblées dans la plupart des attaques par dictionnaire, mais sans aucun doute à mesure qu'elles gagnent en popularité, elles seront de plus en plus ciblées. Je pense que le célèbre exemple xkcd en tient compte, car seulement 11 bits sont attribués à chaque "mot commun". Votre algorithme surestime également ces types de mots de passe.

Donc, pour résumer, l'algorithme fait un assez bon travail d'estimation, mais il devrait vraiment prendre en considération la structure du mot de passe et les modèles connus et courants.