LIP6 » Links » LIP6 events
ALMASTY
Brute-Force Cryptanalysis with Aging Hardware: Controling Half the Output of SHA-256
10/17/2019Speaker(s) :
Charles BouillaguetThis paper describes three random-looking bit strings whose hashes by SHA-256
maintain a non-trivial relation: their XOR starts with 128 zero bits. They have
been found by brute-force, without exploiting any cryptographic weakness in the
hash function itself. This shows that birthday-like computations on 128 bits are
becoming increasingly feasible, even for academic teams without substancial
means.
These bit strings have been obtained by solving a large instance of the
three-list generalized birthday problem, a difficult case known as the 3XOR
problem. The whole computation consisted of two equally challenging phases:
assembling the 3XOR instance and solving it.
It was made possible by the combination of: 1) recent progress on algorithms for
the 3XOR problem, 2) creative use of ``dedicated'' hardware accelerators, 3)
adapted implementations of 3XOR algorithms that could run on massively parallel
machines.
Building the three lists required 2^{68.2} evaluations of the compression
function of SHA-256. They were performed in 7 calendar months by two obsolete
second-hand bitcoin mining devices, which can now be acquired on eBay for about
80€. The actual instance of the 3XOR problem was solved in 300 CPU years on a
7-year old IBM Bluegene/Q computer, a few weeks before it was scrapped.
To the best of our knowledge, this is the first explicit 128-bit collision-like
result for SHA-256. It is the first bitcoin-accelerated cryptanalytic
computation and it is also one of the largest public ones.
damien.vergnaud (at) nulllip6.fr