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
26 = 64). Non-integer entropy values are valid, so for example a
single lowercase letter has an entropy of approximately 4.7 (because
24.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.
