Collision-resistance implies one-wayness.
Proof by reduction: if you have an algorithm $A$ which is able to invert $H: b^* \rightarrow b^n$,
we can build an algorithm $B$ which is able to find a collision (with almost the same time and probability).
Here $b$ means $\{0,1\}$.
Let's consider only input strings of some length $l\ge n$.
Notice that $H$ splits the set $b^l$ into the following $2^n$classes:
$$
\{C_h = \{x: x\in b^l \land H(x)=h \}\}_{h\in b^n}.
$$
On expectation (if function behaves randomly), each class consists of $k = 2^{l-n}$ elements.
But for our concrete function some of the classes could be empty, while some of them have more elements than others.
Algorithm $B$ behaves as follows:
- Picks random $x\in b^l$ and evaluates $h = H(x)$.
- Runs $A$ on input $h$: $x' = A(h)$.
- If $x \neq x'$, returns a collision $(x, x')$. Goes to step 1 otherwise.
Easy to see that probability of success on step 3 is $1 - \frac{1}{k}$ (which is quite a lot, and you can increase $k$ or just make several rounds of algorithm to achieve any probability you want).
The explanation is: when you're picking $x$ on first step, you're picking one of ${C_h}$ with probability proportional to a number of elements in the class: $Pr[C_h] = \frac{|C_h|}{2^l}$.
Then, on the step 3, probability of failure, i.e. $x = x'$, is $1/|C_h|$,
taking into account uniformly random choosing of $x$ and the fact that $A$ "doesn't know" which element $x$ from the class $C_h$ you selected (you've given him just $h$).
So, the common probability of failure is calculated as:
$$
Pr[\texttt{"failure"}] =
\sum_{h\in b^n} {Pr[C_h] \cdot Pr[\texttt{"failure on C_h}"]} =
\sum_{h\in b^n} {\frac{|C_h|}{2^l} \cdot \frac{1}{|C_h|}} = 2^n\cdot \frac{1}{2^l}.
$$
Remark that we do not require any random properties of $A$ nor $H$.
We achieve this probability estimate just using randomness of $B$ (uniformly random choosing of $x$ on step 1).
