I’m in the process of adding a password strength gauge into my current pet project Guten Pass, and wrote this piece to make sure I knew what I was talking about when it comes to password strength…
Hold the press! I need to revisit the calculations in this article…
(I should’ve gone back to first principles to check them all)
As outlined in these xkcd comics, passwords are a tricky thing:
Many security experts are now using the phrasing “Threat Modelling” as a way to justify the kinds of steps that should be taken to ensure your data is safe as it can be. This of course, gives rise to a whole slew of opinions and counter-arguments suggesting that one way is better than some other way. As mentioned by the user ‘Hybrid’ in Security StackExchange who humorously says:
If you get 10 computer security professionals in a room and ask them how to come up with good passwords you will get 11 different answers.*
They go on to describe this problem being outlined here. That the issue of security depends upon what “you’re trying to defend against” [ibid]. I’m here to suggest #12: use a random custom dictionary.
The “correct battery horse staple” comic above illustrates how longer strings in general are both easier to understand, and have more bits of entropy, making such a choice a win-win for many threat modelling instances. Unfortunately, some security experts, such as Bruce Schneier have stated numerous times that word lists such as this are not very good, as the “password crackers are on to this trick.” Mr Schneier then goes on to elucidate how 90% of a list of 16,000 passwords was cracked back in ~2013. Admittedly they were only MD5 passwords, but this is actually a vital part of our Threat Modelling requirements, as will later be shown. He then goes on:
There’s still one scheme that works. Back in 2008, I described the “Schneier scheme”:
So if you want your password to be hard to guess, you should choose something that this process will miss. My advice is to take a sentence and turn it into a password. Something like “This little piggy went to market” might become “tlpWENT2m”. That nine-character password won’t be in anyone’s dictionary. Of course, don’t use this one, because I’ve written about it. Choose your own sentence — something personal.
This, while not bad advice, in my opinion does not gratuitously cover enough problems to be generally recommendable. In today’s GPU accelerated cracking algorithms, such passwords are doomed to failure in the long run, simply because of the lack of entropy. Running the password Mr Schneier mentions in the article (tlpWENT2m) through a well-known password strength checking facility on rumkin.com, it gets a “Reasonable” rating, with 40.9 bits of Entropy listed. By comparison, the same site lists “correct battery horse staple” as 104.2 bits of entropy, more than twice that of Mr Schneier’s demonstration one.
In all fairness however, I have a password that I used to use everywhere and it’s modelled in a similar fashion to Mr Schneier’s (but preceding his claim to naming it). It has never appeared in any password list, including haveibeenpwnd.com. The password’s been ‘out there’ since the late 90’s and is awaiting the right website(s?) to be compromised for it to be generally known.
The problem, is that making unique passwords is hard, and without the use of a password manager, humans are not very good at making unique ones, nor at remembering them. This is why we tend to use the same password in more places than we should. This is why password managers these days are so vital.
The next xkcd comic highlights how dangerous it is to use the same password on multiple site, and how bad humans are at being unique, and how you really shouldn’t trust the security model of any website:
The ironic thing about the above comic, is there’s an article that goes into depth about some of the passwords that were leaked in the Adobe list which found a reference to Edward Snowden and his (likely) password (for that website).
In the last few years we’ve had an enormous amount of passwords being gleaned from various website databases, both unencrypted, but also hashed. The Adobe leaks show quite clearly that even the big companies can get correct password storage horrifically wrong. There’s little reason to assume that we’ll be seeing less websites being hacked for their user information, and so it’s rather reasonable to assume that this ever increasing threat to individual users will increasingly require unique passwords on every site in order retain a little bit of security.
Two Factor Authentication
Many of the larger sites are now offering 2FA or Two Factor Authentication, which is one of the ways to combat any issues that might arise from having your passwords leaked onto the Internet. From a high level perspective, this might seem to be a reasonable approach, and yet we’re increasingly seeing how attacks are being made against such systems, particularly mobile 2FA (TODO references). Then there is the dark anti-pattern of giving extra personal details to websites (such as your mobile number). There’s also the false dark pattern in having a false sense of security with using 2FA, because it promotes the idea that the password isn’t as important. This makes it easier for people to be complacent about passwords and to re-use them, or to use simple-to-crack ones.
2FA should not be the ‘final arbitrator’ in proving ownership of a particular account on a website. It should be treated as just one other key factor, just as the old nuclear missile silos needed two people with two keys to trigger a launch.
It should be noted that Timed One Time Passwords (TOTP) are a simple and effective way of having a 2FA system that does not compromise personal information, and still give a relatively good sense that the person attempting to login is actually who they say they are. Unfortunately, many password managers are now building in TOTP support so that you don’t need to use any other facility. Many security researchers (TODO reference) make the obvious statement that such inbuilt systems are not adding to your security at all. Why? Because if you’re already using a password manager, and using unique passwords, then any 2FA system is an adjunct and useful only if the attacker has gained access to your password (presumably via other means other than from your password manager directly). Any kind of 2FA is only useful if the attacker does not have access to your physical devices (including password manager or physical 2FA device). A good password will always be difficult to brute force, making the need for 2FA less relevant for a range Threat Models, and possibly irrelevant for quite a large range of possible threats.
Entropy is all in the word
“The entropy is a statistical parameter which measures in a certain sense, how much information is produced on the average for each letter of a text in the language. If the language is translated into binary digits (0 or 1) in the most efficient way, the entropy H is the average number of binary digits required per letter of the original language.”
https://csrc.nist.gov/publications/detail/sp/800-63/ver-102/archive/2006-04-30
What constitutes a good password though? Uniqueness is clearly a key facet. Ability to be resilient against dictionary and brute force attacks has been a must for many years, and is why websites have been gradually increasing the requirements for passwords. But technology is progressing faster than our ability to make up a password which will make brute force methods infeasible. Length of string, even if just using western A-Z characters, is proving to be a dominant factor in ensuring brute-force resilience. And this is where Bruce Schneier’s repeated comments about the need for non-alphanumeric characters come in: extra characters add entropy, a level of uncertain-ness, on where a particular password cracker should start. Using a randomly generated password where each character is given a choice of in 1 in 72 (if we had 10 symbols), the resulting password will have an entropy of just over 6 bits per character.
However, most security researchers seem to have their blinkers on when it comes to passwords: we don’t all speak the same language, and assume that a-zA-Z0-9 and a few symbols are all one needs to generate a high entropy password.
We live in the world of unicode however, far beyond the borders of the old ASCII table which most password generators use. If we were to to just add emoji support into a random password generator, we’d gain an extra 1,311 possibilities, per character, giving a staggering entropy of 10.4 bits. Mr Schneier’s password of 9 letters would then yield 93.9 bits of entropy, if he replaced one character with a random emoji.
And yet if we add whole dictionaries to the task, (while still maintaining the small world view that A-Z is all the letters you get) you can easily have a dictionary size of over 100,000. The Oxford Dictionary is reported to have over 300,000, which is 18.2 bits of entropy per word.
It seems to me that this is where Mr Schneier seems to have a blind spot: it doesn’t matter what the (English) word is, whether it has 1 character or 15, if each word is treated like a character (from an Entropy calculation perspective), then it’s extremely dense!
Even better is if the attacker does not know that you’ve used this method, then the entropy races upward very quickly, such that “correct battery horse staple” using brute force methods, yields 133 bits (28 letters of 27 possibilities), whereas a dictionary attack is (assuming a small dictionary of 5000 words) is 49.1 bits.
Gutenberg as a dictionary source
It’s important to remember two facets: English is not the only language out there. English has also been morphing and changing from the day of inception. This means that there are a lot of sources of language that can be used in order to build a dictionary. Imagine having a custom dictionary where even if the attacker knew that you’d used a mere 1000 words to build upon (entropy is 9.9 bits per word), would still yield a 39 bit password for four words. If the attacker didn’t know which dictionary you used, but you used a non-modern one (or greek, or russian, or latin, etc), then the entropy blows out rather significantly. In fact, I don’t know how to effectively calculate the entropy per word for such a system, it’s so large – but would definitely be in excess of the Oxford Dictionary’s 18 bits per word. (Below, I give a poor attempt)
This is why I like the idea of using Project Gutenberg to build custom dictionaries: it has 60,000 books on it’s site, and quite a lot do not use Modern English (British nor U.S), not that it overly matters. It’s quite feasible that many have typographic errors too, which also adds to any uniqueness factor. And then there are the other languages (15 other languages with more than 50 books). Books such as:
- 老子 by Laozi (Chinese, 1159 unique words, 10.1 bits per word)
- Αθηναίων Πολιτεία by Aristotle (Greek, 8616 unique words, 13 bits per word)
- The Book of Quinte Essence or the Fifth Being (Middle English, 2681 unique words, 11.4 bits per word)
- Gwaith Twm o’r Nant by Thomas Edwards (Welsh, 4356 unique words, 12 bits per word)
Of course, as security minded people, we must always assume the worst: that the attacker knows everything about the system they’re about to crack to the password for, which is why the unique word counts on each book should be used as a worst-case scenario. But in the case that the attacker assumes Modern English dictionary only, the attack will fail, 100% of the time, and will need to resort to brute forcing the complete Unicode table for as long as the string is (typically around 28 characters). Since UTF-8 has 1,112,064 code points (20 bits per char), this means 28 characters becomes a 562 bit nightmare to brute force. This is clearly an over-estimation, but it’s unclear on how brute force would need to engage in such problems otherwise.
Effective Threat Modelling
For Guten Pass, I’ll allow the user to select their threat model from the following options:
Ultra paranoid
In this model Guten Pass will assume that not only are the local dictionaries knows, but also every setting that made up the password. This will reduce the dictionary sizes typically by about 80% (depending upon word lengths chosen). And even though Guten Pass has a ‘Random’ selection for the choice of dictionary, it will be assumed that the attacker knows (somehow) which one was chosen. This threat model is suitable for most Evil Maid style attackers, who have physical access to your machine and possibly observed the password being generated.
Relaxed paranoia (the default)
This will have a slightly relaxed view on the dictionary being used where we assume that the attacker doesn’t know the specifics of any settings we used for a password. This method will use all available words in the source text, giving a slightly higher entropy than Ultra Paranoid. This threat model is similar to above, but allows greater entropy of ‘Extra Randomized Words’ setting, that is, randomly choosing 5 words, instead of 4. This is suitable for Evil Maid attackers who are not present in the room at the time of password generation.
Website Dictionary Attack
This threat model makes no assumptions about any text you have selected, but assumes that the attacker will perform a comprehensive dictionary attack on your password if it’s discovered in some website’s database (as a hash). The best defence in this case would be to choose non Modern English texts to gain bullet proof passwords. Of course, your password security is dependent upon the security implemented by the website where your password might be found, so make sure your passwords are unique on every site!
Website Brute Force Attack
If you’re sure your attacker will be script kiddies hammering away at 12-16 length passwords before trying a longer dictionary attack, this is the appropriate threat model for you. Like the above model, your password is as secure as the website that it’s stored on, so make sure it’s unique!
Conclusion
So, we’ve seen how choosing 4 words from a small dictionary can yield what is generally regarded as a reasonable password, even in worst case scenarios. My project Guten Pass is, honestly, overkill. Considering that it’s being distributed as a browser plugin, you’d need to place a whole lot of faith in me and my code and the browser environment in order to faithfully trust it… but you can always use the code I developed for Wordish, to roll your own Gutenberg style generator and use it from the command line.
Some references:
https://security.stackexchange.com/questions/62832/is-the-oft-cited-xkcd-scheme-no-longer-good-advice
https://www.explainxkcd.com/wiki/index.php/936:_Password_Strength
https://www.grc.com/sn/sn-313.htm#!s!math%20is%20wrong
https://7habitsofhighlyeffectivehackers.blogspot.com/2013/11/can-someone-be-targeted-using-adobe.html
-
*https://security.stackexchange.com/questions/62832/is-the-oft-cited-xkcd-scheme-no-longer-good-advice