10
$\begingroup$

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. Gimli permutation in Sponge mode of capacity of at least 128-bit).

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

$\endgroup$
  • 3
    $\begingroup$ It really depends on your use-case. Eg 64-bit is fine for MACs where you drop the connection and re-negotiate as soon as you see one MAC validation error. $\endgroup$ – SEJPM Oct 28 '18 at 13:03
  • 1
    $\begingroup$ Let's assume that brute force is possible, otherwise all the calculations are kind of pointless. My PIN has a security of around 13 bits. $\endgroup$ – Maarten Bodewes Oct 29 '18 at 1:06
  • $\begingroup$ @MaartenBodewes Interesting enough, my PIN has a security of around 20 bits. $\endgroup$ – DannyNiu Oct 29 '18 at 3:01
19
$\begingroup$

TL;DR; Just give me the numbers;

  1. Summit can reach $\approx 2^{63}$ SHA-1 hashes around one hour, $\approx 2^{72}$ hashes in one year.
  2. Titan can reach $\approx 2^{63}$ SHA-1 hashes around two hours, $\approx 2^{71}$ hashes in one year.
  3. Bitcoin miners reached $\approx 2^{91.6}$ SHA-256 hashes per year in 25 September 2018.

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)

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)1. 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;

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

$\endgroup$
  • 6
    $\begingroup$ One may want to note that $2^{64}$ SHA1 evaluations cost about 1M USD on AWS using p3.16xlarge instances. $\endgroup$ – SEJPM Oct 28 '18 at 13:20
  • 1
    $\begingroup$ Depending on the application, you may need to take into account the decrease in this cost over time. A MAC or digital signature that isn't worth forging today might be trivial in 20 years. How long does your security need to last? $\endgroup$ – Gordon Davisson Oct 29 '18 at 1:50
  • $\begingroup$ Would these numbers apply equally to OpenPGP "long" key IDs which are the lower 64 bits of a SHA1 hash of the public key? Related: security.stackexchange.com/questions/198249/… $\endgroup$ – Jonathan Cross Nov 23 '18 at 1:32
  • $\begingroup$ @JonathanCross as Dave commented, it is not clear how one can use the shatter since it requires a freedom. One year is approximately 8765 hours = $2^13$, so Titan may reach $2^75$ in one year but the generic collision is $2^{80}$ $\endgroup$ – kelalaka Nov 23 '18 at 20:21
  • $\begingroup$ @kelalaka 2⁸⁰ would be for a full SHA1 hash collision, but I'm only talking about the lower parts (last 16 hex chars) of the hash. Still, it seems the "freedom" you are talking about would only come from the underlying data (OpenPGP pubkey in this case) so making a usable key would require extra steps of generating new private key => pubkey before hashing. I guess SHAttered isn't particularly applicable here. $\endgroup$ – Jonathan Cross Nov 26 '18 at 18:48
17
$\begingroup$

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.

$\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.