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

The first chosen-prefix collision for SHA-1

sha-mbles.github.io

Post reply on HN
Print view View original

51–60 of 369 posts

Re: The first chosen-prefix collision for SHA-1

#51

Post by DarkWiiPlayer »

emilfihlman wrote: post #44

>Can I try it out for myself? Since our attack on SHA-1 has pratical implications, in order to make sure proper countermeasures have been pushed we will wait for some time before releasing source code that allows to generate SHA-1 chosen-prefix collisions. Sigh. Again with this idiocy. All instances where the adversary is capable of launching this attack financially mean they also have the capability to write the exp…

It does make sense.

Targets worth attacking at a high financial cost will most likely be the first to take measures against this attack.

The kind of target that takes a longer time to switch most likely isn't worth attacking unless it's a very cheap and fast operation.

And the longer you spend developing an exploit, the less viable the attack will become.

Re: The first chosen-prefix collision for SHA-1

#52

Post by simias »

groovybits wrote: post #10
rkangel wrote: post #6

Earlier quoted context omitted.

It adds to the weight of the argument, but there isn't a big issue. This article ( https://www.zdnet.com/article/linus-torvalds-on-sha-1-and-gi... ) and the linked email ( https://marc.info/?l=git&m=148787047422954 ) both seem to still apply.

Further details as to why Torvalds is not concerned: From the email... "I haven't seen the attack yet, but git doesn't actually just hash the data, it does prepend a type/length field to it. That usually tends to make collision attacks much harder, because you either have to make the resulting size the same too, or you have to be able to also edit the size field in the header." [...] "I haven't seen the attack detail…

The fact that this attack is chosen prefix does weaken the first argument though, you may now find a collision even accounting for any prefixed git "header". The rest is still completely valid though.

I still feel like they really should've taken this problem more seriously and earlier. The more we wait the more painful the migration will be when the day comes to move to a different hash function, because everybody knows that'll happen sooner or later. Two years ago we had a collision, now we have chosen prefix, how much longer until somebody actually manages to make a git object collision?

And keep in mind that public research is probably several years behind top secret state agency capabilities. Let's stop looking for excuses every time SHA-1 takes a hit and rip the bandaid already. It's going to be messy and painful but it has to be done.

Re: The first chosen-prefix collision for SHA-1

#53

Post by bjornsing »

groovybits wrote: post #10
rkangel wrote: post #6

Earlier quoted context omitted.

It adds to the weight of the argument, but there isn't a big issue. This article ( https://www.zdnet.com/article/linus-torvalds-on-sha-1-and-gi... ) and the linked email ( https://marc.info/?l=git&m=148787047422954 ) both seem to still apply.

Further details as to why Torvalds is not concerned: From the email... "I haven't seen the attack yet, but git doesn't actually just hash the data, it does prepend a type/length field to it. That usually tends to make collision attacks much harder, because you either have to make the resulting size the same too, or you have to be able to also edit the size field in the header." [...] "I haven't seen the attack detail…

> you have to be able to also edit the size field in the header.”

As I read the OP [1] a chosen-prefix collision attack such as this allows you to “edit the size field in the header”. Or am I missing something?

1. “A chosen-prefix collision is a more constrained (and much more difficult to obtain) type of collision, where two message prefixes P and P’ are first given as challenge to the adversary, and his goal is then to compute two messages M and M’ such that H(P || M) = H(P’ || M’), where || denotes concatenation.”

EDIT: On second thought I was missing something: the adversary is further constrained in the git case because it must find M and M’ of correct length (specified in P and P’). Linus is right (as usual), this probably makes it much harder.

Re: The first chosen-prefix collision for SHA-1

#54

Post by est31 »

tny wrote: post #31
est31 wrote: post #23

Earlier quoted context omitted.

That first quote is misleading. git's special hashing scheme doesn't make the attack "much harder". First there is no difference in length in the original shattered collision already: $ curl https://shattered.io/static/shattered-1.pdf | wc -c 422435 $ curl -s https://shattered.io/static/shattered-2.pdf | wc -c 422435 Second, the length is already being hashed into the content during computation of a SHA-1 hash. Look…

But even if the lengths are same, the resulting SHA1 will be different since you prefix the length before hashing

The shattered prefix was chosen as well, see my other comment in the thread: https://news.ycombinator.com/item?id=21980759

The only thing that prefixing the length makes difficult is using the same prefix multiple times: you basically have to make up your mind about the type and length before mounting the shattered attack. Also, the prefix means you have to do your own shattered attack and can't use the PDFs that google provided as proof of their project's success. Price tag for that seems to be 11k.

[1]: https://github.com/cr-marcstevens/sha1collisiondetection

Re: The first chosen-prefix collision for SHA-1

#55

Post by toyg »

runeks wrote: post #35
est31 wrote: post #23

Earlier quoted context omitted.

