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

161–170 of 240 posts

Re: A new hash algorithm for Git

#161

Post by SQLite »

seniorsassycat wrote: post #143
velcrovan wrote: post #131

Earlier quoted context omitted.

Fossil's main author is chiming in the discussion of this on Fossil's forums: ( https://fossil-scm.org/forum/forumpost/50a5bea5fb ) > That's appalling. Fossil's implementation doesn't require a conversion. “This is a key point, that I want to highlight. I'm sorry that it wasn't made more clear in the LWN posting nor in the HN discussion. “With Fossil, to begin using the new SHA3 hash algorithm, you just upgrade your…

The way I read the fossil's authors comments, old commits continue to use sha1 hashes. A repository will be vulnerable to sha1 collision attacks as long as there is an object in the repository that has not been hashed with the new algorithm. For example, floppy.c could be replaced in a repo with file with the same sha1 hash as long as the last commit that modifies floppy.c used a sha1 hash. Right?

Just to be clear: Every time you modify a file, the new changes get put in using SHA3. In an older repository, any given commit might have some files identified using SHA1 (assuming they have not changed in 3 years) and others identified using SHA3.

For example, the manifest of the latest SQLite check-in is see at (https://www.sqlite.org/src/artifact/29a969d6b1709b80). You can see that most of the files have longer SHA3 hashes, but some of the files that have not been touched in three years still carry SHA1 hashes.

An attack like what you describe is possible if you could generate an evil.c file that has the exact same SHA1 hash as the older floppy.c file. Then you could substitute the evil.c artifact in place of the floppy.c artifact, get some unsuspecting victim to clone your modified repository, and cause mischief that way. Note, however, that this is a pre-image attack, which is rather more difficult to pull off than the collision attacks against SHA1, and (to my knowledge) has never been publicly demonstrated. Furthermore, the evil.c file with the same SHA1 hash would need to be valid C code that does something evil while still yielding the same hash (good luck with that!) and Fossil (like Git) has also switched over to Hardened SHA1, making the attack even harder still.

As still more defense, Fossil also maintains a MD5 hash against the entire content of the commit. So, in addition to finding evil.c that compiles, does your evil bidding, has the same hardened-SHA1 hash as floppy.c, you also have to make sure that the entire commit has the same MD5 hash after substituting the text of evil.c in place of floppy.c.

So, no, it is not really practical to hack a Fossil repository as you describe.

Re: A new hash algorithm for Git

#162

Post by kazinator »

scarejunba wrote: post #130
kazinator wrote: post #114

> There is, of course, a way to unambiguously give a hash value in the new Git code, and they can even be mixed on the command line; this example comes from the transition document: git --output-format=sha1 log abac87a^{sha1}..f787cac^{sha256} > For a Git user interface this is relatively straightforward and concise No, it isn't. It's a complete and utter user interface clusterfuck. Just say no to this insanity.

Perhaps suggest an alternative? It may help understand why this was chosen.

One attractive alternative is not to do a thing.

Don't cave in to sky-is-falling bullshit regarding the existing SHA1.

Git is not a crypto system; it's just version control.

We've used version control systems just fine that had no integrity features at all. For isntance you can go into a RCS ,v file and diddle anything you want. Some BSD people are still on CVS, and their world hasn't fallen apart.

Re: A new hash algorithm for Git

#163

Post by wyoung2 »

kazinator wrote: post #125
microtherion wrote: post #123

Earlier quoted context omitted.

Note the qualifier "for a Git user interface". The average git command is along the lines of "git ph-nglui --mglw=nafh Cthulhu...R'lyeh -- wgah^nagl fhtagn"

That cute rhetoric will not fool anyone. Common git workflows use fairly succinct git commands: git diff git commit -p git rebase -i HEAD~3 The command quoted in my original comment is just this we strip away the SHA256 garbage: git log abac87a..f787cac (Or maybe it is: git log abac87a^..f787cac^ I cannot guess whether the ^ operator still has the same meaning or whether it is part of this ^{sha...} notation.) The ha…

> That cute rhetoric will not fool anyone.

Well, let's see, the Fossil equivalents are:

1. Do nothing at all for a conversion from the SHA-1 to SHA-3 — yes, 3, not 2 as in Git! — because it's automatic for months now and dead easy going back 3 years now. (https://www.fossil-scm.org/fossil/doc/trunk/www/hashpolicy.w...)

2. "fossil diff"

3. "fossil ci"

4. Why are you rebasing in the first place, again? https://www.fossil-scm.org/fossil/doc/trunk/www/rebaseharm.m...

Re: A new hash algorithm for Git

#164

Post by wyoung2 »

SQLite wrote: post #161
seniorsassycat wrote: post #143

Earlier quoted context omitted.

The way I read the fossil's authors comments, old commits continue to use sha1 hashes. A repository will be vulnerable to sha1 collision attacks as long as there is an object in the repository that has not been hashed with the new algorithm. For example, floppy.c could be replaced in a repo with file with the same sha1 hash as long as the last commit that modifies floppy.c used a sha1 hash. Right?

Just to be clear: Every time you modify a file, the new changes get put in using SHA3. In an older repository, any given commit might have some files identified using SHA1 (assuming they have not changed in 3 years) and others identified using SHA3. For example, the manifest of the latest SQLite check-in is see at ( https://www.sqlite.org/src/artifact/29a969d6b1709b80 ). You can see that most of the files have longer…

> Furthermore, the evil.c file with the same SHA1 hash would need to be valid C code that does something evil while still yielding the same hash

...and also produce an innocent-looking diff!

I mean, you could stuff a bunch of random bytes into a C comment to force the desired hash in the output using these documented attack techniques, but anyone inspecting the diffs between versions is likely to see such an explosion of noise and call foul.

If you want an analogy, it's like someone saying they've learned to impersonate federal agent identification cards, only it requires that the person carrying the fake ID to have a thousand rainbow-dyed ducks on a leash in tow behind him.

Such attacks are fine when it's dumb software systems doing the checks, but for a source code repository where people do in fact visually check the diffs occasionally?

Well, let's just say that when someone manages to use SHAttered and/or SHAmbles type attacks on Git (or even Fossil) I expect that it won't take a genius detective to see that the repo's been attacked.

Re: A new hash algorithm for Git

#165

Post by wyoung2 »

seniorsassycat wrote: post #143
velcrovan wrote: post #131

Earlier quoted context omitted.

Fossil's main author is chiming in the discussion of this on Fossil's forums: ( https://fossil-scm.org/forum/forumpost/50a5bea5fb ) > That's appalling. Fossil's implementation doesn't require a conversion. “This is a key point, that I want to highlight. I'm sorry that it wasn't made more clear in the LWN posting nor in the HN discussion. “With Fossil, to begin using the new SHA3 hash algorithm, you just upgrade your…

The way I read the fossil's authors comments, old commits continue to use sha1 hashes. A repository will be vulnerable to sha1 collision attacks as long as there is an object in the repository that has not been hashed with the new algorithm. For example, floppy.c could be replaced in a repo with file with the same sha1 hash as long as the last commit that modifies floppy.c used a sha1 hash. Right?

In addition to D. Richard Hipp's thoughts as HN user SQLite — author also of Fossil, so he oughtta know — I offer these:

1. Keep in mind that Fossil and Git are both applications of blockchain technology, which in this particular practical case means you must not only forge a single artifact's hash, you must also do it in a way that allows it to fit into the overall blockchain.

2. Fossil's sync protocol purposefully won't apply Dr. Hipp's hypothetical evil.c to an existing Fossil blockchain if presented it. Fossil will say, "I've already got that one, thanks," and move on. Only new or outdated clones could be so-fooled.

Re: A new hash algorithm for Git

#166

Post by hinkley »

kazinator wrote: post #114

> There is, of course, a way to unambiguously give a hash value in the new Git code, and they can even be mixed on the command line; this example comes from the transition document: git --output-format=sha1 log abac87a^{sha1}..f787cac^{sha256} > For a Git user interface this is relatively straightforward and concise No, it isn't. It's a complete and utter user interface clusterfuck. Just say no to this insanity.

When people started using the phrase "Stockholm Syndrome" with respect to git I took it as a sort of hyperbole. A rhetorical device.

But the more 'improvements' they make to it the more literal that accusation becomes in my head. And what's worse is that I've grown enough callouses now that my response is an eyeroll instead of pain. I use git all the time, but it's terrible and I need something that is better, not just sucks less. And apparently soon, because I don't know when that koolaid is going to start looking good but it's not long now.

Send help.

Re: A new hash algorithm for Git

#167

Post by loeg »

jolmg wrote: post #158
loeg wrote: post #156

Earlier quoted context omitted.

You're talking about a 160 bit truncated hash collision on SHA256, which is extraordinarily unlikely if SHA256 is not itself completely broken (moreso than SHA1 already is!). I don't think any syntax is needed for that in the porcelain CLI; it could be handled with non-user-facing commands if it ever came up (it won't).

> extraordinarily unlikely if SHA256 is not itself completely broken (moreso than SHA1 already is I was hoping I captured that by saying "very rarely". However, if SHA1 collisions can be made willingly, doesn't that mean that one can also willingly make a SHA1 hash that matches with the prefix of an existing SHA256 hash?

As far as I know, that kind of collision isn't practical at this time. So predicating UI decisions on that basis seems like a mistake to me (given how long git has already ignored the looming threat of SHA1 being broken).

When and if someone injects a SHA1 attack into your repository, and the main git CLI throws up its hands and says "hash collision" trying to access it, I'm not seeing major problems here. The git CLI doesn't need to provide convenient commands to interact with attacks that are not practical today. To the extent that these will become practical, I think git should drop the SHA1 lookup after a migration period regardless, and it would not hurt to provide a gitconfig knob to disable SHA1 lookup.

Re: A new hash algorithm for Git

#168

Post by [deleted] »

kazinator wrote: post #125
microtherion wrote: post #123

Earlier quoted context omitted.

Note the qualifier "for a Git user interface". The average git command is along the lines of "git ph-nglui --mglw=nafh Cthulhu...R'lyeh -- wgah^nagl fhtagn"

That cute rhetoric will not fool anyone. Common git workflows use fairly succinct git commands: git diff git commit -p git rebase -i HEAD~3 The command quoted in my original comment is just this we strip away the SHA256 garbage: git log abac87a..f787cac (Or maybe it is: git log abac87a^..f787cac^ I cannot guess whether the ^ operator still has the same meaning or whether it is part of this ^{sha...} notation.) The ha…

[deleted]

Re: A new hash algorithm for Git

#169

Post by hinkley »

allover wrote: post #147
kazinator wrote: post #125

Earlier quoted context omitted.

That cute rhetoric will not fool anyone. Common git workflows use fairly succinct git commands: git diff git commit -p git rebase -i HEAD~3 The command quoted in my original comment is just this we strip away the SHA256 garbage: git log abac87a..f787cac (Or maybe it is: git log abac87a^..f787cac^ I cannot guess whether the ^ operator still has the same meaning or whether it is part of this ^{sha...} notation.) The ha…

You are now ignoring the fact that in the initial quote you objected to was the intentionally tongue-in-cheek: > 'For a Git user interface this is relatively straightforward and concise'. It kinda looks like you missed the joke and are now doubling-down on your disagreement. The author does not think the proposed example is reasonable. You're in agreement.

And the responder makes a pretty unsubtle allusion to Lovecraft.

Anyone who compares the git CLI to being driven insane by Elder Gods is not defending the git CLI.

Re: A new hash algorithm for Git

#170

Post by wyoung2 »

SAI_Peregrinus wrote: post #80
tialaramex wrote: post #61

Earlier quoted context omitted.

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

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 weakness. SHA-3 is also much newer, with a much shorter list of known attacks.

Post reply on HN