Generating nicer diceware passwords without losing entropy

Question

Yes, another one of those "I have found a great password-generation strategy" waiting to be shot down!

It seems that although diceware aims to be a secure and user-friendly password generation method, there is a consensus that its output is not typically user-friendly. Over the years I have read many posts asking how to generate "nicer" passwords from it. For example 1 2 3 and in particular 4.

To get "nicer" passwords, whatever that means, the suggestions are typically:

• create your own word list (a lot of effort and need a longer password for same entropy since manual word lists are typically shorter)
• use a selection method but be aware you lose entropy (e.g. pick $1$ out of $16$ passwords at the cost of $4$ bits of entropy)

But it seems to me that there is an easy way to get a more memorable yet shorter password, especially if you're bilingual. What you need is a set of $N$ disjoint diceware word lists, each with $6^5$ words.

When drawing a word, lookup the dice combination in the $N$ lists and pick the word you like most.

This is exactly as secure as drawing from a single list. Indeed, assuming there is no overlap between the lists, this is equivalent to processing the $6^5$ sets of $N$ words to create your own "preferred" word list and use a standard diceware on that list.

1 - Am I correct that generating a password in this fashion does not decrease entropy?

In practice, it is hard to find non-overlapping lists (unless you speak several languages, and even then there might be duplicates). The impact of overlaps is trivial to quantify when $N = 2$ but

2 - What is the impact of overlaps between lists when $N > 2$?

Even better, pick your $2$ preferred out of $N$ and flip a coin to choose. You just increased the entropy ($+1/$word) and still get a nicer password than single-list diceware.

Pushing this idea further: there are around $500$K words in the English language, from which one can create $\dfrac{500\cdot 10^3}{6^5} \approx 64$ non-overlapping word lists. For each dice combination, pick your favorite $K$ out of $64$ and pick a final word at random.

That's $\log_2(K)$ extra bits of entropy per word, so with $K=4$ you have $14.9$ $bits/word$ instead of the standard $12.9/word$.

Nicer and shorter password for the same entropy / more entropy for the same number of words.

You control the trade-off between entropy and nicer words by adjusting $K$. With $K=8$ you gain $3$ $bits/word$ whereas with $K=1$ you get your preferred words but standard diceware entropy.

3 - Why is nobody doing this? This is easy enough to automate. Unless something above is wrong?

Answer 1

To get "nicer" passwords, whatever that means, the suggestions are typically:

…

• use a selection method but be aware you lose entropy (e.g. pick $1$ out of $16$ passwords at the cost of $4$ bits of entropy)

What you are doing is effectively ‘a selection method’ (more commonly known in the literature as rejection sampling) with a bound on the number of rejections. For your method to work, you need (say) a word list 16 times the size of a word list for standard (no-rejection) diceware in order to attain the same entropy while giving the user 16 distinct choices for each word position.

1 - Am I correct that generating a password in this fashion does not decrease entropy?

Provided each of your 16 word lists has the same number of distinct words, you are correct that this does not decrease entropy vs. doing standard (no-rejection) diceware on one word list.

2 - What is the impact of overlaps between lists when $N > 2$?

As far as the probabilities are concerned, nothing, provided (a) each word list has the same number of distinct words, and (b) you always accept exactly one of the 16 options presented. As far as the user is concerned, they may be presented with the same objectionable word twice for one position.

3 - Why is nobody doing this? This is easy enough to automate. Unless something above is wrong?

How do you decide how to partition the word lists?

If you have a 16x word list, you could just do rejection sampling on that word list and as long as you reject on average fewer than 16 words per position in the pass phrase, you get the same security with less user interface complexity. For example, you could draw 16 words independently from your 16x word list, and ask the user to pick exactly one of them.

Exercise: Find the probability distribution on what you get by selecting 1 of 16 choices drawn without replacement for each word position. (Independent samples as in the previous paragraph, in contrast, are ‘with replacement’.) This avoids partitioning the word list.