Andrew Hosgood

OO PHP Web Developer specialising in User Interface Design and User Experience

What's in a Password? — A Math-lovers Guide

11th October 2013

With everyone using an increasing number of online services, we need more and more passwords to keep our secret stuff secret. When it comes to choosing a new password, there is certainly no shortage of help in the form of guides and generators. Unfortunately, a knowledge of security doesn't come without a little knowledge of maths and computers so I apologise in advance for all the numbers.

What I have noticed is that people usually go one of two ways — they either choose a password so simple it can be easily cracked or one so obscure that I am constantly having to reset it when they forget it. When it comes to passwords, you need two things: security and memorability. The latter is subjective, but what makes a password secure? Let's have a look at the three main methods used by password crackers trying to access your private stuff.

Common Passwords Attack

What we have learned after using computers for a long time is that people are generally quite bad at picking passwords. Over the years we have built up a list of the most common passwords (examples include Gizmodo, Boing Boing and Symantec who happen to be one of our clients) and according to SplashData, the top ten passwords of 2012 were:

  1. password
  2. 123456
  3. 12345678
  4. abc123
  5. qwerty
  6. monkey
  7. letmein
  8. dragon
  9. 111111
  10. baseball

Not very imaginative, are they? The first thing a password cracker will do is try (in order of popularity) every common password on its list. These are definitely passwords to avoid for (hopefully) obvious reasons.

According to xato.net, 91% of people use one of the 10,000 most common passwords – a list which you can download from them, just to make your life as a password cracker even easier.

Dictionary Attack

Even though a lot of people don't use a common password, a dictionary word is just as bad. There are hundreds of dictionaries online, full of words that can be happily cycled through by a machine. So quite simply: take a dictionary and try every word in it. This approach may sound mind-numbingly boring to you, but luckily computers don't understand boredom.

Some crackers try variations of words, trying common character/number substitutions, capitalisation and common suffixes such as:

  1. password
  2. Password123
  3. pa55w0rd
  4. P455w07d!
  5. …and so on

Brute Force Attack

If the cracker hasn't yet managed to find a match, it will move on to the most time consuming method: the brute force approach. The methodology is simple — given a password of finite length, try every combination possible and you will eventually get the password. The key here is something physicists refer to as entropy. Simplified greatly, entropy is basically: "How many ways can I organise a set amount of things?" In this case, the "things" are letters, numbers and symbols.

Entropy Explained

<maths>

I am asked to make a password 5 characters long using only numbers. There would be 105 (10 character choices I can make, 5 times) which is 100,000 possible passwords to choose from. Written out, these would be 00000, 00001, 00002, 00003…99997, 99998, 99999.

If I were allowed to use only lowercase characters but keep to a length of 5, there would now be 265 or 11,881,376 possible combinations ranging from aaaaa, aaaab, aaaac…ilsdj, ilsdk, ilsdl, ilsdm…zzzzx, zzzzy, zzzzz. As you increase the number of characters in your pool to choose from, the number of possible combinations increases.

If we now double the number of characters to choose from instead of increasing the amount of choices, using both upper and lowercase characters would render 525 combinations, or in human speak: 380,204,032. Although this is a sizeable number of possible passwords, mathematically speaking it would be far more beneficial to double the length rather than doubling the number of characters in your pool, as 2610 produces a gargantuan 141,167,095,653,376 passwords, or 371,293 times as many as doubling the pool. The relationship when changing the base is linear, but changing the exponent is (by definition) exponential – increasing it by a bit results in a massive increase in the results.

</maths>

A lot of password generators and guides will suggest that you substitute numbers and symbols in place of some common letters to increase complexity such as replacing an "e" with a "3" and an "s" with a "$". In essence, all this is doing is making it really hard to remember your passwords. Yes, you have made it more difficult for a human to work it out because it looks complicated, but computers don't care how "complicated" it looks — they will logically and unemotionally try every combination.

The Solution

The best way to pick a password is to pick some easy-to-remember words with a few numbers to increase the entropy. I recently made a password generator that generates simple yet secure passwords. It has a list of adjectives and nouns and picks a password in the form:

[Adjective][Adjective][Noun][3-digit number]

Some of the passwords that have come out are:

All of these passwords have at least 18 characters which gives an entropy of at least ten thousand octillion (1.86 x 1032) or 186,000,000,000,000,000,000,000,000,000,000 which will take even the most hearty computer several billion years to crack, but remain easily memorable due to their use of everyday words and simple numbers.

Rather than make your passwords more difficult to remember with all sorts of $, %, £, @, !, * and ~, try to make longer and more memorable, sensical passwords.

If possible, try to use different passwords for each site so that even if one of your passwords is cracked, the rest will be fine.

SysAdmin

You may have been is a workplace where the Systems Administrator (in his infinate wisdom and knowledge gathered from a "System Administration for Dummies" book or similar) has required that you change your password every so often to keep his beloved system secure. Or so he thinks.

In this situation, people are usually required to change their password every 30 days or so and are not allowed to use one of their previous 5 passwords. Most people have trouble remembering one password for 5 minutes and what you will find is that people start to use patterns in their passwords such as incrementing the last digit or using the date in some form or another. As we already know, computers love (or whatever the simulated electronic equivelant of love is) patterns and common strings as they can check them with greater ease than non-sequential information.

Because people have trouble remembering whereabouts in their sequence they were and because they are forbidden from using a password that is easy to remember, I have walked into a few offices with Post-It notes stuck on monitors with a suspiciously password-looking string of text on them. This is just insane and should be avoided at all costs.

If you are a SysAdmin, please help people choose easy-to-remember passwords and try to help them not write their password on a piece of physical paper stuck to a piece of office equipment. It is 2013 for Gods sake!

Tools

The most helpful tool I have found is How Secure is my Password? which will calculate the amount of time it would take to crack your password. It takes into consideration common passwords and dictionary attacks.

Another password checker I have used is the Gibson Research Corporations haystack calculator which checks the pure entropy of the password.

Footnote

If you enjoy the geekier things in life, you should already be reading xkcd. Even though I have been thinking about writing an article like this for a while, Randal beat me to the point, so respect to him.

Remember that on the World Wide Web, security is key. Treat your password like you treat your home and don't bolt your front door with a paperclip…

Andrew Hosgood

EDIT 06/11/2013

A BBC report on the 2013 Adobe hack shows that the most popular passwords for the stolen Adobe account details are (in decending order):