That first quote is misleading. git's special hashing scheme doesn't make the attack "much harder". First there is no difference in length in the original shattered collision already: $ curl https://shattered.io/static/shattered-1.pdf | wc -c 422435 $ curl -s https://shattered.io/static/shattered-2.pdf | wc -c 422435 Second, the length is already being hashed into the content during computation of a SHA-1 hash. Look…

The point is that the hashed data must follow a specific data format, and can’t just be arbitrary data. This means that the collision data MUST contain the length at some specific offset in the data, which makes it harder to find a collision. The more restrictive the serialization format of the hashed data, the harder it is to find a collision that’s valid in the given application context.

> the harder it is to find a collision that’s valid in the given application context

In the double-digit thousands of dollars, an attack that gets 10x or 100x harder is still cheap for state actors.

Assuming the NSA is at least a year or two ahead of the field, git should now accelerate its migration process.

Re: The first chosen-prefix collision for SHA-1

#56

Post by jen20 »

dafman wrote: post #30
umvi wrote: post #20

Is "a Shambles" British or something? I've always heard it as "in Shambles"

Yes, at least where I live in the south of the UK. Other phrases you might hear are "What a shambles", "That is an absolute shambles" or "Omnishambles"

"Omnishambles" has a fun etymology - it comes from the political satire "The Thick of It": https://en.wikipedia.org/wiki/Omnishambles

Re: The first chosen-prefix collision for SHA-1

#57

Post by simias »

wyldfire wrote: post #19
groovybits wrote: post #10

Earlier quoted context omitted.

Further details as to why Torvalds is not concerned: From the email... "I haven't seen the attack yet, but git doesn't actually just hash the data, it does prepend a type/length field to it. That usually tends to make collision attacks much harder, because you either have to make the resulting size the same too, or you have to be able to also edit the size field in the header." [...] "I haven't seen the attack detail…

I think those are pretty practical approaches. But it sounds as if the cost of changing the hash algorithm is high. What are the impacts of this change? How many things would break if git just changed the algorithm with each new release? Does git assume that the hash algorithm is statically given to be SHA-1 or are there qualifiers on which algorithm is enabled/permitted/configured?

The cost is very high but it's only getting higher with time. People have known that SHA-1 was weak and deprecated for much of git's existence. Doing the switch in 2010 would've been painful, doing it now would be orders of magnitude more so and I doubt it'll get any easier in 2030 unless some other SCM manages to overtake git in popularity which seems unlikely at this point.

Unless Linus really believes that git will be fine using SHA-1 for decades to come I don't think it's very responsible to keep kicking the ball down the road waiting for the inevitable day when a viable proof of concept attack on git will be published and people will have to emergency-patch everything.

Re: The first chosen-prefix collision for SHA-1

#58

Post by StuffedParrot »

cpach wrote: post #24
umvi wrote: post #20

Is "a Shambles" British or something? I've always heard it as "in Shambles"

AFAICT ”a shambles” is correct usage. See https://brians.wsu.edu/2016/05/24/in-shambles-a-shambles/

...for traditional use, maybe, but any editor worth their salt will stop you from doing so. At least in America. Many words have changed their meaning and use over the last 500 years.

Re: The first chosen-prefix collision for SHA-1

#59

Post by toyg »

paulddraper wrote: post #21
wyldfire wrote: post #19

Earlier quoted context omitted.

I think those are pretty practical approaches. But it sounds as if the cost of changing the hash algorithm is high. What are the impacts of this change? How many things would break if git just changed the algorithm with each new release? Does git assume that the hash algorithm is statically given to be SHA-1 or are there qualifiers on which algorithm is enabled/permitted/configured?

After making the actual code change, the biggest problem is breaking compatibility with decades of tools in the ecosystem that rely on historically consistent SHA-1 hashes. Git is moving to a flexible hash though. [1] [1] https://stackoverflow.com/questions/28159071/why-doesnt-git-...

Maybe it's time for a version 3 that breaks a bit of compatibility.

The Python community would freak out, lol.

Re: The first chosen-prefix collision for SHA-1

#60

Post by tedunangst »

groovybits wrote: post #10
rkangel wrote: post #6

Earlier quoted context omitted.

It adds to the weight of the argument, but there isn't a big issue. This article ( https://www.zdnet.com/article/linus-torvalds-on-sha-1-and-gi... ) and the linked email ( https://marc.info/?l=git&m=148787047422954 ) both seem to still apply.

Further details as to why Torvalds is not concerned: From the email... "I haven't seen the attack yet, but git doesn't actually just hash the data, it does prepend a type/length field to it. That usually tends to make collision attacks much harder, because you either have to make the resulting size the same too, or you have to be able to also edit the size field in the header." [...] "I haven't seen the attack detail…

What if somebody makes an attack where they can choose the size and then find a collision?
Post reply on HN