Random Password Strength

Introduction

Random passwords can be generated manually using everyday sources of randomness such as coins or dice. They can also be generated using a computer. However, using software to generate random passwords is non trivial and requires a cryptographically strong pseudo random number generator. Also, just because a password is random, doesn't guarantee it's a strong password; it is possible, although highly unlikely, that an easily guessable password is generated. If a weak password, such as a dictionary word, is generated it should be rejected.

Given a strong random password, how many attempts would it take an attacker to guess it? How do we calculate and specify the strength of such a password? In order to answer these questions we will start by considering something called entropy.

Entropy

In IT security, password entropy is the amount of randomness in a password or how difficult it is to guess. The entropy of a password is typically stated in terms of bits. For example, a known password has zero bits of entropy, while a password with 1 bit of entropy would be guessed on the first attempt 50% of the time. A password with n bits of entropy would be as difficult to guess as an n bit random quantity. Stated more generally, a password with n bits of entropy can be found in ₂ⁿ attempts.

It was the mathematician Claude Shannon who first used the term entropy in information theory.

Calculating the entropy of a password

The entropy of a randomly selected password is based on its length and the entropy of each character. The entropy of each character is given by log-base-2 the size of the pool of characters the password is selected from - see the formula below:

entropy per character = log2(n)

password entropy = l * entropy per character

Where n is the pool size of characters and l is the length of the password.

Thus the entropy of a character selected at random from, say, the letters (a-z) would be log₂26 or 4.7 bits. The table below gives the entropy per character for a number of different sized character pools.

Table 1. Entropy Per Character for Character Pools

So, from the table above, we can see that a 20 character password chosen at random from the keyboard's set of 94 printable characters would have more than 128 bits (6.55 * 20) of entropy. A password with this much entropy is infeasible to break by brute force (exhaustively working through all possible character combinations).

We can see how both the pool size of available characters and the password length affect the strength of the password; and that long random passwords are extremely strong. While these types of passwords may be used by, say, one computer to authenticate to another computer, they are not much use to humans. Humans are notoriously bad at remembering passwords. A difficult to remember password will have an adverse effect on security because the user will need to write it down somewhere - typically on a Post-it Note near to their computer.

User selected passwords

For many situations, a random password is not a practical approach and it is better to ask the user to select a memorable password that meets a number of criteria designed to increase the entropy of the password. Below are some recommendations from NIST for passwords that are used to authenticate a user.

NIST estimate the following criteria for a user selected password yields 30 bits of entropy:

• a minimum of 8 characters, selected by users from an alphabet of 94 printable characters,
• should include at least one upper case letter, one lower case letter, one number and one special character,
• a dictionary is used to prevent users from including common words and
• permutations of the username as a password are prevented.

NIST recommend these password criteria are combined with mechanisms to mitigate against dictionary and brute force attacks and that passwords are changed on a regular basis.

Note the above recommendations are one example and it is important to examine your own security requirements carefully before deciding on a suitable password policy.