[ajanuary]

[Replying to tryeng]

    No, there is an infinite number of inputs that produce the final output O.

Only with an infinite number of inputs. If we restrict our domain to things that are likely to be passwords, say string under 1000 characters in length, then we're increasing the number of inputs in our domain that can produce O.

    you have to find something that generates O after exactly n rounds of hashing

I was using an increasing number of iterations to demonstrate how each iteration potentially increases the number of collisions. Taking n=3, you don't need to know any of the intermediate states A1, B1, B2, B3 or B4 to take advantage of the fact that in our domain of strings under 1000 characters we only have to find one of 8 possible inputs rather than one of 2.

    I said will be true for all relevant hashing functions.

All relevant hashing functions have a probability of collisions in any useful input domain. Okay the tree won't be as dense as the one illustrated, but you're still increasing that probability by repeated hashing.

You need to find some way to mitigate the collisions, at which point you've basically got bcrypt.