Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

First practical SHA-256 collision for 31 steps. fse2024

twitter.com

Post reply on HN
Print view View original

21–30 of 68 posts

Re: First practical SHA-256 collision for 31 steps. fse2024

#21

Post by H8crilA »

tialaramex wrote: post #15
H8crilA wrote: post #11

Earlier quoted context omitted.

Pre-image is approximately "twice as difficult" as a collision. A generic attack on, say, a 256 bit long hash function takes 2^128 time to find a collision, but 2^256 time to find a preimage. And like you say, this also shows up in practice: both MD-5 and SHA-1 are completely broken when it comes to collision resistance, but both are (probably) still OK for preimage resistance. I would still not recommend either of t…

Where on earth did you get this idea from? What is a "generic attack"? How could you turn a collision somehow into a pre-image attack? How is many orders of magnitude "twice" ?

You can find this in any introduction to cryptography textbook/course. "Generic attack" is a common term for "just use brute force" [1]. It's called "generic" because it works regardless of the implementation of the primitive. For pre-image resistance the generic attack just hashes messages until it finds the right image, for collision resistance you can get a quadratic speedup via the so called birthday problem / birthday attack [1][2], where you keep hashing messages and storing the hashes until any two of the messages happen to hash to the same value.

[1] https://crypto.stackexchange.com/questions/19194/is-there-an...

[2] https://en.wikipedia.org/wiki/Birthday_problem

Re: First practical SHA-256 collision for 31 steps. fse2024

#22

Post by Rygian »

hn_p4ttern wrote: post #17
0x073 wrote: post #12

Good that git still use sha1 ;)

Is it used to sign a commit, right ? Which are the probabilities to have a collision that: a) is still code b) is still code AND is code similar to a previous commit c) is still code AND is code similar to a previous commit AND is valid d) is still code AND is code similar to a previous commit AND is valid AND makes sense for something OR at least a) is still code b) is still code AND is valid d) is still code AND is…

For the choices after your "OR at least" line, just consider that most of the collision material could be padded into a comment, so achieving a), b) and d) would be "trivial."

Re: First practical SHA-256 collision for 31 steps. fse2024

#23

Post by hn_p4ttern »

Rygian wrote: post #22
hn_p4ttern wrote: post #17

Earlier quoted context omitted.

Is it used to sign a commit, right ? Which are the probabilities to have a collision that: a) is still code b) is still code AND is code similar to a previous commit c) is still code AND is code similar to a previous commit AND is valid d) is still code AND is code similar to a previous commit AND is valid AND makes sense for something OR at least a) is still code b) is still code AND is valid d) is still code AND is…

For the choices after your "OR at least" line, just consider that most of the collision material could be padded into a comment, so achieving a), b) and d) would be "trivial."

IMHO "be padded into a comment" is included in "is valid code", still 1 in is a good approximation of that probability.

Please, correct me if I'm wrong.

Re: First practical SHA-256 collision for 31 steps. fse2024

#24

Post by jacobgorm »

hn_p4ttern wrote: post #17
0x073 wrote: post #12

Good that git still use sha1 ;)

Is it used to sign a commit, right ? Which are the probabilities to have a collision that: a) is still code b) is still code AND is code similar to a previous commit c) is still code AND is code similar to a previous commit AND is valid d) is still code AND is code similar to a previous commit AND is valid AND makes sense for something OR at least a) is still code b) is still code AND is valid d) is still code AND is…

It is used to name a a commit, not to sign it. So the data structure itself will be corrupted if there is a collision, as it relies on the invariant that each commit has a unique name. And the collision has to happen within a single repo.

Re: First practical SHA-256 collision for 31 steps. fse2024

#25

Post by H8crilA »

tialaramex wrote: post #14
glandium wrote: post #10

Earlier quoted context omitted.

Going backwards, as you say, is called a pre-image attack. That's different from a collision attack, which is generating two inputs with the same hash. Pre-image attacks are MUCH more difficult. How much more? well, MD-5 is considered broken, and yet, there isn't one for it.

There is a pre-image attack for MD5, it's just not considered good enough to be practical. Quoting Wikipedia: > In April 2009, an attack against MD5 was published that breaks MD5's preimage resistance. This attack is only theoretical, with a computational complexity of 2123.4 for full preimage.

