Brute-Force Cryptanalysis with Aging Hardware: Controling Half the Output of SHA-256

10/17/2019
Speaker(s) : Charles Bouillaguet
This 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.