Comment by xg15 | Hacker News Reader

Comment by xg15 | Hacker News Reader

One thing I'm wondering about that I haven't seen discussed yet is the possibility to make circular git histories:

When a git commit hash is calculated, one of the data that is used are the pointers to parent commits. That results in two properties for commits:

1) A child commit's hash cannot be predicted without knowing the parent commits

2) Once a commit is created, its parent pointers are practically immutable. The only way to change them is to create a new commit with a different hash - which cannot carry over the old commit's children.

Those properties meant that it's impossible to construct a commit with a parent pointer that points to its own children. Therefore it was safe to assume that a git history is always a DAG.

I think with deliberate SHA1 collisions now possible, someone could actually violate property (2) and introduce a cycle.

As the DAG assumption is pretty fundamental, I'd imagine such a cycle could break a lot of tools. Has this ever been tested?

You can already play with this using Git's "grafts" and "replace refs" features. Most of Git's graph algorithms are OK with this because they traverse the graph while setting one or more "SEEN" bits on each node. If you find one that loops infinitely, it would be worth making a bug report.

Interesting idea. Continuing your theory, if a git utility then got locked in an infinite cycle trying to import the commit due to the recursive parent-child relationship, then such an attack might be exploitable for DOSing cloud-based git repositories.

I don't think this is possible. While there are ways to use collisions to make a document contain its own hash, they rely on format-specific tricks to insert collisions between each character of the hash. There's no way I know of to do this with a bare, unformatted MD5 or SHA-1 hash.

It sees an easy way to fix this is to scan the report for sha1 tags, and put them on the stack. Then compare the next to the list. If match is found to be duplicated, refuse to load or load in degraded state with warning bells.

A circular directory would be much worse. As soon as you check it out, your disk fills up.

but git doesn't store directory information. it is implicit with the file information.

So symlink-shenanigans shouldn't be possible using just the git objects.

Git doesn't store directory information per se, but the directory structure is still reflected in tree objects.

Reply on news.ycombinator.com