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

11–20 of 68 posts

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

#11

Post by H8crilA »

glandium wrote: post #10
rowbin wrote: post #8

Earlier quoted context omitted.

But your are going backwards though. You have a sha-256 value and want to find an input with the same result. But this input again has to be a sha-256 result and you need to find an input for that as well, right? This would only work if you have the intermediate sha-256 value, that produces the final sha-256 or you can find a collision that itself is a sha-256 value.

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.

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 them for anything.

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

#13

Post by [deleted] »

rowbin wrote: post #8
Karliss wrote: post #7

Earlier quoted context omitted.

I don't think double sha256 makes any difference with regards to collisions. If there is a collision after single sha256 they will still collide after second layer of hashing sha256(x)=sha256(y) => sha256(sha256(x))=sha256(sha256(y)).

But your are going backwards though. You have a sha-256 value and want to find an input with the same result. But this input again has to be a sha-256 result and you need to find an input for that as well, right? This would only work if you have the intermediate sha-256 value, that produces the final sha-256 or you can find a collision that itself is a sha-256 value.

[deleted]

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

#14

Post by tialaramex »

glandium wrote: post #10
rowbin wrote: post #8

Earlier quoted context omitted.

But your are going backwards though. You have a sha-256 value and want to find an input with the same result. But this input again has to be a sha-256 result and you need to find an input for that as well, right? This would only work if you have the intermediate sha-256 value, that produces the final sha-256 or you can find a collision that itself is a sha-256 value.

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.

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

#15

Post by tialaramex »

H8crilA wrote: post #11
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.

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" ?

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

#16

Post by popol12 »

H8crilA wrote: post #11
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.

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…

twice as difficult ? It doesn't match what you say after that

2²⁵⁶ = 2¹²⁸ * 2¹²⁸

So, isn't it rather 2¹²⁸ times more difficult ?

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

#17

Post by hn_p4ttern »

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 valid AND makes sense for something

Let me know.

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

#18

Post by popol12 »

glandium wrote: post #10
rowbin wrote: post #8

Earlier quoted context omitted.

But your are going backwards though. You have a sha-256 value and want to find an input with the same result. But this input again has to be a sha-256 result and you need to find an input for that as well, right? This would only work if you have the intermediate sha-256 value, that produces the final sha-256 or you can find a collision that itself is a sha-256 value.

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.

Let's say I have a string S.

MD5(MD5(S)) = Y

Now, I find a collision string SS (of length 128 bits, like an MD5 hash), where MD5(SS) == Y

Then I find a collision string SSS (this time, length doesn't matter), where MD5(SSS) == SS

Then we have MD5(MD5(SSS)) == Y, which was only twice harder than finding a single MD5 collision.

Could someone explain what is wrong with my reasoning ?

Edit: Oh okay, got it, when we say "MD5 is broken, it's possible to do a collision attack", what we mean is that we can easily find 2 strings S1 and S2 where MD5(S1) == MD5(S2) But S1 and S2 and found randomly, we don't have a way to find a string S3 where MD5(S3) == Y for any Y value (that is what we call a pre-image attack, not a collision attack)

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

#19

Post by H8crilA »

popol12 wrote: post #16
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…

twice as difficult ? It doesn't match what you say after that 2²⁵⁶ = 2¹²⁸ * 2¹²⁸ So, isn't it rather 2¹²⁸ times more difficult ?

Security is typically measured in bits. But yes you're right, maybe I should have written "square as difficult" to be more clear :)

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

#20

Post by [deleted] »

lifthrasiir wrote: post #6

It took me a lot of head scratching to exactly understand what this means, so for your information: this is not a full attack and you are safe (for now). If you need a concrete proof: import hashlib m0 = bytes.fromhex(''' c32aef52 512294ba 9db5ed8c 8c8c88ed b2de2765 63a2d14e ec7619cc 93b21182 e5050f50 f0839b60 7b1ee176 aaa06d68 c462343c 67898962 9558f495 04281f2c ''') m1 = bytes.fromhex(''' 5d0f5ae6 05e98311 8fa3c73a…

[deleted]
Post reply on HN