Password security

An attacker trying to get into a password-protected application (a password-protected RAR archive, an email account…) has several ways of getting a result without knowing the password. Some of them require a certain amount of intelligence, cunning and knowledge, while others require a bit of luck and physical fitness. So let’s start by summing up what options an attacker has.

How to break someone’s password

• Find someone who knows the password (the owner of the email account, for example) and get it from them – talk them round, bribe them, beat it out of them. I will not describe this method any further in the article :-).
• Try to trick the owner into giving the password away without them noticing, for example with a fake email, which is known more technically as phishing. The method consists of sending the account owner an email asking them to send you their username and password. It is up to you how convincing the message looks – the request alone would probably not be enough, so you need to add some kind of story. We often come across the claim that a database has broken down and so all users are asked to enter their password and username again, otherwise their mailbox will be deleted, and so on. If the message looks really convincing, the success rate is often quite high.
• A dictionary attack – we download some lists of the most common passwords from the internet and try them all. If we are lucky and the owner has a fairly common password, we really can get it easily. This leads to the key lesson – do not choose passwords that make sense. Choose the password sunshine, for example, and I guarantee that the first clumsy amateur hacker will crack it in a few seconds. This is probably the most effective method – if you have a really big dictionary of passwords, you can guess the password of a large share of users without much effort.
• Brute force is the crudest method – raw power. It consists of trying every possible password there is in the world. A program assembles letters one after another according to some algorithm and tests whether it has hit the required password. When it finds it, it saves the password and stops. We will look at this method in more detail below.

Brute force

A program using this method simply builds different arrangements of characters and tests whether it happens to hit the password. Let’s work out how long such guessing can take.

Suppose we have a password of five characters made up only of lower-case letters of the English alphabet (without accented letters such as č or š). There are twenty-six letters in the English alphabet. Now we can easily work out how many different passwords we can build from five such letters. We will use arrangements, since order matters (the password stone is not the same as notes, even though they are made up of the same letters), and we also need arrangements with repetition, because letters can repeat in passwords. So let’s get to the calculation itself. The number of arrangements with repetition is n^k: there are n choices for each of the k positions. For n we substitute the number of letters we choose from – the number of letters in the English alphabet – and for k we substitute the number of letters in the password, in our case five. We get 26⁵, which is approximately twelve million different arrangements. Is that a lot or a little?

That depends on the machine we have available. An old, slow machine manages few comparisons per second, while state-of-the-art computers manage ten thousand times more. In these examples I will assume that the computer manages ten million comparisons and evaluations per second. By now everyone can probably see that such a computer would find a five-character password within two seconds, which is really not a good result. But let’s not give up.

Strengthening the password

A five-character password is not secure in the slightest, and some more sensible systems do not even allow you to choose a password that short. It is said that a password should not be shorter than eight characters. Now let’s work out how many arrangements there are for an eight-character password. As before, we will consider only lower-case letters of the English alphabet. Substituting into the formula, we get 26⁸, which is approximately two hundred billion arrangements. That is a nicer number. The computer would check all the arrangements in under six hours. That is better than last time, but let’s see how the strength of the password would grow if you also used capital letters, digits and special characters such as underscores, hyphens and so on.

There are 26 lower-case letters and also 26 capital letters, which gives 52 characters altogether. To that we must add 10 digits and some special characters. Not all special characters are allowed everywhere, so for simplicity I will count only eight special characters, so that the number of characters rounds up to a nice 70. The length of the password will again be eight. After substituting we get this number: 70⁸, which, to give you a better idea, is approximately 5.8 × 10¹⁴, in words almost six hundred trillion arrangements. That is quite an impressive number. Our computer would check all the arrangements in sixteen thousand hours! That is just under two years. The attacker would have to be very lucky to discover the password in any realistic time. On top of that, they would have to know the length of your password – if they did not know the length, they would also have to check arrangements with fewer characters.

Some people are so worried about their data that they use numeric passwords. These passwords are very resistant to a dictionary attack, because it is unlikely that a dictionary of commonly used passwords contains, of all things, 41,274,390,553. Unfortunately, although such passwords are resistant to a dictionary attack, they are less resistant to brute force. There are only ten digits, which means that the number of arrangements is always 10^k. The strength of the password is kept up only by its length. Our previous eight-character password with all kinds of characters had approximately 5.8 × 10¹⁴ arrangements. To reach at least the same with a numeric password, it would have to have fifteen digits, almost twice as many characters. It is clear that it is more effective to choose a shorter password with more kinds of characters.

Do not underestimate the attacker

An attacker can be clever. After reading the lines above, you have, let’s say, decided to change your current password “lemonade” to at least “Lemonade”, which multiplies the number of possible arrangements several times, since the attacker now has to include capital letters in the algorithm as well. But the attacker may assume that the capital letter will only be at the start, because that is easier to remember and it is not usual for a capital letter to be in the middle of a word. So they write an algorithm that checks all the arrangements of words with lower-case letters and possibly with one capital letter right at the start.

Your original password had a complexity (by that I mean how many arrangements there could be in total if we kept the same form of password – eight lower-case letters) of 26⁸. If the attacker did not think ahead, the new password would have a complexity of 52⁸, but if they used the algorithm outlined above, the password would have a complexity of 52 · 26⁷. In the first position of the password there can be any lower-case or capital letter, 52 of them altogether, while in the remaining seven positions only lower-case letters can appear, which is an ordinary arrangement with repetition.

The attacker may also happen to know that your password consists of four letters and four digits, not mixed up, with the digits always together and the letters always together. We would work out the complexity of such a password like this: the first group of four letters has 26⁴ arrangements in total, and the second group of four digits has 10⁴ arrangements. We then multiply these two results: 26⁴ · 10⁴. If the attacker did not know whether the digits or the letters come first, we would have to multiply the previous result by two as well.