How Random.

Posted by Tom Colvin (Conseal Chief Technology Officer), 6 Feb 2011

Computers aren't very good at being random. They're machines built entirely on rules, with no free choice. How can you tell them to pick something randomly?

They end up, in fact, producing only "random-ish" numbers - they look random, but are essentially predictable.

Humans are, by nature, much better at being random. We do completely weird unpredictable things. A lot of people exclusively do completely weird unpredictable things.

Which is why, at least from this perspective, the results of a NIST study on password security may be a little surprising. Their study is worth reading (or forcing your administrators to read). In a nutshell, it describes how much easier human-chosen passwords are to guess than machine-chosen passwords.

It describes the entropy of different types of passwords. Entropy, in this case, is a measure of how random the password is: a password of E "bits of Entropy" can be guessed in 2E trials. Or: the lower the entropy of the password, the faster it can be guessed.

And the really interesting bit is just how much difference there is in the entropy of computer-generated versus human-chosen passwords.

Take for example an 8-character password, chosen from upper case and lower case letters, numbers, and any one of 30 symbols. That gives a choice of 94 symbols for each of the 8 characters, or 948 different possible combinations. If it were truly random, it would therefore need 948 different trials to guess it, because any choice is as likely as any other. (948 is about 252.7, so we say it has 52.7 bits of entropy.)

But if the user were to choose a password themselves, some choices are more likely than others. For example a lot of passwords are based on dictionary words, and we can then analyse different letter combinations to gauge what is more likely. In English, the most common starting letter is 'T' and if the word starts with a consonant then it's likely that the next letter is a vowel.

Naturally one man has spent his career analysing all such patterns, and we derive an estimate of the entropy of human-chosen passwords from this. For an 8 character password chosen from an "alphabet" of 94 characters, there are just 18 bits of entropy. That is to say, you'll most likely guess the password within 218 attempts.

That result is astonishing. An 8-character random computer-generated password is 23 thousand million times harder to guess than a human-chosen one!

So how long would it actually take to guess the password? Let's say we can make 1 million password attempts per second. (This isn't unreasonable: if a hash of the password is obtained, which in many cases is readily available, a modern computer should be able to compare about 1 million keys per second to that hash.) Even at that fast rate, the computer-generated password would take nearly 200 years to crack. But the user-chosen one would take less than a second!

So what recommendations should we make to all those who ask our assistance?

  • Prevent users from choosing common passwords. Preventing users from having any one of the 50,000 most common passwords increases the entropy of their choice from 18 bits to 24 bits (for an 8-character password). In other words, it requires 64 times the amount of time to guess.
  • Apply "composition rules". Requiring at least one of each of a lower case letter, an upper case letter, a number and a symbol increases the entropy for the same 8-character password to 30 bits. That is still crackable in 16 minutes, but that's vastly better than "less than a second".
  • Use long passwords. The longer the password, the greater the entropy. A 12-character password has 34 bits of entropy (~5 hours) and a 20-character password has 42 bits (~51 days) when combined with the above 2 rules. Longer passwords needn't be harder to remember: just think of a mnemonic. For example, the first letter of each word in a verse of your favourite song.
  • Finally, consider computer-generating passwords for users. It's the single most effective way to increase entropy. The downside is that it makes passwords harder to remember, so users will probably write them down. Possibly on a sticky note attached to their monitor.