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

A new hash algorithm for Git

lwn.net

Post reply on HN
Print view View original

41–50 of 240 posts

Re: A new hash algorithm for Git

#41

Post by GlitchMr »

Double_a_92 wrote: post #40
GlitchMr wrote: post #26

Earlier quoted context omitted.

I'm well aware concatenation wouldn't necessarily improve the strength. However, the idea is, even if SHA-1 was hopelessly broken. CONCAT(SHA1(x), SHA256(x)) would be at least as strong as SHA-256 (where "at least" means it may have the same strength).

If you know that it's a concatenation, couldn't you only look at the SHA1 part and completely bypass any other strong hash? On second thought probably not, because you might find any possible collision, that isn't a collition on all the other hash algorithms. If you bruteforce through a password list it would still apply though.

This doesn't work for collision resistance attacks. git commits aren't password hashes. Specifically, the attacker's goal in this case is to find different values a and b for which hash(a) = hash(b), rather than finding a value of m in h = hash(m) for known h.

Re: A new hash algorithm for Git

#42

Post by simias »

nnx wrote: post #11

Surprising they didn't go with Blake3 instead since it has much higher performance and Git's performance-oriented ethos.

Is a significant part of git's typical profile spent computing hashes? I'm genuinely asking because I don't know the answer. I'd expect all the diffing and (potentially fuzzy) merging to be significantly more expensive operations, at least as far as big-O is concerned.

Re: A new hash algorithm for Git

#43

Post by patrec »

GlitchMr wrote: post #24

I wonder if it would make sense to use `concat(sha1, sha256)` hash algorithm. This wouldn't change the prefixes while improving strength of an algorithm (by including SHA256 in a hash).

I supposed you are advocating two distinct Merkle trees? Because otherwise the prefixes will change anyway.

But the only reason this would be attractive is because then people could keep using the existing prefixes to refer to the whole commit. But of course doing this would be insecure. So for this to make any sense at all, people would need to make good choices on when to use an insecure prefix and when to use the whole hash, because it's security relevant. This seems a bit doubtful to me.

Re: A new hash algorithm for Git

#45

Post by scoutt »

HereBeBeasties wrote: post #28
anaisbetts wrote: post #9

I don't understand the practical attack vector for breaking SHA1s in Git. Not only are objects checksummed by SHA1, they also encode the length . Finding a SHA1 collision is plausible, but finding a SHA1 collision that both lets you do something Nefarious, and is the length you need, seems really really unlikely

You're assuming that 100% of the source code matters, but most source code has comments. Some has a lot of comments (boilerplate headers). Delete all the comments and superfluous whitespace, add nefarious code, put in a comment in the remaining bytes for the sole purpose of causing a hash collision (likely plenty of bytes to play with).

Yes, but...

> this new version would have to contain the desired hostile code, still function as a working floppy driver, and not look like an obfuscated C code contest entry

It's still plausible that one can pull a trick like that to introduce malicious code into the repo, but improbable.

Re: A new hash algorithm for Git

#46

Post by pwagland »

Double_a_92 wrote: post #40
GlitchMr wrote: post #26

Earlier quoted context omitted.

I'm well aware concatenation wouldn't necessarily improve the strength. However, the idea is, even if SHA-1 was hopelessly broken. CONCAT(SHA1(x), SHA256(x)) would be at least as strong as SHA-256 (where "at least" means it may have the same strength).

If you know that it's a concatenation, couldn't you only look at the SHA1 part and completely bypass any other strong hash? On second thought probably not, because you might find any possible collision, that isn't a collition on all the other hash algorithms. If you bruteforce through a password list it would still apply though.

This would help if you _only_ shared the prefix, however git would still use the full hash.

The proposed method would have the advantage of keeping existing known abbreviations, which are _already_ less secure than SHA-1, while keeping the security of the second hash.

It also has the disadvantage that the full hash would become excessively large and unwieldy, so pros and cons.

Re: A new hash algorithm for Git

#47

Post by afiori »

AndrewDucker wrote: post #17
mratsim wrote: post #6

> Thus, unlike some other source-code management systems, Git does not (conceptually, at least) record "deltas" from one revision to the next. It thus forms a sort of blockchain, with each block containing the state of the repository at a given commit. Color me surprised, dropping the "blockchain" word in the middle of the introduction

Git is a blockchain. Being, as it is, a chain of signed blocks.

It is still a sort of namedropping. In the sense that it is used due to the trendiness of the term.

It is entirely possible and likely that it is used for didactic purposes as many people are familiar with the blockchain structure and its use of hashes.

Re: A new hash algorithm for Git

#48

Post by GlitchMr »

patrec wrote: post #43
GlitchMr wrote: post #24

I wonder if it would make sense to use `concat(sha1, sha256)` hash algorithm. This wouldn't change the prefixes while improving strength of an algorithm (by including SHA256 in a hash).

I supposed you are advocating two distinct Merkle trees? Because otherwise the prefixes will change anyway. But the only reason this would be attractive is because then people could keep using the existing prefixes to refer to the whole commit. But of course doing this would be insecure. So for this to make any sense at all, people would need to make good choices on when to use an insecure prefix and when to use the…

To be fair, the prefix problem would exist no matter what hash function would you pick. GitHub displays 7 characters of a hash, giving 28 bits. You could very quickly generate collisions with birthday attack in pretty much no time. Prefixes are always going to be insecure because they are so short.

In fact, https://github.com/bradfitz/gitbrute exists.

Re: A new hash algorithm for Git

#49

Post by afiori »

the8472 wrote: post #44
tonyedgecombe wrote: post #19

Earlier quoted context omitted.

Git is a Merkle tree as is a blockchain. https://en.wikipedia.org/wiki/Merkle_tree

It is more a DAG than a tree.

And talking about hash attacks it becomes relevant to consider the possibility of it being just a Directed Graph

Re: A new hash algorithm for Git

#50

Post by simias »

Double_a_92 wrote: post #40
GlitchMr wrote: post #26

Earlier quoted context omitted.

I'm well aware concatenation wouldn't necessarily improve the strength. However, the idea is, even if SHA-1 was hopelessly broken. CONCAT(SHA1(x), SHA256(x)) would be at least as strong as SHA-256 (where "at least" means it may have the same strength).

If you know that it's a concatenation, couldn't you only look at the SHA1 part and completely bypass any other strong hash? On second thought probably not, because you might find any possible collision, that isn't a collition on all the other hash algorithms. If you bruteforce through a password list it would still apply though.

Things like signed commits would still use the full hash, so that would make tampering with that impossible.

This solution would basically just make the UI backward-compatible while still requiring the complete modification of the internal to change the hash function.

You'd still risk a collision if you refer to commits using a shortened hash outside of git but something tells me that you don't even need a vulnerability to take advantage of that if you have an attack vector. For instance github seems to use 7 hex digit in short hashes, this could probably be bruteforced relatively easily (be it for SHA-1 or SHA-256). To give you an idea I looked at the current bitcoin difficulty (which AFAIK uses two rounds of SHA-256 internally and works by bruteforcing hashes with a certain number of leaning zeroes) and the hashes look like this: 000000000000000000028048b31e42bd53d3b36da90d1a840ae695ec1a5ee738

Post reply on HN