The main conceptual trick here is the one used over and over in cryptography proofs, known as "reduction". Suppose that you have a problem $A$, which is assumed to be a "hard problem". You want to show that another problem $B$ is also a "hard problem". To do that, you imagine that you have some machine or system that can solve $B$; and from that machine or system, you build a solver for problem $A$; that new solver uses the solver for $B$ as an elementary block box. If you can do that, i.e. solve $A$ as long as you have access to a solver for $B$, then this shows that solving $B$ must be hard: an easy solver for $B$, used in your construction, will become an easy solver for $A$, which contradicts the hypothesis of $A$ being a hard problem.
I'll take an example with square roots modulo a big non-prime integer. This is an example meant to explain how a problem $A$ is reduced into a problem $B$, and vice versa. To follow this example, you don't need to fully understand the details of the involved algebra; what matters here is that we make solvers for some problems based on solvers for other problems.
Suppose that you have $n = pq$, where $p$ and $q$ are two unknown and big prime integers; you only have their product $n$. Finding $p$ and $q$ from $n$ is a hard problem; it is called integer factorization, and mathematicians have looked for efficient ways to do that for more than 2500 years, and they still don't know how to do it for large integers (current record is for a 768-bit integer $n$). This integer factorization is the problem $A$. We assume that it is hard.
Now consider the problem $B$: from an integer $x$ such that $1 < x < n$, find an integer $y$ such that $y^2 = x \bmod n$. This is basically finding a square root of $x$ modulo $n$; about 1/4th of integers $x$ in the $1..n-1$ range admit square roots, and if $x$ has a square root, then it will (usually) have four distinct square roots. We want to show that, in all generality, $B$ is a hard problem.
Suppose, then, that you have some system $S$ that can find a square root for any input $x$ (for any $x$ that has square roots, that is). We can then build a new system, that uses $S$, and can be used to factor $n$. It works in the following way:
- Generate a random value $k$ in the $q$ to $n-1$ range.
- Compute $t = k^2 \bmod n$.
- Invoke the system $S$ on $t$. We build that $t$ as a square, thus it has square roots, and we already know two of them, which are $k$ and $n-k$. The system $S$ will return one of the four square roots of $t$; let's call it $u$.
- If $u = k$ or $u = n-k$, we were unlucky. This happens half of the time. Start again with a new random $k$.
- Otherwise, compute the Greatest Common Divisor of $n$ and $u+k$. This GCD will be either $p$ or $q$ with very high probability.
This algorithm shows how to factor a big integer $n$, provided that a square root extractor (system $S$) modulo $n$ is made available. Since integer factorization is hard, this should not be feasible.
The same concept works in the other direction in that case. What the algorithm above shows is that extracting square roots modulo $n$ cannot be easier than factorizing $n$. In the other direction, we can show that factorizing $n$ cannot be easier than extracting square roots modulo $n$: suppose that you have a machine or system $F$ that can factor big integers. Now, given an integer $n$ and an input $x$ for which you are challenged with finding a square root, you can do the following:
- Call $F$ on the integer $n$ to get its factors $p$ and $q$.
- Compute the square roots $y_p$ and $y_q$ of $x$ modulo $p$ and $q$, respectively. Modulo a prime, square root extraction is easily done with the Tonelli-Shanks algorithm.
- Recombine $y_p$ and $y_q$ into a square root $y$ for $x$ modulo $n$, using the Chinese Remainder Theorem.
Thus, if you can factor integers, you can extract square roots. Therefore, integer factorization cannot be easier to do than extracting square roots: whenever you find an efficient way to factor integers, the algorithm above can be used to turn that into an equally efficient way to extract square roots.
Since integer factorization is not harder than extracting square roots, and extracting square roots is not harder than integer factorization, then both problems are equivalent. In particular, they must be either both hard, or both easy (in practice, as far as we know, they are both hard).
Now back you your problem of hash functions. You have a given hash function $H$, and it is assumed to be collision-resistant. This means that the "problem $A$" is about finding a collision for $H$: find $m$ and $m'$ such that $m \neq m'$ but $H(m) = H(m')$. The exercise supposes that problem $A$ is hard.
Now, problem $B$ is about the collision resistance of $G$: you are challenged with finding $m$ and $m'$ such that $m \neq m'$, but $G(m) = G(m')$. The goal of the exercise is to show that $G$ is collision-resistant, i.e. that problem $B$ is hard.
Therefore, the way to do it is to make a reduction: you first suppose that you have a solver for $B$, i.e. a way to make a collision for the hash function $G$. You want to show how you can use such a solver in order to make a solution for problem $A$, i.e. finding a collision for the hash function $H$. By describing such a method, you show that finding a collision for $G$ cannot be easier than finding a collision for $H$. Since $H$ was supposed to be collision-resistant, it follows that $G$ is also collision-resistant.
All you have to do, therefore, is to find out how a collision for $G$ can be turned into a collision for $H$ (and that I leave as an exercise, because the whole point is to have you find it by yourself).
