Hacker News Reader

Comment by 0x0 | Hacker News Reader

I'm trying to play with this in git. Added the first file, committed, and then overwrote the file with the second file and committed again. But even when cloning this repository into another directory, I'm still getting different files between commit 1 and 2. What does it take to trick git into thinking the files are the same? I half expected "git status" to say "no changes" after overwriting the first (committed) pdf with the second pdf?

View on HN

This is because git adds a header and zlib compresses the PDFs such that they no longer collide when stored in git. But of course, they still collide when extracted from git:

    $ ls -l; for i in 1 2; do sha1sum < shattered-$i.pdf; \
    git cat-file -p $(git hash-object -w shattered-$i.pdf) |
    sha1sum; done; find .git/objects -type f -print0 | xargs -0 ls -l
    total 1664
    -rw-r--r--@ 1 jay  staff  422435 Feb 23 10:32 shattered-1.pdf
    -rw-r--r--@ 1 jay  staff  422435 Feb 23 10:32 shattered-2.pdf
    38762cf7f55934b34d179ae6a4c80cadccbb7f0a
    38762cf7f55934b34d179ae6a4c80cadccbb7f0a
    38762cf7f55934b34d179ae6a4c80cadccbb7f0a
    38762cf7f55934b34d179ae6a4c80cadccbb7f0a
    -r--r--r--  1 jay  staff  381104 Feb 23 10:41 .git/objects/b6/21eeccd5c7edac9b7dcba35a8d5afd075e24f2
    -r--r--r--  1 jay  staff  381102 Feb 23 10:41 .git/objects/ba/9aaa145ccd24ef760cf31c74d8f7ca1a2e47b0

See "Object Storage" for details at https://git-scm.com/book/en/v2/Git-Internals-Git-Objects

It's worth noting that either of the changes, adding a header or deflating the content, would remove the collision. The former because this is a chosen-prefix collision attack, the latter because the compression alters the content entirely.

I'm not a cryptographer, so I wonder: do the git header and zlib compression add significant complexity to manufacturing two files that collide inside git?

The compression is applied after the hashing, so it doesn't make any difference. Only the "blob <size>" header matters.

Probably just as easy. They used a fixed header for PDF and a tweakable middle. So just add the git blob header, as long as the tweakable middle is fixed size.

Git stores the files as so-called blob objects, they're prefixed with a simple header. So even if sha1(file1)==sha1(file2), your git will still get different hashes, because it's doing sha1(prefix+file1), sha1(prefix+file2). You'd need a file that collides with this prefix. This is certainly possible, but not sure if it may mean you need to pay for that several thousand cpu/gpu cluster google used to make it feasible. Maybe there are precomputations that can be reused somehow.

Why wouldn't the header be the same? The files have the same size and same name here? Does it have anything to do with zlib compression (I'd imagine the two files compress differently since they are actually different?)

Even if you use exactly the same headers it means that at the moment the SHA1 algorithm encounters the specially crafted data that creates the collision it's in a different state than with the "naked" files, so the collision (very probably) won't happen. Adding more content at the end of the file would work though, since at this point the SHA1 state machine would be in the same state on both sides.

You can test that easily with the files provided:

    $ sha1sum shattered-*
    38762cf7f55934b34d179ae6a4c80cadccbb7f0a  shattered-1.pdf
    38762cf7f55934b34d179ae6a4c80cadccbb7f0a  shattered-2.pdf

    $ echo 'more content at the end' >> shattered-1.pdf
    $ echo 'more content at the end' >> shattered-2.pdf
    $ sha1sum shattered-*
    42cfb194d7e7d557c00d9f2c8d590641ee8f871c  shattered-1.pdf
    42cfb194d7e7d557c00d9f2c8d590641ee8f871c  shattered-2.pdf

    $ echo 'more content at the start' > other-1.pdf; cat shattered-1.pdf >> other-1.pdf
    $ echo 'more content at the start' > other-2.pdf; cat shattered-2.pdf >> other-2.pdf  
    $ sha1sum other-*
    ed2ab5fc6c7109a7c7da13fdc05585e4d9e4fe0c  other-1.pdf
    a41e3539ca0e317a4097bb26ae978e79119d09c8  other-2.pdf

True, but the attack already builds upon modifying the state machine to get the same end result, creating data to allow for a specific prefix (e.g. always getting the desired intermediary state) should also be doable in some form of this attack.

Would it help if we padded the prefix so that the rest of the files are aligned to the block size of SHA1 (512bits), so that the crafted blocks are still block-aligned? Or does the different initial state (due to a different prefix) break any chance of re-colliding with these specific files? (i.e. you'll have to run the full brute force attack again with a valid git blob header as a common prefix?)

It's content specific. Changing anything before that point ruins the whole attack.

So yeah you'd need to do the whole attack again but with the prefix.

That's not the attack on git -- it's the commit ID. You can have two patches that have the same commit. Apply one now, and in the future replace it with the second one, without affecting any other commits IDs afterwards.

But I thought files in git were also identified by the sha1 of their contents? Why isn't there a conflict/de-duplication happening when committing one file over the other? I must be misunderstanding something, but I thought the commit points to a hash of a tree (file list) which has a list of blobs (file referenced by their sha1 sum), how does it know which of the two pdf file blobs to pick out of the blob store?

No, each commit (or merge) is simply the SHA1 of the diff-patch.

Thus adding the second file does create a diff, since the contents are not the same.

No, a commit is not the SHA-1 of the diff. The fundamental object model of Git does not store diffs, it stores the actual state of the source tree as represented by a commit. For instance, here's a commit file [1]—

  $ git cat-file -p fdf4fc3
  tree d8329fc1cc938780ffdd9f94e0d364e0ea74f579
  author Scott Chacon <schacon@gmail.com> 1243040974 -0700
  committer Scott Chacon <schacon@gmail.com> 1243040974 -0700

  first commit

A commit object just points to the tree object (in turn, another SHA-1, this time of the complete directory listing) and other meta information such as author name etc.

[1] https://git-scm.com/book/en/v2/Git-Internals-Git-Objects

Correct -- I was being terse: the commit is a function of the changes going in (and metadata like time, authorship).

Details: https://gist.github.com/masak/2415865

I'm not really talking about entire git commits, but just single files (blobs) within any commit/tree/repository

That is not correct and also not supported by your link. A git commit does not contain any changes. It is always a full sapshot of the repo state.

To have any kind of concept of "change", you need two gït commits. Just like a simple text file.

It's not simply a sha1(contents), but sha1(header + contents); the addition of that header means that SHA1's internal state is different from what it was in the raw PDFs when we encounter the section of the PDF that — without the header — would cause the internal state to align in the two PDFs. So, the header throws things off. But, if you took the header into account, redid the giant computation that Google did, then you could get two PDFs with different SHA1 hashes that, when committed (and thus get the header added) hash to the same thing.

It's semi-relevant to your question, but if you want to learn more about Git internals, I recommend the last chapter of the "Pro Git" book, which is free:

https://git-scm.com/book/en/v2/Git-Internals-Plumbing-and-Po...

Reply on news.ycombinator.com