Verifiably Bad Passwords

Verifiably Bad Passwords

MATT WEEKS | @SCRIPTJUNKIE1
December 3, 2019

Nearly every day I need to create a new password for another website, for an expired login, or to encrypt a file to send to a friend. Re-using the same one or two passwords is a bad idea but trying to come up with an unguessable and uncrackable password is also highly likely to fail. People overestimate their own cleverness; most begin with memorable words or phrases and apply predictable modifications. These modifications may include replacing letters with lookalike characters, repetition, or appending a number or symbol. As a result, adversaries operating with very limited resources usually crack over 90% of hashed passwords when the predominant users’ language is known. (http://www.adeptus-mechanicus.com/codex/hashpass/hashpass.php) This level of success occurs even with passwords over 50 characters long and those composed of many words. Nearly any password generated by a user themselves is a verifiably bad password. As a result, truly randomly generated passwords are the only way to ensure password security.

It is sometimes necessary to share a password with someone else. This commonly occurs when encrypted files must be sent via email or file share service. The password is typically shared over a more secure (but usually lower-bandwidth) medium. The password could be shared verbally or read over an encrypted phone call. Sharing the password through a secure messenger app on a mobile device is another option. In any of these situations, a passphrase is a far more efficient option than a typical “complex” randomized password using letters, numbers, and symbols. But common phrases and quotes can be guessed just like passwords; a verifiably random phrase is required. And how long is long enough?

Users must defend against well-resourced adversaries. Such adversaries may have the ability to design and manufacture custom chips to crack password derivation schemes. The most prominent example of this is in the bitcoin network. In exchange for block rewards currently valued around $130,000, approximately every 10 minutes bitcoin miners create and operate ASICs and other hardware using vast amounts of electrical power. This entire network calculates 90 million TH/s; that is, 90 million trillion SHA-256 hashes per second. This number(9 × 1019) is roughly equivalent to 266 hashes per second (log base 2 of 9 × 1019 is about 66.29). All mined bitcoins are currently valued around $180 billion. While many miners make a profit, many more have netted losses. We can therefore infer it would take a comparable amount of money to create a comparable cracking network. In other words, it would almost certainly take billions and possibly hundreds of billions of dollars to attempt 266 hashes per second.

If the entire worldwide bitcoin mining network was instead built to crack passwords hashed with SHA-256, it could crack any and every 66-bit-long password every second. Or alternately, suppose all the passwords were made of lowercase letters. The multi-billion-dollar cracking network could attempt every 14 character password against a hash in one second (log base 26 of 9 × 1019 is about 14.1).

Even though a typical user will likely never face an adversary this powerful, passphrases should ideally have at least this level of entropy. We can calculate this as follows:

  1. Start with a wordlist of distinct words. I like this one (http://www.mieliestronk.com/corncob_lowercase.txt) which contains 58,109 different words.
  2. Randomly pick a word. Please Note: The default random number generators in most languages and systems (such as the .Net Random or C rand function) are predictable; use a cryptographically secure one instead. (For example: RNGCryptoServiceProvider or /dev/random)
  3. Assume the adversary has the user’s scheme and wordlist. These do not change (or do not change much) so it is not a good idea to assume they will stay secret.
  4. A single randomly selected word out of 58,109 has 15.826 bits of entropy (log base 2 of 58109); each random word added to the passphrase adds the same amount to the total entropy of the password.
  5. More than four words are required to get past 66 bits of entropy (since log base 58109 of 9 × 1019 is about 4.188); five words results in 79.132 bits of entropy. An attacker would need to try 279.132 guesses before trying all the possibilities.
  6. The randomly selected password could be one of the first the attacker tries or it could be one of the last. It is unknown in which order the attacker will guess. But on average, the attacker needs to try only half before hitting your password; that is 278.132 attempts.
  7. If the attacker had a bitcoin-equivalent network, this will take on average 211.845 seconds, or just over an hour, to perform the attack.
  8. A six-word long password results in an average crack time of 227.671 seconds, or nearly 7 years, even for adversaries with a bitcoin-comparable cracking network. That is much better! However, that’s not the whole story. File encryption software should also use a key derivation function to make cracking more difficult. For example, per http://www.crark.net/crark-7zip.html, 7zip uses over 130,000 iterations of SHA-256 in its key derivation function. That means that each guess takes not one hash, but 130K or 217 executions of SHA-256. This would result in a five-word password taking over 15 years on average to crack. A four-word password would take over two hours on the multi-billion-dollar bitcoin-equivalent network. Attackers with mere millions of dollars’ worth of cracking horsepower would likely still take years to crack such a four-word password.

So, what is a practical way get passwords like this? From Windows, the simple way is to open this zip file at https://git.io/JeO11 and drag the shortcut to the desktop. Any time a password is needed, just double-click the shortcut. The first time the user clicks, it downloads the script and dictionary file. From that point forward, it operates entirely off-line.

Should you be justifiably wary of clicking links, the script it grabs and runs can be examined at https://git.io/JeO1a. I encourage all to try it for better password security!