# 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

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 '14 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 '14 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 '14 at 19:03

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.