Parallel Rho Hash Collisions I've been having a hard time placing DJB's analysis of Oorschot &amp; 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?
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).