HashDice - strong passwords that are easy to recover

How can we create passwords that are strong, easy to remember, easy to change and that are different for different places where you log in? Trying to solve this puzzle I came up with a method I call HashDice. In this piece I share it with you to improve your passwords or to hear explanation why the method is bad and should not be used.

Disclaimer

HashDice is not proven to be absolutely safe yet. This article is not a safe recipe, it is just my personal experience, my thoughts and invitation to discuss the method. If I am wrong, use of the method may cause significant damage. The author specifically disclaims liability for incidental or consequential damages and assumes no responsibility or liability for any loss or damage suffered by any person as a result of the use or misuse of any of the information or content of this article.

If you see problems or vulnerabilities of HashDice or, equally, solutions to drawbacks of the method please let me know.

Incentives

So, what do we want from a password? We want it to be strong. That means that an attacker has to try so many passwords in order to find a correct one that it is impractical. The problem with strong passwords is that good passwords look random and hard to remember. A password that is easy to remember is likely a weak password.

We also want to have different passwords for different websites. It is not very good idea to use the same password for online banking and for a some shady random website you do not know much about and do not trust, but have to register for some reason. Even big websites with dedicated security teams may leak your data as it happens from time to time, not to mention smaller websites that may store your password in plain text. For example, I have registered at least at 100 resources, and I know for sure that some of them store passwords unencrypted. If any of them is stolen, my banking password would have be known to the intruder if I had used the same password for all the websites.

It is also recommended to change your password from time to time, or at least when it become known that some resource you use have been found to have security issues. This fact together with the previous two makes managing your passwords a nightmare.

One solution to the problem is password managers. They store passwords in a database and losing this database as a result of some technical problem would be disastrous. So backups, backups of backups, and hassle of keeping them all up-to-date. Another thing is that if you are away from you password manager for some reason, you cannot login to any website or app. I would personally prefer not to be tied to any file, device or service. Ideally, for full independence I would like to be able to restore all my passwords from my head alone.

That is how I came up with HashDice.

Derivation

My solution is to use different passwords for different applications/websites, but all these passwords are derived from the same secret. This technique is widely used in cryptography. It is known as key derivation. As a key derivation function we will use a cryptographic hash function SHA-256 because it has all properties we need for our purpose.

It's easy to calculate almost on any device. Linux and Windows both has tools to calculate it without installing anything and plenty of tiny nice phone apps are available for free for Android (I am sure there are some for iPhones, too).
It accepts on its input a string and outputs statistically random garbage on its output. Moreover, tiny change of input causes completely different output. This property allows us to use the same secret string (Secret) with a Modifier (such as name of a website) to get completely different passwords for different websites.

It is impossible to restore our secret knowing its hash. This property of cryptographic functions is very important as we do not want some random website A to be able restore our Secret and then get ability to generate passwords for different websites.

So, basic idea of the method is to remember only one strong Secret, hash it together with names of websites to get different passwords for different websites. We can restore any password exclusively from information from your head with any computer or phone you trust enough to type you Secret on it. And we have to remember only one passphrase!

Implementation details

First thing we need for HashDice is a secret. Please, don't pick Secret from your head - your Secret should be as random as it's possible, but people are horrible at being random. No, you are not an exception. There are different ways to do this properly, but I personally prefer DiceWare method. With this method we choose words for our passphrase from a known list using a dice. It allows you to know for sure how much randomness (entropy) we add to our phrase with each additional word, and ultimately to know for sure how strong our Secret is. Some recommend using casino grade dices, but I did not bother to buy them and just used a dice from my daughter's tabletop game. I find it's easier to remember words from EFF's long word list then from original list, but it's up to you.

Suppose we generated and remembered our Secret phrase, and it is 6 words long. We will use it for every password we generate. As we used the long list of words (with 7776 entries in it), our phrase is one of 7776^6 possible phrases and is equivalent of log2(7776^6) = 78 bits of entropy.

Now we need to derive different keys for different places from our Secret. So, we create a string with the following format:

Site Date Modifier Salt Secret

We can place them in any order we want, until we keep Secret at the end of a string (see Sidenotes section to know why).

