Can an attacker exploit the nonuniform distribution of letters in a diceware password to improve a brute force search?

Question

I use some diceware pass phrases in some places but I have one question that I can't find the answer to.

Let's say I roll the dice and get $N$ words with a total of $M$ letters and that I don't put spaces in between the words.

An attacker wishing to brute force my secret could have to try $7776^N$ times to break it as a diceware pass phrase OR $26^M$ to break it as a "normal" password (assuming I get only words with letters).

But the attacker trying to break it as a normal password could assume that it is made up of English words and then they'd know that some letters and combinations of letters are more common.

So my $M$ letters will not have the entropy of letters selected at random but some lower entropy.

My question is, what $M$ do I need to make up the same entropy as the $N$ words?

Answer 1

But the attacker trying to break it as a normal password could assume that it is made up of English words and then they'd know that some letters and combinations of letters are more common.

They could try this, but they would be stupid to try this, because there are many fewer $N$-word diceware passwords than $M$-letter strings of English letters of the same length as an $N$-word diceware password!

Suppose you use a ten-word diceware password. There are $7776^{10} \approx 8 \times 10^{38} \approx 2^{129.2}$ such passwords. This is already a larger haystack than any adversary can find a single needle in. (If passwords are hashed without salt, an extremely powerful adversary may be able to find one of many needles in a haystack that big, but you could pick $N = 20$ instead, and the service oughta salt their password hashes.)

Any distribution on sequences of $M$ independent English letters that covers more possibilities than these $7776^{10}$ diceware passwords is an even larger haystack to search for a needle in.

A smart adversary, who knows all the details of your method and just doesn't know the password you chose by that method, won't give themselves a larger haystack to search in. A stupid adversary who does give themselves a larger haystack to search in will just waste more time searching!

For example, the distribution on $M$ independent English letters following the usual letter frequencies in English would give relatively high probability to sequences like aoqothropaaeeaetphtticawglesttgeectoyheldshnfznecr which has a lot of e's and t's and a's but not many z's, x's, q's, etc. This is not a possible diceware password, however, even though it has the same length as a ten-word diceware password with five letters per word. And it would give lower probability to woozydizzybuzzyfuzzyjazzymezzoexxonpizzapyrexvixen, which (with an appropriate word list) is a possible diceware password.

Let's work through a simplified example. We'll use a dictionary of five words: cat, car, act, art, and rat. We'll pick a single word uniformly at random from the dictionary, so that each word has equal probability 1/5, with just over two bits of entropy.

The corpus in this dictionary has letter frequencies a 5/15, c 3/15, r 3/15, t 4/15, under which distribution each letter position has under two bits of entropy. There are $4^3 = 64$ possible three-letter words from this alphabet, of which the vast majority, 59, aren't in our dictionary.

1. An adversary trying to guess our password from the dictionary has a $1/5 = 20\%$ chance, of getting it right in a single trial.

   This is the smartest, most efficient adversary.

2. An adversary trying to guess our password from the letter frequencies independently has a $\frac{1}{5}\cdot\frac{19}{225} = 19/1125 \approx 1.7\%$ chance of getting it right in a single trial.

   Why? The distribution on three-letter passwords is the product of the letter probabilities in this model. If the adversary guesses a word in our dictionary this way, there's a 1/5 chance that it's the right password, but there's only a $19/225 \approx 8.5\%$ chance that the word the adversary guessed with these letter probabilities is in our dictionary. With probability $206/225 \approx 91.5\%$, the adversary will be guessing passwords that you would never have chosen: they're wasting most of their time barking up the wrong trees in a much larger haystack.

   This is the adversary who takes advantage of the per-letter entropy as you described. Even if they sort by probability rather than choosing randomly, they'll first try aaa, then aac, then aat, aca, etc., wasting time on impossible passwords. Even if every word in the dictionary happened to come first in this ordering, this adversary has no better chance than adversary (1).

3. An adversary trying to guess our password from the letters, ignoring the frequencies, has a $1/64 \approx 1.5\%$ chance of getting it right in a single trial.

   Why? Under this distribution, every letter has equal probability 1/4 independently, so every three-letter word has equal probability $(1/4)^3 = 1/64$, including the one we chose. With probability $59/64 \approx 92\%$, the adversary will be guessing passwords that you would never have chosen. They're also rummaging through a much larger haystack, but they're doing it even less efficiently than adversary (2).

   This adversary just tries all combinations without regard to letter frequency. As you can see, this adversary is slightly worse at the job than adversary (2), so knowledge of the letter frequencies helps a little bit, but they're both much worse at the job than adversary (1).

Every word you add, if drawn independently, multiplies these probabilities: pick a second word independently from the same dictionary, and adversary (1) now has $(1/25)^2 = 1/25 = 4\%$ chance of success, adversary (2) now has $(19/1125)^2 = 361/1265625 \approx .029\%$ chance of success, and adversary (3) now has $(1/64)^2 = 1/4096 \approx .024\%$ chance of success. If you make the dictionary large enough and the sequence of words long enough that you defeat the smart adversary (1), then you also defeat the stupid adversaries (2) and (3).

My question is, what $M$ do I need to make up the same entropy as the $N$ words?

Don't worry about $M$. Pick $N = 10$ for diceware and you're all set.

Answer 2

Diceware passwords are based on guarantees of minimum entropy. the $7776^N$ number is the number of possible passwords generated with $N$ words from the Diceware list. If you use dice, or an equivalent, that is a guarantee on the strength of the password against brute force attacks.

That paragraph assumes that the fact that you are using Diceware is public knowledge, as is their word list. If you expose everything about your password generation scheme except the key (the actual dice rolls or the actual words), you still have that guarantee.

If your threat model assumes less knowledge of your password generation routine, brute forcing will be more difficult. If your threat model assumes no knowledge of your password generation approach (other than that it is lower case), the difficulty of brute forcing the password will be equivalent to that of a password with $26^M$ possibilities. It still only has precisely $7776^N$ possibilities, but it appears to have more because your adversary doesn't know everything.

From there, one can discuss the possibility that, since English words do not have a uniform distribution of letters, the entropy of the password is much less than $26^M$, which is true. But Diceware's security proofs are not based on that number. They are based on the $7776^N$ number, and the random rolls of the dice drawing from that 7776 entry table.

Thus, if I make a 16 character password using Diceware, I should not assume that it is as strong as a 16 character password made via other means (such as random characters). In fact, per character of the password, Diceware provides less entropy and apparent entropy than other approaches. 16 characters may only be 3 words, which is merely $7776^3$ possibilities.

The strength of diceware is that it observes that entropy per character is not the best metric for judging a human memorable password. It encourages long passwords (4-8 words) which are easier to memorize because they are words, but still contains a provable amount of entropy in the password to be used in security proofs. The exact number of words you use should be derived directly from how much entropy you require for your password.

... now the challenge of typing said password correctly without typos is another question entirely.

If you're interested in converting between systems, 7776 possibilities per word means your Diceware password generates 12.925 bits of entropy per word. Round it up to 13. Thus a 5 word password has 65 bits of entropy. A 10 word password has 130, meaning it is as hard to brute force as a 128 bit encryption key.

Wikipedia has a great table of how many bits of entropy per random character a password can have, based on the character set. An alphanumeric password, case sensitive, has just shy of 6 bits of entropy per character. So every word in your diceware password is slightly better than 2 random characters of a password. An 8 character random alphanumeric password is comparable in strength to a 4 word Diceware password.

Of course, if your password generation scheme is anything less than a purely random character stream, your actual entropy will fall short of this 6 bits/char line. In such cases, the exchange rate for Diceware words will be even better.