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

31–40 of 187 posts

Re: Linus on Git and SHA-1

#31

Post by hueving »

hermitdev wrote: post #8
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:…

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?

What is this known vulnerable attack you are talking about? The birthday paradox applies to every hashing function.

Re: Linus on Git and SHA-1

#32

Post by pshc »

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.

It doesn't sound possible for all but the most trivial diffs. An attacker would have to guess not only the exact commit text, but also its timestamp. And the only attack scenario I can conceive of seems pretty silly. Maybe I'm missing something...

Alice clones an open source git repo, commits one secret change where she edits a config file's default password to her own secret password (a bad practice), and then publishes the new hash in public for some reason (build info?). Mallory would have to (a) know that exactly this happened, (b) guess the commit message, (c) guess the commit's timestamp to the second (or within a few seconds), and (d) preimage-attack her password.

And the preimage attack must pierce git's Merkle tree, which sounds downright impossible. (Unless Mallory is just bruteforcing, in which case a strong password is enough.)

Re: Linus on Git and SHA-1

#33

Post by hueving »

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.

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

Re: Linus on Git and SHA-1

#34

Post by theseoafs »

Have there been writings on what exactly git's migration strategy to a new hash function will be? Apparently they have a seamless transition designed that won't require anyone to update their repositories, which seems like a pretty crazy promise in the absence of details.

Re: Linus on Git and SHA-1

#35

Post by mappu »

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:…

>(Also: if he's going to truncate a hash, he use SHA-512, which will be faster on 64-bit platforms)

BLAKE2 is faster still! It's also at least as secure as SHA-3, and produces any choice of output size up to 512bit.

Re: Linus on Git and SHA-1

#36

Post by pedrocr »

bascule wrote: post #12
tytso wrote: post #4

Earlier quoted context omitted.

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.

Can you please link me to "the plan" then? I have been trying to follow some of the ML discussion and that was the last plan I saw him put forth, e.g.: https://marc.info/?l=git&m=148787047422954

By clicking "next in thread" in that very post you get Linus replying to himself with a non-truncating plan:

https://marc.info/?l=git&m=148787163023435&w=2

Re: Linus on Git and SHA-1

#37

Post by hermitdev »

hueving wrote: post #31
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?

What is this known vulnerable attack you are talking about? The birthday paradox applies to every hashing function.

While there may not be a known, direct, attack against git, WebKit's SVN repository was demonstrably attacked by the SHA-1 vulnerability, oddly by their own developers today (or yesterday?). That it took that little time from a PoC to an actual production issue leads me to believe it wouldn't take long for a dedicated individual or team to extend the vulnerability to git and it's "mitigation" involving the header.

I prefer not to take the bury my head in the sand approach to this, at least when it comes to public repositories.

Re: Linus on Git and SHA-1

#38

Post by debatem1 »

AsyncAwait wrote: post #20
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.

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.

I'm not saying he should go out and break things now. I'm saying that the way forward he outlines could have been followed years ago, as essentially the rest of the industry did. Instead he waited until his user base was totally panicked to address their concerns.

In my view, that's not the right-- or even a rational-- way to do things.

Re: Linus on Git and SHA-1

#39

Post by runeks »

diminish wrote: post #13
ksherlock wrote: post #5

Earlier quoted context omitted.

On the mailing list he suggested displaying 160 bits for backwards compatibility with existing tools. The full 256 bits would be used internally (and displayed externally with the proper --flag)

additionally cosmetics but instead of hex string could they not use a-zA-Z0-9 in the visual output to the user to make the git command line text output shorter? 0efaa. -> 2AdC..

Then you have stuff like 1, I and l, which are difficult to distinguish. Which was why base58 was invented (basically the range you suggested, without visually similar characters).

Re: Linus on Git and SHA-1

#40

Post by kzrdude »

runeks wrote: post #39
diminish wrote: post #13

Earlier quoted context omitted.

additionally cosmetics but instead of hex string could they not use a-zA-Z0-9 in the visual output to the user to make the git command line text output shorter? 0efaa. -> 2AdC..

Then you have stuff like 1, I and l, which are difficult to distinguish. Which was why base58 was invented (basically the range you suggested, without visually similar characters).

This really should not be a problem since that's task #1 that a programmer's good font needs to solve.
Post reply on HN