We broke 92% of SHA-256 – you should start to migrate from it

[flagged]

>The neat thing about bitcoin is that the incentive to break it is so high that it would almost certainly be the first place you would learn that SHA2 had been broken.

We actually see the incentive in the other direction, if we were able to reduce the search space for bitcoin proof-of-work (by applying thousands of higher-order algabraic theorems end-to-end to reduce the search space somewhat[1]), we would be financially incentivized not to tell anyone and mine at a discount. The financial incentive is against open research and disclosure. We don't get anything out of disclosing this except a neat publication.

[1] interestingly, ASICs (which are usually used to mine bitcoin) basically encode every operation verbatim, they don't use higher order mathematics at all. However, reducing mining complexity is not really on the horizon, even with our latest approaches, since it would require end-to-end complete control over the double-SHA-256 pipeline. That's considerably harder than just finding a collision when you're allowed to search just the tail part (the final rounds).

Is a partial collision an indicator that it could be broken? The "we broke it" seems an exageration, but maybe that's a failure of my understanding.

Thank you for pointing out that that section could be clearer. I've now updated it. It now reads:

>We've just gotten 92% of the way to finding a single collision (this means that there is no full collision yet.). This has security ramifications in that other researchers are expected to be able to complete the work through similar methods as explored in the paper, and eventually produce collisions at will. We weren't sure if this was a remarkable result, since it's not a full collision, but we shared the work with the leading cryptographer in the field, who holds the world records in reduced-round attacks, and got great encouragement to proceed to publish it as a paper, so we did so.

(if we had found a single full collision, we would have just written "we broke SHA-256". This is 92% of the way to a full collision. Any collision is considered a great reduction in the security of the hash, because it means that there two different files with the same cryptographic hash. This is what happened to other algorithms such as MD5, as demonstrated in the linked tool.)

Fixed, thank you and my apologies for the oversight. The titles were accurate and we consulted those works in preparing this work.

You can verify the certificates yourself or just wait for us to make an end-to-end collision generator as we did for MD5[1] - you can use that to generate a collision in seconds on your phone or any computer. If you wait for us to complete the end to end collision, in a sense it will be a little too late as TLS certificates and other security that relies on SHA-256 needs time to move away. We think it's responsible to disclose at this stage, and as mentioned, our peer reviewer said it is a "very good result" that is "worth publishing". We've gone to great pains to make our method completely reproducible, even writing in the article that we'll help anyone who is having trouble with any part.

[1] https://stateofutopia.com/experiments/md5collider

I didn't ask for money on the website.

This hn post is made by author of the paper. It needs even a tiny bit of peer review.

No, or we would have said so. It means that by relaxing the equations schedule somewhat, we are able to find a pair of differing messages that produce the same digest. However, we only relax the schedule a little bit, we still enforce 59 out of 64 schedule equations through the full 64 rounds - which is why we're only 92% of the way through to breaking it and not 100% of the way as we are with MD5. Importantly, we are not yet implementing the most advanced technique of Wang-style message modification, and we therefore expect that someone will be able to satisfy all 64 equations soon. This will result in an actual full-schedule, full-round collision. The previous record was only just 39 rounds out of 64 rounds, leaving 25 rounds, usually each of which mixes the message up completely. As mentioned in the paper, this attacks the problem from a different direction.

Also, a collision on single-sha256 would imply a collision of double-sha256 right off the bat, since the inputs to the second round would be matching. But as you say, a collision attack doesn't do much to BTC mining.

Thanks, you're right. My "it is possible" is doing some heavy lifting there :). We've found theorems (stated in the paper) that carry through 64 rounds, so it is possible that theorems might carry through the full 128 rounds of double-SHA256. Bitcoin's proof-of-work is indeed a "partial second preimage", and constraints a certain number of leading zeros, i.e. a certain number of set bits. It's possible (there we go again) that this could leave enough wiggle room for large algabraic solvers like kissat to satisfy a large number of clauses about them. So far nobody is doing that, and ASICs are very simplistic. However, we are not making any claims about preimage attacks in this paper!

Indeed, the text feels very LLM-written.

I believe I hold the actual record for most colliding bits in full-round SHA256 (72% of bits matching). My proof fits in a tweet, why doesn't yours?

https://news.ycombinator.com/item?id=38668893

(Also my work does not demonstrate any weakness in SHA256, it's just an application of the birthday paradox)

Why omit the name of the leading cryptographer in the field?

What does it mean to “break broken 92% of SHA-256“?

Go seek a mental health professional and never post here again until you have been diagnosed and medicated.

That's not how this works, though. I don't care if the method is interesting. I care if it works. I can write an interesting proof that P=NP but that doesn't make it valid.

It's on the author to explain what they mean. Here, they haven't.

Claude didn't "think" anything

Does the fact that Claude wrote the paper help Claude to think the paper was interesting? <facepalm> I'd suggest sticking to your "I don't normally do this" idea

Extraordinary claims require extraordinary evidence, and the burden of proof lies with the one making the claim.

See also https://en.wikipedia.org/wiki/Brandolini%27s_law -

> The amount of energy needed to refute bullshit is an order of magnitude bigger than that needed to produce it.