Tunnels used in md5

Question

I'm reading a paper about finding collisions for the MD5 hash algorithm involving the concept of tunnels.

But I couldn't understand about the difference between point of verification and point of choice. Aren't they the same?

Answer 1

The search for MD4/MD5 collisions involves a lot of different concepts. To keep things simple, a differential path is chosen and messages are found so that the conditions put on the internal state values for the differential path to lead to a collision are satisfied.

The tunnels are transformations on the message that do not impact the status of these conditions up to some step $p_v-1$ of the algorithm, where $p_v$ is called point of verification: if they are fulfilled for the message M, they are also fulfilled for the transformed message.

Now tunnels are nice but one also need to find the proper messages to apply the tunnels to. Leurent's technique is meant to find colliding messages with a particular shape and therefore has some additional constraints. Hence he builds messages unorthodoxly (compared to the previous works such as Klima's) so that they meet the conditions only up to step $p_c-1$ of the algorithm where he calls a point of choice the value $p_c$. Between step $p_c$ and $p_v-1$ probabilities are at work and some freedom in the messages built so far is used to wait for the remaining conditions to be fulfilled.

Answer 2

First of all, it depends on how you design the hash function

You may go to Hash Collisions (The Poisoned Message Attack) "The Story of Alice and her Boss" to find more.

And more importantly, I really do not understand about the difference between point of verification and point of choice. As least, these words or phrases are not in the PDF context.

You have got to think the purpose of using such technology and even using other algorithms such as RSA and the AES keys. MD5 itself is a one-way crypto. The key is that it is difficult to retrieve the original password and other sensitive information unless you call the encryption method again. Using crypto with symmetric key is better.