Password Authentication and Password Cracking
Introduction to Authentication
In this article we’re going to explore different authentication mechanisms. An authentication mechanism (or method) is a way for you to prove that you’re allowed to access something. Passwords have been the default method of authentication for as long as most of us have needed to prove to a computer that we’re allowed to access it. However, passwords are not the only authentication mechanism.
Something you know: Examples of this are your good-old password, bank card PIN or a safe-word when the alarm company calls your home; these are all examples of using something you know to authenticate yourself.
Something you have: Examples are a swipe card to access a secure area, a code sent to your cellphone as part of a login process (to prove you have your cellphone) or a SecureID token that provides a constantly changing code you need to enter to gain access – all are something you have that can be used to authenticate yourself.
Something you are: This is where biometric security comes in. To access our data center we have to put our index finger on a fingerprint scanner after swiping a card. Unless you steal someone’s index finger you won’t be able to access our data center, even if you’ve stolen a valid swipe card. Other biometric systems include retinal scans (the blood vessels at the back of the eye) and iris scans (the colored part of the eye).
Other attributes used for authentication: A few other attributes that you occasionally see used for authentication are:
- Somewhere you are. E.g. at a physical address able to receive snail mail.
- Something you can do. E.g. accurately reproduce a signature.
- Something you exhibit. E.g. a neurological trait that can be scanned by an MRI.
- Someone you know. E.g. that can be validated by a social network graph or chain of trust.
Our focus in this article is passwords. Most of us see them as an inconvenience – something you have to tolerate to be able to use a service you need access to. In this article we’re going to explain how computer systems have evolved in the way they process your password, how modern online applications do authentication and why it’s important to choose a strong password. Once you finish reading this you should have a working knowledge of hashing algorithms, how password cracking works and what “strong password” really means.
Plain Text Passwords
In the early days of computers and mainframes, passwords were stored in a database as plain text. When you wanted to sign-in, a gatekeeper application would ask you for your password. It would take whatever you typed in and check if it was equal to whatever it had stored in the database and if true, you were granted access.
As the Internet evolved and grew, malicious hackers started gaining unauthorized access to systems. Once they were in, they would immediately download the plain-text password database and have instant access to all users passwords. Developers and systems administrators needed to come up with a solution to this problem and the solution they came up with was ‘password hashing’.
Introduction to Password Hashing
Think of a hashing algorithm as a machine. In one end you input any text or binary data. Out the other end you get a number that is a certain length – lets say 32 digits long in our example. The data you feed in can be any size, from a few bytes to many terrabytes or larger. No matter what data you feed in, you get a 32 digit number (in this example) that uniquely represents the data.
What is amazing about a hashing algorithm machine is that if you feed something identical in you get the same 32 digit number. If you feed in War and Peace, you get a number. If you copy the book verbatim and feed in exactly the same text, you get the same number. If you change a single character in the novel, you will get a completely different number.
Hashing algorithms differ in the way they work and the most notable difference is the length of the number each one spits out.
- MD5 which is extremely popular spits out 128 binary digits.
- SHA2 spits out 256 bits (or binary digits).
When system administrators and developers first encountered the security problems with password databases that stored as plain text, they turned to hashing algorithms for help. What they came up with is, instead of storing your password in a database, they would just store a hash of your password. That is, the number that a hashing algorithm generates when it operates on your password.
When a user changes their password, or when a user account is created, the new password is typed in for the first time, the computer security application takes that password and runs it through a hashing algorithm and stores the resulting number in a database. The next time you try to sign-in and enter your password, the security system runs the password you entered through the same hashing algorithm and checks if the resulting hash matches the hash in the database (a hash is the number that a hashing algorithm spits out). If they match, then you’re allowed in.
No longer are passwords stored in clear text in a database. If a hacker steals the user accounts database, they don’t automatically have all passwords, all they have is a list of hashes.
Hashes are Not Perfect
Storing hashes of passwords instead of passwords themselves was a major breakthrough in information security. The story unfortunately does not end there. Now that hashes are commonly used to authenticate users instead of plain-text passwords, a hacker does not immediately have a list of all passwords when they steal the user accounts database. However, there is a way for a hacker to steal hashes and turn them back into passwords.
The method is relatively simple. When a hacker steals a database of hashed passwords, to reverse engineer the hashes (convert them back to passwords) the hacker generates hashes from a dictionary of words he thinks might be the passwords that were used. If any of those hashes match what he has in the database, he has managed to reverse engineer a hash and now knows what the original password is.
For example, lets say you have stolen a password database and you have the hash of the password that ‘mark’ uses. You want to know the actual password for the ‘mark’ account, so you take the word “banana” and run it through the same hashing algorithm that the password database uses. You end up with a number and if the number matches the hash in the password database for user ‘mark’, you now know his password. If it doesn’t match then I try ‘pear’ and ‘apple’ and ‘ApplePear435’ and progressively more words and more complex word combinations.
So to crack a password you need to take a very large dictionary of passwords and hash each of them, then compare those hashes to what is in the password database you stole and when you get a match you know the original password.
The problem is that generating hashes of words takes time. Each word might take a few milliseconds to hash. So you need a very fast computer to do this. Or alternatively you can take a very large dictionary of well-known passwords, generate hashes from all the words and store the words and their hashes. Then every time you steal a password database you can just reuse that list of words and their hashes. You don’t need to recreate the hashes every time. All you need to do is match your list of hashes with hashes in the password database and where you get a match you’ve cracked the password.
What we’ve just described is called a “Rainbow Table”. Rainbow tables are a method commonly used by hackers to crack password databases that use ordinary hashing without any additional security. Rainbow table attacks on hashed password databases are very effective because they are fast. To help protect against these kinds of attacks, developers and system administrators came up with a technique called ‘Salting’ Passwords.
Understanding Password Hash Salting
How Salts Work
A rainbow table attack relies on a hacker being able to take a dictionary and pre-computed hashes of the words in that dictionary and compare those hashes to the hashes in a password database. To defeat rainbow tables, the information security community invented “salted hashes”. The concept is relatively simple:
When you create a new password, instead of just running the password on its own through a hashing algorithm, you do the following: Generate a random little piece of text. Put that text at the beginning of the password. Then run the combination of the little piece of text and the password through a hashing algorithm. Then you store the little piece of text (as plain text) and the resulting hash. That little piece of text is called a “Salt”.
When someone wants to sign in, they type their password. The security application takes the stored piece of text or Salt, puts it at the front of the password that was entered and runs it through the same hashing algorithm to get a hash. It compares the resulting hash with the hash stored in the database and if they match you are granted access.
It’s important to note that the salt or “little piece of text” is stored as plain text with the hash. It’s also important to note that the salt is random for each password. In other words every password has its own special little piece of text.
This is a relatively simple concept but it makes cracking hashed passwords significantly more difficult.
Why Salts Make Cracking More Difficult
Recall that rainbow tables are a dictionary of words and the hashes of those words. In the above example, we used salts (the little piece of text) combined with our password to generate hashes. If a hacker wants to crack passwords, he can’t use his rainbow table because the rainbow table is just a hash of individual words. He needs to combine those words with the stored salt to get the actual hash that is stored in the database.
That makes cracking passwords much harder because it means a hacker’s rainbow table is useless and it forces him to recompute hashes for every word in his dictionary.
Here’s an example of a password being created for someone called “good-guy”:
- The system administrator creates a new account on the system for a user called good-guy with password ‘apple’.
- The system automatically generates a short piece of text “yrtZd”.
- The system takes the short text and combines it with ‘apple’ to create the text “yrtZdapple”.
- It then runs “yrtZdapple” through a hashing algorithm and ends up with a 128 bit number.
- The system stores that number as the hashed password for good-guy’s account.
Here’s how “good-guy” signs in:
- ‘good-guy’ arrives at work and tries to sign-in. He types in ‘apple’ as his password.
- The system retrieves the record for the ‘good-guy’ account. That record is a hash and the text “yrtZd” which is a salt.
- The system combines the word “apple” that good-guy just typed in with the salt to make the text “yrtZdapple” and runs a hashing algorithm on that.
- The system checks to see if the hash it retrieved matches the hash it just generated, it does match and it allows ‘good-guy’ to access the system.
Here are the steps a hacker takes to crack good-guy’s salted password:
- A hacker arrives and manages to hack into the system and he steals the database of password hashes and salts.
- The hacker tries to use pre-computed hashes of words in his English dictionary. One of the hashes is of the word ‘apple’ but that doesn’t work because the hacker needs to combine the salt, which is ‘yrtZd’ with the word apple before he hashes it.
- The hacker realizes his pre-computed rainbow table is useless. He needs to combine the salt for good-guy’s password with every word in his dictionary and then see which hash matches. That means he needs to recalculate hashes for his entire dictionary which is going to take significantly longer.
As you can see from the above example it is possible to crack passwords that use salts. It just takes much longer and requires more processing time.
Hashed passwords that use salts are what most modern authentication systems use. It does not make a password uncrackable but it does slow down the cracking process because it forces a hacker to hash every password that they want to guess.
You now have a working knowledge of how modern password authentication works on systems like WordPress, Linux, Windows and many other systems. You also understand why salts are useful – because they prevent a hacker from very quickly cracking password hashes by using rainbow tables. Now that you understand the benefit of salted hashes it may seems obvious to you that everyone should use them when building authentication systems. Unfortunately they don’t – there are many examples of custom-built web applications out there that did not use salts – they just used plain old hashes and when they are hacked it is relatively easy to reverse engineer the passwords using rainbow tables.
GPUs and the Home Supercomputer
Because modern password cracking uses salts, if you want to use a dictionary of words to try to crack a password database, it means that you are going to be hashing every one of those words with a salt each time you want to make a guess. So it becomes useful to be able to do hashing fast.
It turns out that modern graphics processing hardware (GPUs or graphics processing units) is very good at hashing and can do it in parallel. Using an off-the-shelf high-end gaming graphics card you can hash passwords thousands of times faster than even the fastest CPU on the market. This has resulted in most competent hackers purchasing GPUs for password cracking or using an online GPU accelerated password cracking cluster.
In just a few seconds, a modern GPU can allow a hacker to make several million password guesses.
Many of the algorithms that are used for hashing, like MD5, were developed decades ago when CPUs were very slow and GPUs did not yet exist. To try to compensate for the increase in computational power we’ve experienced, developers of authentication systems have come up with something called “stretching”. What this does is take a hashing algorithm like MD5 and instead of running it once on the password and the salt, it runs it thousands of times. In other words, the system will generate a hash, then generate a hash of the hash, then generate a hash of the hash of the hash and so on for thousands of cycles.
The result is that when a password cracker wants to try to guess a password, for each guess they don’t just have to generate one hash, but thousands of hashes. This has the effect of slowing things down but it still isn’t enough.
WordPress uses salted hashes to store passwords using the MD5 hashing algorithm. It stretches MD5 by doing over 8000 rounds of MD5 to try and make password guessing more computationally intensive. But a modern GPU can guess WordPress passwords at a rate of 3.2 million guesses per second. That is quite amazing in terms of performance. When MD5 was developed and when salts were first invented, hashing lots of words to try and guess a password took a long time. You might get a few guesses every second. Now we can achieve 3.2 million guesses a second.
You now have a good understanding of how passwords are used on services like Gmail, Yahoo, on WordPress websites and most other services that use a password to authenticate you. You also have a reasonable understanding of how to crack passwords.
Why Strong Passwords are Important
If one of the services you use is compromised and hashed passwords are stolen, even a teenager in his bedroom with a gaming PC under $2000 can try to turn your hashed password into a plain text password at a rate of 3.2 million guesses per second and possibly much faster. When you consider that eHarmony, LinkedIn, Google and many other well known brands have been successfully hacked over the past few years, it is quite likely that a service you use will have its hashed passwords stolen some time in the near future.
This means that it is important to use passwords that are very difficult to crack. Any password with less than 12 characters is weak.
How Crackable Is a Given Password
You need to assume a service you’re using is run by reasonably competent system administrators and that they are, at a minimum, storing hashed passwords rather than plain-text. For safety sake assume they’re using a weak hashing algorithm. In this case we’ll assume 1 round of salted MD5. Note that we’re giving them the benefit of the doubt that they’re actually salting their passwords.
If your password is 9 characters of lowercase numbers and letters, that gives you 101,559,956,668,416 possible passwords. (36 to the power of 9).
At Wordfence, we have an 8 GPU cluster that can crack salted MD5 at a rate of 90.6 billion salted MD5 guesses per second. It will take us 1128 seconds or 18 minutes to crack your password if we are guessing every single combination of letter and number 9 characters long. We can do it faster than that if we exclude certain patterns.
Now you begin to understand why longer passwords are better. You also begin to see why you should not just use letters and numbers, but special characters too. Any password that uses just letters and numbers is weak. Here’s why:
If you have a password made of just 1’s and 0’s and it’s 4 digits long, you will have:
2 to the power of 4 possible passwords or 16 possible passwords.
If you have a password made of the digits 0 to 9 (that is 10 possible characters) and it is 4 digits long you have:
10 to the power of 4, which is 10,000 possible combinations.
Now if you instead build your password out of all lower-case letters, upper-case letters, numbers and a set of 10 symbols, you have 26 + 26 + 10 + 10 = 72 possible characters. So if you have a password that is just 4 characters long you now have:
72 to the power of 4 possible passwords, which is 26,873,856 possible passwords.
As you can see, every time you increase the number of characters your password is made up of, you get a huge increase in the number of possible passwords, even though you keep the length at just 4 characters in our example.
You get 26 million possible passwords from just 4 characters if you use a wider range of characters in your password. That really illustrates how important it is to use upper-case, lower-case, numbers and symbols in your password.
If you now expand the length of your password to 12 characters, you have 72 to the power of 12 or 19,408,409,961,765,342,806,016. Even with our 8 GPU cluster it would take us 2495937 days or 6838 years to guess your password if we try every possible combination.
We would consider a 12-character password that uses random (see next paragraph) upper-case letters, lower-case letters, numbers and symbols to be a strong password. And to be clear, it is a strong password even if the service you’re using is storing passwords using 1 salted round of MD5 which is relatively weak. For comparison, WordPress uses over 8000 rounds of salted MD5 which of course makes it 8000 times slower for a hacker to crack WordPress passwords.
It is important to note that your password should be random characters and not made up of patterns like beginning or ending with a number or dictionary words. As soon as you introduce dictionary words and predictable patterns into passwords, they become significantly easier to guess because a password cracker can simply exclude everything that does not match a predictable pattern.
As computers get faster at hashing, what will developers do?
If the trend over the last few years is anything to go by, reverse engineering hashed passwords back into their plain-text is going to keep getting faster at an increasing rate. The GPU cluster that we built to audit passwords for Wordfence customers is faster at hashing than the fastest computer on Earth in 2003. This is an illustration of how fast computing power is increasing.
The past 5 years has seen an explosion in purpose built hardware that does what a CPU would previously have been used for. The difference is that this hardware processes in parallel and is therefore much faster. The consumer gaming GPUs that we have discussed above contain over 2000 cores that can do calculations in parallel. Another area that has been fuel for innovation in parallel computing is Bitcoin mining hardware. You can buy ASICs and FPGAs which are both ways of creating an application on a chip – and both can perform tasks like hashing in a massively parallel fashion. Bitcoin miners use ASICs and FPGAs for mining and have driven the price of this hardware down. It can also be used to crack passwords in parallel and at very high speed.
If we assume that hardware will keep getting faster at an increasing rate, we need to focus on how we store passwords. Using hashing to store passwords is widespread and is the accepted solution for now.
Can we use better hashing algorithms?
In computer science we usually strive to make algorithms faster. Paradoxically, a better hashing algorithm for passwords is one that is slower, or computationally more expensive.
The benefit of a more expensive and slower hashing algorithm is that if you can slow down how long it takes to hash a password, you are slowing down how fast hackers can guess passwords. Algorithms like bcrypt let you specify “complexity” which affects the speed at which hashing occurs and therefore the speed at which guessing occurs.
Another useful algorithm is scrypt which is designed to make it difficult to do calculations in parallel. That means that a hacker can no longer use the 2000 cores in their GPU to try to crack your password at the same time. They instead need to make one guess at a time.
These options are not without problems. Application developers like Facebook and Google want to provide useful services to you. They become popular and have 10s of thousands of customers that want to log in. If they use a hashing algorithm that takes say 5 seconds per hashed-password on a server, that means they need 5 servers just to allow 1 user per second. They would need 50,000 servers to be able to allow 10,000 users per second to sign-in. For Facebook that might be unacceptable and they may opt for a faster but weaker hashing algorithm.
There are a few interesting options to allow slower hashing without overloading servers that are being discussed in the information security community. One of them is quite simple and it’s called “server-relief”. The way server-relief works is it uses a slower hashing algorithm like bcrypt or scrypt, and actually does most of the hashing in your web browser when you are signing in. That uses your workstation’s CPU instead of the computing power of the servers belonging to the service that you are signing into.
A hash that took longer to calculate is then sent by your web browser to the server you are signing in to, which turns that into a salted SHA256 hash and stores it. The effect is that you used a CPU intensive hashing algorithm that might be hard to parallelize and is slower. Your web browser did most of the computation which saved valuable CPU cycles on the server you are signing in to. This would allow an authentication server to handle a large number of customers signing in and to use a computationally expensive hashing algorithm without getting overloaded.
That concludes our introduction to hashing and passwords. We have covered the history of password storage, why password hashing is used, what rainbow tables are and how salted passwords defeat a Rainbow Tables attack. We have also discussed how password cracking is done and how hardware like GPUs ASICs and FPGAs can accelerate cracking. We also gave you a brief introduction to algorithms that make it more difficult to crack passwords and a performance architecture that allows the use of a strong hashing algorithm without overloading servers.