Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Having read various resources about password strength I'm trying to create an algorithm that will provide a rough estimation of how much entropy a password has.

I'm trying to create an algorithm that's as comprehensive as possible. At this point I only have pseudocode, but the algorithm covers the following:

  • password length
  • repeated characters
  • patterns (logical)
  • different character spaces (LC, UC, Numeric, Special, Extended)
  • dictionary attacks

It does NOT cover the following, and SHOULD cover it WELL (though not perfectly):

  • ordering (passwords can be strictly ordered by output of this algorithm)
  • patterns (spatial)

Can anyone provide some insight on what this algorithm might be weak to? Specifically, can anyone think of situations where feeding a password to the algorithm would OVERESTIMATE its strength? Underestimations are less of an issue.

The algorithm:

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

A few inputs and their desired and actual entropy_bits outputs:

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"

The algorithm does realize (correctly) that increasing the alphabet size (even by one digit) vastly strengthens long passwords, as shown by the difference in entropy_bits for the 6th and 7th passwords, which both consist of 36 a's, but the second's 21st a is capitalized. However, they do not account for the fact that having a password of 36 a's is not a good idea, it's easily broken with a weak password cracker (and anyone who watches you type it will see it) and the algorithm doesn't reflect that.

It does, however, reflect the fact that xkcd1 is a weak password compared to xkcd2, despite having greater complexity density (is this even a thing?).

How can I improve this algorithm?

Addendum 1

Dictionary attacks and pattern based attacks seem to be the big thing, so I'll take a stab at addressing those.

I could perform a comprehensive search through the password for words from a word list and replace words with tokens unique to the words they represent. Word-tokens would then be treated as characters and have their own weight system, and would add their own weights to the password. I'd need a few new algorithm parameters (I'll call them lw, Nw ~= 2^11, fw ~= .5, and rfw) and I'd factor the weight into the password as I would any of the other weights.

This word search could be specially modified to match both lowercase and uppercase letters as well as common character substitutions, like that of E with 3. If I didn't add extra weight to such matched words, the algorithm would underestimate their strength by a bit or two per word, which is OK. Otherwise, a general rule would be, for each non-perfect character match, give the word a bonus bit.

I could then perform simple pattern checks, such as searches for runs of repeated characters and derivative tests (take the difference between each character), which would identify patterns such as 'aaaaa' and '12345', and replace each detected pattern with a pattern token, unique to the pattern and length. The algorithmic parameters (specifically, entropy per pattern) could be generated on the fly based on the pattern.

At this point, I'd take the length of the password. Each word token and pattern token would count as one character; each token would replace the characters they symbolically represented.

I made up some sort of pattern notation, but it includes the pattern length l, the pattern order o, and the base element b. This information could be used to compute some arbitrary weight for each pattern. I'd do something better in actual code.

Modified Example:

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

The exact semantics of how entropy is calculated from patterns is up for discussion. I was thinking something like:

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

The modified algorithm would find flaws with and reduce the strength of each password in the original table, with the exception of s^fU¬5ü;y34G<, which contains no words or patterns.

share|improve this question

migrated from codereview.stackexchange.com Oct 3 '12 at 12:03

This question came from our site for peer programmer code reviews.

2  
Have you seen tech.dropbox.com/?p=165? It may give you some ideas. There is a demo at dl.dropbox.com/u/209/zxcvbn/test/index.html and the code is on github. –  Bill Oct 3 '12 at 2:30
2  
xkcd.com/936 –  mouviciel Oct 3 '12 at 12:19
    
one option might be to run them through a compression algorithm and see how well they compress, the only catch here is that most compression algos are design to work with large amounts of data and you need one for small amounts of data –  jk. Oct 3 '12 at 13:00
1  
@mouviciel: I beat you to the punch. Read the first line :D –  Wug Oct 3 '12 at 13:20
    
@Wug - Great! I didn't follow the link: couldn't imagine that various resources covered that kind of studies! –  mouviciel Oct 3 '12 at 13:54

4 Answers 4

Check out the source code for KeePass at the bottom of this page. The QualityEstimation class implements a rather nice algorithm which seems to be in line with what you're looking to have in place. My results look as such:

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
share|improve this answer
    
Does this calculate entropy or some other metric, like perhaps bogofitness? Also you remembered to expand [a^36] into 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa' right? –  Wug Oct 3 '12 at 14:19
    
Er, no, I copied those strings verbatim :( I totally thought it was cool use of special characters, not a regex at first glance. I'll give it a shot again and update it. Secondly, it calculates bits of entropy, yes. –  Jesse C. Slicer Oct 3 '12 at 14:54
1  
It wasn't so much of a regular expression as weird notation I used to avoid having to enfatten my table by 25 characters –  Wug Oct 3 '12 at 15:04
1  
I had to +1 that comment for 'enfatten'. Seems like a perfectly cromulent word for this situation. –  Jesse C. Slicer Oct 3 '12 at 15:07
1  
It's actually spelled "KeePass", instead of "KeyPass." (I'd just make an edit myself, but they have to be more than 6 chars...) –  Ian Dunn Apr 15 '13 at 18:14