• Site is a name of a website/app/service we create the password for.
• Date is the current year. We want to change our passwords at least once a year, so the next year we will have a different password for the same website. If we want to change passwords 4 times a year, we can put something like 2Q19 for the second quarter of 2019. You got the idea.
• Modifier is any optional modifier we please to choose. Maybe we have many accounts on the same service and we want to have different passwords for them - just use corresponding login as a modifier. Or maybe the website security was compromised and we had to create a new, out of schedule, password for it…
• Salt. It is something unique to us, not necessary super secret. Maybe it is your unique Twitter handle or a funny word your little kid come up with when she learned to speak. We can use the same Salt for different passwords. It's not a salt in it's cryptographic sense, but it prevents attacker from creating tables of hashes of known universal phrases in advance. Salt is meant to prevent attacker from using rainbow tables. With Salt our phrases have a unique word and universal rainbow tables will not work for us.

You must be consistent to make HashDice work. Make rules and follow them, so that you don't have to remember specifics of each password for each website. Choose your policy about upper/lower case letters and stick to it, as one letter in wrong case will cause completely different password. Use always the same order of fields in your string, so you don't have to remember.

Then we put this string into the hash function. If we use Linux, just use the command

$ echo -n "twitter 2019 stebanoid my super secret sacred phrase" | sha256sum

The key -n is used because we do not want depend on end-of-line character encoding, which is not consistent between different systems and may case headache.

If you have to use Windows instead, you can use a command

certutil -hashfile pathToFileWithAString SHA256

but you have to save your string in a file (without end-of-line character at the end!). Alternatively, try to find an app for Windows that is able to calculate SHA-256 from manual input, rather than from a file.

For my Android phone I installed a tiny (175k) Hash Droid app and I am quite happy with it. You may find something else more convenient.

For more security I use my ancient smartphone which still works, but I no longer use. I just restored it to the factory defaults, installed only one app for hash calculation and switched off Wi-Fi. The phone has no SIM card, no Wi-Fi, no other way to connect to the Internet. It is completely isolated little computer I use to create passwords. As a result, my Secret have never been exposed to any connected device. I create a hash on my isolated phone, manually transfer  the hash to my computer and that's it.

After creating a hash we truncate it to appropriate size. 256 bits created by SHA-256 is an overkill and difficult to handle. As our Secret contains only 78 bits of entropy, we truncate the hash to 96 bits or 12 bytes or 24 symbols. We don't truncate it to 80 bits to avoid hash collisions. See Sidenotes for more details.

Now we have 24 symbols that could have been used as a password if websites would not restrict format of passwords. Many websites require that a password contains both upper and lower case letters, numbers and special symbols. We already have lowercase letters with probability 1-(1-6/16)^24=0.999987 in our truncated hash, and we have numbers with probability 1-(1-10/16)^24=0.99999999994, so we just have to add a special symbol and an uppercase letter. Just choose an uppercase letter and a special symbol you like, and always add this constant prefix to the beginning of each password to satisfy "password strength checkers". They will be happy as they usually happy with "1" added to "Password" password.

Our final arrangement for passwords is

Prefix + truncated_SHA256(Site Date Modifier Salt Secret)

I still use a password manager to store some of my HashDice passwords I need on regular basis, but now it is not a necessity, but only to reduce typing.

What is not achieved with HashDice

There is no perfect solutions, and HashDice is not an exception. There are still websites that do not allow to setup our own password, but send a password via email instead (yes, in plain text - all for our security). I am also registered on a VoIP service that restrict maximum length of passwords and my password does not fit there. Some sites restrict maximum length of a password and restrict set of characters that can be used (hello, Aliexpress). We have to treat these exceptions separately.

HashDice is also not very convenient for places where we have to login often and without aid of a password manager. For example, it is not very suitable for login to an account of a personal computer or for unlocking password a manager itself.

Also, some websites have weird requirements for logins and we have to somehow save our website-login pair list so that we can look up our login. Luckily logins are not very secret, so it's much easier to arrange. I also add to this silte-login data my Date and Modifier fields, as (let's face it) I am not going to change my passwords for all websites regularly. Somewhere in 2026 some websites will be with passwords from 2019 and I don't want to have to try all 7 possible dates + possible Modifiers.

Another problem is that when you find a nice hash like ffffffff…. you can't tell anyone about string which creates the hash without disclosing your Secret.

A few tips I find helpful

Don't use end of line character, as it is platform-dependent.  I would not use characters from national alphabets either because I don't like to think about encoding.

