Passphrase Length

Mike

May 5, 2020 • 7 min read

I wanted to address a tweet posted today by the UK's National Cyber Security Centre advising people to use three random words as a passphrase.

When choosing your password, use #threerandomwords: memorable but not easy to guess, a good compromise between protection and usability https://t.co/6pEf004ohb pic.twitter.com/hnhKmmPdM8
— NCSC UK (@NCSC) May 5, 2020

While I understand and agree with the general concept, and it's something I've written about on Reddit before, I wanted to dedicate a post specifically to the length advertised here. If you want the TL;DR, assuming we're taking three random words just smooshed together, 3 is too short, aim for at least 5.

Edit: Something last minute that I wanted to throw in. If you're here looking for password advice, remember that it's more important not to re-use passwords, and my advice is to get and used a password manager. This was focused only on the length mentioned in this tweet, and it's still better advice than the standard 8-character-use-everywhere password most people have.

Show me the numbers...

Here's the math behind my reasoning. I'm going to use the dictionary available from MakeMeAPassword. That dictionary contains 17,103 entries. If we combine all these entries in every possible way, that would be 17,103^2 or a bit over 292 million. If we do this again, so we have every possible three-word entry, we have 17,103^3, or a bit over 5 trillion. That's a lot of possibilities! well... not really...

Using the hashes/second speed for NTLM (standard Windows hash) on my non-optimized Windows Desktop with an RTX 2080 Ti, I can make 27 billion guesses every second. At that rate, it takes me 183 seconds, or just a bit over 3 minutes, to test every possible combination.

So how about 4 words? 17,103^4 gives us 85 quadrillion combinations. For those of you paying attention, we're going up by factors every time (go back and read the Reddit post if you haven't already). We've gone from thousands to millions to trillions to quadrillion in 4 steps. This still isn't that difficult though. I would have to let hashcat churn away at combinations for just over 14 hours to try every possible combination.

At 5 words though, things change a bit. We add another power, 17,103^5, and get 1.5 sextillion combinations (1,463,394,702,729,450,000,000 to be precise). Our single RTX would have to chug away for about 28 years to try every possible combination.

Even if we bought eight RTX 2080 Ti's, optimized them to get up to 73 billion hashes/second, we would have to leave the system running for about 1 year and 4 months to get through every combination. Realistically though, we only have to crack the hash we're after, so statistically speaking, we should be able to get the plaintext password after only about 8 months. This still isn't impossible, but I'm going to say it's outside of my threat model. We picked the weakest possible hash, a dedicated cracking machine, and it would still take over half a year to crack. I would call 5 a minimum, longer is always better though.

Other issues we run into

Bringing things down closer to Earth, we have a lot of other issues to worry about. We have to somehow generate all of those combinations. Storing every two word combination isn't too bad, the list is only 4 GB in size. As we continue to exponentially increase though, we run into problems. My estimate is that every 3 word combination would take 84 TB of storage. Every 4 word combination, 1.4 exabytes. I think the only realistic way to get to 5 word combinations is to store every two word combination and then use combinator3.bin (from hashcat utilities) piped into hashcat to do something like this: combinator3.bin 2wordlist.txt 2wordlist.txt 1wordlist.txt | hashcat64.bin ... and.. ho boy does this affect cracking speed. A quick test brings me from the 27 billion guesses above down to about 1.2 million hashes/second. It seems to actually be faster running without the -O (optimized-kernel) flag. I assume this is because we aren't rejecting nearly as many candidates that are over the max length. As I said in the Reddit post, this is either going to take more space than is reasonable, more time than is reasonable, or both (I'm betting on option three).

At 5 random words, I believe we have moved things clearly outside the realm of what is possible for an average attacker. If you have a better way of attacking a password based on 5 random words, I would love to hear about it in the comments.

Qualifiers

We've made some assumptions here.

What if you're using some kind of mutator? Adding a number to the end, or randomly capitalizing a word. Well, I can still use rules with word combinations. The rule set I use will will dictate how much this affects the total time, but some back of the envelope math says that it will take just under a day to run every three word combination in conjunction with the best64 rule set. So I still don't feel like three words is enough. However, you've increased the time it would take for 4 words to 36 years.

What about the password storage algorithm? We're looking at NTLM, one of the fastest hashes available, what if hashes are being stored in bcrypt? I can't control, nor do I often know, what hashing method is being used to store my passwords. Thus, I opted for a worst case scenario here. Bcrypt, for those of you unaware, is a slow hashing algorithm designed for password storage. My 27 billion NTLM guesses/second drops to 26 thousand for bcrypt.

What if we're using MakeMeAPassword's phrase generator that I'm so fond of? We could theoretically reject everything that doesn't fit a sentence like structure. In other words, the phrase generator negatively affects the entropy (randomness) of the password being generated. I'm honestly not sure by how much though, so I can't answer the math side of it. However, the implementation problem you would run into is that you would have to write software capable of generating all of these guesses, at a rate of 27 billion per second, without duplication. I don't feel like it's impossible, but we've left behind the generic question of X words in a passphrase and entered the realm of a targeted attack.

What if the dictionary we pick our words from is larger? Smaller? Then cracking the password (assuming we know the dictionary used) will be easier or harder :P Since it's primarily the number of words used (which increases difficulty exponentially), as opposed to the size, I think the overall results will be the same. Diceware uses 7776 words. I'm also fond of the top 10,000 English word list. The short amount of research I performed says that the average active vocabulary is in the 20,000 word range, and the passive vocabulary is in the 40,000 word range. We had to start somewhere, and if people are making up passwords, they'll likely use words they know, so I think 17 thousand is a good dictionary for our purposes here.

What about online attacks/password spraying/etc.? We've approached this as an offline attack. We have direct access to the hashes, and we can try them as fast as our hardware and software allows. If we're looking at any form of online attacks, then yes, number of words becomes less important, and password reuse becomes more important. Again, use a password manager and forget 90% of this post.

What about rainbow tables? What about them, they're dead.

Summary

To reiterate my opening paragraph, attacking 3 words is easy. Attacking 4 is a bit harder, but doable. 5 words is can be cracked, but I'm calling it safe.

I've tried to keep the terms I used fairly general. If you see an inaccuracy caused by this, please let me know. Likewise, I did use a lot of password-cracking related terms, so if you don't understand something, leave a comment or get in touch with me and I'll be happy to clarify.