I'm currently trying to solve this exercise (sorry for image, it's for the notation and I'm not allowed yet to post images directly):
I have read the exercise question a lot of times and I think I do understand the most of it.
However, I'm a bit confused about what is meant with the first task "Show that if one can find a...".
I assume that if I can find two messages producing the same hash value, then I got $s_{t+1} = s'_{t'+1}$, and then it would just be to use the same values in the function $f$, which means I would end up with $f(m_{t+1}, s_t) = f(m'_{t'+1}, s'_{t'})$.
Could someone help me by pointing out / give me a hint how I am supposed to show it?
Indeed. But $f(m_{t+1}, s_t) = f(m'_{t'+1}, s'_{t'})$ is only a collision if the inputs are truely different. So if $m_{t+1} \neq m'_{t'+1}$ or $s_t \neq s'_{t'}$, then the inputs are different, and we have a collision in $f$, which we need to show (a collision is two different inputs going to the same output). So you still have to handle the case that $m_{t+1} = m'_{t'+1}$ and $s_t = s'_{t'}$.
Now note that $m_{t+1} = m'_{t'+1}$ means that in fact $m$ and $m'$ had the same length (because the last block encodes the original length!). This implies that $t = t'$ as well, because the $t$ (the number of message blocks) is determined directly by the length of the message.
Using that we now know that $s_t = s'_t$ which means $f(m_t, s_{t-1}) = f(m'_t,s'_{t-1})$. Now make the same distinction as before: either a collision in $f$ is found or....