Combining cryptographic hashes, part 2

January 14, 2010 at 10:05 am (cryptography)

In a previous post I discussed Joux’s multicollision attack and how it can significantly decrease the efficiency of concatenating hash functions. Today I will discuss a recent paper (December 2009) by Mendel, Rechberger and Schlaffer, which shows how specific attacks against two hash functions can be used against the concatenation combiner. Using this attack, the authors can find collisions in md5||SHA1 with a complexity around $2^{59}$ , thus breaking the $2^{64}$ birthday limit.

First, let’s restate the old result : the cost to find collisions in F||G with Joux’s multicollision attack is $\frac{n}{2}.2^{\frac{m}{2}} + 2^{\frac{n}{2}}$ where m and n are the respective output lengths of F and G. This total is calculated by adding the cost of finding a $2^{\frac{n}{2}}$ multicollision in F ( $\frac{n}{2}.2^{\frac{m}{2}}$ ) and the cost of hashing these $2^{\frac{n}{2}}$ messages to find a collision in G. Now even if there were a better attack against F, this would decrease the first term of the total cost, but not the second one (the verifying step). As a result the total cost would always be higher than $2^{\frac{n}{2}}$ , so Joux’s attack is clearly not sufficient to break the birthday limit.

Let’s now see the new attack, and to simplify things let’s consider that m=n. The new attack is based on two assumptions:

F suffers from a type-1 collision attack, meaning that given a message block m0 we can find m1 and m1′ such that $F(m_0||m_1)=F(m_0||m_1\prime)$ with a complexity lower than $2^{\frac{n}{2}}$

G suffers from a type-3 collision attack, meaning that given two message blocks m2 and m2′ we can find m3 such that $G(m_2||m_3)=G(m_2\prime||m_3)$ with a complexity lower than $2^{\frac{n}{2}}$

The attack then goes as follows:

Using the type-1 collision attack in F, find k pairs of message blocks $(m_1,...,m_k) (m_1\prime,...,m_k\prime)$ such that for any $i \leq k$ , $F(m_1||...||m_i)=F(m_1\prime||...||m_i\prime)$ . The value of k depends on the size and structure of G. Following Joux' attack, this effectively gives a $2^k$ multicollision on F, in other words $2^k$ messages which hash to the same value through F.

Using these $2^k$ messages as prefix, use the type-3 collision attack on G to find a message block p such that $G(m_1||...m_k||p) = G(m_1\prime||...m_k\prime||p)$ . A large part of the paper describes how to perform this attack in an efficient way, using a combination of birthday techniques and differential shortcut techniques.

Finding p also gives a collision on F, as we append p to a known pair of colliding messages for F.

This is the first documented attack where a weakness in two hash functions can be combined to break the birthday limit of the concatenation, and it will be interesting to see if it can be applied to other hash functions.

Like this:

Be the first to like this post.

1 Comment

Combining cryptographic hashes, part 3 « Sam280's Blog said,

January 25, 2010 at 12:35 pm

[...] significantly decreases the efficiency of concatenating hash functions and how it can be used to break the birthday limit of md5. Now the obvious remaining question is: if concatenation is not effective, are there better ways to [...]

Reply

Sam280's Blog