2
$\begingroup$

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.

$\endgroup$

marked as duplicate by AleksanderRas, kelalaka, Maarten Bodewes Jun 20 at 23:27

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ @SqueamishOssifrage I am asking a different question not answered there, though the underlying issue is similar. $\endgroup$ – Winter96 Jun 14 at 0:03
  • 1
    $\begingroup$ Can you explain how the questions are different? $\endgroup$ – Squeamish Ossifrage Jun 14 at 1:37
  • $\begingroup$ I don't see any difference either, and since I've not seen an accept nor a reaction on the comment of Squeamish, I've closed the question as a dupe. Please flag or comment below to object, but please provide some reasoning why the question needs to be reopened. $\endgroup$ – Maarten Bodewes Jun 20 at 23:29
6
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ My point is that the process for generating the passphrase is not simply the dice throws. It is that plus the second step of converting the throws into English words. The letter-redundancy in those words adds redundancy to the passphrase. Surely this reduces the entropy of the passphrase. $\endgroup$ – Winter96 Jun 13 at 19:32
  • 2
    $\begingroup$ @Winter96: again, no it doesn't; as long as the process in invertible, such a mapping does not decrease the entropy... $\endgroup$ – poncho Jun 13 at 19:39
  • $\begingroup$ I appreciate that the process of mapping as such does not decrease the entropy. My argument is that the map (English words) contains redundancy that was not in the original. Another way of looking at it goes to your argument that entropy depends on the process of selecting the passphrase. That assumes that an observer reading the passphrase is in a sense affected with the selection process. Surely the observer can assess the information content of the phrase in any way without knowledge of the selection process. $\endgroup$ – Winter96 Jun 13 at 19:44
  • 3
    $\begingroup$ @Winter96: 'Another way of looking at it goes to your argument that entropy depends on the process of selecting the passphrase' - well, yes, if you look at the definition of Shannon entropy (or min entropy, which happens to have the same value in this case), the entropy is defined entirely as a function of the probability distribution of the output; it is independent of the observer. Such definition does makes entropy hard to measure... except when we know the probability distribution, which we do for diceware. $\endgroup$ – poncho Jun 13 at 20:29
  • $\begingroup$ I agree that it depends on the probability distribution of the output, but the mapping changes the distribution. Expressing the output in numbers, each digit 1-5 will have equal probability and contribute ≈ 2.585 bits of entropy, giving a 7-'word' phrase 90.47 bits. Converted to words, the letters of the resulting string will not be equi-probable. E.g. the standard Diceware list has 462 words starting with A, 354 starting with L and only 35 starting with X. The probability distribution of the phrase depends both on the uniform dice throws and the differently distributed word list letters. $\endgroup$ – Winter96 Jun 13 at 23:48
3
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.