Score:72

How easy is it in 2022 to find a SHA1 collision?

us flag

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?

fgrieu avatar
ng flag
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](https://eprint.iacr.org/2020/014.pdf) relatively recent article, stating 8 GPU-years for a collision using GTX 1080 Ti, whatever that may be.
Hormoz avatar
us flag
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.
kelalaka avatar
in flag
I’m voting to close this question because this is rather performance of the GPUs not about new improvements of the cryptographical attaks.
Hormoz avatar
us flag
Does it really matter though? Performance of GPUs affects cryptographical attacks.
kelalaka avatar
in flag
You are asking to compare them. You need to ask what is the current best attack that might use many different GPU/CPUs/ASIC to achieve their target.
kelalaka avatar
in flag
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.](https://crypto.stackexchange.com/a/63537/18298)
Blockchain Office avatar
gw flag
how about quantum attacks in speed to generate a collision?
Score:115
cn flag

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".

cn flag
Side note (no affiliation), but services like https://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.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.