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
<http://home.online.no/~vlaenen/sha1crk/index.html>

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
.