Join Log in
Score:2
jocerfranquiz avatar Crypto

Is there a quantum algorithm to find SHA256 collisions?

in flag
jocerfranquiz

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?

160
0 + 0
poncho avatar
my flag
poncho
"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...)
2
Reply
fgrieu avatar
ng flag
fgrieu
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.
0
Reply
Score:4
kodlu avatar Crypto
sa flag
kodlu

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.

0 + 0
kelalaka avatar
in flag
kelalaka
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.
1
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.