3
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ "In 2008, an attack methodology by Stéphane Manuel reported hash collisions with an estimated theoretical complexity of $2^{51}$ to $2^{57}$ operations. However he later retracted that claim after finding that local collision paths were not actually independent, and finally quoting for the most efficient a collision vector that was already known before this work." (source, wikipedia, it has a reference). $\endgroup$ – Maarten Bodewes May 20 '16 at 22:58
  • $\begingroup$ This paper by Marc Stevens seems to be more up to date (it doesn't seem to have a time stamp, but the PDF was last changed in 2013). Ah, yes, EUROCRYPT 2013... $\endgroup$ – Maarten Bodewes May 20 '16 at 23:05
  • 1
    $\begingroup$ OK, and finally a 2011 paper with the same title where he seems to perform a 180 and show why previous low estimates were incorrect (based on the first 3 pages I could see). I'd answer based on that, but it costs me $$$ :( $\endgroup$ – Maarten Bodewes May 20 '16 at 23:18
1
$\begingroup$

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).

$\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.