5 ms·

Does this mean that it is now possible to create a circular data structure in git? :)

by m1el 11y ago

strmpnk 11y ago
I'm not an expert but here's my interpretation. It doesn't seem so. They still require that the SHA-1 is given different initialization vectors (if you look closely you'll notice IV1 and IV2 are different) so I'm thinking this is what freestart means. Git objects tend to have a stricter format so injecting an initial state may be a bit further out of reach. What it does mean is that the triviality of a full collision is greatly increased. I'd not trust arbitrary git DAGs anyway... I'd double check but I bet you could forge a pack with some objects that are given invalid content addresses. An integrity check would pick it up but I would also expect most git code to not check that on every operation.
coldpie 11y ago
The big take-away from the article seems to be: > Even though freestart collisions do not directly lead to actual collisions for SHA-1, in our case, the experimental data we obtained in the process enable significantly more accurate projections on the real-world cost of actual collisions for SHA-1, compared to previous projections. Concretely, we estimate the SHA-1 collision cost today (i.e., Fall 2015) between 75K$ and 120K$ renting Amazon EC2 cloud computing over a few months. So if I understand their estimates correctly, it would cost around $100,000 and several months to create your circular data structure. (Or, somewhat less trivially, compromise Git's SHA1 integrity promise in a still-probably-useless way.)
- joeyh 11y ago
  There's a way to embed arbitrary garbage invisibly inside git commit objects. Just put your garbage after a NUL and nothing will display it as part of the commit message. Using that to generate two commit objects that collide is the most likely attack method. Exploiting the result will involve some social engineering. Starting with getting one of the colliding objects accepted into the repo you want to attack. At this point, it's cheaper to generate a SHA1 collision than it will be to fix git not to use SHA1. Which is deeply worrying. Basic hygiene at this point probably includes only merging git commits from others that are gpg signed (as well as gpg signing as many commits yourself as you can without going mad at the password prompts). Unfortunately, tooling doesn't make this easy, and some things like git format-patch are actively unhelpful by not preserving gpg signatures.
  - agwa 11y ago
    How does GPG-signing help, when the signature is over a SHA-1 hash?
    - acveilleux 11y ago
      GPG does not require SHA1 so you can enfore SHA-2 for example.
      - agwa 11y ago
        GPG can use SHA-2, but the way that GPG signing works in Git is that you essentially GPG-sign the SHA-1 hash of a Git object. So even if GPG is using SHA-2 for its signature, it's no protection against a collision in one of the underlying Git object IDs. Edit: this is only true of tag signing - with commit signing you GPG-sign the whole commit object.
    - joeyh 11y ago
      Thanks, I forgot that git got that wrong :/ Edit: Actually, looking at the code (do_sign_commit), git appears to gpg sign the whole commit object. I think it's in signed tags where git only signs the sha1 being tagged.
      - agwa 11y ago
        Yeah, I just emerged from the Git code myself ;-) So you're correct that GPG-signing commits (but not tags) prevents collisions in commit objects. The problem though is that a commit ultimately contains a SHA-1 hash of a tree object, so now the concern is someone generating colliding tree objects. Edit: fortunately, the format of tree objects looks pretty rigid. I feel somewhat reassured, but only somewhat.
        joeyh 11y ago
        http://joeyh.name/blog/entry/size_of_the_git_sha1_collision_attack_surface/ http://joeyh.name/blog/entry/size_of_the_git_sha1_collision_... has some discussion of colliding tree objects.

Does this mean that it is now possible to create a circular data structure in git? :)

by m1el 11y ago

Does this mean that it is now possible to create a circular data structure in git? :)

I'm not an expert but here's my interpretation. It doesn't seem so. They still require that the SHA-1 is given different initialization vectors (if you look closely you'll notice IV1 and IV2 are different) so I'm thinking this is what freestart means. Git objects tend to have a stricter format so injecting an initial state may be a bit further out of reach. What it does mean is that the triviality of a full collision is greatly increased. I'd not trust arbitrary git DAGs anyway... I'd double check but I bet you could forge a pack with some objects that are given invalid content addresses. An integrity check would pick it up but I would also expect most git code to not check that on every operation.

coldpie 11y ago

The big take-away from the article seems to be: > Even though freestart collisions do not directly lead to actual collisions for SHA-1, in our case, the experimental data we obtained in the process enable significantly more accurate projections on the real-world cost of actual collisions for SHA-1, compared to previous projections. Concretely, we estimate the SHA-1 collision cost today (i.e., Fall 2015) between 75K$ and 120K$ renting Amazon EC2 cloud computing over a few months. So if I understand their estimates correctly, it would cost around $100,000 and several months to create your circular data structure. (Or, somewhat less trivially, compromise Git's SHA1 integrity promise in a still-probably-useless way.)

joeyh 11y ago
There's a way to embed arbitrary garbage invisibly inside git commit objects. Just put your garbage after a NUL and nothing will display it as part of the commit message. Using that to generate two commit objects that collide is the most likely attack method. Exploiting the result will involve some social engineering. Starting with getting one of the colliding objects accepted into the repo you want to attack. At this point, it's cheaper to generate a SHA1 collision than it will be to fix git not to use SHA1. Which is deeply worrying. Basic hygiene at this point probably includes only merging git commits from others that are gpg signed (as well as gpg signing as many commits yourself as you can without going mad at the password prompts). Unfortunately, tooling doesn't make this easy, and some things like git format-patch are actively unhelpful by not preserving gpg signatures.
- agwa 11y ago
  How does GPG-signing help, when the signature is over a SHA-1 hash?
  - acveilleux 11y ago
    GPG does not require SHA1 so you can enfore SHA-2 for example.
    - agwa 11y ago
      GPG can use SHA-2, but the way that GPG signing works in Git is that you essentially GPG-sign the SHA-1 hash of a Git object. So even if GPG is using SHA-2 for its signature, it's no protection against a collision in one of the underlying Git object IDs. Edit: this is only true of tag signing - with commit signing you GPG-sign the whole commit object.
  - joeyh 11y ago
    Thanks, I forgot that git got that wrong :/ Edit: Actually, looking at the code (do_sign_commit), git appears to gpg sign the whole commit object. I think it's in signed tags where git only signs the sha1 being tagged.
    - agwa 11y ago
      Yeah, I just emerged from the Git code myself ;-) So you're correct that GPG-signing commits (but not tags) prevents collisions in commit objects. The problem though is that a commit ultimately contains a SHA-1 hash of a tree object, so now the concern is someone generating colliding tree objects. Edit: fortunately, the format of tree objects looks pretty rigid. I feel somewhat reassured, but only somewhat.
      - joeyh 11y ago
        http://joeyh.name/blog/entry/size_of_the_git_sha1_collision_attack_surface/ http://joeyh.name/blog/entry/size_of_the_git_sha1_collision_... has some discussion of colliding tree objects.