Tuesday, 26 June 2012

Password Storage Challenge: bcrypt or loop salted hashes?

Background

A recent data breach on the LinkedIn database leaked around 6.5 million salted hashes. This ignited a healthy debate in the security community:
- Some people said you should only use bcrypt and that salted passwords are useless
- It was clear that LinkedIn failed to salt their passwords: This is the immediate worst option after storing passwords in clear-text.
- Other people suggested that "adding a salt only marginally increases the difficulty in cracking the passwords"


Since LinkedIn did not store the hashes securely 2 million out of the 6.5 million hashes were cracked within hours.

So who is right? I think the OWASP Password Storage CheatSheet provides the best advice:

1- Use a modern hash algorithm
2- Use a long cryptographically random per-user salt and make the salt hard to steal: Then the attacker must also bruteforce the salt and rainbowtables won't work, good luck!
3- Iterate the hash: This step seriously increases cracking difficulty

I only slightly disagree on this:
"As such general hashing algorithms (eg, MD5, SHA-1/256/512) are not recommended for password storage. Instead an algorithm specifically designed for the purpose should be used such as bcrypt, PBKDF2 or scrypt."

Challenge
Let me illustrate what I mean:
I challenge you to crack a random 15 character password hash that has been generated this way (assume you have the 2 different random 60 character long System and User salts):

Python example:



PHP example:

The point I am trying to make is that with a relatively modern sha512 algorithm if you salt and iterate in this way using a hidden System Salt (i.e. stored outside of the DB) and a per user Salt (i.e. stored in the DB and which you can reset as users reset their password also) most people are going to have a seriously hard time cracking this:


- For starters most tools do not support homebrew algorithms that iterate the hash and use fancy salts as above
- If you "only" hacked the DB you will have to brute-force the System Salt (could happen)
- The whole process is just too slow with 1 million iterations per user and the salts thrown in just for fun
- If you force users to have passwords longer than 14 characters the number of cracked passwords will be reduced significantly


Bcrypt
Ok. What about bcrypt?


- First of all, bcrypt is just making things slow, which is something that you can achieve to a much more granular level by experimenting with the number of iterations above: A delay that is very slow but acceptable for a user. Therefore despite all the crypto going on in bcrypt, we can achieve something similar with the number of iterations variable.
- Second of all, Jim Manico gave a great presentation for developers in Dublin recently where he touched on this very topic, he said something that surprised me (start at 02:09:08): ""You can take one of the biggest monster servers, one of the biggest CPUs on the planet and if you can hit bcrypt concurrently about a hundred times that CPU is pinned for like 30 seconds". So bcrypt does not scale and may DoS your box even without you being targeted (does your website have more than 100 concurrent users?).


For a great summary on this topic I would suggest to watch Jim Manico's summary for developers on Password storage (starting at 02:05:00). The rest of Jim's talk is also interesting, even if you are not a developer.


I also liked the following article by Troy Hunt: "Our password hashing has no clothes" (published right after I wrote this :)).