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

61–70 of 240 posts

Re: A new hash algorithm for Git

#61

Post by tialaramex »

jakeogh wrote: post #2

Is there an archive of crypto related future predictions? How long until a specified length preimage attack can break bittorrent blocks? I remember a paper published a ~decade ago estimating very short (well funded) ASIC sha1 collisons. Anyone have that ref? EDIT: Should I have not said preimage? My understanding is bittorrent is broken (by DDoS, not infohash(?)) if you can make a bad block that matches the length an…

> EDIT: Should I have not said preimage? My understanding is bittorrent is broken (by DDoS, not infohash(?)) if you can make a bad block that matches the length and sha1 of a target block.

There are three different attacks

1. Collision, which is practical (expensive but practical) for SHA-1 today, lets somebody make two documents A and B which have the same hash. This is only useful if you can fool people somehow into accepting document B when they think it's document A because of the hash, for example with digital signatures.

2. Pre-image, which is not practical for any hashes you care about including MD5. This lets you find the document A given the hash(A) value. This is very niche, since obviously for large documents by the pigeon hole principle there will be many such pre-images and it's impossible to get the "right" one, for small inputs it can be relevant, sometimes.

3. Second Pre-image, likewise not practical. Given either document A or hash(A) which you could easily determine from document A, this lets you produce a new document A' that is different from A but hash(A') == hash(A). This would be extremely bad, and is what you'd need to attack real world Bittorrent from somebody else.

Often people say "pre-image" meaning strictly second pre-image, it's usually clear from context, and a true pre-image attack as I explained above is only rarely relevant.

Collision would only let bad guys corrupt their own purposefully constructed collision bittorrent, which like, why? So yes, Bittorrent would only really be in serious trouble if there was a second pre-image attack. But on the other hand, don't use broken cryptographic primitives. Attacks only get better, always.

Re: A new hash algorithm for Git

#63

Post by majewsky »

nullc wrote: post #30
nnx wrote: post #11

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

> Git's performance-oriented ethos Than sha256 will likely be preferable in the long run: It's faster with SHA-NI than blake3. If you're not developing on a system with sha-ni, get with the program. Zen2 is freeking awesome. :)

Great! I can't wait to have to throw away perfectly fine systems because of a new Git version. /s

Re: A new hash algorithm for Git

#64

Post by londons_explore »

velox_io wrote: post #60

Unless I'm missing something, why not just allow repositories to be upgraded to SHA2 hashes? The only problem is ensuring everyone's tooling supports it.

I don't think it's that unreasonable to release git binaries today with sha256 support, then wait 5 years, then make all new commits use sha256.

Anyone who tries to use a git client more than 5 years old wouldn't be able to pull+push to a new repo. Sounds reasonable to me. Git clients more than a few years old are pretty broken already due to TLS changes.

Keeping around a dual hash system forever sounds like baggage and complexity that outweighs the benefits.

Re: A new hash algorithm for Git

#65

Post by hannob »

simias wrote: post #42
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.

> Is a significant part of git's typical profile spent computing hashes?

No. Hashes are really cheap.

This annoys me a bit, because every discussion about hashing goes into endless bikeshedding which hash function to use. The simple truth is: SHA2, SHA3, Blake2/3 are all good enough from both a security and performance perspective that for almost any use case and the advantages and disadvantages are so minor that it really doesn't matter.

Re: A new hash algorithm for Git

#66

Post by phaemon »

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

As mentioned, the shattered PDFs[1] have the same length, however it's worth noting that adding the Git header breaks the matching, ie. you get different SHA sums for the files in Git because of the header.

[1] https://shattered.io/

Re: A new hash algorithm for Git

#68

Post by velox_io »

majewsky wrote: post #62
velox_io wrote: post #60

Unless I'm missing something, why not just allow repositories to be upgraded to SHA2 hashes? The only problem is ensuring everyone's tooling supports it.

This question is exactly what a major portion of the article covers.

It isn't the easiest article to read, plus they over complicate things by talking about things such as truncating SHA2 hashes.

I don't see why changing the hashing algorithm is so problematic, hence the reason why I asked the question. Converting a repository to SHA2 should be straight forward (the only issue is everyone's tooling), you could also run the repositories side-by-side. I'm genuinely interested as I think Git & Bittorrent are quite elegant solutions to complex problems.

Re: A new hash algorithm for Git

#69

Post by tialaramex »

hannob wrote: post #65
simias wrote: post #42

Earlier quoted context omitted.

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.

> Is a significant part of git's typical profile spent computing hashes? No. Hashes are really cheap. This annoys me a bit, because every discussion about hashing goes into endless bikeshedding which hash function to use. The simple truth is: SHA2, SHA3, Blake2/3 are all good enough from both a security and performance perspective that for almost any use case and the advantages and disadvantages are so minor that it…

Length extension is an unnecessary problem in MD constructions. It makes sense to get rid of the problem. So if you are building a new thing today there's some sense in not picking SHA-256 in order that you won't later hit your head on a length extension attack. SHA-512/256 (that's not a choice, it's just one hash in the SHA2 family) is a reasonable choice though, and of course if Git was vulnerable to length extension somehow they'd be in trouble years ago so for them why not SHA-256.

Re: A new hash algorithm for Git

#70

Post by donatj »

powerapple wrote: post #67

is it a real problem for git? Do we merge code based on hashes instead of looking at the code.

The problem is in if you can make evil code with the same hash as innocuous code, you can poison people who pull from a given repo you have access to. It would allow you to make changes to the history without merging anything or anyone being the wiser.

It makes the distributed aspect of git untrustworthy, as previously you knew if you pulled from anywhere and the hash was good, you’d pulled the correct code. With SHA1 being functionally broken that’s no longer necessarily the case.

Post reply on HN