## Mar 11, 2019

### 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.

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

### 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

$P&space;=&space;1&space;-&space;(1&space;-&space;1/M)^N&space;=&space;1&space;-&space;\left(&space;{\left&space;(&space;1&space;-&space;{1&space;\over&space;M}&space;\right)^&space;M&space;}&space;\right)&space;^&space;{N&space;\over&space;M}$

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

$\lim_{x\to\infty}&space;\left&space;({1&space;-&space;{1&space;\over&space;x}}&space;\right)&space;^&space;x&space;=&space;{1&space;\over&space;e}$
$P&space;=&space;1&space;-&space;\left&space;({1&space;\over&space;e}&space;\right)^&space;{N&space;\over&space;M}&space;=&space;1&space;-&space;\left&space;({1&space;\over&space;e}&space;\right)^&space;{2&space;^&space;{n&space;\over&space;m}}$

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.

1. This comment has been removed by the author.

2. "printf is more a portable shell function across Unix, especially Solaris, than "echo", and doesn't append a newline:

\$ printf 'twitter 2019 stebanoid my super secret sacred phrase' | sha256sum

3. I had to remove and republish this comment because of some horrible typos: