Re: SHA1CRK – Request for Comments and Participation

On 05/10/2010 15:50, Filip van Laenen wrote
link to my presentation at NDC 2010, see

Quoting that:
SHA1CRK uses a technique called Floyd's cycle-finding
algorithm to find collisions in SHA-1. This is the same
technique that MD5CRK used a few years ago.

Just like MD5CRK, SHA1CRK considers any point whose
first 32 bits are zeroes to be a distinguished point.

With this definition, it is expected that a bit more
than 2^48 distinguished points will be needed, requiring
2^53 bytes to be communicated and stored.
With the current idea of tweeting each distinguished point,
and assuming 2^10 tweets/second (more than the average
total tweet count), less than 2^-13 of the expected job
will be achieved in the first year.

The bandwidth and storage issue can be fixed by raising
the number of bits fixed in a distinguished point.
The computing power (and associated carbon footprint)
can NOT be fixed, except to a degree with dedicated ASICs;
see estimates in my earlier post.

Simply put: drop that idea. It is doomed to failure.
Most likely the first SHA-1 collision will not be found
just by brute force. Much like MD5CRK never got a sizable
chance of finding the first MD5 collision, and disbanded
with no tangible result.

Francois Grieu

Relevant Pages

  • Re: SHA-1 and the "birthday paradox"
    ... risk of collision when using SHA-1 as a digest, or hash key, for ... identical SHA-1 digest referring to two distinct blocks rather than a ... If you find a collision on SHA-1 then you may publish it and become ... (Cost is here expressed in number of hash function computations which ...
  • Re: Standalone SHA-256 or 512
    ... What do MD5 and SHA-1 have in common, ... > anything slower than that isn't an attack in a real sense. ... Finding a collision for SHA-512 requires, on average, hashing ...
  • Re: [9fans] In case anyone worries about block hash collision in
    ... collision are 1 2^80. ... And being worried about both leads to the choice of SHA-1 as a suitable ... have picked ROT-13 for performance reasons. ...
  • Re: Security myths
    ... it's the beginning of the end for MD5 and SHA-1 (Perhaps even the whole SHA ... The fact of the matter is, there is a valid certificate collision out ...