Don't bother making upper/lower case letters in your string. Just use one case. Each letter in different case makes your password a lot harder to remember, but adds only 1 bit of entropy. If you want more protection, just add another word to your Secret, as each word from a long list adds 13 bits of entropy. Don't forget to take truncate to longer part of the hash in this case. Add 4 additional characters of hash for each additional word of your Secret.

If you use a separate, unconnected, device for password generation and transfer your passwords manually, it is not a problem to make a typo when you are logging in. On the other side, if you are setting up a new password, misspelled password can ruin your day or two. That is why I first verify my string against already existing password from my password manager, then change Site field of the string from existing website to a new one, calculate a new hash and type it manually twice. Once in type it to a "password" field on the website, another time - to a "verify your password" field. If the website does not have "verify your password" field I check it myself using other tools before copying it to the website.

I already mentioned that I ask my app to display hash in upper case to make it easier to tell "b" from "d". But, maybe, it's just my thing.
If you use Linux you probably already know how to truncate your hash easier:

$ echo -n "twitter 2019 stebanoid my super secret sacred phrase" | sha256sum | head -c 24; echo ""

Sidenotes (bonus track)

SHA-256 is vulnerable to length extension attacks, so I chose to have my Secret at the end of the string. Otherwise, attacker may try to find a new valid password H( Pad(Secret Site) || Y) for some Modifier, extending known to him H(Secret Site) value even if Secret is not known. If we always keep our Secret at the end of a string, to my understanding, there no way for an attacker to produce a second valid password we actually use from a known previous password. We could have chosen SHA-3 hash function which is not susceptible to length extension attacks, but there are much fewer tools that support calculation of SHA-3.

Another characteristic of SHA-256 is that it is subject to collisions, i.e. there are some different strings giving the same hash. If our Secret has n bits of entropy (78 in the case of 6 words in Secret field), meaning that there are N=2^n possible combinations. Then we calculate a hash value and truncate it to m bits, meaning that there are M=2^m possible combinations of a truncated hash value. Due to the nature of the hash function, there can be two different Secrets giving the same truncated hash (collision). Probability that our chosen Secret creates a password that has at least one collision is



Given that M is huge we can use one of Notable special limits




If we would have truncated our hash to 80 bits while entropy of Secret is 78 bits, P would be 0.2 which looks like a lot. If we do ignore processing power, required for calculating hashes, it would be advantageous for an attacker to try to guess our Secret and then to hash it instead of directly guessing our password, because if our password has a collision, attacker may find another Secret1, which is different from ours, but still produces the correct password. To avoid thinking about practicality of this attack I just chosen to truncate hash to a size that is at least 16 bits more than there is bits of entropy in my Secret. It lowers probability of collision on a password below 0.000015 which is even theoretically not a great advantage.

It think, that it should be noted explicitly, that when I say that different modifiers create absolutely different password, I imply that one cannot calculate the second password, knowing the first password and both modifiers without knowing the secret.
Saying that I rely on a conjecture that a hash function has the following property:
Given hash function H, known substrings A and B, and known hash h1=H(A||X), it is infeasible to find h2=H(B||X) if X is unknown.
This is neither a classic property of a hash function nor I can derive it from other properties of a hash function. Strictly speaking, I don't know it, but I believe that it is true.
Some people I spoke about it suggest that this property is a consequence if pre-image resistance (one-wayness) of hash functions, but I think it is not correct. Pre-image resistance implies that one cannot calculate h2 through finding out argument of H. But we can imagine that someone could find h2 from h1 directly, without calculation of A||X. I think it is impossible for cryptographically strong hash functions, but I cannot prove it.

Summary

With the proposed system we do not need to have our password stored somewhere. We can restore them at any time purely from information in our head. We have to remember only one strong passphrase.

Our passwords are strong. They are different on different websites and one website cannot use data available to it to login to another website. HashDice allows using the same Secret for websites with different level of trust from banking to some shady web resources.

We are not afraid of losing access to our password manager's database. We are only scared of forgetting our secret words. That is why we are regularly refresh it on our mind.

Our passwords are easy to change regularly. We don't have to remember new jaw-breaking combination of symbols.


I find HashDice convenient and to my knowledge it is very safe.

Please, let me know what do you think about HashDice.