Does the use of English words weaken diceware passphrases [duplicate]

Question

A Diceware passphrase is constructed from a set of words chosen from a 7776-word database, using five dice throws to choose each word. The argument is that each word in the phrase adds about 12.92 bits of entropy since $\log_2(7776)≈12.92$. As Arnold Reinhold, the creator of Diceware, explains, the entropy comes from the size of the database, not from the way in which the elements are represented. So, in principle, it does not matter whether a 7-word passphrase is formed as 7 English words from a Diceware database, the original 7 five-dice throws (in effect 7 five-digit base six numbers with each digit increased by 1), or seven Chinese characters chosen from a database of 7776 Chinese characters. Each would have an entropy of about 90 bits.

Is it not the case, however, that using English words in place of the underlying dice-throw numbers reduces the entropy of the passphrase. The words in the standard Diceware database have an average length of 4.2 characters. This means that the average length of a 7-word passphrase would be about 30 characters. It is said that letters in English text have an entropy of about 1.3 bits each due to the redundancy of the language. This would imply that, analyzed as English text, the passphrase would only have an entropy of 38 bits. Arguably a Diceware passphrase is not typical English text, but presumably one could do a similar analysis to determine the redundancy of text drawn from the Diceware database, but, if my argument is correct, each letter in the passphrase would have to have at least 3 bits of entropy in order not to downgrade the entropy of the underlying Diceware elements.

Reinhold himself glosses over this. He says:

But, you might ask, Diceware is made up mostly of English words. Doesn't that redundancy affect it at all? Well, it does. The seven word Diceware passphrase we talked about above would average about 30 letters in length (36 if you count the spaces between the words). If those letters were selected randomly, you would get 4.7 bits of strength per letter. That would work out to a lot more than the 90 bits Diceware claims for a seven word passphrase. The difference is the redundancy of English at work. However English redundancy does not affect the calculation that each Diceware word has 12.9 bits of randomness, which is based entirely how many different words there are in the Diceware list. You can rely on that number.

The redundancy of English does not affect the entropy of the Diceware passphrase, so long as you can rely on each letter having 4.7 bits of entropy, or indeed at least 3 bits. But I don't see what guarantee there is that this is the case.

Note that this question is not answered by Can an attacker exploit the nonuniform distribution of letters in a diceware password to improve a brute force search? since this question raises a different argument not considered in that question. The underlying issue is similar, but the question asked about it is different.

Answer 1

I don't believe that looking at the diceware phrase is very helpful.

Instead, look at it this way; there are $7776^7 \approx 2^{90.47}$ possible 7 word diceware phrases, and diceware will select one of those possibilities uniformly.

That means that the probability that one specific phrase is selected is at most $2^{-90.47}$. Or, in other words, if someone were to guess random diceware phrases, he would make an expected $2^{90.47}/2 = 2^{89.47}$ guesses on average before hitting the right one.

Is it not the case, however, that using English words in place of the underlying dice-throw numbers reduces the entropy of the passphrase.

No; there is a one-to-one mapping between diceware throw numbers and valid diceware phrases; one can take the phrase, and map it back to the throws that generated it. And, a one-to-one mapping never effects the entropy.

What it does effect is the 'entropy-per-character' measurement; because the diceware phrase is (usually) lengthy, the 'entropy-per-character' measurement is a bit low. However, we don't really care about the 'entropy-per-character', instead, we care about the security that the entire passphrase gives us.

Remember, the 'entropy of a passphrase' is a bit misleading; if we talk about entropy, we need to talk about the process that selected the passphrase. In diceware, we have a very different process than if someone were writing some English text (and so the entropy estimates that may be valid for human generated English text do not apply to diceware generated texts)

Answer 2

Here are a few games we can play:

• 1. I roll a die 50 times.
  2. I write down the results as 1, 2, 3, 4, 5, or 6.
  3. You try to guess what I wrote down.
• 1. I roll a die 50 times.
  2. I write down the results as one, two, three, four, five, six.
  3. You try to guess what I wrote down.
• 1. I roll a pair dice, 25 times.
  2. I write down the results as 11, 12, …, 16, 21, 22, 23, …, 66.
  3. You try to guess what I wrote down.
• 1. I roll a pair dice, 25 times.
  2. I write down the results as one one, one two, …, one six, two one, two two, two three, …, six six.
  3. You try to guess what I wrote down.
• 1. I roll a set of five dice, 10 times.
  2. I write down the results as 11111, 11112, 11113, ….
  3. You try to guess what I wrote down.
• 1. I roll a set of five dice, 10 times.
  2. I write down the results as a, aardvark, aardwolf, ….
  3. You try to guess what I wrote down.

Which of these games would you rather play to get a better chance of winning?

What happens if we play the following variation on the very first game?

• 1. I roll a die 50 times.
  2. I write down the results as 1, 2, 3, 4, 5, or 6.
  3. I pass the sheet of paper to my friend, who replaces 11111 by a, 11112 by aardvark, 11113 by aardwolf, etc.
  4. You try to guess what my friend wrote down.

Could this possibly change your chances at winning the game? Does it matter whether you are guessing what I wrote down vs. what my friend wrote down—does trying to guess one have an advantage over trying to guess the other?

Answer 3

I think there are two things that are confusing you.

1. Consider sequences of n digits, e.g. 12946, and sequences of n words-for-digits, e.g. one two nine four six. The former have much more entropy per character, in that (for example) the first digit (1) tells you nothing about the second (2) whereas the first letter (o) sometimes completely determines the second (n). But the latter make up for this defect by having more characters, such that they end up with the exactly the same total entropy. So if an attacker knows how you're generating your passphrases, then choosing passphrases like 12946 is neither better nor worse than choosing passphrases like one two nine four six.

2. You write that "letters in English text have an entropy of about 1.3 bits each due to the redundancy of the language", but Diceware-generated passphrases aren't English text. A typical English sentence is something like I had a great time yesterday, let's meet up again soon!, whereas a typical sequence of entries from the Diceware word list is something like relic cross jose smithy ev hewitt harsh lam fred. English sentences have low entropy per word because in many places you can replace a word with a blank and have very few likely options for what might go there (consider I ___ ___ great ___ yesterday, ___ meet up again soon!), whereas in a sequence of entries from the Diceware word list there are exactly 7,776 words that can fit in each position in the sequence (consider relic cross ___ smithy ___ hewitt harsh ___ fred). Now, that's entropy per word; it may not be immediately obvious which one has more entropy per character (since word-lengths in English sentences vary more than those in Diceware word-list sequences), but you've presented reasonable figures for both, and I see no reason to doubt them.