How Strong Is Your Password, Really? The Math of Cracking

In 2011 the webcomic xkcd compared two passwords. One was Tr0ub4dor&3, a dictionary word with a capital letter, a few letters swapped for digits, a symbol and a number on the end, the kind of password most sign-up forms push you towards. The other was correct horse battery staple, four ordinary words. The comic's author, Randall Munroe, estimated the first at about 28 bits of strength and the second at about 44, and pointed out that the second is also much easier to remember. Security people have quoted the comic ever since, because the arithmetic behind it is right.

Illustration: each extra character multiplies the combinations an attacker has to try.

Counting guesses

The strength of a password is the number of guesses an attacker would need to find it. Because those numbers get very large, it is usually written in bits: each bit doubles the count. Ten bits is 1,024 possibilities, twenty bits about a million, forty bits about a trillion.

If every character is chosen at random from a set of R characters and the password is L characters long, there are R^L possibilities, which is L × log₂R bits. A random 8-character password using all 94 printable keyboard characters comes to 52.4 bits. A random 12-character password using only lowercase letters comes to 56.4 bits, slightly more, even though it uses no capitals, digits or symbols. Each extra lowercase letter multiplies the total by 26. Widening the character set from 26 to 94 multiplies each position by only about 3.6.

Passphrases work the same way, with words in place of characters. The Electronic Frontier Foundation publishes a list of 7,776 words for picking passphrases with dice; five dice give one word, and each word adds 12.9 bits. Four words from that list give 51.7 bits and six give 77.5. Munroe's 44 bits assumed a list of 2,048 common words.

People are not random

Those figures only hold if the password really was chosen at random. Human-chosen passwords aren't, and attackers know it. In 2012 the computer scientist Joseph Bonneau analysed about 70 million Yahoo passwords, collected anonymously with the company's cooperation. He estimated that against an attacker guessing in the best possible order, the passwords offered fewer than 10 bits of security against online guessing and only about 20 bits against an offline attack. That is the gap between what the formula promises and what people actually choose.

Attackers try dictionary words and keyboard patterns first, because that's how people choose passwords. Photo: Abdelrahman Ahmed / Pexels

Cracking tools are built around that gap. Hashcat and John the Ripper start with dictionary attacks: real words, names and, above all, lists of passwords leaked in past breaches, such as the 32 million exposed by RockYou in 2009. Then come rule-based attacks, which take each word and apply the changes people habitually make: capitalise the first letter, swap a for @ and o for 0, add 1 or ! or a year to the end. Mask attacks try common shapes, such as one capital, five lowercase letters and two digits. Tr0ub4dor&3 falls to a dictionary word plus a few standard rules. That is why Munroe rated it at 28 bits and not the 72 that its length and character mix would suggest.

Composition rules make this worse. Asked to include a capital and a number, most people put the capital first and the number last. A 2011 study at Carnegie Mellon University by Saranga Komanduri and colleagues compared password policies on thousands of volunteers. Passwords made under a simple "at least 16 characters" rule were harder to guess than those made under an 8-character rule demanding upper and lower case, a digit, a symbol and no dictionary words, and people found them less annoying to create.

How fast the guesses come

The other half of the sum is speed, and that depends on where the attacker is guessing. Through a website's login page, the site controls the pace. NIST's digital identity guidelines require a service to lock a password after no more than 100 failed attempts in a row. At that rate, even a modest password lasts.

A stolen database is different, because the attacker can test guesses against the stored hashes on their own hardware as fast as it will go. Using published Hashcat benchmarks for a single Nvidia RTX 4090 graphics card, here is how long it would take, on average, to find a randomly chosen password:

• 8 random characters from all 94: about 5 hours if the site used MD5, about 500 years if it used bcrypt at a low cost setting.
• 12 random lowercase letters: about 3 days with MD5, about 8,000 years with bcrypt.
• Four random words from a 2,048-word list: under a minute with MD5, about a year and a half with bcrypt.
• Six words from the EFF list: about 21,000 years with MD5, and far beyond any meaningful time with bcrypt.

Two things stand out. The way the site stores passwords matters as much as the password; our piece on how passwords are stored explains why. And an attacker with a room full of these cards, or rented cloud time, can divide every figure by a hundred or more, which is why the larger margins are worth having.

With stolen hashes offline, GPUs can test guesses far faster than any login form allows. Photo: Nana Dua / Pexels

What the numbers recommend

The current version of NIST's guidelines, SP 800-63B, follows the same arithmetic. It requires passwords used on their own to be at least 15 characters long, tells services not to impose composition rules or force periodic changes, and asks them to check new passwords against lists of common and breached ones. Those are much the same conclusions the numbers above lead to.

For your own accounts, three habits do most of the work. Use a different password on every site, so a breach at one gives an attacker nothing to try elsewhere. Make passwords long and random, either generated by a password manager or a passphrase of five or six words picked by dice or a random generator, not by you thinking of words. And turn on two-factor authentication where it's offered. The Pythous password generator makes random passwords and passphrases in your browser, and the password strength checker estimates how a given password would fare against the attacks described here.

Sources

1. Randall Munroe, "Password strength", xkcd 936, 2011. https://xkcd.com/936/
2. Joseph Bonneau, "The science of guessing: analyzing an anonymized corpus of 70 million passwords", IEEE Symposium on Security and Privacy, 2012: 538–552. https://doi.org/10.1109/SP.2012.49
3. Saranga Komanduri, Richard Shay, Patrick Gage Kelley, Michelle L. Mazurek et al., "Of passwords and people: measuring the effect of password-composition policies", CHI 2011: 2595–2604. https://doi.org/10.1145/1978942.1979321
4. National Institute of Standards and Technology, SP 800-63B, Digital Identity Guidelines: Authentication and Authenticator Management. https://pages.nist.gov/800-63-4/sp800-63b.html
5. Electronic Frontier Foundation, "EFF dice-generated passphrases". https://www.eff.org/dice
6. Hashcat wiki, "Mask attack" and "Rule-based attack". https://hashcat.net/wiki/doku.php?id=mask_attack
7. Chick3nman, "Hashcat v6.2.6 benchmark on the Nvidia RTX 4090", 2022. https://gist.github.com/Chick3nman/32e662a5bb63bc4f51b847bb422222fd