6
$\begingroup$

Given the recent news about SHA-1 collisions, what is the complexity of finding a SHA-1 collision?

Marc Steven's HashClash is still detailing about 260. Does the previous complexity still hold?

$\endgroup$
5
$\begingroup$

Yes, according to the technical paper linked from that site:

the state-of-the-art collision attack on full SHA-1 was presented by Stevens [Ste13b] with an estimated cost of $2^{61}$ calls to the SHA-1 compression function.

They further state:

Based on experimental data obtained in this new work and the 2013 state-of-the-art collision attack, we can project that a real SHA-1 collision will take between 49 and 78 days on a 512 GPU cluster. Renting the equivalent GPU time on EC2 will cost between 75K US\$ and 120K US\$ and will plausibly take at most a few months.

I would be surprised if no one has a search running in the next couple of months (if not already).

$\endgroup$
2
$\begingroup$

There's now a published collision between two PDF documents that took:

  • 9,223,372,036,854,775,808 (2 ^ 63) SHA1 computations,
  • 6,500 CPU years and,
  • 110 GPU years

to find. This is actually the same as the upper limit that was predicted above. It is, of course, not arbitrary since there are some preconditions but these things tend to get easier to do with time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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