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

Linus' reply on Git and SHA-1 collision

marc.info

Post reply on HN
Print view View original

231–240 of 273 posts

Re: Linus' reply on Git and SHA-1 collision

#231

Post by [deleted] »

more_original wrote: post #111
Strom wrote: post #26

Downloading the PDFs [1] and comparing their sizes takes less than a minute. They're the exact same size. Yet here we have Linus making one bet after another that size has to be different for this attack. Now to be fair, he also keeps repeating that he hasn't seen the attack yet . Which leads me to question why is this post interesting to HN? Is it to show how Linus aimlessly speculates and gets his guesses wrong? --…

The PDFs have the same size, but they do not have a header in the file that states their overall size. If PDF had a header at the beginning of the file that states the file size, then it could be harder to find a collision. From what I understand, the attack works by inserting garbage data after a fixed file prefix and before a fixed file suffix (anyone please correct me if I'm wrong).

[deleted]

Re: Linus' reply on Git and SHA-1 collision

#232

Post by more_original »

acqq wrote: post #230
more_original wrote: post #111

Earlier quoted context omitted.

The PDFs have the same size, but they do not have a header in the file that states their overall size. If PDF had a header at the beginning of the file that states the file size, then it could be harder to find a collision. From what I understand, the attack works by inserting garbage data after a fixed file prefix and before a fixed file suffix (anyone please correct me if I'm wrong).

> If PDF had a header at the beginning of the file that states the file size, then it could be harder to find a collision. No. It doesn't change anything if the size is in the PDF header. The size of both PDFs are the same, the header of both PDF files is the same on the both "shattered" files now. What Linus says is that if you tried to put these two PDF files in git, it would not see them as the same, as git calcul…

> But Google would be able to produce two PDF files that would, as git sees them, appear to be same just as easy as these that were produced.

Right, but they would have to re-do their enormous calculation. ("This attack required over 9,223,372,036,854,775,808 SHA1 computations.")

Google started with a common prefix p (the PDF header), then computed blocks M11, M12, M21 and M22, such that (p || M11 || M21 || S) and (p || M12 || M22 || S) collide for any suffix S. Given p, M11, M12, M21 and M22, anyone can make colliding PDFs that show different contents quickly. But to generate a collision with a different prefix q, e.g. one including the file size, one would have to do the expensive computation all over again, I think.

Note: I'm not trying to argue that SHA-1 can be made secure with padding. I was just trying to say that the statement "The PDFs have the same size" misses the point.

Re: Linus' reply on Git and SHA-1 collision

#234

Post by officelineback »

danmaz74 wrote: post #212
orblivion wrote: post #106

Earlier quoted context omitted.

I control a fleet of servers. I have a saltstack or ansible script. One of the steps in provisioning a new server is to pull library X from github.com. One day Egor Homakov finds a new hack and finds his way into access to the master branch for library X. As a prank, he force pushes a change to master. Being aware of such a possibility, instead of setting up my script to pull from master or even a specific tag, perha…

> Tomorrow, when preimage SHA-1 attacks are cheap, it will no longer save me. Well, Moore's law is petering out isn't it? :)

Moore's law is, but the cost of a given amount of computational ability is still going down quickly.

Re: Linus' reply on Git and SHA-1 collision

#236

Post by dromen »

hannob wrote: post #194
dromen wrote: post #193

Earlier quoted context omitted.

Some more advanced Git operations (I sadly never needed so far) can be used to break the "append only" part, right? Like for instance rebases?

You can always break append only logs, the point is, it's detectable.

What do you mean by detectable in the context of Git-as-append-only-log?

Re: Linus' reply on Git and SHA-1 collision

#237

Post by xkxx »

braveo wrote: post #105
xkxx wrote: post #80

Earlier quoted context omitted.

> What's shocking is how badly people understand the purpose of an analogy. The purpose of an analogy is to simplify something that's too hard to understand for the person you try to convey your idea to. Sometimes analogies are appropriate, e.g. when you teach something. When you want to convince somebody whose opinion is very different from yours, analogies aren't appropriate. They sound condescending: "because you…

We're talking about a conversation amongst kernel/software developers about a very technical software issue. Anyone who doesn't understand why the risk was so small doesn't belong in the conversation. Can you even imagine where our medical field would be if we expected surgeons to talk amongst themselves as if they were speaking to the general public? It is absolutely acceptable for the speaker to make assumptions ab…

> Can you even imagine where our medical field would be if we expected surgeons to talk amongst themselves as if they were speaking to the general public?

The Git devs are not heart surgeons, software development is not a medical field. Again, you are using an analogy to "prove" your point. Can you, please, use a real argument?

>> The purpose of an analogy is to simplify something that's too hard to understand for the person you try to convey your idea to.

> It's to convey an idea. That's it, anything you add to that is your own bias at work.

Do you disagree that using an analogy is oversimplification? If you don't, then that part about "to simplify a complex idea" in my statement should absolutely stay. If you do disagree, then please show why and how an analogy doesn't oversimplify a complex idea.

Re: Linus' reply on Git and SHA-1 collision

#238

Post by mi100hael »

victorNicollet wrote: post #206
otabdeveloper wrote: post #108

Earlier quoted context omitted.

> Not saying it's easy, but now it's on the horizon. Not really. It's not a preimage attack. They spent several hundred dollars to find two random byte strings with the same SHA1 hash. There's still no way to SHA1-collide a specific byte string instead of random junk.

This is exactly what euyyn is saying: create two files with the same SHA1 (by adding bytes of gibberish to an unused section), commit one to the repository, and now you have an collision available.

That's not how git uses hashes. In that scenario, there would still be a diff and hence git would recognize the files were different.

Re: Linus' reply on Git and SHA-1 collision

#239

Post by xkxx »

hulahoof wrote: post #93
xkxx wrote: post #80

Earlier quoted context omitted.

> What's shocking is how badly people understand the purpose of an analogy. The purpose of an analogy is to simplify something that's too hard to understand for the person you try to convey your idea to. Sometimes analogies are appropriate, e.g. when you teach something. When you want to convince somebody whose opinion is very different from yours, analogies aren't appropriate. They sound condescending: "because you…

Sometimes facts and logic can be extremely verbose - I feel many analogies are in place not to be condescending, but because the author has faith in the reader that they can make the connection between the analogy and the problem. And to be quite honest abstracting ideas is core to problem solving, and I think it's a bit disingenuous to say that anyone misunderstood what Linus was getting at there.

> abstracting ideas is core to problem solving

Sure. But don't confuse abstractions with analogies.

Here is a good proof about both the integers and rational numbers. Every integer and rational is a real number (abstraction). When you add any 2 real numbers, you get the same result regardless of their order (fact). So it must be true that, when you add any 2 integers, you get the same result regardless of their order (correct conclusion #1). It also must be true that, when you add any 2 rationals, you get the same result too (correct conclusion #2).

Here is a bad proof about the integers and rational numbers. Both the integers and rationals are very similar: you can add them, subtract them and so on (analogy). Between every 2 rational numbers there is another rational number (fact). So it must be true that between every 2 integers there is another integer (wrong conclusion).

Re: Linus' reply on Git and SHA-1 collision

#240

Post by squeaky-clean »

zkms wrote: post #21
paulddraper wrote: post #16

Linus has toned down a lot from a decade ago. > You are _literally_ arguing for the equivalent of "what if a meteorite hit my plane while it was in flight - maybe I should add three inches of high-tension armored steel around the plane, so that my passengers would be protected". > That's not engineering. That's five-year-olds discussing building their imaginary forts ("I want gun-turrets and a mechanical horse one mi…

> "what if a meteorite hit my plane while it was in flight - maybe I should add three inches of high-tension armored steel around the plane, so that my passengers would be protected" I think this is a shockingly good example of how smart people get security questions utterly wrong. The right analogy when it comes to security has to involve some type of adversary, not just random, unmotivated natural phenomena -- as l…

This was also in response to the original sender's claim that plain ol' non-malicious bad luck could cause sha1 collisions in git commits.

So this is a shockingly good example of how quotes taken out of context are pretty useless in a discussion.

Post reply on HN