# Tunnels used in md5

I'm reading the paper "Message Freedom in MD4 and MD5 Collisions: Application to APOP" about finding collisions for the MD5 hash algorithm involving the concept of tunnels as described in "Tunnels in Hash Functions: MD5 Collisions Within a Minute".

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

-
Sorry, I don't understand at all what you are asking about. Could you elaborate a bit? What is "message freedom"? What are "tunnels"? –  Paŭlo Ebermann Jun 14 '12 at 19:05
I think he is talking about the "tunnel attack" on the MD5 hash: cryptography.hyperlink.cz/2006/Tunnels.pdf –  woliveirajr Jun 14 '12 at 19:14
I don't even see the phrase "point of choice" in the paper linked in the question. –  mikeazo Jun 15 '12 at 11:54
Perhaps it's not that paper/idea he was discussing in the original question, but it was so vague that I tried to fix it. But I'm not sure I could... :( –  woliveirajr Jun 15 '12 at 12:39
This paper builds on the Tunnel attack paper above and makes mention of a "point of choice". Note on pg. 8 where a "point of choice" and a "point of verification" are individually specified. –  B-Con Jun 15 '12 at 21:20

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.

-