md5/sha1+salt and Bcrypt


Just the day before yesterday, the biggest developer community website in China, CSDN, was cracked, and the database is leaked. In the leaked database, the password was stored in plain text. People are tweeting password and security related message around. I noted a message saying that md5/sha1+salt is unsafe to store password. It strongly suggested using Bcrypt instead. Even I am not good at encryption and security, in my memory, sah+salt is the most popular way to store password. How could it be unsafe?

I defined the password security in two levels: yellow level and red level. When database is leaked, calculating out a password which passes through the authentication gets yellow. If it also calculates out the original password, it gets red.

Red is much more serious than yellow. People usually use the same password in different sites. If the original password is leaked, all the sites are in trouble. If the attacker cannot calculate out the original password, it only affects the website which is cracked. In my mind, people need protection against red. Protection against yellow is not a hard requirement.

In my mind, hash+salt is good enough. Why do I have to use Bcrypt?

If we analyze the definition of yellow and red, we should raise the question: for a given calculated password, how to judge if it is the original one. The common solution is to use dictionary, or analyze the literal patterns. It’s getting interesting when dictionary involves. Brutal force and dictionary are the two ways crackers use. From Wikipedia and Bcrypt introduction, it is difficult to brutal force hash+48bit salt. It takes half a minute to iterate all the 6-character passwords. With 48bits hash, it should take months to go over all of them.

In such condition, cracker usually gives up unless the target user is an important figure. When brutal force fails, the only way is to use dictionary. If the password is unfortunately in the dictionary, you are screwed.

Above analysis is based on that the salt is not leaked. If the salt is leaked as well, the protection for single user is lost. In this case, the cracker just needs to calculate individually. The cracker cannot use rainbowmap. If the password is complex with 8 digital, it should take more than 70 hours to iterate all possibilities.

From above analysis, using hash+salt, the results are different in different situations:

If the salt is still safe, you are safe, unless you are an important figure and you are the target. Normal cracker should just let you go.

If salt is leaked, the situation depends on the complexity of your password. For simple password, it may only take seconds. For 8 digital password like 315@hkBJ, it takes a cracker several hours to get yellow level, but getting red level takes at least several days with powerful cluster machines.

Bcrypt scarifies performance to get security. It is 10000 times slower than hash+salt to calculate the hash, so it increases the cracking cost 10000 times too.

In Bcrypt, if the salt is leaked, the cracking cost of a simple password goes from seconds to days. It is still unsafe to use simple password. But if the salt is not lost, or the salt is lost but the password is a bit complex, it takes years to reach yellow level, and it is impossible to get red level.

As a summary, nothing helps if user use simple password.

With hash+salt, usually you should not worry about red level if your password is complex. The exception is that you are the target and the cracker is willing to put huge cost against you.

With Bcrypt, you are always safe if you do not use simple password. However, the cost of using Bcrypt is that you need to buy more web servers to do authentication. As it is 10000 times slower, to get into the same level of performance, you need to increases the capacity of your hardware 10000 times. If you have 2 authentication servers now, you need to buy 20000 servers!

You can make tradeoff to help Bcrypt’s performance. You can configure the factor of Bcrypt to make it faster, but the security goes weak too. Or, you can cache the plain text password and the calculated hash in memory, but if the memory dump leaks, all the plain text passwords leak.

In such a condition, my suggestion is that using hash+salt is still ok, if you take care of the following:

  1. Store the hash and salt separately.
  2. Always enforce the user to use a strong password.
  3. Design your hash function by yourself. Don’t just copy and paste the common open source.
    [update on 6/12/2013]  I did not mean to write your own hash “algorithm”. I wanted to emphasize that you should not just copy the code from Internet. You should design and understand your own function logic so that the algorithm provided by the SDK/System and the hash value is used in the right way. Don’t try to write your own algorithm.

 

Related sources:

http://codahale.com/how-to-safely-store-a-password/

http://en.wikipedia.org/wiki/Bcrypt

http://en.wikipedia.org/wiki/Rainbow_table

http://en.wikipedia.org/wiki/Salt_(cryptography)

http://cmd5.com/

 

Comments (1)

  1. Anyone says:

    I can tell this is terrible advice because you just told me:

    1) Not to use bcrypt without saying "use scrypt instead"

    2) To roll my own hashing function

    Please delete it before anyone else reads it, TYIA.

Skip to main content