Let's apply this to a password. Suppose we are only allowed to use numeric digits in our password. In other words, our password is a PIN that we use to get cash from an ATM. Each character is selected from a set of 10, from 0 to 9. How many bits of entropy are there per character, assuming that each character is going to be selected randomly?
First of all, there are eight bits per character using an ASCII character set, but most of those bits can be discarded without losing the 'essence' of the digit. We can compress the characters to a simple binary code: 0000 for 0, 0001 for 1, all the way to 1001 for 9.
We can say there are between three and four bits of entropy for each digit (only 8 and 9 need four bits – the rest of the digits need three) and use a bit of mathematics to basically calculate log2(10), which gives us 3.3 bits per digit.
If the digits in the password are chosen randomly (so that the PIN isn't 1111 or 1234, for example), the digits are independent from each other. In other words, knowing one or more digits in the PIN doesn't help us guess the remaining ones. The total entropy in a four-character PIN is about 13 bits.
This means that guessing a four-digit PIN is equivalent to tossing a fair coin 13 times to get a particular sequence of heads and tails. Since there are 2ˆ13 (8,192) different ways to toss a fair coin 13 times, we have some appreciation of how many trials a hacker would have to make in order to break a PIN. I know there are 9,999 possible different PINs. I've rounded the total entropy down, but the error is insignificant and using bits of entropy makes the estimates for cracking a password easier to understand.
Bear with me. Now let's look at it from the hacker's viewpoint again. Let's say that using some specialised password-cracking programs, a hacker might be able to generate and try one million passwords per second. One million is roughly 2ˆ20, so another way of looking at this is that our hacker can test 20 bits of entropy per second.
Our PIN number would fall instantly. Luckily the issue with hacking PINs is the validation of them: hopefully your bank would lock the account after three invalid attempts or so. Still, this is a nice round number for evaluating the strength of a password: a password with an entropy of 20 bits will be cracked in one second.
Also, since there are approximately 2ˆ25 seconds in a year, we can estimate that our virtual hacker will crack a password with an entropy of 45 bits in a year. We'll call such a password a year-strong password.
Since every extra bit of entropy doubles the cracking time, we can estimate that a 50-bit password will take 32 years to crack. Doubling the speed of cracking will halve the time taken, and therefore require an extra bit of entropy to get us back to where we were.
Now that we have a feel for the strength of passwords using entropy, we can try using different character sets for our passwords. For now we'll assume that each character in a password is chosen randomly; we'll talk about what happens if this is not the case later.
Let's add the characters A to F to our set of possible symbols. This is what WEP passwords were like on your old Wi-Fi router (WEP was deprecated in 2004).
There are exactly four bits of entropy per character. A 10-character WEP key (the original standard) would have 40 bits of entropy. A brute force attack would discover it in 2ˆ20 seconds, or 11 days. WEP suffers from other security issues, so a brute force attack wouldn't be needed in practice.
Now let's look at just using single case letters to form a password. Since there are 26 of them, we have 4.7 bits of entropy per character (2ˆ4.7 = 26). Let's suppose we want to have a year-strong password, then we would have to have a 10 letter password, with each letter being completely random. If you're using uppercase, lowercase and digits, that's a 62 element set, or just under six bits per character. A year-strong password would need eight characters, and these would need to be completely random.
Adding punctuation like commas, semicolons, question marks and so on would give us another 16 possible characters, to make 6.3 bits of entropy per character. A year-strong password would need about seven characters.
The biggest problem for us as humans when presented with completely random passwords is memorising them. It's possible with one eight-letter random password I suppose, although I'd hate to, but several of them would be a chore, especially if they involved punctuation.
A better option is to generate quasi-random (or random-looking) passwords. You could say these types of passwords have mnemonics built in and are nothing like '123456' or 'password'.
While we're discussing entropy and character sets, let's play around with another type of symbol set: the set of all words. To be more specific, suppose we have a list of 2,000 words. The entropy per word is 11 bits, since 2ˆ11 is roughly 2,000. How many random words from this list concatenated together would produce a year-strong password?
The answer is, surprisingly, roughly four. If each word is seven letters long or fewer, you'd be typing in 28 characters or fewer for your password. If the 2,000 words in the list were specially chosen to help evoke images in your mind, memorising the four-word password would be much easier.
Unfortunately, few services will allow a 28-character password. And how would you choose the words randomly? A computer program is one way, but if you just have the numbered list of words, you could try shuffling a pack of cards. Take out the court cards. Shuffle the rest well and deal out three. Counting 10 as zero and ignoring suits, you can read off a four-digit number between 0 and 999.
Now check the colours shown: if you have more reds than blacks, add 1,000 to your number. You now have a random number referencing one of your words in the list. Repeat this three more times to get the four random words.
As a final word, let's repeat the winner of the Best Gag award at the 2011 Edinburgh Fringe Festival. It was by Nick Helm and went as follows: "I needed a password eight characters long, so I picked Snow White and the Seven Dwarves." And on that note, I'm logging off and changing my password.