antirez weblog

Yesterday I finally released the initial public release of Lamer News, that is both a real world Redis programming example in the form of an Hacker News style site, and a project to run a completely independent (with a consortium) programming news site.

The project was well received, and was in the top page of HN for some time. Thanks for providing your feedbacks.

After the release of the code I got a few requests about changing the hash function I was using in order to hash passwords in the database:

# Turn the password into an hashed one, using
# SHA1(salt|password).
def hash_password(password)
    Digest::SHA1.hexdigest(PasswordSalt+password)
end

The above code uses SHA1 with a Salt. As others pointed out this is not the safest pick, since there are ways to compute SHA1 very fast. After some time a chorus of people started twitting and commenting a single sentece: "Use bcrypt". I proposed using nested SHA1 in a loop, in order to avoid adding more dependencies in the code (if you check the README one of the goals is to take the code simple and depending on just a few gems). And at this point it happened: the crypto dogma. No way to reason about crypto primitives and their possible applications and combinations, but just "use bcrypt". In the eyes of this crew programmers are just stupid drones applying guidelines, that can't in any way reason about cryptography. But I'll talk more about that later...

For now let's do a step backward... and show what the original problem is with all this, and how much insecure the original code is.

The problem

The problem is pretty easy to understand, but it is worth to be explained in details. In order to avoid storing passwords in cleartext into the database is common practice to hash passwords. So:

HP (hashed password) = HASH (password)

When the software needs to perform the user authentication it receives the plaintext password, hashes it again, and verifies that it matches the one in the database. If so the user is authenticated.

However what happens if an attacker, let's call it Eve, will steal the database and the passwords are leaked? Eve has a number of hashed passwords, let's call them HP1, HP2, HP3, ... Her goal is to find an attack such that it can turn back HP into P.

The hashing algorithm HASH is public, so the first thing Eve can do is to apply HASH to a dictionary composed of common words and check if HP matches the HASH(common_word). If there is a match the original password was found. Note that there are not so many words in the English dictionary, so this attack is very easy to perform, and super fast.

But maybe our user, Bob, picked a password that is not in the dictionary, but is neither particularly long.

Eve can generate all the combinations up to 6 chars passwords and hash them with HASH, trying to find a match. This attack is computationally harder. If the password is a completely binary string, let's say of six characters, there are 256^6 passwords, that is, 281474976710656.

If our attacker can hash one billion passwords per second (it is possible with modern GPUs without spending a fortune on it) cracking this password takes:

281474976710656 / 1000000000 = 281474 seconds

This is just... three days, so one day and half in the average case. Not good! it's too easy to crack. There is another problem, an user will hardly use all the 256 characters with equal probability. Let's consider the worst case of it just using 26 low case letters without number nor symbols. This time let's consider an 8 characters password.

There are 26 ^ 8 possible passwords, that is: 208827064576 possible passwords. This time our password can be cracked in 208 seconds (half that time in average).

This is clearly not good. How long should be a 26 letters alphabet password to be unaccessible for the attacker able to compute HASH 1 billion times per second?

A 14 characters password will resist 1024 years on average to be cracked. For a 16 characters password our attacker needs 1382824 years.

Just 12 chars will resist for one year and half in average, definitely too little for most applications.

So is SHA1 secure for hashing passwords? Yes if the user picked a strong password of 14 chars or more. Otherwise not very secure. It all depends on the length of the password, and guess what, users have a bad habit of picking bad and short passwords.

It is worse than that

Unfortunately it is worse than that. For instance the attack against our 12 chars password can be made instantaneous in an easy way: using three years to compute a table of all the 12 chars passwords and associated resulting hash value. This is basically a big map between HASH(P) and P.

However such a table takes space, a lot of terabytes (86792 for precision) to store the lookup table assuming we have a so cool compression algorithm that can use just a byte per HP,P pair (an unreachable goal likely). However this is a valid attack when the size of the table is reasonable.

The point here is, many times in cryptography an attack can be made working using space instead of time.

The good thing is that there is a way to avoid the user precomputing a single table that will work for all the sites using the same hash function, that is, using *a salt. A salt is an (assumed public) string we concatenate to our password before hashing it, so if our salt is "lame", and the password is "foo" we will perform:

HP = HASH("foolame")

This way for the table-based attack to work the attacker needs to pre-compute a table with all the 12 char passwords combination hashed with the same salt. This means, this table is useless if Eve plans to attack another site with a different salt.

Random salts

We can do even better than that, and not just store HP, but also a random salt. When we create the user account we also generate an user-specific random salt, and store it along with the hashed password.

With a per-user salt we are safer, the requirement is a table per user now if the attacker wants to precompute it. And even more interesting while a global salt is more likely to be leaked even if the user passwords are not leaked, this is unlikely to happen if you have a salt per every user.

Making HASH slow

However even if we stop all the table based attacks, there is still a fundamental problem: if the password is short and Eve is able to compute HASH 1 billion times per second we have problems.

There is one thing we can do: using an hash function HASH that is MONKEY ASSES SLOW.

There are algorithms that are very slow both in hardware and in software for instance. Or we can take an existing algorithm and make it very slow by using it into a loop.

For example Blowfish is an encryption algorithm with a slow key scheduling algorithm (the algorithm is pretty fast once you performed the key scheduling, so Blowfish is not good only if you want to encrypt many short messages with different keys, but can be fast if you want to encrypt a big message with a single key).

The fact Blowfish key scheduling algorithm is slow makes it a good candidate for HASH.

So Niels Provos and David Mazières designed an algorithm called Bcrypt that can be used in order to hash passwords. The algorithm was presented in 1999 and uses a modified blowfish key scheduling algorithm. I'm not sure if past analysis against Blowfish can be applied to Bcrypt after the modifications, nor how much analysis was performed against Bcrypt itself, so I can't comment about the security of the algorithm in question.

However it is a popular pick, Provos and Mazières are two known cryptographer so probably the algorithm has no obvious flaws as well.

Once you use a slow HASH the attacker will start to have much troubles. For instance Bcrypt is "tunable", you can modify an input parameter to make it slower or faster. If you make it slow enough so that even with good hardware you can't compute more than 1000 hashes per second, it is still probably fast enough for your authentications servers to handle, but it is unpractically slow for Eve to crack even a 8 characters password, even using just 26 letters:

26^8/1000/3600/24/365 =6.6218627782

3.3 years on average to crack an 8 digits password. Probably still a bit too weak but better than a few seconds...

However note how we are still not secure against a dictionary attack. If the user picked a common word there are no hopes. 30k hashes are still trivial to perform in a reasonable amount of time.

On dogmas

So far we showed a few interesting points I think, first: there is no hashing schema that will save users picking very bad passwords. It is very important to force users to add non alphanumerical characters and a few capital letters in the password IF security is very important for your application.

It is important to understand how things work. And this brings us to the following point. After the "use bcrypt" chorus I replied that I could use another solution instead, based on just iterating SHA1. But apparently cryptography is not a topic a programmer should understand for many. It is just a dogma. When you have dogmas you are going to be a bad programmer probably, what about if your system does not have bcrypt support for some reason and you still want to mount something useful?

What I proposed was this trivial schema:

SHA1(SHA1(SHA1(...(SHA1(password|salt))))

How heretic! I was marked as a stupid not understanding security, that is not safe to chain hash functions like this, and so forth. But if you think at it:

SHA1 is a one way hash function. It is composed of a small computation step called round that is iterated again and again. There is no key scheduling as it is not a block cipher, it just compresses a stream of bits into a fixed length output.

It is very important to understand that many crypto algorithms are based on that idea of taking a simpler function and iterating it many times to strength the effect it has. This concept is so important that sometimes an attack to an algorithm disappears (becomes not practical or requires more time than brute force) if you add more rounds. Sometimes cryptographers use a variant of the algorithm with a reduced amount of rounds just to analyze the algorithm in a more attackable form, to understand better how strong the variant with the full number of rounds is.

So why we don't just add a lot of rounds? Because it is slow. Even an amateur cryptographer could design an algorithm that is secure but slow. A good cryptographer will be able to find the tradeoff between security and speed.

But... now we know this concept of rounds, and we know that in SHA1 there is no key scheduling algorithm, the output of the function is only related to its input, nor SHA1 is designed to be inverted, as there is no decryption stage.

So it is quite natural that the schema I proposed of computing SHA1(SHA1(SHA1(..))) will just do that, adding rounds to SHA1. So for the fundamental properties of SHA1 it should be computationally unfeasible to write a function SHA1000 that is equivalent to 1000 times SHA1 nested but that can be computed easily.

Note that the output of SHA1(SHA1(..)) is not the same as modifying the algorithm adding more rounds since there is a pre and post stage in the SHA1 algorithm that will make the output differ compared to a plain SHA1 with more rounds.

But guess what? This morning I discovered that actually the algorithm PBKDF1 described into RFC2898 does exactly what I proposed.

There are people that are very happy to show you the way, but if you look at them more closely you discover they are clueless. So please use proven standards, try to write secure code, but use your mind, learn about cryptography and how you can combine primitives. Dogmas are lame.

It is not a good idea for a programmer to try designing a block cipher and then use it for sensible purposes, there are specialists doing that, but understanding what are the building blocks, and what you can do with cryptography, how to mount protocols, it is a very important skill for our community.

Finally it is ok for me when people are rude with me when they are right. Arrogance can be handled if it is mixed with smartness. When instead it meets ignorance it is really just a sad affair.

Edit: two new interesting links from HN:

• How SHA1 and SHA2 will lose some entropy at every iteration. Not a big problem for our application (too little iterations) but worth knowing.
• How nesting SHA1 does not help if you want to slowdown a pre-image attack.

About the second link, in the message the explanation is not very clear but this is what happens:

Here the attack they want to mount is the following: find another string, ANY string, that will hash to the same output, but only 32 bits of the output.

Since it is any string, it can also be a SHA1 itself. So what you do is to start with an "X" that can be ANY ANY value, even "foo". And you start doing:

    x = SHA1(x)
    x = SHA1(x)
    ... again and again ...

ok? Well in the average case after 2^31 iterations you find a collision, right?

But the output 65536 iterations ago was it! The string that will output that specific 32 bit output after SHA1() nested 65536 times. So you want to go backward but it is not possible, SHA1 can't be inverted. So what you do? You start again from "X" and stop exactly 65536 iterations before you found the wanted value.

Obviously doing 65536 more SHA1s of that string you get the previous output. So you found your string. Why the original poster says that the attack takes 2x time but can even optimized? Since you can store the value of SHA1 at 10000 iterations, at 20000 and so forth. Then instead of re-running the iteration again you start from the nearest cached value.