I'm trying to understand why some key stretching methods are better than others. The wikipedia article presents 3 different key stretching methods:
A collision prone simple key stretching method:
key = hash(password) for 1 to 65536 do key = hash(key)
A better simple key stretching method. ("+" denotes the operation of concatenation):
key = "" for 1 to 65536 do key = hash(key + password)
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?