Random passwords are not necessarily good passwords

July 17, 2007

I was recently writing a random password generator and in the process it occurred to me that there is an important difference between random passwords and good passwords, because we mean different things by those terms.

A truly random password is one that an attacker can't guess better than through random chance even if they know your password generation algorithm, so that on average they would have to try half of all of the possible passwords before successfully guessing yours.

(How many possible passwords there are is based on how many bits of information are in the password.)

However, a good password is a password that will not be found by an attacker that is trying common password patterns (or the password patterns that are feasible for them to brute-force). A truly randomly generated password necessarily has a chance to be a bad password, unless you took explicit steps to exclude the space of bad passwords from what your random process can generate (which reduces how many bits of randomness are in the password).

How likely is it that a randomly generated password will be a bad password? If you are using general enough categories, you can use the difference in the number of bits of information. For example, if our password generation alphabet is letters plus digits and we consider all-letter passwords to be too weak, then there's a four bit difference in the total bits and thus our truly random password generator has a one in sixteen chance of generating a bad password.

I suspect that the best way to get rid of bad passwords is not to try to tweak your random password generator to exclude them, because that may have hard to understand effects on how many bits of information its generated passwords really have. Instead I would check the generated password for badness and, if it is bad, generate another.

Written on 17 July 2007.
« Why SSL and name-based virtual hosts don't get along
Why I like Python's large integer support »

Page tools: View Source, Add Comment.
Search:
Login: Password:
Atom Syndication: Recent Comments.

Last modified: Tue Jul 17 23:23:40 2007
This dinky wiki is brought to you by the Insane Hackers Guild, Python sub-branch.