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

21–30 of 187 posts

Re: Linus on Git and SHA-1

#21

Post by chainsaw10 »

bascule wrote: post #3

Linus's transition plan seems to involve truncating SHA-256 to 160-bits. This is bad for several reasons: - Truncating to 160-bits still has a birthday bound at 80-bits. That would still require a lot more brute force than the 2^63 computations involved to find this collision, but it is much weaker than is generally considered secure - Post-quantum, this means there will only be 80-bits of preimage resistance (Also:…

> reversing commit hashes back into their contents

Somewhat off topic, but is this actually possible?

Given hashing is inherently lossy, I'm inclined to assume it's not possible for anything must longer than a password, but commits are text, which I suppose is low entropy per character, so I don't know.

Re: Linus on Git and SHA-1

#22

Post by spatulon »

debatem1 wrote: post #11

I'm mystified as to why this is even a discussion. SHA1 is busted. That impacts some git users. The fix is not invasive. Fix the bug. Make the transition. Move on. Super unprofessional.

"Unprofessional" is an odd choice of word. I cannot see what you mean.

He explains why he wrote the post: "since the SHA1 collision attack was so prominently in the news." I think a lot of people on Hacker News and elsewhere are interested in both the SHA1 collision and how it affects git, even if it doesn't impact them.

Still, even if this were some obscure bug that nobody cared about, what would be unprofessional about explaining his plan to fix it? It's an open-source project, after all.

If anything, I'd say it's quite professional that he's calmly explained why there's no need to panic, that they have everything under control, and that the path forward should be smooth.

Re: Linus on Git and SHA-1

#23

Post by bascule »

chainsaw10 wrote: post #21
bascule wrote: post #3

Linus's transition plan seems to involve truncating SHA-256 to 160-bits. This is bad for several reasons: - Truncating to 160-bits still has a birthday bound at 80-bits. That would still require a lot more brute force than the 2^63 computations involved to find this collision, but it is much weaker than is generally considered secure - Post-quantum, this means there will only be 80-bits of preimage resistance (Also:…

> reversing commit hashes back into their contents Somewhat off topic, but is this actually possible? Given hashing is inherently lossy, I'm inclined to assume it's not possible for anything must longer than a password, but commits are text, which I suppose is low entropy per character, so I don't know.

Yes this is possible. It's called a preimage attack:

https://en.wikipedia.org/wiki/Preimage_attack

It's computationally infeasible against most cryptographically secure hash functions. However, Grover's algorithm results in a sqrt(keyspace) reduction in security levels (effectively halving bit-sized security levels):

https://en.wikipedia.org/wiki/Grover's_algorithm

Re: Linus on Git and SHA-1

#24

Post by cwbrandsma »

debatem1 wrote: post #11

I'm mystified as to why this is even a discussion. SHA1 is busted. That impacts some git users. The fix is not invasive. Fix the bug. Make the transition. Move on. Super unprofessional.

What is the realistic worst case situation here? From what I understand, git uses SHA1 as a way of generating an id for a file, not for security. So two files might match up when they shouldn't? Is that it or is there more to this?

Or is this a proverbial "since SHA1 is don't work over there, then it shouldn't be used anywhere under any circumstance" attack?

Re: Linus on Git and SHA-1

#25

Post by [deleted] »

tytso wrote: post #4
bascule wrote: post #3

Linus's transition plan seems to involve truncating SHA-256 to 160-bits. This is bad for several reasons: - Truncating to 160-bits still has a birthday bound at 80-bits. That would still require a lot more brute force than the 2^63 computations involved to find this collision, but it is much weaker than is generally considered secure - Post-quantum, this means there will only be 80-bits of preimage resistance (Also:…

That's not the plan. That was an idea that was thrown out if this was an emergency (it's handling different length hashes, and doing so that we don't have to force a flag day conversion which is hard), but once people realized that in fact, the sky was not following, the plan which Linus outlined in his G+ post was devised --- which does not involve truncating a 256-bit hash.

[deleted]

Re: Linus on Git and SHA-1

#27

Post by hermitdev »

hdhzy wrote: post #14
hermitdev wrote: post #8

Earlier quoted context omitted.

Although, I generally defer to someone such as Linus in having far more domain knowledge such as this, but I'm concerned willingness to just drop bits of the hash like this. I mean 20-30 years ago, I could quasi understand for the sake of performance, but are we really so concerned about performance of a few clock cycles vs opening ourselves to a known vulnerable attack?

I think the truncation is considered because a lot of software assumes git commit id has 160 bit length. It's not because of performance.

There are only 2 reasonable rationales for the 160 bit restriction: it was arbitrary because that was the length of the chosen hash, or for performance (and no one will ever need more that 640kb of RAM, or 160 bits of hash). I'm guessing it was probably the first, though, and Linus designed for the immediate now, and not for the future.

Re: Linus on Git and SHA-1

#28

Post by [deleted] »

bascule wrote: post #3

Linus's transition plan seems to involve truncating SHA-256 to 160-bits. This is bad for several reasons: - Truncating to 160-bits still has a birthday bound at 80-bits. That would still require a lot more brute force than the 2^63 computations involved to find this collision, but it is much weaker than is generally considered secure - Post-quantum, this means there will only be 80-bits of preimage resistance (Also:…

[deleted]

Re: Linus on Git and SHA-1

#29

Post by hueving »

bascule wrote: post #3

Linus's transition plan seems to involve truncating SHA-256 to 160-bits. This is bad for several reasons: - Truncating to 160-bits still has a birthday bound at 80-bits. That would still require a lot more brute force than the 2^63 computations involved to find this collision, but it is much weaker than is generally considered secure - Post-quantum, this means there will only be 80-bits of preimage resistance (Also:…

>Preimage resistance does matter

Is there a preimage weakness though? I thought this attack only reduced collision resistance.

Re: Linus on Git and SHA-1

#30

Post by vacri »

debatem1 wrote: post #11

I'm mystified as to why this is even a discussion. SHA1 is busted. That impacts some git users. The fix is not invasive. Fix the bug. Make the transition. Move on. Super unprofessional.

Perhaps you should re-read the last paragraph of the article.
Post reply on HN