[Whonix-devel] Diceware and Quantum Computing resilience

[Arnold Reinhold]

> On Aug 16, 2018, at 2:36 PM, procmem <procmem at riseup.net> wrote:
> 
> Hi Arnold, Whonix (privacy distro) maintainer here. We are big fans of
> Diceware and were recently revisiting our password advice and so I had a
> few questions:
> 
> * How much entropy does a special character add in Diceware?
> 
> * I was considering using a massive wordlist/dictionary
> https://packages.debian.org/stretch/wamerican-insane that has about 650K
> words as a way to potentially increase entropy per word to allow using
> less words for passphrases. It came up in discussion that this is a bad
> idea since some of the words are difficult to spell and some very short
> words 3 characters and less harm passphrase strength. Is it that short
> words reduce entropy?
> 
> * Do you advise steering clear of dictionaries and sticking to the
> prepackaged wordlists, can you please explain?
> 
> * Quantum computers will halve the keyspace using Grover's so we need to
> recommend passphrases with 256bits today using EFF's wordlist if users
> are to achieve quantum resistance. However this requires 20 words and so
> things start getting unwieldly. What is the best approach to dealing
> with this while maintaining usability as much as possible?
> 
> I have CC'd our ML so your reply can benefit our users.

The important thing to understand is that entropy comes from the password or pass phrase creation process. If you select one symbol at random from a set of  M distinct symbols, the resulting entropy is log2(M), assuming the selection process is truly random. If you select N symbols from that set the entropy is N*log2(M). Here log2(M) is the base-2 logarithm of M which is equal to log(M)/log(2) in any other base. 

Truly random is the tricky part. Ordinary dice come pretty close. Casino dice are nearly perfect. The "random number" function in most computer languages is not adequate for passphrase generation. Crypto-grade random number generators, such as /dev/random can be ok, assuming the computer itself has some source of randomness and has not been compromised. 

Selecting random words from your 650K word list will generate 19.3 bits of entropy per word. That’s more than the 12.9 bits from a Diceware list, but you’ll end up with bigger words that are harder to remember and type. It’s a human-factors question; as long as the total entropy is the same, it does not matter from a security viewpoint. Very short words are not a problem, except in the highly unlikely case where the resulting pass phrase is so short that it is subject to brute force attack letter by letter. I recommend a minimum length of 20 characters, including spaces between the letters. 

Adding a special character at a random point in the pass phrase gets entropy in two ways. First there are 32 special characters on a standard U.S. keyboard. Log2(32) is 5. A six-word Diceware(tm)  passphrase has about 25 characters on average, plus another 5 spaces, so selecting a random position in the passphrase to add the special character yield about another 5 bits, for a total of 10 bits.  If you are using a longer passphrase, you’ll get a little more, but not much. 

The advantaged of prepackaged Diceware-style word lists, like mine or the EFF’s, is that they are designed to make selection using dice easy. The number of words, 7776 is a power of 6 (the fifth). If you use an ordinary dictionary, you’ll have to figure out exactly how to make a uniformly random selection from it. Also note that many security programs limit the length of passwords, so lists with large words, such as the EFF’s and your 650K dictionary, often generate pass phrases that will be truncated by the input program, which defeats the purpose. The new NIST SP 800-63B guidelines say passwords up to 64 characters should be accepted, but not everyone follows them, particularly Microsoft.

Resistance to quantum computing is somewhat speculative since we do not know when they will arrive or what they will be able to do in practice. Doubling key length is based on good theoretical foundations, but as you point out, a 20-word Diceware pass phrase is needed for 256 bit security. I think that is far more than most people can memorize. You’ll have to write it down. An alternative might be random characters. You can select characters for the set a-z, 0-9 by making a 6 by 6 table with the 36 characters and using two dice to select each character. A password 50 random characters, or ten 5-character groups will get you to 256-bits. Still not easy to use. Mixed case helps a little, but typing gets much much harder, not worth it IMHO.

The real solution, I think, is to only use security software that incorporates key stretching for your pass phrase. Algorithms that use a lot of memory as well as processing power, such as HEKS, scrypt or argon2, should be much more resistant to quantum attack.  It’s one thing to build a quantum computer with enough coherent q-bits to attack AES, quite another for the millions of q-bits presumably needed to attack argon2, though I have not seen a formal analysis.

Hope this is helpful and thanks for your interest in Diceware,

Arnold Reinhold

>