Collision attack is finding distinct messages $x$ and $y$ such that these two messages has the same hash value; $hash(x) = hash(y)$. There is no restriction on the length of the $x$ and $y$.
For a hash function with output size $\ell$, the generic cost of finding a colliding pair is $\mathcal{O}(2^{\ell/2})$-time with 50% probability. This is due to the birthday attack.
First block collision
By playing with the first block of a message we can find colliding pairs easily. For example, if the first bit of the IV is zero then two messages
- $m_1= 0\mathbin\| \text{rest of the message}$
- $m_2= 1\mathbin\| \text{rest of the message}$
is an example of collision since $0 \wedge 0 = 0$ and $0 \wedge 1 = 0$. Therefore the compression function will have the same inputs. If the first bit is not zero, apply it in the position where it has the first zero. This attack can be applied to any position where the IV has a zero.
Actually, we can find many collision pairs, easily. There are $2^k-1$ pairs for an IV that has $k$ zeroes.
Identical prefix collision
It is possible to play with the other blocks, too. Just keep the first block the same, and calculate the first compression, then the IV to the second block is the output of the first.
- $m_1= \text{prefix}\mathbin\| \text{block to collide 1}\mathbin\| \text{rest of the message}$
- $m_2= \text{prefix}\mathbin\| \text{block to collide 2}\mathbin\|\text{rest of the message}$
The same attack as in the first block collision applies here, too. No, difference.
Distinct prefix collision
Also, different prefix message collision is possible. Just calculate the compression of the prefixes, and try to collide the input with the next compression by using the AND's property.
- $m_1= \text{prefix 1 may be longer}\mathbin\| \text{block to collide 1}\mathbin\| \text{rest of the message}$
- $m_2= \text{prefix 2}\quad\quad\quad\quad\quad\quad\;\mathbin\| \text{block to collide 2}\mathbin\|\text{rest of the message}$
This is harder to achieve than the first block collision.