6
$\begingroup$

I've been having a hard time placing DJB's analysis of Oorschot & Wiener parallel rho collision search into context. There is plenty of discussion about the birthday bound and quantum computers in relation to hash functions, but these speedups are much more dramatic.

How does this attack alter the runtime analysis for brute forcing hash collisions? Is it only a linear speedup, but how big are hashes going to balloon to?

$\endgroup$
5
$\begingroup$

How does this attack alter the runtime analysis for brute forcing hash collisions?

Absolutely nothing whatsoever.

The traditional brute force analysis counts the total number of hash computations required, and nothing else. In this model, the best we can do is hash $O(2^{n/2})$ distinct messages, and then scan them all, and see if there are two messages that hash to a common value.

If the hash function acts like a random function, we can't do any better; however if we look at actually implementing this attack, we notice that this attack also requires $O(2^{n/2})$ space, and that's actually a bigger problem than the computation required.

What rho (and parallel rho) collision attacks do is increase the number of hash computations required by a constant factor (nothing huge, but greater than 1); and also drastically reduce the amount of memory involved.

If we're actually looking to do a brute force collision (say, of a 100 bit hash function), a rho collision attack would be much more feasible than anything requiring you to store $2^{50}$ or so hashes. However, if you're just thinking about how much processing power it would take, the traditional birthday attack scores better.

And, because a standard birthday attack against a 256 bit hash function would require $O(2^{128})$ hash evaluations, which we believe is infeasible, a rho attack would require even more (and hence, also be infeasible).

If you're worried about the parallel side of it, well, the possibility of parallel computation is already baked into the analysis; it is commonly believed that $O(2^{128})$ (or more) hash evaluations is infeasible, even if someone had vast (but realistic) quantities of parallel processors.

BTW: DJB's point wasn't that parallel rho attacks are actually a threat against SHA-256 or SHA3-256; he is trying to show that attack is better than a quantum computer running Grover's algorithm to search for collisions (and so if those hash functions are safe against a parallel rho attack, they are certainly safe against a quantum attack).

$\endgroup$
2
  • $\begingroup$ So their break of MD5 was specific to the length of its output? $\endgroup$
    – Indolering
    Mar 22 '17 at 23:07
  • $\begingroup$ @Indolering: No, the break of MD5 was not a brute force attack; instead, it was cryptanalysis of the internals of MD5. $\endgroup$
    – poncho
    Mar 23 '17 at 1:11
2
$\begingroup$

How does this attack alter the runtime analysis for brute forcing hash collisions?

If you care only about runtime, it states that you can reach $t\approx2^{b/6}$ (b=output bit size of the hash) on non-quantum dedicated hardware, if you give it enough cores. Still, it's not a new result of that paper.

how big are hashes going to balloon to?

If you mean a change in the standard hash size due to the parallel rho attack, it's not going to change. At the time of the question that algorithm has been around for 23 years.

Is it only a linear speedup

You are right, it is 'only' a linear speedup. (when compared to Floyd's algorithm as explained in that book, in the chapter 2.3.2: Cycle detection).

The time of Floyd's algorithm is around $2^{b/2}$ while parallel rho is around $2^{b/2}/M$ (M as the build cost or machine size, e.g. number of cores or of memory).

What you are not considering is that DJB uses an M that is exponential in b. For example when on his paper there is a $M=2^{b/3}$, it means that with a SHA256 $M=2^{256/3}\approx4.87*10^{25}$ cores. The speedup is linear in M, and exponential in b.

I've been having a hard time placing DJB's analysis of Oorschot & Wiener parallel rho collision search into context. [...] but these speedups are much more dramatic. How does this attack alter the runtime analysis for brute forcing hash collisions?

You shouldn't read that paper looking for fixed speedup, or looking for how much time it takes to find a collision. Those two can vary, what is fixed is the relationship between time and machine size.

For example:

  • Parallel rho attack is $t\approx2^{b/2}/M$ (for $M\le2^{b/3}$).
  • The quantum algorithm by Brassard, Høyer, and Tapp is $t\approx2^{b/2}/\sqrt{M}$.

Notice how $\sqrt{M}$ increases more slowly than M (which is the only difference between 1° and 2°). The faster the denominator increases, the faster the time decreases. This means that increasing M in the 2° leads to a lower improvement in the time (when compared to the 1°). This can be seen in the graphs of the paper.

Also, you can compare the machine size needed to reach the same time complexity. From above using the same time and output bit size, $t\approx2^{b/2}/M_r$ for rho and $t\approx2^{b/2}/\sqrt{M_q}$ for quantum. They become $M_r\approx2^{b/2}/t$ and $\sqrt{M_q}\approx2^{b/2}/t$, then $\sqrt{M_q}\approx M_r$, which means $M_q\approx M_r^2$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.