Yes, but that's very little improvement over the generic 2^128 attack - trying random messages until one happens to match the target hash. The attack quoted by Wikipedia achieves only 4.6 bits of speedup (note that it's 2^123.4, not 2134.4 :) ). There are attacks of this sort against many cryptographic primitives, including AES, where you can gain just a few bits over the generic / brute force attacks.

Re: First practical SHA-256 collision for 31 steps. fse2024

#26

Post by nabla9 »

popol12 wrote: post #5

Bitcoin is using double sha256, just in case someone is wondering. Though I wonder if double sha256 makes it twice harder to break or if it's better or lower than that.

Frank @jedisct1

>Wouldn’t help in that case. Collision resistance of a composition degrades to the one of the weakest function (it’s even slightly worse). Double SHA2 only protects against length extension attacks. https://twitter.com/jedisct1/status/1772911384356868586

Re: First practical SHA-256 collision for 31 steps. fse2024

#27

Post by pornel »

hn_p4ttern wrote: post #17
0x073 wrote: post #12

Good that git still use sha1 ;)

Is it used to sign a commit, right ? Which are the probabilities to have a collision that: a) is still code b) is still code AND is code similar to a previous commit c) is still code AND is code similar to a previous commit AND is valid d) is still code AND is code similar to a previous commit AND is valid AND makes sense for something OR at least a) is still code b) is still code AND is valid d) is still code AND is…

For now the SHA-1 collisions are easily detectable, but it could get worse.

In case of MD5, there is now a collision I wouldn't expect was possible: in readable ASCII.

https://mastodon.social/@Ange/112124123552605003

Re: First practical SHA-256 collision for 31 steps. fse2024

#28

Post by panzi »

H8crilA wrote: post #9
jl6 wrote: post #2

I assume “steps” here means rounds? For reference, standard SHA-256 is 64 rounds.

SHA-2, including SHA-256, is constructed using a Davies–Meyer compression function. That compression function starts with a block cipher - so an object like AES, but with wider keys and wider block size. For SHA-2 this block cipher is called SHACAL-2. Now what we're seeing here is an attack on SHA-2 assuming a very, very significant degradation in SHACAL-2, where we run far fewer rounds than assumed in the standard.…

I wonder, given the current rate of development when will there be the first collision in the hashes of the Linux kernel git repository. Wait, did git finish the switch to SHA-256 or is it still using SHA-1. Googling... all I can find suggests that everyone is still using it with SHA-1 and SHA-256 repos aren't compatible with SHA-1 repos (whatever that means exactly).

Re: First practical SHA-256 collision for 31 steps. fse2024

#29

Post by tialaramex »

H8crilA wrote: post #21
tialaramex wrote: post #15

Earlier quoted context omitted.

Where on earth did you get this idea from? What is a "generic attack"? How could you turn a collision somehow into a pre-image attack? How is many orders of magnitude "twice" ?

You can find this in any introduction to cryptography textbook/course. "Generic attack" is a common term for "just use brute force" [1]. It's called "generic" because it works regardless of the implementation of the primitive. For pre-image resistance the generic attack just hashes messages until it finds the right image, for collision resistance you can get a quadratic speedup via the so called birthday problem / bi…

I don't think that "look, raw brute force has this property" is at all useful in this context where you'd obviously actually compare a real attack not brute force. There's no reason to believe (and every reason not to) that the same property somehow applies.

That Stack Exchange answer also immediately set off alarm bells in my head because it pretends to be entirely generic, but the obvious thing to do with entirely generic cryptographic intuitions is apply them to the One Time Pad and check their answers work. This intuition doesn't work. Even if you could try all the possible keys you learn nothing, because of the hand-waving about "plausible" plaintext.

Re: First practical SHA-256 collision for 31 steps. fse2024

#30

Post by Rygian »

hn_p4ttern wrote: post #23
Rygian wrote: post #22

Earlier quoted context omitted.

For the choices after your "OR at least" line, just consider that most of the collision material could be padded into a comment, so achieving a), b) and d) would be "trivial."

IMHO "be padded into a comment" is included in "is valid code", still 1 in is a good approximation of that probability. Please, correct me if I'm wrong.

That's what I meant.
Post reply on HN