# How is the SHA-1 collision detector so fast?

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?

• 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. – Maarten Bodewes Feb 23 '17 at 20:26
• 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 ;) – Maarten Bodewes Feb 24 '17 at 0:42
• @MaartenBodewes Welcome to the Copy Editor club! ;) – e-sushi Feb 24 '17 at 5:13

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.