73
$\begingroup$

Most of the answers I can find date to years back where the first collision(s) were found, but hardware mainly GPUs have progressed a lot in the past few years (with for example the new line of 3090s coming).

How easy is it to do so right now?

$\endgroup$
7
  • 2
    $\begingroup$ Earlier computational work can be extended cheaply to find new collisions. I guess the question restricts to obtaining collisions independently of earlier work. There's that relatively recent article, stating 8 GPU-years for a collision using GTX 1080 Ti, whatever that may be. $\endgroup$
    – fgrieu
    Apr 21 at 16:19
  • $\begingroup$ 1080 TI is outdated, and there are big performance upgrades in newer generations, and you can have a hundred or even thousand of those GPUs working. $\endgroup$
    – Hormoz
    Apr 21 at 16:38
  • 2
    $\begingroup$ I’m voting to close this question because this is rather performance of the GPUs not about new improvements of the cryptographical attaks. $\endgroup$
    – kelalaka
    Apr 21 at 17:57
  • 4
    $\begingroup$ Does it really matter though? Performance of GPUs affects cryptographical attacks. $\endgroup$
    – Hormoz
    Apr 21 at 18:29
  • 2
    $\begingroup$ The $9,223,372,036,854,775,808 \approx 2^{63}$ so the Summit can execute in one day and the collaborative powers of the Bitcoin miner can execute in one second. $\endgroup$
    – kelalaka
    Apr 22 at 19:52

1 Answer 1

116
$\begingroup$

According to some Hashcat benchmarks, a current Nvidia GPU can compute SHA-1 hashes at a rate of:

  • NVIDIA GeForce RTX 3090 ~22.6×109 hashes per second
  • NVIDIA GeForce RTX 3080 Ti ~21.7×109 hashes per second

And AMD graphics cards seems to perform in the same range as per this benchmark:

SHA-1 Speed.#1.........: 20.6×109

Given its MSRP price of ~\$649, the AMD RX 6800 XT seems to be our best candidate to conduct a similar attack. (Notwithstanding any chip shortage driving the prices up like crazy...)

Next, according to the 2017 shattered.it website and paper:

This attack required over 9,223,372,036,854,775,808 SHA1 computations [9×1018]. This took the equivalent processing power as 6,500 years of single-CPU computations and 110 years of single-GPU computations.

But as mentioned in fgrieu's comment, in 2020, a new paper ("SHA-1 is a Shambles") came out, further improving the SHAttered attack in which they estimated the cost of their attack to $~2^{61.6} = 3.5\times 10^{18}$ SHA-1 computations vs. the $2^{63}$ computations in the SHAttered one (see Table 4.)

We can thus compute that with the current GPUs it takes:

$$\frac{2^{61.6}}{20.6×10^9} \approx 169\times10^6$$

seconds with a single GPU, which is ~5.36 years. But this parallelizes relatively well, so you could just add more GPUs to the mix and you could get one in six months with 10 GPUs, or in 2 months with 30 GPUs... And that's at a theoretical cost of ~\$19,470 of GPUs, plus ~ \$2,000 of electricity costs running your 30 GPUs for 2 months...

You can also just rent three p3.16xlarge AWS instance with a hash rate of ~135GH/s each at a cost of ~\$24.48 per instance per hour, for a total of 405GH/s for \$73.44 per hour. That would take you ~2397.12 hours (3 months) and cost you ~\$176,044.

Remarkably, we can see that in only 5 years, we're down from an attack costing ~110 GPU years to an attack costing ~8 GPU-years in 2020 (thanks to theoretical improvements & newer GPUs) to just ~5.4 GPU years nowadays (thanks to newer, faster GPUs).

Also note that this is not taking possible ASICs into account, unlike this 2021 paper ("On The Cost of ASIC Hardware Crackers: A SHA-1 Case Study") which answers your question when assuming custom ASICs are an option:

In particular, we remark that the chosen-prefix collisions for SHA-1 can be generated in under a minute, with an ASIC cluster that costs a few dozen Millions dollars. Such ability would allow an attacker to apply the SLOTH attack on TLS or SSH connections using SHA-1.

Finally, if we take into account supercomputers and the Bitcoin network, this question is already covered in this excellent answer by kelalaka from 2018, and things aren't looking good: the Bitcoin network could do it in 1s, given its current hashrate of over 200TH/s... Yup: one second! But that's not technically true since Bitcoin's dedicated hardware is actually specialized in computing SHA-256 hashes.
In a more realistic way, it would take less than a day to do it on a super-computer such as the one owned by the US Department of Energy's Oak Ridge National Laboratory (ORNL) named "Summit".

$\endgroup$
1
  • 8
    $\begingroup$ Side note (no affiliation), but services like vast.ai cost between \$3 to \$5 per hour for 8x 3090s, so about the same speeds for this purpose. Another factor of eight down from the cost (~$25-35k). Though I love using Amazon as an example of GPU pricing for password cracking, actual costs can be much lower with other services, spot instances, etc. $\endgroup$ Apr 25 at 5:41

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.