# Why are some key stretching methods better than others?

I'm trying to understand why some key stretching methods are better than others. The wikipedia article presents 3 different key stretching methods:

1. A collision prone simple key stretching method:

key = hash(password)
for 1 to 65536 do
key = hash(key)

2. A better simple key stretching method. ("+" denotes the operation of concatenation):

key = ""
for 1 to 65536 do
key = hash(key + password)

3. Even better method with a salt:

key = ""
for 1 to 65536 do
key = hash(key + password + salt)


So, I was wondering why #1 is the weakest of the 3 while #3 is the strongest. My understanding is the following :

The problem with #1

A != B // 2 messages
hash(A) = hash(B) // It's possible in theory
hahs(hash(A)) = hash(hash(B)) // Same thing again…


So, it is easier to find 2 hash that gives the same end result, because if at any time in the hash chain they get the same result that result will not change afterward.

How #2 solves it :

A != B
hash(A) = hash(B)
hash(hash(A) + A) != hash(hash(B) + B)


Since only the last hash matter instead of every hash, we are less likely to get a collision.

The problem with #2

It is still vulnerable to rainbow table attack. That's why we need to use a salt like in #3.

Now… Is there a problem with #3, and/or what makes password hashing like PBKDF2 and bCrypt better key stretching methods than #3?

-
For what it's worth, I've removed those algorithms from the Wikipedia page. Wikipedia should not be encouraging amateurs to implement their own bespoke key stretching algorithms. –  Stephen Touset Aug 28 at 18:18
@StephenTouset Even if I know you should never implement your own cryptography, I found the example very useful to understand the concept. –  Gudradain Aug 28 at 18:24
Really? Your question here quotes the entire section I removed, asking for clarification of exactly why the given pseudocode has the properties claimed. –  Stephen Touset Aug 28 at 19:03

## 1 Answer

On the non technical side, the main reason for choosing PBKDF2 or BCrypt is that they're commonly used. This means they have seen more analysis, reducing the risk of a dumb mistake and it's easier to defend them when somebody questions your choice.

What I dislike about your third variant is that it does not separate the different inputs. This isn't an issue if both key and salt have fixed length, but it's ugly. PBKDF2 has similar ugly but not practically relevant properties.

PBKDF2 has pretty similar properties to your third scheme. It has the additional feature of a variable output size, but it's so badly designed that this is more of a pitfall than an advantage. But you could always combine HDKF-Extract with your scheme if you need long outputs.

Bcrypt on the other hand has an advantage over both your scheme and PBKDF2 (used with common hashes like SHA-2): It's not friendly to GPUs. If you can afford 100ms of hashing on your CPU, the cost of a GPU based password cracker computing a hash is higher for Bcrypt than for PBKDF2. When an attacker uses an ASIC or FPGA, the advantage of bcrypt is smaller and you should consider using scrypt instead.

I also think that the need for including the password on each iteration of the hash (which you pointed out as a flaw in the first scheme) is often exaggerated. Even with a short hash like MD5 exploiting this is infeasible and becomes completely ridiculous once you use a 256 bit hash like SHA-256.

-
Also, check out this post that may help to explain the use of including the password for each iteration. –  smang Aug 28 at 15:58