I am trying to understand why a preimage attack is different than a birthday attack.
Following the general description from Wikipedia (sorry if that is a poor source?):
- A preimage attack is where an output $y$ of a hash $h$ is known, and the task is to find some input $x$ such that $h(x) = y$
- A birthday attack is where the task is to find any two inputs $x_1$ and $x_2$ such that $h(x_1) = h(x_2)$
It seems to me that a preimage attack is the same as a birthday attack, it's just that $x_2$ is effectively fixed ahead of time. Said another way, I don't see how varying both inputs to $h$ will yield an output collision so much more efficiently. What am I misunderstanding here?
In the birthday attack, you can save the results of guessing $h(x_i)=y_i$. The more outputs you have, the easier it is to match one of them. For example, after $i$ guesses the problem is to find $x_{i+1}$ such that $h(x_{i+1})\in \{y_1,y_2,...y_i\}$ whereas in the preimage attack you still have to find $h(x)\in \{y\}$.