Can anyone provide some insight on what this algorithm might be weak to? Specifically, can anyone think of situations where feeding a password to the algorithm would OVERESTIMATE its strength?

You've hinted at some in the preamble (dictionary attacks, etc). Essentially, there are a number of common practices that can be guessed at by the attacker which greatly lowers the search space. I am pretty sure that your algorithm will "overestimate" the following:

  • everywhere
  • Everywhere
  • Everywhere1

The password is quite long, but is trivially crackable since the original word appears in a basic dictionary, and the modifications are considered common enough to form part of any decent dictionary attack. Typical letter -> number conversions (i.e. 3v3rywh3r3) should also be considered pretty weak, and you should penalise for these.

To a much lesser degree, other trouble passwords may be ones that have obvious patterns, such as:

  • abcdefghijklmnop
  • abcde12345

Although these are probably less likely to be targeted in actual dictionary attacks, they suffer from similar problems as your "aaaaa..." example.

I'm not sure if password phrases are currently targeted in most dictionary attacks, but no doubt as they gain popularity, they will be targeted more and more. I think the famous xkcd example takes this into account, since only 11 bits are assigned for each "common word". Your algorithm overestimates these types of passwords, as well.

So, to summarise, the algorithm does a fairly good job of the estimation, but it really should be taking into consideration the structure of the password and common, known patterns.

share|improve this answer
    
One level of derivative checking will identify all of those patterns. –  Wug Oct 3 '12 at 14:31

You ask

Specifically, can anyone think of situations where feeding a password to the algorithm would OVERESTIMATE its strength?

But you have an example in the question. By design, xkcd2 has ~44 bits of entropy, but your estimate is 160.5 bits.

share|improve this answer
    
So, generalizing, the algorithm breaks down when when considering words, or combinations of characters that are considerably more likely to be used than others. I'll also point out that the canonical xkcd example does not include spaces and my calculation did. –  Wug Oct 3 '12 at 13:27
    
@Wug, that's a fair generalisation. It's something which is tackled by zxcvbn, which is mentioned in the first comment on this question. –  Peter Taylor Oct 3 '12 at 14:50

Appendix A on p46 of NIST SP 800-63 talks about the work of Claude Shannon, who estimates password entropy using a number of bits. Indeed, this is the document that the XKCD cartoon uses to calculate the entropy bits. Specifically:

  • the entropy of the first character is taken to be 4 bits;
  • the entropy of the next 7 characters are 2 bits per character; this is roughly consistent with Shannon’s estimate that “when statistical effects extending over not more than 8 letters are considered the entropy is roughly 2.3 bits per character;”
  • for the 9th through the 20th character the entropy is taken to be 1.5 bits per character;
  • for characters 21 and above the entropy is taken to be 1 bit per character;
  • A “bonus” of 6 bits of entropy is assigned for a composition rule that requires both upper case and non-alphabetic characters. This forces the use of these characters, but in many cases thee characters will occur only at the beginning or the end of the password, and it reduces the total search space somewhat, so the benefit is probably modest and nearly independent of the length of the password;
  • A bonus of up to 6 bits of entropy is added for an extensive dictionary check. If the attacker knows the dictionary, he can avoid testing those passwords, and will in any event, be able to guess much of the dictionary, which will, however, be the most likely selected passwords in the absence of a dictionary rule. The assumption is that most of the guessing entropy benefits for a dictionary test accrue to relatively short passwords, because any long password that can be remembered must necessarily be a “pass-phrase” composed of dictionary words, so the bonus declines to zero at 20 characters.

The idea is that an authentication system would pick certain entropy levels as thresholds. For example, 10 bits may be weak, 20 medium and 30 strong (numbers picked arbitrarily as an example, not a recommendation). Unfortunately, the document does not recommend such thresholds, probably because the computational power available to brute force or guess passwords increases over time:

As an alternative to imposing some arbitrary specific set of rules, an authentication system might grade user passwords, using the rules stated above, and accept any that meet some minimum entropy standard. For example, suppose passwords with at least 24-bits of entropy were required. We can calculate the entropy estimate of “IamtheCapitanofthePina4” by observing that the string has 23 characters and would satisfy a composition rule requiring upper case and non-alphabetic characters.

This may or may not be what you are looking for but is not a bad reference point, if nothing else.

[Edit: Added the following.]

The paper Testing Metrics for Password Creation Policies by Attacking Large Sets of Revealed Passwords (by Matt Weir, Sudhir Aggarwal, Michael Collins and Henry Stern) demonstrated the Shannon model, described above, is not an accurate model of entropy for human generated passwords. I would recommend looking at "Section 5 Generating New Password Creation Policies" for more accurate proposals.

share|improve this answer
2  
the Wikipedia article on password strength states those rules were found to not be accurate for human generated passwords. –  Ryathal Oct 3 '12 at 12:29
1  
True (goo.gl/YxRk for an interesting read). –  akton Oct 3 '12 at 12:37
    
There is one caveat to this of course. It may be fairly accurate for statistically typical passwords, which tend to follow certain rules because people are people. These guidelines will not take into account the fact that randomly generated passwords will far outstrip human generated ones at typical lengths because they will (probably) contain no patterns and no words. –  Wug Oct 3 '12 at 14:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.