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

211–220 of 240 posts

Re: A new hash algorithm for Git

#211

Post by mb7733 »

SQLite wrote: post #188
seniorsassycat wrote: post #181

Earlier quoted context omitted.

Isn't this the same attack given as an example why git is migrating hash functions in the subject article? The attack may be difficult and unlikely I'm not questioning that, but if I understand correctly then Fossil's migration is straightforward because they did not address the same issues Git chose to.

> if I understand correctly then Fossil's migration is straightforward because they did not address the same issues Git chose to. I think more is at play here. (1) You can set Fossil to ignore all SHA1 artifacts using the "shun-sha1" hash policy. (2) The excess complication in the Git migration strategy is likely due to the inability of the underlying Git file formats to handle two different hash algorithms in the sa…

(2) The excess complication in the Git migration strategy is likely due to the inability of the underlying Git file formats to handle two different hash algorithms in the same repository at the same time.

But, I could be wrong. Post a rebuttal if you have evidence to the contrary.

It seems unfair to demand a rebuttal when you are the one who made the claim.

According to the article at least, the difficulty stems mainly from their migration strategy, for converting all existing SHA1 hashes.

Re: A new hash algorithm for Git

#212

Post by strenholme »

tialaramex wrote: post #69
hannob wrote: post #65

Earlier quoted context omitted.

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

The length extension attack is a non-issue for Git’s use case, and SHA-256 (unlike SHA-512) benefits from having hardware acceleration in the new Ice Lake Intel chips (as well as on the AMD side of things), and has been around 11 years longer than SHA-512/256. And, yes, there are places which say “If you will use a hash, you will use SHA-256”.

Personally, the last time I was in a place where I had to choose which cryptography to use, I used SHA3’s direct predecessor, RadioGatún, because I needed a combined hash + stream cipher and, at the time (late 2007), RadioGatún was the only option.

RadioGatún also benefits from being about as fast as BLAKE2 (it would be faster in hardware, FWIW, having SHA3’s hardware advantages), and is approaching 14 years old without being broken by cryptoanalysis. Also, unlike BLAKE2/3, and like SHA3 and all sponge functions, it’s computationally expensive to “fast forward” in RadioGatún’s XOF (stream cipher, if you will) mode, which is beneficial for things like password hashing. Another nice thing about RadioGatún: It doesn’t have any magic constants in its specification, allowing a useful implementation to fit on my coffee mug, e.g.

  #include//RadioGatun
  #include/*32-bit**/
  #define b(z) for(c=0;c>j%32|k>8*c)&255);c=j;if(c%2)m
  ();}return 0&puts("");}}}}}//
If someone asked me which hash algorithm to use, I would suggest SHA-256, unless I think they needed protection from length extension attacks (so SHA-512/256), or needed an XOF (stream cipher-like) construction (so SHAKE256).

If performance mattered more than a conservative security margin, BLAKE3 (software performance) or KangarooTwelve (SHA3 variant; excellent hardware performance) would be good choices. If I were to do choose a hash + XOF for use today, I would use KangarooTwelve’s variant with a little larger security margin: MarsupilamiFourteen.

Re: A new hash algorithm for Git

#213

Post by nsajko »

Disappointed they went with an ARX based hash, instead of KangarooTwelve, which uses the Keccak permutation. A lot of people on this thread think that SHA2 is more secure because it is older, but it is my understanding that that is completely wrong. Keccak is not only standardized, to get to that it had to win the SHA3 competition, during and after which it received, as far as I understand, unprecedented levels of scrutiny. And not only that, but, according to what I read, the Keccak-like cryptographic constructions (including the hash) are much more amenable to mathematical/cryptographical analysis because of not using addition (word-wise, instead of bit-wise, to be more correct). The idea is that a resourceful/moneyed attacker (like the NSA or China, etc.) could create successful attacks on an ARX hash without the public being able to come to the same developments because of no researchers having access to similar levels of resources.

The sad thing is that the ARX BLAKEx functions seem to be gaining undeserved amounts of hype. I do not think they are getting comparable scrutiny from researchers, seeing as BLAKEx hashes are ARX, and also changed considerably since the SHA3 contest (so it is far from clear that the scrutiny that BLAKE did receive translates to BLAKE2 or BLAKE3).

Re: A new hash algorithm for Git

#214

Post by remram »

wyoung2 wrote: post #204
remram wrote: post #199

Earlier quoted context omitted.

The problem is that we are considering an issue where different people can get different objects for the same hash. If the people checking all see the valid files, they cannot raise any alarms to save the poor victims who got poisoned with the wrong objects. They'll clone from the wrong fork, and no amount of checking hashes or signed tags will prevent them from running compromised code.

> If the people checking all see the valid files ...which will likely contain thousands of bytes of pseudorandom data in order to force the hash collision... > they cannot raise any alarms You think a human won't be able to notice that the diff from the last version they tested looks awfully funny? Code that can fool the compiler into producing an evil binary is one thing, but code that can pass a human code review i…

If this is your threat model, you don't need hashes or signed tags at all. Good for you. Thankfully both Fossil and Git disagree with you and take the threat seriously :)

Re: A new hash algorithm for Git

#215

Post by themaxdavitt »

zokier wrote: post #136

Does anyone know if a standard format for sort of tagged-union hash type, something similar as crypt format for passwords? Feels like everyone is needing to support multiple hash types at some point, and basically needs to reinvent that particular wheel again and again.

Multihash? https://multiformats.io/multihash/

Re: A new hash algorithm for Git

#216

Post by tangent128 »

wyoung2 wrote: post #196
kazinator wrote: post #186

