1
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ "Why is nobody doing this? " because the Zeitgeist hasn't morphed there yet. Presently only password character complexity and expiry rates matter. E.g. "Passwords must contain at least eight characters, including at least 1 letter and 1 number." - StackExchange. $\endgroup$
    – Paul Uszak
    Aug 7, 2019 at 13:15
  • 1
    $\begingroup$ “Nicer and shorter password for the same entropy” Not if you've made the word list bigger by including longer words (making the password longer) or more obscure words (making the password harder to remember) or more sets of similar words (making the password harder to remember). In my own word list, I exclude plurals and words longer than 5 letters. $\endgroup$ Aug 7, 2019 at 13:38
  • $\begingroup$ Good point... Although you could avoid longer words if you wanted to as part of your selection of K out of N words. In a way, you make the decision of how long words can be instead of the word list deciding for you. Point taken though. I wonder how many short English words there are. $\endgroup$
    – asac
    Aug 7, 2019 at 13:43
  • $\begingroup$ I believe the big problem is generating your 16x word list. Yes, English does have circa500,000 words, but many of them are obscure, archaic or technical terms that most people would not be familiar with $\endgroup$
    – poncho
    Aug 23, 2019 at 21:46

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ "Provided you have partitioned your 16x-size word list into disjoint word lists, you are correct that this does not decrease entropy vs. doing standard (no-rejection) diceware on one 1x-size word list." - actually, you don't have to do this - you can display sets of 16 words at random from your 16x size list (and have the user arbitrarily pick one) is as good as (no worse than) standard diceware on you 1x-size word list $\endgroup$
    – poncho
    Aug 23, 2019 at 21:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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