How to use Linux’s Traceroute (3 Examples)
Linux: Changing your password from the CLI
Chrome locking up with .pki/nssdb directory error
Updating Chromium on Debian 6 (Squeeze)
How to upgrade Ubuntu to 12.10 – Quetzal
Salting passwords – how & why?
Our lives are now run by passwords. We’re forced to remember more passwords everyday it seems. How can developers secure passwords more securely? Why is salting passwords important and how does using salts improve the strength of stored passwords?
Consider this; what happens if the online store you run is hacked and all your customers details lifted? Hopefully all they will get is a list of email addresses, passwords and a list of the cereal products they regularly consume. But what happens if your customers use those passwords on other sites too?
What happens if your customers use that password and email combination for their banks, or contract mobile phones? Then this grocery store hack suddenly becomes quite a daunting ordeal. The bad guys suddenly have access to thousands (maybe millions) of email addresses and passwords they can try on other, more lucrative, sites.
This is where salting passwords becomes hugely important.
Why cryptographic hashing isn’t even enough
We’ll skip over the obvious security failings of storing your users password in plain-text, moving straight to why even hashing passwords isn’t enough now.
If you’re unaware of what hashing is; in simple terms it’s a mathematical function that turns your password into an arbitrary string of characters. Hashing A to B is easy; however de-hashing B back into A is hugely computationally expensive. The strength comes in the one-way nature of these functions.
So how can they be weak? Well carry on reading.
Password hashing isn’t enough
Lets say our email address and password are firstname.lastname@example.org & swindon respectively, nice and simple to remember. You’re one of a million people registered on a site. Well shock horror, the database is compromised and our data is stolen. If the password is stored in plain-text, they’ve got everything they need. Game over.
However, some clever software engineer stored the passwords after running them through the MD5 hashing algorithm. So instead of our ‘swindon’ password appearing in the password column, this appears:
Looks complex! You’d think that’d be really hard to crack, right? Wrong.
True it’d be hard to calculate that hash back into the word ‘swindon’, but crackers have been compiling dictionaries of known hashes for years. For example they’d have their own database with millions of rows of this kind of information:
71d0a9c7ba282e2329191836d61efbdd -> bristol
bc180dbc583491c00f8a1cd134f7517b -> london
05c448b67a6e304f6b03692bfe2ef02f -> swindon
d177b4d1d9e6b6fa86521e4b3d00b029 -> liverpool
They’d then simply compare their stolen data of a million users, to all of these pre-calculate values, quickly noticing that our password hash matches row #3, giving us the value swindon. Cracked in milliseconds! (sigh)
That’s why everyone is told to use a mixture of letters, numbers and special characters etc.
Shame few people ever listen.
However even with special characters and digits, that only increases the range of each character from 1 in 26 to about 1 in 50. So if my maths is correct; every 6 character password that is physically possible to enter, can be stored by our crackers with their corresponding hashes, in a 15,625,000,000 row table.
These pre-compiled tables of hashed passwords are pleasantly named rainbow tables. Sound pretty don’t they. Sounds big too? Sounds like they’d take a while to make?
Well it probably would take them a while, generating cryptographic hashes is slow (in computing terms), but they’ve had years to make these tables. How many new letters or characters appeared on your keyboard in those years? None.
You’d think these cryptographic hacking tools, the rainbow tables, are difficult to get your hands on? Wrong! This is the internet people, come on! Google it. For example, more rainbow tables than you can ever need (thankfully not literally!)
Why static salts are bad
So we can either tell people to remember longer and longer passwords, or we can introduce password salting into the mix. Well people aren’t getting smarter (IMHO), so we better improve our security systems then!
Password salting combines the users password with an arbitrary string of bits, thus modifying what is stored in the database. When the user comes to sign in, their attempted password is combined with the salt again, to see if it matches the value in the database.
So our original password, swindon, is now salted with the word ‘roundabout’.
So the hash for swindon becomes:
93610f3e507f52a65b04b4d3dac5d435 – (Different from our original MD5 hash)
So surely this is nice and secure?
Well it’s getting there, but consider these two points.
Point #1) Somewhere in the code of the system, this salt value is written down in multiple places. It needs to be, after all, your system needs to know what value to combine the passwords with. Well if someone cracks your site and steals the database of 1M passwords, they’re likely to be able to look around for this salt value as well. So in our example, they quickly find the value roundabout and start creating their own rainbow table with this salt value combined to each password combination. If the salt is known AND is static, then it doesn’t increase complexity at all. It just increases the time before the system is defeated.
Point #2) Okay lets assume you’ve managed to hide the salt value perfectly, or the rainbow table is taking for ever to generate. Look at the example below, showing usernames and password hashes.
alex b35dcfd919c7f0a0e4ca44b5c44c5453 bary s21f3e507f52a60004b4d3da8ac5e41c carl b35dcfd919c7f0a0e4ca44b5c44c5453 dave 569bd6b536f36f3916fa34e4fbf15f41
Notice a weakness?
Well if you haven’t spotted it, you can see that Alex and Carl have used the same password. Their hashes are identical. This is quite likely to occur in large databases too. So if it takes 60 seconds to reverse look-up Alex’s password in the rainbow table, then you can save yourself an additional 60 seconds later on by noticing that Carl used the same password. Their passwords cracked even with the roundabout salt, revealing their secret geeky nature.
Why double salting password is worse!
It’s quite common on security forums and blog to see people talking about double hashing the password, that is to take your hash…
93610f3e507f52a65b04b4d3dac5d435 – (swindon + roundabout, hashed in MD5)
… and pass it back through the same, or different, hashing function.
While this does indeed create an extra level of complexity that will probably guarantee the fact your attackers need to create a bespoke rainbow table for you, this doesn’t add much strength to the final solution. They’re still producing a rainbow table that once made, can crack the whole database.
So time to move onto the most secure form of salting.
Uniquely salting password = hugely secure
As you’ve probably guessed from the heading, this method uses a unique salt to give each row in the table its own strength. By that I mean that each password in the database has a different salt, unique only to that row. For example instead of using roundabout as the salt for the entire passwords database, you now use something distinct, such as their email address.
So if we go back to our previous example where Alex and Carl’s password were the same, this time using each of their names as the salt, we get:
alex 3d718bdbfb906b80183961a4e6b8dd94 bary b59a55b5a6397500a53eff9bfdae2043 carl 3df771eda635994d2e1c2a5cd6eddd6d dave 02e2a824720248f1dea06833d61b9221
In fact, all four of these people have the same password, but you can no longer tell because their unique salt is making each password personalised BEFORE the hashing occurs.
Now if by either brute force, luck or other method we work out Alex’s password, we can’t use that piece of knowledge to guess the other people’s passwords. Strength!
Even if our attackers work out we’re combining the password with their name / email address beforehand, they still have to generate a rainbow table for each ROW in the table. More strength!
Thus for a 6 character password, by using a unique salt to store them, we’ve gone from needing one 15,625,000,000 row table, to needing 1 million of these tables! Not only that, each table needs to be made there and then, for each email address. You can’t pre-generate those tables as the scope of email addresses is so vast.
If it took the attackers a single day to generate a rainbow table with 15 billion hashes in it, then knowing the 1 million email addresses it’d still take over 2,700 years to crack your entire passwords table.
This doesn’t even take into consideration the fact passwords are often longer than 6 digits, and sometimes contain other special characters too. Even more strength!
So we should be able to see the security strength we can gain by uniquely hashing passwords.
Summary on Password Salts
So in a very quick summary, because this is quite a long post, you should implement individual and unique hashing to passwords in your system.
Do not re-use salts from one row to the next, try to keep it as unique to each password as possible. This is easy to do in most system languages and you should take a quick look into the documentation for each language to ever improve your system security.
I haven’t even touched on hash collisions or different hash algorithms, although it should be said that MD5 shouldn’t be used due to possible weaknesses. It is used purely in this article for demonstration purposes.
P.S) What hashing function to use?
I’d recommend using either SHA256 or SHA512 if possible, although there are dozens out there. Avoid SHA1, MD5 or anything you’ve written. You might think its secure using a hash function you’ve created, but I can guarantee you it’ll be mathematically weaker than the latest SHA’s.
P.P.S) A little note on passwords
Even if no sites are hacked, what happens if the password you use is actually quite a common password? I don’t mean in the top 25 list of passwords either, I’m talking in the top few millions! When sites say not to use dictionary words, they mean it. Always use a combination of uppercase, lowercase, special characters and numbers for EVERY password.
If you want to go down the “it’s for the greater good” path too, the more unique your password is the less likely it is to accidentally match (‘collide’) with someone elses. This makes the attacker’s job that little bit more difficult.