8.1. Password Generation

Assume that user passwords change once a year and that it is desired that the probability that an adversary could guess the password for a particular account be less than one in a thousand. Further assume that sending a password to the system is the only way to try a password. Then the crucial question is how often an adversary can try possibilities. Assume that delays have been introduced into a system so that an adversary can make at most one password try every six seconds. That's 600 per hour, or about 15,000 per day, or about 5,000,000 tries in a year. Assuming any sort of monitoring, it is unlikely that someone could actually try continuously for a year. Even if log files are only checked monthly, 500,000 tries is more plausible before the attack is noticed and steps are taken to change passwords and make it harder to try more passwords.

To have a one-in-a-thousand chance of guessing the password in 500,000 tries implies a universe of at least 500,000,000 passwords, or about 2^29. Thus, 29 bits of randomness are needed. This can probably be achieved by using the US DoD-recommended inputs for password generation, as it has 8 inputs that probably average over 5 bits of randomness each (see section 7.1). Using a list of 1,000 words, the password could be expressed as a three-word phrase (1,000,000,000 possibilities). By using case-insensitive letters and digits, six characters would suffice ((26+10)^6 = 2,176,782,336 possibilities).

For a higher-security password, the number of bits required goes up. To decrease the probability by 1,000 requires increasing the universe of passwords by the same factor, which adds about 10 bits. Thus, to have only a one in a million chance of a password being guessed under the above scenario would require 39 bits of randomness and a password that was a four-word phrase from a 1,000 word list, or eight letters/digits. To go to a one-in-10^9 chance, 49 bits of randomness are needed, implying a five-word phrase or a ten-letter/digit password.

In a real system, of course, there are other factors. For example, the larger and harder to remember passwords are, the more likely users will bed to write them down, resulting in an additional risk of compromise.