27

In XKCD #936: Short complex password, or long dictionary passphrase? Jeff claimed that password cracking with "dictionary words separated by spaces", or "a complete sentence with punctuation", or "leet-speak numb3r substitution" is "highly unlikely in practice".

However, there are certainly John-the-Ripper rulesets that perform l33t-speak substitutions and "pre/append punctuation or 1-4 digits (some are even included in the default set, and more are discussed e.g. at https://www.owasp.org/images/a/af/2011-Supercharged-Slides-Redman-OWASP-Feb.pdf, which talks about cracking ~50K "corporate" passwords using such techniques; http://contest-2010.korelogic.com/rules.html has some of the specific JtR rules used), and I can't see any reason why an attacker wouldn't use them.

Jeff used rumkin.com in part to justify his claim that Tr0ub4dor&3 is in practice as secure as a 4-word-from-2K-wordlist passphrase. But rumkin.com doesn't seem to take into account l33t-speak substitutions in determining the entropy.

So my question is: Are there any password strength checkers which take account of the limited entropy added by l33t-speak and similar substitutions and concatentations?

Ideally the rating would closely correspond with the amount of time that an actual attacker (using "state of the art" techniques, not just character-by-character brute-forcing) would take to find the password. Those techniques would include l33t-speak transformations, common passwords, wordlists, etc.

Open-source non-web-based preferred, for obvious reasons. While a good password generation algorithm (by definition) is secure even when the attacker has seen other passwords produced by the same algorithm, the idea is to point naive users at this checker, and the whole point is that their passwords are unlikely to have been generated via a sound algorithm.

Extra points if it learns from passwords submitted to it... unless it then automatically breaks into the users' paypal accounts and uses the money to fund Skynet...

Misha
  • 2,699
  • 2
  • 19
  • 17
  • 2
    I can imagine that a JtR ruleset would be ordered to try the rules that result in the smallest search-space first (commonly-used passwords, then common-password-words-with-minor-digit-variations, then l33t-sp34k, then markov-chain di/trichar patterns, etc.). The ruleset would include as many as possible of the "how to complexify your password" and methods found on the web. Possibly the order could be adjusted to take account of likelihood (e.g. based on how frequently they are found in password leaks such as gawker). – Misha Aug 23 '11 at 11:07
  • 2
    Obviously "run JtR on it with a really good ruleset" works as an implementation. Unfortunately if our aim is to be able to say "it would take JtR with a good ruleset >1 yr to find your password" then the checker response time (of up to 1 yr!!) may become an issue. We'd want to have a way to check whether a specific string matched a particular JtR (or equivalent) rule in O(len rule) time rather than O(number of possible matches). Does that exist? – Misha Aug 23 '11 at 11:11
  • I'm curious how do you intend to use such a password strength checker? It's probably going to tell 99% percent of the users "Pfft. Your password is weak". – Nikola Kolev May 20 '14 at 14:10

11 Answers11

13

In theory, password strength checkers do not work. That's because the strength of a password does not depend upon the password value (which you give to the checker) but upon the password generation process (which you do not formalize often, let alone enter in the checker).

In practice, password strength checker use a set of rules which describe common password generation methods; they then tell you how long your password would resist if the attacker uses exactly the same rules. But the attacker does not use exactly the same rules. The attacker is after you; he knows you (if you are attacked only by people who do not know you, then you can consider yourself very lucky -- or very uninteresting). Therefore, the attacker will amend his password brute-force methods so as to target your psyche, your probable password generation methods.

Password strength checkers are good at telling you how robust your password is against incompetent attackers. This has some value, if only because there are so many incompetent wannabe hackers. But it would be a mistake to rely too much on such tools.

Thomas Pornin
  • 320,799
  • 57
  • 780
  • 949
  • Why are you assuming that the attacker knows you, or is even after you. If a db is leaked, someone will certainly try to brute force the passwords even if they know nothing about you. What OP is suggesting would be possible to do, and while I don't really disagree with your answer, it's more like a comment than an answer since it doesn't really answer anything. – FINDarkside May 28 '18 at 13:27
9

Synthesizing the answers here, and from looking at the code for several of the (Javascript) password quality checkers, I don't believe there is a checker that fully meets the criteria.

Specifically, while there are several that use wordlists and several that special-case l33t-speak, there are none that do both together in a way that parallels JtR and similar "audit" tools. So "Christmas" is spotted, but the almost-as-insecure "Chr1stm4$" gets a free pass.

Where wordlists are used (Microsoft, Rumkin, How Secure ...), they are generally relatively small. How Secure ... and Rumkin each have ~10K, while JtR has millions of words (across multiple languages).

