[cryptome] Countdown to SHA-3 Collisions

  • From: Michael Best <themikebest@xxxxxxxxx>
  • To: cpunks <cypherpunks@xxxxxxxxxx>, cryptome <cryptome@xxxxxxxxxxxxx>
  • Date: Sun, 22 Nov 2015 22:57:03 -0500

The SHA-3 standard was released by NIST in August of this year. I'm
wondering if anyone has done the math on how long until we should no longer
consider it pretty secure enough-ish.

For comparison, here's the 2012 maths for SHA-1:

https://www.schneier.com/blog/archives/2012/10/when_will_we_se.html

On a NIST-sponsored hash function mailing list
<http://csrc.nist.gov/groups/ST/hash/email_list.html>, Jesse Walker (from
Intel; also a member of the Skein <http://www.schneier.com/skein.html>team)
did some back-of-the-envelope calculations to estimate how long it will be
before we see a practical collision attack against SHA-1. I'm reprinting
his analysis here, so it reaches a broader audience.
According to E-BASH <http://bench.cr.yp.to/ebash.html>, the cost of one
block of a SHA-1 operation on already deployed commodity microprocessors is
about 214 cycles. If Stevens' attack
<http://2012.sharcs.org/slides/stevens.pdf> of 260 SHA-1 operations
serves as the baseline, then finding a collision costs about 214 * 260 ~ 2
74cycles.
A core today provides about 231 cycles/sec; the state of the art is 8 = 23
cores
per processor for a total of 23 * 231 = 234 cycles/sec. A server
typically has 4 processors, increasing the total to 22 * 234 = 236 cycles/sec.
Since there are about 225 sec/year, this means one server delivers about 2
25 * 236 = 261 cycles per year, which we can call a "server year."
There is ample evidence that Moore's law will continue through the mid
2020s. Hence the number of doublings in processor power we can expect
between now and 2021 is:
3/1.5 = 2 times by 2015 (3 = 2015 - 2012)
6/1.5 = 4 times by 2018 (6 = 2018 - 2012)
9/1.5 = 6 times by 2021 (9 = 2021 - 2012)
So a commodity server year should be about:
261 cycles/year in 2012
22 * 261 = 263 cycles/year by 2015
24 * 261 = 265 cycles/year by 2018
26 * 261 = 267 cycles/year by 2021
Therefore, on commodity hardware, Stevens' attack should cost
approximately:
274 / 261 = 213 server years in 2012
274 / 263 = 211 server years by 2015
274 / 265 = 29 server years by 2018
274 / 267 = 27 server years by 2021
Today Amazon rents compute time on commodity servers for about $0.04 /
hour ~ $350 /year. Assume compute rental fees remain fixed while server
capacity keeps pace with Moore's law. Then, since log2(350) ~ 8.4 the
cost of the attack will be approximately:
213 * 28.4 = 221.4 ~ $2.77M in 2012
211 * 28.4 = 219.4 ~ $700K by 2015
29 * 28.4 = 217.4 ~ $173K by 2018
27 * 28.4 = 215.4 ~ $43K by 2021
A collision attack is therefore well within the range of what an organized
crime syndicate can practically budget by 2018, and a university research
project by 2021.
Since this argument only takes into account commodity hardware and not
instruction set improvements (e.g., ARM 8 specifies a SHA-1 instruction),
other commodity computing devices with even greater processing power (e.g.,
GPUs), and custom hardware, the need to transition from SHA-1 for collision
resistance functions is probably more urgent than this back-of-the-envelope
analysis suggests.
Any increase in the number of cores per CPU, or the number of CPUs per
server, also affects these calculations. Also, any improvements in
cryptanalysis will further reduce the complexity of this attack.
The point is that we in the community need to start the migration away
from SHA-1 and to SHA-2/SHA-3 now.

Other related posts: