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

Linus on Git and SHA-1

plus.google.com

Post reply on HN
Print view View original

101–110 of 187 posts

Re: Linus on Git and SHA-1

#101

Post by simplehuman »

aseipp wrote: post #79
simplehuman wrote: post #72

Earlier quoted context omitted.

So did anyone on this thread send patched to the mailing list? Obviously you guys are very serious right?

This conversation has gone on several times over the course of years on the Git mailing list. In almost every situation it's been completely brushed off as a mostly non-issue to change from SHA-1 inside Git, despite the fact it's been known SHA-1 has basically been on life support. There are lots of opinions on both sides, but ultimately, until now, the Upstream decision seemed to be "WONTFIX". Given this context, of…

> This is all aside from your argument being fundamentally weak, however ("you can't criticize anything unless i say so and contributed by meeting this arbitrary standards. i mean, didn't do anything either, i just get to make up the rules you abide by!!")

Are we both reading the same GP comment? It reads as "If he took this stuff seriously, he wouldn't have waited 12 years since SHA-1 was broken to even start considering any changes.".

Re: Linus on Git and SHA-1

#102

Post by [deleted] »

azernik wrote: post #97
maxander wrote: post #96

I don't really get the threat model here. If an attacker is pushing commits into your repository, you're long since toast on all possible security fronts, right? Is there anything nefarious they could accomplish through hash collisions that couldn't be done simply by editing commit history?

If they edit the commit history and you're using a secure hash algorithm, then the hash of the current commit will change and no longer match the signed tag your trusted maintainer sent you.

[deleted]

Re: Linus on Git and SHA-1

#103

Post by AgentME »

simplehuman wrote: post #72
AgentME wrote: post #57

Earlier quoted context omitted.

If he took this stuff seriously, he wouldn't have waited 12 years since SHA-1 was broken to even start considering any changes.

So did anyone on this thread send patched to the mailing list? Obviously you guys are very serious right?

Linus ranted[0] about how it's idiotic to worry about SHA-1 collisions in 2005 months after significant weaknesses[1] were found in it (which have recently been demonstrated by Google). I'm certainly not about to waste effort making a patch that he's going to reject as idiotic.

[0] http://www.gelato.unsw.edu.au/archives/git/0504/0885.html

[1] https://www.schneier.com/blog/archives/2005/02/sha1_broken.h...

Re: Linus on Git and SHA-1

#104

Post by bascule »

pvg wrote: post #99
bascule wrote: post #90

Earlier quoted context omitted.

"maybe the 1 in a million collision chance for a few million hashes is too high" Well, let's look at what the actual numbers are. There's a nice table on this page: https://en.wikipedia.org/wiki/Birthday_attack For a 64-bit tag, even with 6,100,000 objects we'd only have a 1 in 10 million chance of a collision, so a 64-bit tag is more than sufficient to meet your stated requirements.

No no, I don't have any requirements, I just did the numbers and missed a zero instead of sensibly looking at a table. But that doesn't change the argument much - if one in a million isn't crazy, one in ten million is not completely insane either. With a 64 bit hash, you probably should write code to deal with a potential collision. Beside the (tiny) chance, someone might legitimately plop some test vectors that coll…

If you feel CRC64 does not meet the requirements, use CRC128.

For what it's worth, I think CRC64 should be fine for git-like workloads (but would still recommend using a cryptographically secure hash function, because git's usage is security-critical despite Linus constantly insisting it's not).

Re: Linus on Git and SHA-1

#105

Post by joatmon-snoo »

snakeanus wrote: post #64
AsyncAwait wrote: post #20

Earlier quoted context omitted.

It's not that simple. Git is a widely used software integrated into many places, so keeping some backwards compatibility is important. Just going ahead and start breaking things would really be unprofessional.

They did break backwards compatibility with git v2.0 but sadly they did not bother to change the hash function.

What backwards compatibility was broken?

Re: Linus on Git and SHA-1

#107

Post by pvg »

bascule wrote: post #104
pvg wrote: post #99

Earlier quoted context omitted.

No no, I don't have any requirements, I just did the numbers and missed a zero instead of sensibly looking at a table. But that doesn't change the argument much - if one in a million isn't crazy, one in ten million is not completely insane either. With a 64 bit hash, you probably should write code to deal with a potential collision. Beside the (tiny) chance, someone might legitimately plop some test vectors that coll…

If you feel CRC64 does not meet the requirements, use CRC128. For what it's worth, I think CRC64 should be fine for git-like workloads (but would still recommend using a cryptographically secure hash function, because git's usage is security-critical despite Linus constantly insisting it's not).

Why would you do that? Even if you don't know exactly what you want, are wrong about whether it's the basis of 'trust', for the purposes of writing git, you'd just take SHA-1. Nothing terrible is going to happen if it's both overkill and you aren't really building a secure system. You seem to be arguing, if I'm understanding you right, that you should only use a cryptographically strong hash iff you need all its properties. That seems like a really odd angle.

Re: Linus on Git and SHA-1

#108

Post by snowwrestler »

bascule wrote: post #63
infinity0 wrote: post #58

Earlier quoted context omitted.

> "A hash that is used for security is basically a statement of trust [..] In contrast, in a project like git, the hash isn't used for "trust". I don't pull on peoples trees because they have a hash of a4d442663580. Our trust is in people, and then we end up having lots of technology measures in place to secure the actual data." This is horseshit, and Linus should not be saying these hugely misleading statements abou…

Yes, exactly. If Linus truly doesn't care about security, then git could use any error correcting code that produces a uniform distribution of tags, such as CRC64. The size of the tag only affects the number of objects we'd expect to be able to commit before we see a collision: over 4 billion in the case of CRC64. Linux mistakenly claims using a cryptographic hash function helps avoid non-malicious collisions, but th…

Linus: "You can have people who try to be malicious... they won't succeed."

Linus talked about why git's use of a "strong hash" made it better than other source control options during his talk at Google in 2007.

https://youtu.be/4XpnKHJAok8

Edit: the whole talk is good but the discussion of using hashes starts at about 55 min.

Re: Linus on Git and SHA-1

#109

Post by recursive »

grzm wrote: post #65
colin_fraizer wrote: post #60

Earlier quoted context omitted.

A generally reasonable guideline, but in this case, I am actually criticizing the tribalism that makes people rise to that bait. It similarly leads to the discussion of how "I can't believe Linus is trying to defend SHA-1 when The Tribe already knows it is cryptographically 'bad'."

If you are taking the view that you're expecting downvotes to prove the point that people who are trying to uphold community standards are doing so blindly or ignorantly, you'll very likely think you're proven correct when you do receive downvotes. Can you blame them? You're explicitly flaunting the guidelines they choose to abide by while telling them they're wrong to do so in your special case .

ahem... "flouting"

Re: Linus on Git and SHA-1

#110

Post by hueving »

x1798DE wrote: post #80
hueving wrote: post #33

Earlier quoted context omitted.

No, you're correct that for large inputs there are obviously going to be many that lead to the same hash (see pigeonhole principle).

This is presumably true also of small inputs, given that the large and small inputs are all mapping to the same space.

Well not necessarily true for small inputs. Hash a single byte for example. There is no collision in sha1 for that so you can build a 1:1 mapping of hashes back to input examples for that case.

But yeah, as the input size approaches the output size, the probability of a collision existing gets to 1. The birthday paradox formula will give the probability of a collision (assumes random placement in output space) based on number of inputs.

Post reply on HN