[Cryptography] generated passphrases

Arnold Reinhold agr at me.com
Wed Aug 14 14:00:44 EDT 2019

> On Aug 13, 2019, at 6:57 PM, jamesd at echeque.com wrote:
>> On Tue, 13 Aug 2019 06:53 jamesd asked:
>>> Jitsi uses a random passphrase generator which generates grammatically
>>> correct nonsense phrases, but its passphrase generator only generates
>>> four word phrases.
>>> Obviously, we would be better off using randomly generated grammatically
>>> correct twelve word nonsense phrases than randomly generated strings of
>>> words.
> On 2019-08-14 1:49 am, Arnold Reinhold wrote:
>> Please see my Diceware(tm) page (diceware.com) which has word lists in 27 languages and a simple random generation scheme using dice. 
> random words is the same as bips32, which open source and the standard for crypto currency wallets.  But Diceware has a larger vocabulary.
> Passphrases that are grammatically correct will have significantly lower entropy, the sum of the binary logarithms of the number of words for each part of speech. A "randomly generated grammatically correct twelve word nonsense phrase” is unlikely to come close to 128 bit entropy.
> Assuming your grammar uses six categories of words generate sentences with five hundred words in each category and total number of words is three thousand.
> Then a randomly generated string of eleven random words will be 127 bits of entropy, whereas a randomly generated grammatically correct nonsense phrase of fourteen words will be 129 bits of entropy.

Yours is a reasonable design, but going from 11 words to 14 words just to get a passphrase that is roughly grammatically correct is a significant penalty.  It would be worth building such a generator and seeing what the generated passphrases look like. 

>> I also have made a table that generates a grammatically correct sentence for any random string of 10 English letters:
>>     https://www.researchgate.net/publication/324089943_Making_Random_Letter_Passwords_Memorable
>> Two sentences worth (twenty random characters) provides 94 bits of entropy. A third shorter sentence with 7 letter can be added for 128 bit entropy. Just to be clear, the random letters are the password, the sentences are mnemonics for the user.  I do recommend writing passphrases down and keeping them somewhere safe.
> One  could get denser entropy than that with grammatically correct sentences.

The passwords in my scheme are completely random strings of English letters. You can’t get higher density than that with the same alphabet. The sentences I generate are just mnemonics, the passwords are comprised of the initial letter of each word. The sentences need never, indeed should never, be entered into the keyboard. 

As long as the entropies are correctly calculated and are about the same, passphrase format issue is largely a matter of taste.  I could see a system that generates passphrases offering several equivalent versions in different format. Of course this assumes the system accepting the passphrases accepts long enough strings. And if threat models include acoustic or video spying, then passphrases are less desirable than random letters since the former have significant redundancy that can aid those attacks.

But the reality is that almost no one is willing and able to memorize a 128-bit passphrase, indeed few will memorize an 80-bit passphrase. Any crypto currency or other security scheme that depends on people memorizing and entering very long passphrases is not going to gain wide consumer acceptance. 

That leads to the necessity of using effective key stretching. The only widely accepted standard is PBKDF2, which uses a single processor and very little memory. (i proposed memory intensive hashing way back in 1999. http://world.std.com/~reinhold/HEKSproposal.html) There was a community-sponsored Password Hashing Competition in 2015 that selected Argon2, but it seems to get very little use. NIST has not adopted it, perhaps because it uses the Blake2b hash, which is not NIST-approved. NIST SP800-63B briefly mentions the Balloon hash approvingly, but that is not the same as recognizing it as a standard. If other standards bodies have a better key stretching hash standardized or in the works I’d like to hear about it.  There is also a need for standards on how key stretching is used and how much is needed for various cases. And I believe there is a need for a key stretcher that intensively uses modern graphics processors. Let’s use all the horse power a user has to protect their secrets.

Key stretching addresses a critical mismatch in security technology, how much entropy a typical user can be expected to remember and enter accurately, vs how much entropy is needed for system security. So here is a big question: why doesn’t key stretching get more respect?

Arnold Reinhold

More information about the cryptography mailing list