on
Algorithmic passwords - Memorable, high entropy, and unique
Background
Passwords… ugh. I would wager that passwords rank among many peoples least favorite topics, but they are an integral part of life and therefore warrant discussion.
Back in 2003 NIST published authentication guidelines for the US Federal government. Those requirements are largely responsible for password requirements for the last 15 years. In typical NIST fashion the document is comprehensive, includes threat models, mitigations, and detailed requirements. For their purposes a password is referred to as a “Memorized Secret Token” and the relevant threats and mitigations are:
| Threat | Description |
|---|---|
| Duplication | The Subscriber’s token has been copied with or without his or her knowledge. |
| Eavesdropping | The token secret or authenticator is revealed to the Attacker as the Subscriber is submitting the token to send over the network. |
| Phishing or pharming | The token secret or authenticator is captured by fooling the Subscriber into thinking the Attacker is a Verifier or RP. |
| Social engineering | The Attacker establishes a level of trust with a Subscriber in order to convince the Subscriber to reveal his or her token or token secret. |
| Online guessing | The Attacker connects to the Verifier online and attempts to guess a valid token authenticator in the context of that Verifier |
Offline cracking is in the threat table but interestingly is only applied to keys! There is no strict requirement for salting password hashes (though hashes are required, plaintext password storage is not allowed), and rainbow tables are never mentioned. Dictionary attacks are mentioned, and therefore the guidance is to ban dictionary words from passwords. To increase entropy the guidance requires the familiar lower-upper-numeral-symbol pattern that so many of us loathe.
In 2003 it was probably not imagined that we would have accounts on literally 100’s of systems so having a handful of 8 character complex passwords that change every 90 days did not seem arduous.
The ultimate result of this is famously summarized in this excellent xkcd comic:
The only problem with the suggestion is that you cannot (or should not) use “correct horse battery staple” for every site you have a password on.
Algorithmic Passwords
With the background out of the way, let’s come up with some new threats:
Offline cracking | Cracking secret hashes offline, either with rainbow tables or brute forcing Secret reuse | Using secrets on multiple sites, whereas one site getting hacked allows an attacker access to other sites Duplication | Paper or a file containing passwords is copied without user knowledge Online Guessing | Adversary attempts to brute force password on the site
At this point I’ll mention what probably every reader is thinking, duh, just use a password manager. I will write another post on my thoughts on password managers, this article is actually meant to feed into that one.
So, algorithmic passwords are meant to mitigate the threats listed above. In order to mitigate offline cracking we need high entropy passwords that are unlikely to show up in rainbow tables. To mitigate reuse the passwords need to be different for each site. To mitigate duplication these passwords will not be stored on paper or in a file. To mitigate online guessing the passwords should be high entropy. Ready? Let’s go.
Additionally passwords will need to meet the ‘standard’ complexity requirements, since those are still widespread.
Level 1
The absolute simplest way to approach this (and not actually recommended by me) is to build a password pattern and integrate the site name somehow. Something like this:
A1!<sitename>2@
This will meet most complexity requirements, a capital letter, 2 numbers, and 2 symbols. Some examples and their respective entropy:
| Site | Password | Entropy (bits) |
|---|---|---|
| A1!google2@ | 49.5 | |
| Bank of America | A1!bankofamerica2@ | 82.3 |
| Lyft | A1!lyft2@ | 40.2 |
You can see that there is a dramatic difference in entropy. 40.2 bits is pretty low. grc estimates that it could be cracked on a massive cracking array in 1.77 hours. This, of course, will go down over time.
We need something that increases the entropy, and makes the entropy more consistent.
Level 2
A sentence or random words with the site name, and other complexity requirements is an easy way to increase entropy!
| Site | Password | Entropy (bits) |
|---|---|---|
| 1! Correct Battery Google Horse Staple | 186.1 | |
| Bank of America | 1! Correct Battery Bankofamerica Horse Staple | 219.1 |
| Lyft | 1! Correct Battery Lyft Horse Staple | 176.7 |
The entropy still varies somewhat but it so high it is unlikely to matter. grc estimates the lyft password will take “5.07 hundred billion trillion trillion trillion centuries” on a massive array now. Probably secure enough for now :)
It should be noted that some terrible sites do not allow spaces. This strategy may require _ in place of space.
The problem with this strategy is that, while a machine is very unlikely to brute force these passwords, a targeted attack by a dedicated attacker will easily notice the pattern and be able to log into other sites. Therefore, this only partially mitigates the reuse threat.
Level 3
Words are clearly advantageous from an entropy point of view, but how do we make passwords less guessable?
Let us create a dictionary of letter-word mappings:
| letter | word |
|---|---|
| a | asteroid |
| b | batcave |
| c | clarify |
| … | … |
| e | elephant |
| f | fruitfly |
| g | glacier |
| o | occular |
| l | lanturn |
| t | terrible |
| y | youthful |
Now the pattern. Start with the familiar 1!, then substitute words for letters starting with the last, then the first, then next to last, then second:
| Site | Password | Entropy (bits) |
|---|---|---|
| 1! Elephant Glacier Lanturn Occular | 173.9 | |
| Bank of America | 1! Asteroid Batcave Clarify Batcave | 168.8 |
| Lyft | 1! Terrible Lanturn FruitFly Youthful | 186.9 |
Interestingly BoA has the lowest entropy now, but it still estimates “5.34 billion trillion trillion trillion centuries” on a massive array.
This is a little more work upfront. The dictionary may need to be written down for a while, but after using this method for a month or so they should be memorable.
This mostly mitigates the password reuse problem, it is possible that 2 sites will have the same letter patterns but an attacker would probably need to gather many, many passwords to fully defeat this scheme.
So, it is not perfect but I posit that, combined with 2 factor authentication, it is better than the alternatives. Not only does it completely mitigate the duplication threat (once the dictionary is memorized) it allows you to log into sites on different computers or mobile devices without having to access a password manager.
Drawbacks
There, of course, are drawbacks to this. Mostly they are induced by sites forcing poor password hygiene. Length limitations are a possible killer which will require a fallback to a less secure way of password handling. Character limits are similar, in these examples I chose symbols unlikely to be blocked (aside from space, as noted above).
One main drawback are sites that require regular password changes. Since these passwords are very, very difficult to brute force this should not be a requirement, but you can’t help what a site chooses to do. I handle this by keeping the same basic pattern, but ‘bumping’ some characters, so in the above example, when BoA makes me change my password it would become “2@ Asteroid Batcave Clarify Batcave”, then “3# Asteroid Batcave Clarify Batcave” and so on. It may take a couple tries to remember which step you were on, hopefully not enough to get locked out (which has never happened to me).