# 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

## 2 Answers

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.

-

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.

-
The last paragraph is confusing to say the least, it looks like you are trying to compare a hash function and a symmetric encryption algorithm? Could you elaborate, please? –  Thomas Sep 30 '12 at 23:33