Paper 2021/886

Computational Records with Aging Hardware: Controlling Half the Output of SHA-256

Mellila Bouam, Charles Bouillaguet, Claire Delaplace, and Camille Noûs

Abstract

SHA-256 is a secure cryptographic hash function. As such, its output should not have any detectable property. This paper describes three bit strings whose hashes by SHA-256 are nevertheless correlated in a non-trivial way: the first half of their hashes XORs to zero. They were found by “brute-force”, without exploiting any cryptographic weakness in the hash function itself. This does not threaten the security of the hash function and does not have any cryptographic implication. This is an example of a large “combinatorial” computation in which at least 8.7 × 10 22 integer operations have been performed. This was made possible by the combination of: 1) recent progress on algorithms for the underlying problem, 2) creative use of "dedicated" hardware accelerators, 3) adapted implementations of the relevant algorithms that could run on massively parallel machines. The actual computation was done on aging hardware. It required seven calendar months using two obsolete second-hand bitcoin mining devices converted into "useful" computational devices. A second step required 570 CPU-years on an 8-year old IBM BlueGene/Q computer, a few weeks before it was scrapped. To the best of our knowledge, this is the first practical 128-bit collision-like result obtained by brute-force, and it is the first bitcoin miner-accelerated computation.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Parallel Computing
Keywords
3XORGeneralized Birthday ParadoxBrute-forceImplementationHardwareASICbitcoin hardware
Contact author(s)
charles bouillaguet @ lip6 fr
History
2021-06-29: received
Short URL
https://ia.cr/2021/886
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/886,
      author = {Mellila Bouam and Charles Bouillaguet and Claire Delaplace and Camille Noûs},
      title = {Computational Records with Aging Hardware: Controlling Half the Output of SHA-256},
      howpublished = {Cryptology ePrint Archive, Paper 2021/886},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/886}},
      url = {https://eprint.iacr.org/2021/886}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.