5

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?

Maarten Bodewes
  • 88,868
  • 12
  • 146
  • 304
Meir Maor
  • 11,497
  • 1
  • 22
  • 52
  • Note that the sha1 collision detector seems to be called "hardened SHA-1", see also my (more general) [previous question](http://crypto.stackexchange.com/questions/44141/what-is-hardened-sha-1-how-does-it-work-and-how-much-protection-does-it-offer) - that is, unless I'm grossly mistaken about the naming. – Maarten Bodewes Feb 23 '17 at 20:26
  • 1
    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 00:42
  • @MaartenBodewes Welcome to the Copy Editor club! ;) – e-sushi Feb 24 '17 at 05:13

1 Answers1

4

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.

William Luc Ritchie
  • 156
  • 1
  • 4