Kind of counters the idea from this xkcd comic that longer passwords are better, even when they just contain dictionary words:
A single AMD Radeon Pro Duo graphics card can perform an estimated 8 billion guesses per second on the password hashes (unsalted SHA-1). A sub $10000 cracking rig with four of them can do 32 billion per second. That would mean the 550 year guessing time of XKCD's example password has been reduced to 9 minutes due to sheer computation power alone [1]. This is why it's important for everyone to use a slow and salted password hashing function (Argon2, scrypt, bcrypt, PBKDF2) to make sure that GPUs cannot guess hashes so terribly efficiently.
Note that this even ignores any benefits attackers have had cracking a large amount of unsalted passwords, which will have been substantial.
[1]: Edit: Looking up the current status quo, a single Nvidia GTX Titan XP can do almost 12 billion hashes per second in oclHashcat, that's 48 billion hashes per second for your cracking rig. Down to 6 minutes it is.
I doubt any web service lets you try 32 billion logins/sec.
Limit attempts to 1 per second per user ID, and block IPs with 50 consecutive failed attempts per user ID. These should be invisible to a human, but totally stop the brute force of any but the most obvious passwords.
These don't seem like they would be difficult to do, but I am shocked at how few web apps do this. Last I checked, Wordpress ships with no limits at all on login attempts, for example.
scrypt should be about in that order of magnitude even on modern hardware.
The point of the comic is that a character salad is both less secure and harder to remember than four random dictionary words. That's no less true today.
The MD5 hash of "correcthorsebatterystaple" might be trivial to brute-force today, but it is - and always will be - harder to brute-force than "Tr0ub4dor&3", even if in both cases the attacker knows how you generated the password.
(john manages 24 million hashes/second on my five years old laptop for that, even crypt(3) with md5 is three orders of magnitude harder to brute force.)
To illustrate, suppose you have a word list of 8,192 entries, and a cryptographically secure random function. Shannon entropy says that each word in that list then contains exactly 13-bits of entropy (2^13=8,192). According to https://gist.github.com/epixoip/a83d38f412b4737e99bbef804a27..., 8 Nvidia GTX 1080 GPUs with Hashcat 3.0 can process 200 billion MD5 hashes per second, which means 5 of those password cracking rigs, working in concert, can do 1 trillion MD5 hashes per second.
So, if you have a cryptographically secure random function choosing your words from that list of 8,192 words, what are we looking at?
- 1 word (13-bits): 1 in 8,192 possibilities
- 2 words (26-bits): 1 in 67,108,864
- 3 words (39-bits): 1 in 549,755,813,888
- 4 words (52-bits): 1 in 45,03,599,627,370,496
- 5 words (65-bits): 1 in 36,893,488,147,419,103,232
- 6 words (78-bits): 1 in 302,231,454,903,657,293,676,544
There is no need to go any higher than that, as we'll see in a second. If the password cracker is only interested in searching 1/2 of the total combinations, then that means at each hash, after completion, there is a 50% probability that the password was found (on average). So, armed with this, it would take the password cracker:
- 13-bits: < 1 second to search 1/2 the space
- 26-bits: < 1 second
- 39-bits: ~ .3 seconds
- 52-bits: ~ 38 minutes
- 65-bits: ~ 213 days
- 78-bits: ~ 4,792 years
It's reasonable to conclude that if your threat model is password cracking clusters working on leaked hashed password databases, and assuming the password is hashed with MD5, then at least 65-bits of entropy, or 5-6 words chosen from a list of 8,192 with a cryptographically secure random function, is a good target for a secure passphrase length.
For what it's worth, Diceware has been promoting this approach for years now, where the word list is 7,776 entries (~12.93-bits of entropy per word), and the cryptographically secure random function is 5 fair 6-sided dice. The XKCD "correct horse battery staple" approach is just a simplified implementation, forgetting the random factor.
https://www.schneier.com/blog/archives/2014/03/choosing_secu...
> This is why the oft-cited XKCD scheme for generating passwords -- string together individual words like "correcthorsebatterystaple" -- is no longer good advice. The password crackers are on to this trick.
If your password can have arbitrary length (or arbitrary enough, about ~120 letters), you can generate a 128 bit password with dictionary words as tokens. Sure, the password will be much longer (factor ~6), but also much easier to memorize.
The comic proposes that correcthorsebatterystaple would be a secure password. It is 26 characters long and contains 4 basic english words that would be in even the smallest of dictionaries. Let's say a dictionary with 100.000 entries contains these words. Combining 4 words in the dictionary gives you 100,000^4 = 1.e+20 possibilities. Not bad, but let's say 15 random uppercase and lowercase (like the first letters of every word in a phrase like Schneier proposes) letters give you (26+26)^15 = 5.49e+25, still 5 orders of magnitude better.
Edit: a phrase with 26 words in to take each letter from indeed isn't doable to remember, changed it to 15.
The Schneier method is basically equivalent but with important caveats: 1) Such a phrase is not randomly chosen but follows at minimum basic English grammar and at worst is well-known and thus part of the attacker's dictionary and 2) even if that is taken account for the first letters are not distributed uniformly across the alphabet, you just need to take a look at any (printed) dictionary. That greatly reduces entropy and makes it hard to reliably estimate entropy.
I've been generating all my (memorized) passwords from a 120k word dictionary for years now, can't complain. And estimating the entropy is easy.
But for "take the first letters in an English phrase" you can't just do (2*26)^{length} or you are way overestimating.
Entropy. It's all about entropy calculation. There is no trick.
Look at it this way:
- choose 68 bits at random. This is findable by a nation state; if they are your adversary, add a couple more words. - split those bits into 4 17-bit numbers (17 bits has a maximum of about a hundred thousand) - your password is 4 words from a hundred thousand word dictionary - there is no trick: you've encoded 68 random bits securely, and guessing just those bits is pretty impossible.
Schneier is normally sensible but calling entropy a "trick" is idiocy.
https://github.com/creshal/yspave/blob/master/yspave/pwgen.p...
A password generator does not care whether its input alphabet is \d, \w, all emoji codepoints, or `cat /usr/share/dict/words`. You determine the entropy of it, and then output as many tokens as needed. It doesn't matter whether an attacker has a copy of your input alphabet, or knows your algorithm. You defeat him by setting the entropy bar high enough (and using a cryptographically secure RNG to generate it).
But a random selection of /usr/share/dict/words (~120,000 entries on Arch Linux) will be easier to memorize than a random selection of the ascii printable range.
If I choose 4 words from a dictionary of 50,000 words [1] that produces 50000^4 possible passphrases. That's equivalent to 62 bits of entropy, or a 10-character [a-zA-Z0-9] password. About 8 years to brute force on MD5 with 2x AMD HD 6990. And obviously an extra word makes it take thousands of years.
It's not ideal, but it's better than a lot of password advice.
[1] cat /etc/dictionaries-common/words | grep -v "'s" | egrep -v 's$' | wc -l gives me 51726
Why filter those out?
Why?
I doubt many people are taking away from that comic that they should use software to reliably randomly choose the words they memorize. Instead the advice seems to usually get shrunk down to "choose 4 random words," i.e. out of your own head. Most people don't carry 50,000 word dictionaries around in their heads. More like a few thousand. That changes the math considerably.
(For the record I do use the "4 random word" method for some passwords I want to be able to remember without having to open up my password manager. But I have nagging doubts about its security vs. random strings.)
grep --perl-regexp '^[a-z]{5,8}$' /usr/share/dict/words | shuf -n 5 | tr '\n' ' '
I memorize 3 passwords and they are extremely hard. The rest are not created by me and I don't have repeated passwords.
Not everyone is a masochist. It doesn't matter whether you encode 128 bit entropy in a base95 string, or a list of ~8 random words, it's still 128 bit entropy… but the word list will be easier to memorize and to type out.
Zero. Why would I bother memorizing them?
> How many passwords are you going to memorize
The LUKS password for my home laptop, the LUKS password for my work laptop, logon passwords words for each, and password manager master passwords for each. I guess I could move some of these to hardware keys, but I'm too lazy.
> how are you going to not repeat a password?
The same anyone is not repeating passwords: Strong password generators.
So why are you disagree with me?