[Cryptography] Passwords (Smallest feasible work factor today?)

[Arnold Reinhold]

On Sep 2022 11:20:34 -0400 Phillip Hallam-Baker asked:

> Folk, what are people's thoughts on the smallest work factor that can be
> considered acceptable today? I am thinking 2^80.

For over 25 years I have been encouraging people to use ordinary dice to select strong, random passphrases from word lists. The Diceware.com <http://diceware.com/> website has word lists in 30 different languages, most supplied by users. Six word passphrases, provide about 77.5 bits of entropy. Someone wanting more can simply add additional words with each word providing 12.9 bits.

Threat model
You are protecting an asset that would be valuable to an attacker with significant resources who knows who you are.  

When passwords are used protect access to enterprise resources, a central question is how securely the password verification information is stored. Typically that data is protected by hashing, hopefully with salt. But if an intruder can steal the stored hashes, they can mount an attack offline. That happens all too often.

One factor is the speed of the password hash employed. Standard cryptographic hashes, such as the SHA series, are designed to be fast, which is exactly what we don't want when using hashes to obscure stored passwords. Using a good resource-consuming hash instead can be the equivalent of reducing the required length of a passphrase by one or even two words. That makes a material difference to most people in terms of what they can memorize. 

But websites and other logins rarely disclose what kind of hash is being used and whether protection measures like salt are employed. This means that users often must assume the worst and pick larger passwords or passphrases than are really necessary.

So assume there is a material risk that the attacker can get the stored hashes or another crib  such as known plaintext for a cipher). 

Work factor
Current hash rates for standard GPUs are available at: 
https://www.onlinehashcrack.com/tools-benchmark-hashcat-gtx-1080-ti-1070-ti-rtx-2080-ti-rtx-3090-3080.php.

Here are a few examples based on Hashcat version 6.2.3 on one  NVIDIA RTX 3080 TI GPU, currently costing $900 each. Hash performance is shown in giga- or kilo- hashes per second, and the equivalent number of bits of password entropy searched per second:

MD5 65 GH/s, 36 bits per second
SHA-256 9.2 GH/s, 33 bps
SHA-512 3.1 GH/s, 31.5 bps
Bcrypt (32 iterations) 100 KH/s, 16 bps

For searches per week (604,800 seconds) add 19 bits of entropy, e.g. the RTX 3080 can search 55 bits worth of MD5 hashes per week. For per year, add 5.7 bits. 

If you want make it unlikely that an attacker will luck out and find your password after searching one thousandth of the search space, add another 10 bits.

Cryptocurrency miners have built hash farms with large numbers of GPUs. Assuming your attacker could amass 1000 GPUs, add another 10 bits.

So worst case if the attacker could command a GPU farm for a week and you can’t assume anything stronger than MD5 is in use, one needs a password with 75 bits of entropy. A six word Diceware passphrase still seems reasonable, but maybe add a seventh word as a safety factor for future hashing improvements. Note that if one could be sure that the password hash function was bcrypt, one could get by with 5 words and still have a margin of safety. Using harder hashes is a win.

Re other comments in this thread:

Composition rules
Those who complain about password composition rules, such as demanding 
special characters or varying capitalization, should know  that NIST agrees with them. The latest edition of their SP 800–63B contains an appendix making exactly that argument. And random capitalization is a really bad idea if you think of it in terms of entropy per keypress rather than entropy per character. This is especially true for mobile devices where getting to all the possible characters can take several shift presses per per character.

Write them down
Another bit of foolishness is the warning never to write down a password or passphrase. That may be good advice for spies entering hostile territory but most people can find a reasonably safe place to keep a paper list of written passwords. The common threat is electronic access, not a house search.

Initial letter passwords
One problem with using initial letters of sentences is that most people will end up picking a quote from their favorite song or book or other literary work, and the number of sentences in such works is actually quite limited. If you assume of 8000 sentences per book and 20 million books in the Library of Congress that turns out to be only 2^37 sentences. Even if you are clever enough to create a sentence that is unique but memorable, most other people likely will stick to well-known quotes. 

Random sentence generator
An alternative approach starts with a completely random string of letters and generates a memorable sentence sentence with those letters as the initial letters. The sentence generator is just a table, and works for strings up to 10 characters, so for a 20 letter password two sentences would be needed. The sentences are purely mnemonic and can be discarded once the random letter password is memorized. See https://www.researchgate.net/publication/324089943_Making_Random_Letter_Passwords_Memorable

It’s unreasonable to expect most people to memorize more than a couple of truly strong pass words or pass phrases. Password managers are a useful tool for medium security accounts but they still need a master password for themselves. 

Finally there is the issue of password reset, which has become quite convenient to the point where, regrettably, it's almost not worth remembering the password for an occasional, unimportant website. That makes ones e-mail account, commonly used to validate a reset, perhaps the most important to secure with a strong password.

Arnold Reinhold
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://www.metzdowd.com/pipermail/cryptography/attachments/20220913/f1ea7134/attachment.htm>