Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
Can this attack be parallelized? It is a $2^{57}$ complexity collision attack on SHA-1 based on disturbance vectors.
If it is practical it is easy on a GPU ($\approx1.1$ GPU-days). If it is completely sequential it is much more tedious but still possible ($\approx556$ days on a 3GHz CPU).
Both numbers are small enough to beg the question "Why has nobody done it already?".
Reference: Classification and Generation of Disturbance Vectors for Collision Attacks against SHA-1
Based on the more recent Disturbance vectors for collision attacks against SHA-1 by the same author, which Maarten Bodewes mentioned in the comments, the initial attack/complexity was optimistic/erroneous. The algorithm actually leads to a disturbance vector that had already been published:
Using our algorithm and those cost function we retrieved all previously known vectors and found that the most efficient disturbance vector is the one first reported as Codeword2 by Jutla and Patthak, A matching lower bound on the minimum weight of SHA-1 expansion code.
The estimated complexity of that attack based on the original source is $2^{62}$. The later paper by Stéphane Manuel quotes two estimates of $2^{65}$ and $2^{69}$ depending on the cost function used, and gives some evidence that even those may be optimistic:
Furthermore, the statistical evaluation of local collisions’ holding probabilities described in the next section shows that local collisions are not independent. Consequently, this type of cost function only gives a rough basis for an estimation of the complexity of the attack.
Either way, this is more costly than the freestart collision attack recently performed ($2^{57.5}$), and similar or slower than Stevens' proposed full collision attack. So that explains why it has not been performed so far.
Regarding the original question about parallelization, yes, these types of attacks should be "easily" parallelizable (to the degree that implementing them on a GPU is easy).
