Re: [PATCH] Implement fast hash-collision detection

On Thu, 2011-12-01 at 00:26 -0500, Jeff King wrote:

Yes, - the digest of digests is used to check things that would not be sent.

That's a good question, of course. After Linus pushes a commit, he'll notify others, and if some fetch before the repository is hacked, they will detect an error on a subsequent fetch. For fetches, the server reports a series of commits, and the client responds with 'have' for those it has, with the CRCs added so the server can check for a mismatch. I made minimal changes to fetch-pack.c and upload-pack.c: just adding the CRC fields to the messages already sent. The server asks about more commits than it actually transfers, but all the ones it asks about are tested. One could send additional 'have' replies if necessary (for ones the server didn't mention) but I didn't do that, partly for simplicity but also because I was looking at the fetch-pack.c and update-pack.c code for the first time. If desired, such changes can be added.

I also do some similar checking when a commit is pushed - the server tells the client the last commit it has and the client will send the CRCs in its reply to allow the server to cross check those. I didn't mention that before because only the latest is really checked. Again, I just changed a message format (backwards compatible, of course), but additional checking could be added if desired.

You could also add options to check tips of branches and all commits that have tags (e.g., a v1.0 tag) All of that simply requires more work on commands such as fetch-pack, upload-pack, send-pack and receive-pack.

That's really a server-security issue, not a git one. Perhaps repositories should be configured so that all the executables are on read-only partitions. It's an important question in general of course, but it is probably useful to distinguish attacks that put bad data on a server from ones that install new software.

Of course, but that is an expensive operation - in the case of Git transferring some 50 MBytes of data per repository. A command to fetch the SHA-1 ID and a CRC or message digest for each object would not only run faster, but should put a much lower load on the server.

Getting back to the birthday attack question (this is an area where your comments were very useful for me), there's a case I didn't consider.

Suppose two developers bounce code back and forth by email and one of them commits it, but the other developer is a bad guy. The bad guy would then have had an opportunity to use a birthday attack by sending back subtly modified code (e.g., changes to how comments are formated, additional blank lines, etc.) He can even put a humorous comment at the end of the file such as "the first 200 Chinese characters I learned" and then include the Chinese characters (I've tested this with gcc - the Chinese characters, represented in Unicode, print in an editor and are ignored by the compiler.) Unicode is a lot closer to binary data so you have a lot of bits you can alter in a small amount of space, with each character requiring multiple bytes to represent it. The comment will look silly but innocuous. I think Linus Torvalds once suggested being suspicious of anything that looked like "line noise" in a patch. Non-western unicode characters can serve the same function but look legitimate, at least to people who don't know the language and when coupled with some "social engineering" to set expectations.

As an example of how this attack might work, without breaking into a system, assume two programmers collaborating on a project both have write-access to the same shared repository.

1. The project is using  Java, with a rule that all classes and methods
that are protected or public be documented (so javadoc can create API
documentation).

2. Programmer A emails some Java source code to programmer B with a
request to edit the comments to improve them or fix any obvious
mistakes.

3. Programmer B fixes the comments, but also creates a modified file
with the same SHA-1 hash as the correct file in order to add some bugs
or security flaws. 

4. Programmer B creates a branch from an earlier version, adds some
tests, puts the contents of the modified file into the directory tree
under an obscure name, adds it and does a commit.  B then pushes it,
creating a new remote branch.

5. Programmer B then tells Programmer A that he'll have the modified
file back quickly, but could he please fetch his new remote branch
and run a test, and answer some questions about what happens as B needs
that information to finish his review of the documentation.

6. Programmer A tells B the results, so B knows that A has fetched the
remote branch, an B then sends A the corrected file (not the modified
one). Programmer A reviews the file, notes that everything seems OK,
specifically that only comments were changed, and runs commit -a
followed by a push.  Because Git tries to be smart, it will (I think)
notice from the SHA-1 hashes and from the remote branches that the
server already has the object so there is no need to send it.

8. Programmer B fetches the changes, deletes his temporary branch, both
locally and on the shared repository.  He tells A that the temporary
branch is deleted so that B should run "git branch update --prune ..."

So what happens? Hopefully someone finds the problem, either through a source-code review or some QA testing, but regardless Programmer A may get the blame as the evidence of any tampering has pretty much been erased. In the worst case, a release with a security hole goes out.

Why would Programmer B do that? Maybe he's leaving the company because he's hard to work with and is blaming Programmer A for the problem, and wants to "get back" at Programmer A by harming his career. But in any case he didn't have to break into the repository to get the effect he wanted. At least is is extremely hard to do in terms of computational resources.

Bill