Also, none of the checkers I found treats the common "append digit/symbol" pattern as any different from "randomly mixed charsets".

If someone wants to extend one of the existing checkers, it probably wouldn't be too hard. Rumkin would be a good place to start (and is GPL licensed), by adding a "de-l33t-ify" step before both the dictionary check and the trigraph frequency lookup. One would also want to add some assumed factor in to reflect the fact that Chr1stma5 is not quite as easy to crack as christmas, e.g. by treating "l33t-ified" as a slightly bigger character set than "letters".

For a corporate environment, spending the time to implement a password change policy of "you get to keep your password until JtR guesses it" (combined with good advice on creating strong passwords/passphrases) would probably be a better persuader -- employees are a captive audience who need to always be able to log in, and people find forced password changes annoying so would soon learn not to use weak passwords (except the CIO who would demand an exemption...). That approach won't work with a public website where irritating your customers may drive them to (less secure!) competitors, though.

Misha
  • 2,699
  • 2
  • 19
  • 17
  • 4
    The "you keep your password until JtR guesses it" is actually a pretty good step. For password strength audits I always used to use JtR - passing JtR for 48 hours indicated a decent level for general purposes. Adding a rainbow tables check to cull the <9 char passwords means you can now use JtR to just look for 9 and over with dictionary/bruteforce – Rory Alsop Aug 29 '11 at 09:39
  • The checker: http://password-checker.online-domain-tools.com recognizes "l33t" as leet speech (it returns "Words 'leet' and 'l33t' are the same after applying leet speech rules."). It recognizes "Christmas" as a dictionary word. But it does not recognize "Chr1stm4$". – Martin Vseticka Feb 03 '13 at 12:57
  • 4
    Have you already tried [zxcvbn](https://dl.dropboxusercontent.com/u/209/zxcvbn/test/index.html)? – Gumbo Feb 24 '14 at 19:35
5

I think passwdqc package (by the creator of John the Ripper) should also be mentioned.

pwqcheck from that package is standalone password/passphrase strength checking program.

timoh
  • 499
  • 2
  • 9
3

zxcvbn, developed and used by Dropbox, nicely fits your criteria:

it recognizes and weighs (...) common patterns like dates, repeats (aaa), sequences (abcd), keyboard patterns (qwertyuiop), and l33t speak.

It is an open source JavaScript library with ports to many other languages. On its demo page you can see in detail how it extracts and weighs the different elements of a password, including removal of l33t speak.

Examples:

  • Tr0ub4dour&3 score 2 of 4, guesses_log10 = 4.97882
  • pVdOE&!@lj score 3 of 4, guesses_log10 = 10
  • correcthorsebatterystaple score 4 of 4, guesses_log10 = 14.43696

Note that as @Thomas Pornin's answer points out, the very idea of checking the strength of a password without knowing how it was generated is flawed. Still, password checkers might still help users choose better passwords, or even replace static rules about password composition.

3

The research paper by some of the researchers at CMU, Guess again (and again and again):Measuring password strength by simulating password-cracking algorithms, presents an analysis of the strength of various password policies for text-based password against password guessing.

The results of the paper suggest that basic16 policy (password must have at least 16 characters.) is superior than the comprehensive8 policy (password must have at least 8 characters including an uppercase and lowercase letter, a symbol, and a digit. It may not contain a dictionary word.). This, combined with the fact that basic16 is also easier to remember for users, suggests basic16 is the better policy choice.

Rahil Arora
  • 4,259
  • 2
  • 23
  • 41
3

In answers to this previous question on how to determine password entropy over on SU, three tools are mentioned:

How secure is my password seems to give reasonable results.

Rory Alsop
  • 61,367
  • 12
  • 115
  • 320
  • As a simple test, lets try some variations of "christmas" (plain lower case, initial cap, i->1). – Misha Aug 24 '11 at 19:09
  • Rumkin.com: plain = 29.9b ("common password!"), initial-cap = 36.3b ("common password!"), i->1 = 38.7b, s->5 = 38.1b, +& = 43.1b, +&3 = 46.7b. Rumkin uses a wordlist to detect "common passwords", BUT it doesn't reduce the entropy as a result. It does use character digraphs to estimate the entropy (based on English digraph frequencies), which will compensate for that to some extent. However, it doesn't take l33t-speak substitutions into account for either the "common word" or digraph frequency estimates. – Misha Aug 24 '11 at 19:23
  • How secure...: plain & initial-cap = instant ("in top 6910"), i->1, s->5 = 1 year, +& = 928 years, +&3 = 71K years. How secure... also uses a wordlist but doesn't use it to reduce its entropy estimate as such, and l33t-speak defeats it. It doesn't use diagraph-frequences so words score the same as alpha-gibberish the same length. – Misha Aug 24 '11 at 19:30
3

and I can't see any reason why an attacker wouldn't use them.

Can't speak for everyone but when I pen test I always do this. Personally I use the nice, simple CUPP but I'm aware of RSMangler too.

Rushyo
  • 627
  • 1
  • 5
  • 13
1

The best password meter that I've seen is Passfault. It's analysis takes the following into account:

  • Length
  • Presence in dictionary (English, Spanish). When searching it makes letter insertions and substitutions, backword writings, leetspeak substitutions
  • Repeated patterns
  • Keyboard patterns (horizontal, diagonal; English, Russian)
  • Date patterns
Andrei Botalov
  • 5,267
  • 10
  • 45
  • 73
1

This Microsoft Security Center password checker is one of the best. It encourages passwords that are actually better as far as entropy. It doesn't tell you much about how long it will actually take to crack and only increases a bar that says whether a password is "weak", "medium", "strong", or "best". Swapping letters for l33tspeak is taken into account. Try the XKCD entropy example - you'll see that the password checker follows the math.

Joe Hansen
  • 285
  • 1
  • 8
  • 3
    The Microsoft checker gives a "strong" rating to both Troubador&3 and Tr0ub4dor&3. Skimming the (javascript) source code, it does seem to be doing the right thing wrt l33t-speak and dictionary words but as a user I can't tell because the rating is so coarse-grained (only 4 grades). For example, password123, p455w0rd123 and 7as4w9rd123 are all "medium", and removing the last character from any of them results in a "weak" password. It doesn't seem to have a very long wordlist, and the rules for "best", "strong" etc. use the same "does it span enough character sets" heuristics other checkers use. – Misha Aug 23 '11 at 13:59
  • 2
    In particular, the Microsoft checker doesn't "follow the math" of the comic wrt to the (limited) entropy added by the l33t-ifying and punct/digit modifiers. It also doesn't use any math for the impact of length on security -- rather it has minimum lengths of 8 and 14 chars. – Misha Aug 23 '11 at 14:00
  • 1
    The password `11111111111111111111` gets a strong rating on this scanner. I wonder if there's a good computer program that finds bounds on Kolmogorov Complexity. Of course, KC won't be useful in practice, because it's only relevant for long strings ... but I still feel that if a proper encoding is used, compressible strings, using this encoding, should be detected as bad passwords. – ripper234 Jan 13 '12 at 06:06
  • KeePass rates it as 7 bits of entropy. – ripper234 Jan 13 '12 at 06:12
  • I like the KC idea, but unfortunately, KC is not computable (see http://en.wikipedia.org/wiki/Kolmogorov_complexity#Incomputability_of_Kolmogorov_complexity), whatever the string length. Compression algorithms provide an upper bound on KC - the trick is to choose a good compression algorithm. We'd want the algorithm to "know" all the dictionary words, as well as how to make l33t, suffixed, etc. combinations. That algorithm is basically JtR, isn't it, where the compressed result is the index in the list of attempted passwords? – Misha Jan 14 '12 at 01:55
0

You can try KeePass , it has a built in password strength checker.

  • Tr0ub4dor&3 - 66 bits of entropy
  • correct horse battery staple - 98 bits.
  • 11111111111111111111 - 7 bits (unlike the Microsoft scanner that gives it a "Strong" rating).
  • asdfasdfasdfasdfasdf - 30 bits
  • asdffdsaasdffdsaasdf - 35 bits

And oddly enough:

  • Pas - 18 bits
  • Pass - 3 bits
  • Passwor - 38 bits
  • Password - 6 bits

So it seems to take common passwords into consideration.

ripper234
  • 1,126
  • 1
  • 8
  • 11
  • But (like most of the others) any l33t-speak defeats its "common passwords" list, and it also doesn't use diagraph/trigraph frequencies for "english-like" character sequences. – Misha Jan 14 '12 at 01:49
0

I like http://password-checker.online-domain-tools.com

  • Provide brute-force attack statistics
  • Provide password statistics (unicode characters are recognized, mostly they are considered as symbols)
  • Common passwords are checked. If your password is in the list then the final score is 0.
  • It allows you to do a dictionary check too.

I noticed that the http://www.passwordmeter.com/ tool has a few bugs. One of them is that really long passwords have strength 0 (e.g., 65946555555555555555555555555555555554656465466666666666666666664444444444). So the calculation of the final strength is suspicious to me.