5
$\begingroup$

The google collision website shattered.it refers to a collision detector: https://github.com/cr-marcstevens/sha1collisiondetection.

It claims a false positive rate of $2^{-90}$ and to take less then twice the time of regular SHA-1. But the counter-cryptanalysis paper mentions that the false positive rate is $C \cdot 2^{-160}$ and it takes $C+1$ times longer then regular SHA-1 - and they suggest using $C=14$.

What am I missing? How many triplets does the detector use? Is there another paper explaining a more advanced technique that explains the performance?

Improve this question
$\endgroup$
3
  • $\begingroup$ Note that the sha1 collision detector seems to be called "hardened SHA-1", see also my (more general) previous question - that is, unless I'm grossly mistaken about the naming. $\endgroup$
    – Maarten Bodewes ♦
    Commented Feb 23, 2017 at 20:26
  • 1
    $\begingroup$ Could you please review your posts before hitting the button that publishes the answer? I can see you're not a native speaker, but a spell check and correct capitalization makes your post look a lot more professional and it will result in more upvotes in general. Besides that, I just earned the "copy editor" badge after editing your post, so I'm done ;) $\endgroup$
    – Maarten Bodewes ♦
    Commented Feb 24, 2017 at 0:42
  • $\begingroup$ @MaartenBodewes Welcome to the Copy Editor club! ;) $\endgroup$
    – e-sushi
    Commented Feb 24, 2017 at 5:13

1 Answer 1

Reset to default
4
$\begingroup$

One trick used by the collision detector you mention is to check for "unavoidable conditions", described in the paper here: http://oai.cwi.nl/oai/asset/23932/23932A.pdf

Essentially, the unavoidable conditions are a faster check, but may have false positives. If a given block meets these conditions, the detector then runs the full check. Per the paper above, the total cost of doing this is only 1.96 times the regular SHA-1 runtime.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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