5 ms·

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 clonin

by 0x0 10y ago

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?

anilgulecha 10y ago
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.
- 0x0 10y ago
  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?
  - anilgulecha 10y ago
    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.
    - kinkrtyavimoodh 10y ago
      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 https://git-scm.com/book/en/v2/Git-Internals-Git-Objects
      - anilgulecha 10y ago
        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 https://gist.github.com/masak/2415865
        0x0 10y ago
        I'm not really talking about entire git commits, but just single files (blobs) within any commit/tree/repository
        chronial 10y ago
        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.
  - deathanatos 10y ago
    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.
hannob 10y ago
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.
- 0x0 10y ago
  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?)
  - simias 10y ago
    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
    - consp 10y ago
      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.
eneveu 10y ago
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-Porcelain https://git-scm.com/book/en/v2/Git-Internals-Plumbing-and-Po...
js2 10y ago
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 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?
- cesarb 10y ago
  The compression is applied after the hashing, so it doesn't make any difference. Only the "blob <size>" header matters.
- kzrdude 10y ago
  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.

by 0x0 10y ago

anilgulecha 10y ago

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.

0x0 10y ago
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?
- anilgulecha 10y ago
  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.
  - kinkrtyavimoodh 10y ago
    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 https://git-scm.com/book/en/v2/Git-Internals-Git-Objects
    - anilgulecha 10y ago
      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 https://gist.github.com/masak/2415865
      - 0x0 10y ago
        I'm not really talking about entire git commits, but just single files (blobs) within any commit/tree/repository
      - chronial 10y ago
        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.
- deathanatos 10y ago
  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.

hannob 10y ago

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.

0x0 10y ago
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?)
- simias 10y ago
  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
  - consp 10y ago
    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.

eneveu 10y ago

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-Porcelain https://git-scm.com/book/en/v2/Git-Internals-Plumbing-and-Po...

js2 10y ago

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 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?

cesarb 10y ago
The compression is applied after the hashing, so it doesn't make any difference. Only the "blob <size>" header matters.
kzrdude 10y ago
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.