Blog & White

Passwords are difficult to generate and to remember, and once you finally know how to type yours quicky, you don't want to change it. That's usually the time when someone is forcing you to change it… Here is a synthesis of what I've found out about how to generate secure passwords.

Entropy as a measure of password strengh

The strength of a password is usually expressed as its entropy, measured in bits. In a nutshell, it expresses the total number of different passwords that can be created (given some construction rules), represented as the base 2 logarithm of that total number. For example, if you know that a password is composed of a single character which may be a letter (uppercase or lowercase), a digit, a white space or a period (which conveniently makes 64 different symbols: 26 lower case letters, plus 26 uppercase letters plus 10 digits plus 2 punctuation symbols), the entropy of that password is 6 bits (because 2⁶ = 64). Non-integer entropy values are valid, so for example a single lowercase letter has an entropy of approximately 4.7 (because 2^4.7 ≈ 26). The addition of one bit of entropy multiplies the total number of different possible passwords by 2; a password made of 2 characters (64 symbols: upper/lowercase letters, digits and 2 punctuation signs) has therefore an entropy of 12 bits and a password made of 8 lowercase letters has an entropy of 37.6 bits.

The human factor

The above entropy measurement is true only if the password is truly randomly generated, and that each symbol has an equal probability of being selected. Humans seem to be rather bad at generating random passwords, and in Special Publication 800-63, the entropy of a human-generated password of length 8 is estimated to have an entropy of 18 bits.

Moreover, if the password is a word from a natural language, the number of possible different passwords is equal to the size of the vocabulary in that language; for English language this is estimated to be between 250,000 words. The entropy of a password made of a single English word is therefore approximately 17.9 bits.

Forcing more entropy

To increase the entropy of human-generated passwords, it is quite common to enforce rules, such as a minimum length, the use of more symbols than just the 26 lowercase letters and forbidding the use of common words. The NIST report above estimates that the additional symbols add 6 bits of entropy and the dictionary check adds 5 bits. An 8 character password following all the rules above is therefore estimated to have an entropy of 30 bits. For comparison, a randonly-generated password of 8 character chosen amongst the most common symbols on a computer keyword (80 symbols) has an entropy of 50.6 bits

Such password become however difficult to remember, especially if you have to memorize several of them and are forced to change them every few months.

And they are still pretty insecure.

Cracking passwords

There are two different methods for cracking a password.

The first method consists in connecting to the service asking for the password, and trying passwords until the right one is found. This method is slow, one can expect to test at most a few dozen of passwords per second (let's say 100 passwords per second). Using the entropy to measure the strength of the attack, that represents 6.6 bits per second, or 23.0 bits/day, or 27.9 bits/month, or 31.5 bits/year.

This gives the following times:

• 18 bits password: at most 45 minutes
• 30 bits password: at most 128 days
• 50.6 bits password: at most 560,000 years

The thing here is that reasonnably secure services will not allow that many trials.

The second method for cracking passwords requires a list of encrypted passwords e.g., stolen from a badly secured service. Depending on the encryption algorithm used with those passwords and the hardware at hand, one can expect an attacker to try between 2,000 and 15,500,000,000 passwords per second (between 11 and 33.8 bits/s) with a standard desktop computer (equipped with a modern GPU).

This gives the following times:

• 18 bits password: at best 128 seconds, at worst a few microseconds
• 30 bits password: at best 6 days, at worst less than a second
• 50.6 bits password: at best 274 years, at worst 32 hours.

How many bits are needed?

The times indicated above represent the maximum time needed for cracking the password. There is a 50% chance of cracking it in half that time, and a 10% chance of cracking it in a tenth of that time.

So if a password needs to be safe for at least 1 year, the time needed for cracking it needs to be at least a year i.e., 33.8 + 24.9 = 58.7 bits (entropy of the number of passwords tested per second plus the “entropy” of the number of seconds per year). There is however a chance that the password will be cracked in less time. Adding 1 bit of entropy will reduce the attacker's chance of finding the password in a given time by half, and adding 10 bits reduces it to 1 chance out of 1024 to crack it in that time. 7 bits would reduce it to 1 chance out of 128, which may be sufficient as well.

How to generate such a password?

A 68.7 bits password means 15 lowercase letters, or 11 common-keyboard-symbols. These have to be selected by a true random process, such as dice rolls, nuclear desintegration or electronic thermal noise. 6-sided dice are easy to come by, and the Diceware method is probably the easiest one for generating secure and easy-to-remember passwords. A rolls of 5 dice allows to select one word in a list of 7,776, providing 12.9 bits of entropy. The strenght of the password therefore depends on the number of words that are selected (by repeatedly rolling 5 dice):

• 1 word: 12.9 bits, cracked in less than a microsecond
• 2 words: 25.8 bits, cracked in less than 4 milliseconds
• 3 words: 38.3 bits, cracked in less than 30 seconds
• 4 words: 51.6 bits, cracked in less than 2 days
• 5 words: 64.5 bits, cracked in less than 55 years
• 6 words: 77.4 bits, cracked in less than 423,000 years
• 7 words: 90.3 bits, cracked in less than 3231 million years

The Diceware method also allows to add a random non-letter symbol to the password, adding about 9.5 bits of entropy for a 20 character password (about 5 words). Therefore a 5-word password with one random symbol can be considered secure for at least a few years.

How long will the password be safe?

Between 2002 and 2011, CPU and GPU computing power has been multiplied by 10 and 100 respectively i.e., +0.37 and +0.74 bits/year regarding password cracking. The rate of growth will probably not remain that high, but if one wants to keep a password for more than a year or two, it should be taken into consideration. For example, if a password must remain safe for the 4 next years, add 3 bits. The 5-word password with one random symbol will therefore be safe for the next 7 years.

One must also consider that computer clusters become affordable, and that a 25-GPU computer has been built exactly for the purpose of cracking passwords. This type of machine adds about 4 bits to capacity of cracking encrypted password (the “second method” above). That makes the 5-word diceware passphrase safe for barely over a year. Finally, cloud computing and parasitic computing using cloud-based browsers may reduce the safety period even further.

Conlcusion

The only truly secure passwords are long and truly random; any other method for generating passwords will lead to easily crackable passwords, and is therefore giving a false sense of security. Long enough passwords need to be changed, but not too often; 3 years is a reasonnable lifetime. The Diceware method allows to generate such password in a simple way.

Finally, memorizing a lot of passwords is difficult and induces people to reuse the same passwords. There is a simple solution to that, promoted by Bruce Schneier: write down your password and keep it in your wallet.