Earlier quoted context omitted.

The diatribe against rebasing is stupid. In fact, not having more than one parent is a good thing because you with multiple parents, you don't know what is relevant. The history has turned into a hairball. When you try to navigate back in time, you face forking roads at every step and it turns into a maze walk. The point is valid that when we rebase, we are losing history: the context of where that change was origina…

> history does not matter if the change was parented in some temporary context It does if it means a big ball o' hackage lands on the public working branch, since it complicates merges, backouts, cherrypicks, and bisects. Git users can also hide individual commit messages behind one big combined message, losing part of the project's development history and logical progression. When I pull your repo and build it, and…

Squashing changes isn't the only use of rebasing.

It's reasonably common for me to start exploring a problem space, stub out a concept, and have a long drawn-out conversation with the compiler that touches many files, before finally reaching a point that is working enough to be interesting.

At that point, I can take a step back and note that actually, not all of those changes have to be made all at once, and I can break that patch up into a bunch of simpler pieces.

In Git, I have two essentially-equivalent choices:

1. stage the commit in small chunks, adding a separate descriptive comment for each.

2. commit everything as a WIP commit so this working state is in the reflog, then break it up into smaller commits with interactive rebase.

In either process, I'm able to get a better comprehension of my own thoughts along the way.

Fossil, refusing both staging would force me to commit the proverbial 500-line blob all at once, which is less helpful to the reviewer trying to discern my thought process.

If rebasing isn't important to your workflow, Fossil probably is a better choice for you than Git. It has a lot of comforts that I really appreciated even eight years ago when I did frequently use Fossil (distributed wiki and tickets are really nice, the web interface serving raw artifacts from any point in time is great for HTML5 game jams, SQLite is a very portable repository format, etc. etc. etc.), and I'm sure it's only improved in that regard. The only reason I use Git for personal projects is because rebase is that helpful to my process.

Re: A new hash algorithm for Git

#217

Post by tialaramex »

wyoung2 wrote: post #170
SAI_Peregrinus wrote: post #80

Earlier quoted context omitted.

1.5 Chosen-prefix collision: Given a prefix A, generate two values AB and AC, where B and C differ but are both prefixed with A. (AX is A concatenated with X). This exists for SHA1. It's more powerful than a basic collision wheri you can't pick the prefix, but weaker than either type of pre-image.

It's worth noting that this attack is a property of the Merkle–Damgård hash construction, not of SHA-1 specifically, which means SHA-2 (Git's path forward) is also vulnerable: https://en.wikipedia.org/wiki/Merkle%E2%80%93Damg%C3%A5rd_co... https://www.reddit.com/r/crypto/comments/44p5jc/eli5_why_are... Fossil uses SHA-3, which has an entirely different construction, which is not at this time known to have a similar w…

Ha that ELI5 is adorable, I love both how the person trying to answer in the affirmative resorts to more and more frantic hand-waving as it becomes obvious none of what they've said is true and most of it doesn't even make sense, while the person being "flagged" for their supposedly "highly inaccurate" simple statement that er, no, chosen prefix isn't about MD at all remains calm and doesn't care as people insist they must be wrong because after all they were flagged, and why would some anonymous user flag something as wrong unless they were an expert...

Anyway, as hinted above, chosen prefix has nothing to do with the type of hash construction, except in the sense that so far there were lots of Merkle–Damgård hashes and some of them are no longer safe, whereas until recently there weren't many of the Keccak family hashes.

The Wikipedia article is talking about Length Extension, which is a different phenomenon from chosen prefix collision attacks, and if it was a problem in Git (or indeed Fossil) would have doomed them both immediately anyway.

For a generic crypto hash you should use SHA-512/256 (NB this is not offering a choice that slash is part of the name) to avert Length Extension but since the DVCSs already seemingly put the effort in to be safe against it SHA-256 is a perfectly reasonable choice.

Re: A new hash algorithm for Git

#218

Post by cestith »

I just want to add something the article couldn't cover. I know bmc and he's both a software geek's software geek and one of the friendliest, most helpful, and most genuine people I've ever met.

Re: A new hash algorithm for Git

#219

Post by tialaramex »

strenholme wrote: post #212
tialaramex wrote: post #69

Earlier quoted context omitted.

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

The length extension attack is a non-issue for Git’s use case, and SHA-256 (unlike SHA-512) benefits from having hardware acceleration in the new Ice Lake Intel chips (as well as on the AMD side of things), and has been around 11 years longer than SHA-512/256. And, yes, there are places which say “If you will use a hash, you will use SHA-256”. Personally, the last time I was in a place where I had to choose which cry…

Genuinely intrigued what you used RadioGatún for? I actually only read about it today because of reading around Keccak.

Re: A new hash algorithm for Git

#220

Post by kazinator »

wyoung2 wrote: post #203
kazinator wrote: post #197

Earlier quoted context omitted.

Regarding (1), not "everything will work as before". What happens if a Fossil repo that has had SHA3 commits written to it is accessed by old Fossil software before that change was introduced?

If you try to use Fossil 1.37 — the last 1.x release — to clone a repo that has SHA-3 hashed artifacts in it, it says, "server returned an error - clone aborted". Since 1.37 pre-dates this feature, it can't give a more detailed diagnosis than that. If you have an old clone made from before the transition and try to update it, I'm not sure what it says, since I don't have any of those around any more. It has, after al…

> Git's going to have to go through a transition like this, too.

The moment I can't read new repos with an installation of git 1.6 or 1.7, I'm ditching the garbage and finding something else.

Forward and backward compatibility, forever, please!

Post reply on HN