3
$\begingroup$

As I understand, the Bitcoin network can be seen as a supercomputer looking for SHA256 collisions. It hasn't found one yet (March 2022). Also, in the post-quantum cryptography era, you would be capable of reversing SHA256 hashes.

But in the case of finding hash collisions, is there an algorithm already proposed?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ "Also, in the post-quantum cryptography era, you would be capable of reversing SHA256 hashes" - could you expand on that - if you know of a Quantum Algorithm that can feasibly compute preimages of SHA256 hashes, that would be Big News (and in any case, if you can compute SHA256 preimages, finding collisions is easy...) $\endgroup$
    – poncho
    Commented Mar 2, 2022 at 22:39
  • $\begingroup$ You can see what you want in bitcoin, but no, it's not looking for SHA-256 collisions. It's generating SHA-256 values that could collide. But it considers only a ticy fraction with a certain rare arbitrary property, and discards all others, where collisions (if any) are most likely to occur. What's true is that it's still quite far from having generated enough SHA-256 that a collision is likely anyway, thus it makes no difference that it's not looking for collisions. $\endgroup$
    – fgrieu ♦
    Commented Mar 3, 2022 at 16:27
  • $\begingroup$ computing hash pre-images is not possible/reliable because hashing is inherently lossy. $\endgroup$
    – Sean
    Commented Mar 11 at 18:31

1 Answer 1

Reset to default
5
$\begingroup$

In 2009, D J Bernstein wrote one of the early papers on this topic available here:

The abstract states:

Current proposals for special-purpose factorization hardware will become obsolete if large quantum computers are built: the numberfield sieve scales much more poorly than Shor’s quantum algorithm for factorization. Will all special-purpose cryptanalytic hardware become obsolete in a post-quantum world? A quantum algorithm by Brassard, Høyer, and Tapp has frequently been claimed to reduce the cost of $b$-bit hash collisions from $2^{b/2}$ to $2^{b/3}.$ This paper analyzes the Brassard–Høyer–Tapp algorithm and shows that it has fundamentally worse price-performance ratio than the classical van Oorschot–Wiener hash-collision circuits, even under optimistic assumptions regarding the speed of quantum computers.

More recently some partial progress was reported by Hosoyamada and Sasaki in CRYPTO 2021 on reduced round versions of SHA-256 and SHA-512, see here; there may also be a publicly accessible version in the iacr.org preprint server. Edit: The slides and talk are available here

The abstract states:

In this paper, we study dedicated quantum collision attacks on SHA-256 and SHA-512 for the first time. The attacks reach 38 and 39 steps, respectively, which significantly improve the classical attacks for 31 and 27 steps. Both attacks adopt the framework of the previous work that converts many semi-free-start collisions into a 2-block collision, and are faster than the generic attack in the cost metric of time-space tradeoff. We observe that the number of required semi-free-start collisions can be reduced in the quantum setting, which allows us to convert the previous classical 38 and 39 step semi-free-start collisions into a collision. The idea behind our attacks is simple and will also be applicable to other cryptographic hash functions.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Brassard et al.'s algorithm requires $\approx 2^{85}$-time and -space that makes it infeasible on the space. Yes, the reduced version can be faster than the classical attacks, however, the rounds are always problematic. $\endgroup$
    – kelalaka
    Commented Mar 2, 2022 at 21:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.