How reassuring is 64-bit (in)security?

Question

In Feb 2017, CWI and Google announced SHAttered hash collision attack on SHA1, which took $2^{63.1}$ work estimated 6500 CPU years, to achieve. Therefore, 64-bit should be considered now an insecurity.

However, that's on the cloud computers of one of the largest tech company in the world, possibly taking hours if not days to find the collision. So 64-bit assurance may still be meaningful in some scenario (e.g. hash table in the implementation of associative arrays) assuming it can be correctly achieved (e.g. SipHash-2-4-128).

Also, $2^{-64}$ seems to be small enough a probability, that it's not uncommon that some protocols happily truncate their MAC to 64 bits, and some PQC KEMs take that as quite comfortable a margin of encryption failure probability.

So my question is: How reassuring is 64-bit security in terms of the fastest (classical) supercomputer in 2018, the IBM Summit (used in Oak Ridge National Laboratory).

Answer 1

TL;DR; Just give me the numbers;

Machines	in a second	in an hour	in a day	in a year
Summit on SHA-1	$\approx 2^{49.7} $	$ \approx 2^{61.5}$	$\approx 2^{66.1}$	$\approx 2^{74.6}$
Titan on SHA-1	$\approx 2^{49.1} $	$\approx 2^{61.0}$	$ \approx 2^{65.5}$	$\approx 2^{74.1}$
Bitcoin Miner on SHA-256D	$\approx 2^{67.1}$	$\approx 2^{78.9}$	$\approx 2^{83.5}$	$\approx 2^{92.09}$

1. Summit can reach $\approx 2^{63}$ SHA-1 hashes around 3 hours, $\approx 2^{74.6}$ hashes in one year.
2. Titan can reach $\approx 2^{63}$ SHA-1 hashes around 4 hours, $\approx 2^{74.1}$ hashes in one year.
3. Bitcoin miners reached $\approx 2^{92.09}$ SHA-256D hashes per year in 7 February 2021 ( or $\approx 2^{93.09}$ SHA-256)

---

Performance Results of some GPU's

1. On Amazon AWS P2, up to 16 Nvidia Tesla K80 GPUs has total $31,664.7$ MH/s SHA-1 calculations on average per board $\approx 1,992$ MH/s with hashcat-3.10
2. on 8x Nvidia GTX 1080 Hashcat Benchmarks has total $68,771.0$ MH/s SHA-1 calculations and on averageper board $8,596.4$ MH/s with hashcat 3.00
3. Tesla V-100 has $17,225$ MH/s with hashcat 4.0, ( very big? see comparison of NVdia's)

The below tables is constructed from various web-sites [1][2][3] and not taken on average.

\begin{array}{|l|c|}\hline Device & MH/s \\ \hline \text{GTX 1080 TI} & 12098.4 \\ \hline \text{RTX 2070S} & 11283.1 \\ \hline \text{RTX 2080 TI} & 16823.6 \\ \hline \text{RTX 3090} & 22220.5 \\ \hline \text{Tesla T4} & 5428.3 \\ \hline \text{Tesla P100} & 9653.8 \\ \hline \text{Tesla V100} & 17535.9 \\ \hline \text{Tesla K80} & 31664.7 \\ \hline \end{array}

Calculation based on Tesla V-100

This answer based on the 3rd GPU, Tesla V-100. Tesla V-100 has listed price as $10,664 and has 250 W power consumption. This is closest to

$ 17,225\;MH/s \approx 2^{35} H/s$

If you run the Tesla V-100 for one hour;

$2^{35}\cdot 2^{12} \approx 2^{47} H/h$ calculations.

OCLF's Summit

The Summit contains 27,648 ($\approx 2^{16}$) NVIDIA Volta architecture GPUs. According to Oak Ridge Library's news the GPU's are Tesla V100. From the picture of the server board, it is Tesla V100 SXM2, ~10% faster than Tesla V100 PCle and consumes 300W.

Total SHA-1 calculations of Summit in one hour $ \approx 2^{47}*2^{16}= 2^{63}$

• The SHAttered hash collision attack on SHA1 can be executed in a little more than 1 hour with Summit.

OCLF's Titan

The Titan contains $18,688 \approx 2^{15}$ physical nodes each contains an NVIDIA Kepler™ accelerator (GPU)¹. Assuming that Kepler = Tesla V-100

Total SHA-1 calculations of Titan in one hour $ \approx 2^{47}*2^{15}= 2^{62}$

• The SHAttered hash collision attack on SHA1 can be executed in 2 hours with Titan.

Cost

Here I will only talk about the initial cost of GPUs and their runtime cost by power consumption.

• Titan :The initial cost of GPUs : $27,648 * 10,664 \approx \\\$300M$
• Summit :The initial cost of GPUs : $18,688 * 10,664 \approx \\\$200M$
• Titan : Each VT-100 requires $250W*18,688 = 4.67MW$, and taking 12 cents per kilowatt-hour is an average in US, one year cost is \$4,896,256
• Summit : Each VT-100 requires $300W*27,648 = 8.29MW$, and taking 12 cents per kilowatt-hour is an average in US, one year cost is \$8,709,120
• And, if you rent AWS using p3.16xlarge instance the $2^{64}$ SHA1 evaluations cost about 1M USD.^{SEjPM's comment}

security

There are two question on this site answer the practicability of the shattered;

1. Does “Shattered” actually show SHA-1-signed certificates are “unsafe”?
2. After Google's collision attack, is RSA-SHA1 signature still safe?

tl;dr; for this answers;

• But it is not safe, regardless of Google's attack. Before Google attacked, we knew that SHA-1 is not the best choice.
• You are already too late. Migrate away from SHA-1 now.

---

notes;

¹ This calculation is based only GPUs and CPUs are slower in magnitude order. Only Titan has GPU on the Summit of Oak Ridge National Laboratory. rhea has only 9. Eos and ARM don't have any.

Answer 2

There is a huge difference between $2^{-64}$ probability of failure, which is indeed very small, and having to run $2^{64}$ in order to carry out the attack. The latter is much too small to be considered reasonable. Of course, one could argue about protecting secrets that are not very significant and you only need weak protection. However, it is usually very problematic to argue about this. My salary (sexual preference, health situation, etc.) may not be very secret to me, but may be very secret for someone else. It also may not be very secret now but may become so later on. However, beyond all of these arguments, the chance that this is the bottleneck and problem in your application is almost zero. You should use strong cryptography and not make these types of calculations at all. Bottom line, 128-bit security is the minimum required today.