13 ms·

SHA1 collisions make Git vulnerable to attacks

171 points by wyldfire 10y ago

zamalek 10y ago
This argument still assumes that Git uses SHA1 for security. Linus points that out and John doesn't attempt to refute it, simply ignoring it. Linus should have used Murmur, CityHash or something - a SHA1 collision was going to happen eventually. By using a content identification hash function we could have avoided this argument entirely.
- jcoffland 10y ago
  A SHA1 collision has happened and it has broken at least one (SVN) repo already. https://arstechnica.com/security/2017/02/watershed-sha1-collision-just-broke-the-webkit-repository-others-may-follow/ https://arstechnica.com/security/2017/02/watershed-sha1-coll...
  - zamalek 10y ago
    SHA1 is not used for security in Git, the session layer (SSH, HTTPS) is. Edit: The broken repo was caused by SVN and not Git.
    - deleted 10y ago
      [deleted]
    - kpcyrd 10y ago
      > SHA1 is not used for security in Git -S[<keyid>], --gpg-sign[=<keyid>] GPG-sign commits. The keyid argument is optional and defaults to the committer identity; if specified, it must be stuck to the option without a space. Yes it is.
      - zamalek 10y ago
        Fair enough, clearly I was mistaken.
      - junke 10y ago
        I don't know much cryptography. Wouldn't an attack require you to forge a commit object which is a good-looking patch, along with a valid signature (signed from someone you trust), which has the same identity (SHA1 hash)?
        nicky0 10y ago
        No need to forge the signature. The signature will still verify since your forged object has the same hash as the genuine one.
        cyphar 10y ago
        The attack is not as difficult as that. If you can create a valid git object which collides with another git object, signatures for the previous object tree (which is identified by SHA-1 hash) will be valid for the new object tree (which has the same hash). So a collision in a blob that represents a file (or any other internal git object) will cause in your old signature still being valid for the new file that corresponds to the git collision.
      - baby 10y ago
        Yup. But Signatures rely on the hash pre-image resistance. Not on the collision resistance of the hash.
  - jfoutz 10y ago
    I could be crazy, but aren't the hashes the diffs of checkins? It's certainly possible to create a valid patch file that causes a collision, but it seems really hard to make a collision that looks like a valid pull request. I understand your concern (I think) but consider all the extra stuff that has to happen for someone to accept a pr. Edit. I do agree it's time to start thinking about moving to the fire exits
    - RichardCA 10y ago
      No, that's not how Git works. There are multiple objects in Git that use SHA-1 for identification. A common point of confusion is when someone thinks a commit is essentially a diff. It's not, each commit is a snapshot that can be used to reconstruct the entire work tree. You get the diff when you compare the commit to its parent. Here, this is a good read: https://github.com/git/git/commit/e83c5163316f89bfbde7d9ab23ca2e25604af290 https://github.com/git/git/commit/e83c5163316f89bfbde7d9ab23...
    - kpcyrd 10y ago
      No, the commit hash is a hash of the commit object, which holds a hash of the tree object, which holds hashes of the file objects.
    - grandalf 10y ago
      As long as the first part of the diff shown appeared not to be abnormal, some users might be fooled. For example, a file could be created that appears to be a normal source file at the front but contains some other behavior further down.
- chopin 10y ago
  Just a nitpick: Git predates Murmur and CityHash.
- kzrdude 10y ago
  That's just some mantra to shape the discussion in the way they like. Git allows signing tags and commits, and those features are now broken because all object names use SHA1.
  - moonshinefe 10y ago
    So wait, when is SHA-1 ever used for signing tags and commits in git? that's new to me.. My understanding was you're using a public key type of encryption such as PGP at that point. I feel I may be missing the point here. (apologies if so)
    - zamalek 10y ago
      My original statement is slightly incorrect; you can. The commit hash is probably used as part of the signature. It would have been better to sign the commit blob directly, as Git stores the length alongside the hash from that point down in the DAG (making prefix attacks impossible).
    - daurnimator 10y ago
      I sign all my commits. Github even make it easy to see: https://github.com/blog/2144-gpg-signature-verification https://github.com/blog/2144-gpg-signature-verification And I also use it in a few places e.g. for http://hashbang.sh/ http://hashbang.sh/, we only allow signed commits into master However, as far as I know, when you sign a git commit you are actually sign the hash of the commit. With SHA-1 broken in the current way it essentially means someone with 110K to burn could forge a commit and reuse my PGP signature.
      - moonshinefe 10y ago
        Well holy smokes. I don't know which repository you contribute to, but if you're getting undermined by such James Bond-esque deception by super villains, in addition to someone spending 6 figures into breaking your stuff, I'd hope you'd at least review the commits you sign with your key after glancing at it. In addition, you'd have to have everyone else not notice it, all the insanely cheaper exploits not been tried on your current setup, and all the other stars aligning...
ivrrimum 10y ago
Cmon.. Its still very very hard to make a sha1 collision. Sure in theory its possible, but not in the real deal
tgummerer 10y ago
I feel like this still ignores most of what Linus said on why git isn't broken. In particular "it's fairly trivial to detect the fingerprints of using this attack" in his Google+ post. https://plus.google.com/+LinusTorvalds/posts/7tp2gYWQugL https://plus.google.com/+LinusTorvalds/posts/7tp2gYWQugL And there are already patches on the mailing list for that.
- strictfp 10y ago
  I think the fingerprint argument is pretty weak actually. There is still a lot of unreadable content in git repos, including binary blobs in the kernel.
  - moonshinefe 10y ago
    Please PoC a Git exploit then?
    - goodplay 10y ago
      Sure, just wire me 200k.
      - moonshinefe 10y ago
        If you're working on such a massively important git repo with very poor security measures and trust levels at $200k break in status that are practical... yeah, maybe bigger problems.
    - strictfp 10y ago
      I'g glad you're willing to discuss things so freely /s
  - baby 10y ago
    There is already danger in accepting unreadable content by itself.
    - 10y ago
luckystarr 10y ago
Well, he was saved by SHA-1 being still cryptographic enough to rely on the head-sha of his tree to know nobody changed anything after somebody broke into kernel.org. Not sure how his fetch/push policy is, but my guess is this would have been more of a headache if it would have been MD5.
- baby 10y ago
  yup, this was relying on SHA-1 pre-image resistance. Imagine that even MD5 still has pre-image resistance.
wfunction 10y ago
Why does Linux think that the source file in question has to acquire an incomprehensible blob in the middle in order for a commit hash collision to occur? Can't the attacker just make all the changes he wants and then insert a random 1 KiB file somewhere to compensate for the commit hash? It could be totally tucked away somewhere you don't expect... you wouldn't see it just by looking at source code.
- Aldo_MX 10y ago
  I'm not an expert, but for me an incomprehensible blob that is pretty likely to be overlooked begins with: This program is free software; you can redistribute it and/or modify it under the terms of...
  - alkonaut 10y ago
    Haha true, add gibberish below the fold of License.md and no one will ever read it. commit -m "Added dutch license translation"
- mattkrause 10y ago
  The demonstration is a pair of PDFs that display differently. However, Google didn't find two PDFs that just happen to collide. Instead, they built one PDF that contains two jpegs and a switch that selects one of them for display. The neat bit is that the file has the same hash regardless of the switch's setting. This attack won't work on plain text source because it won't look like source code.
RubyPinch 10y ago
Its possible to go in and replace the hash algorithm with something else, which none of these "git is going to ruin everything with not replacing SHA1 this instant!" people seem to bother with, to prove their points, instead of endless posturing. http://stackoverflow.com/a/34599081 http://stackoverflow.com/a/34599081 has actually gone about doing it, but it has been over a year since that, and as linus says, there has been multiple collision mitigations added as well, so tests should probably be re-done
- hvidgaard 10y ago
  You can, but they should reengineer Git to use any hash function, and not assume output length.
  - mattkrause 10y ago
    I think the bigger problem is that tons of other stuff also assumes the output length.
    - hvidgaard 10y ago
      That can be mitegated, but the sooner steps are made towards changing it, the easier it will be.
- CJefferson 10y ago
  My git with different hash would be useless. It wouldn't be able to interact with github, bitbucket, or pull/push to anyone else's repositories. I may as well rename the package. Fixing this is going to require breaking backwards compatability with every program that works with git -- it's going to be a huge undertaking, because early in git's design they didn't support multiple hash functions.
  - RubyPinch 10y ago
    To clarify, I mean to replace the hash with something that would collide far more often, to simulate collisions, to see how git handles them
chmike 10y ago
The forged hash collision will always be a weak point. Things will get worse with cost reduction of processing power. It's a loosing battle. The only way to detect without error two identical files is by comparing the files. This comparison can be speed up by comparing compressed version of the files. The other functionality of hashes is to build a presumably unique file identifier. The byte sequence of the compressed file could serve as identifer. So instead of using the file system as index with the sha1 name as file name, we would have to build a specific database organized as a set whose values (compressed files) would be the keys. A hash index could be used to speed up the search and equality test. Here a very fast hash would do the trick. Sha1 or a faster hash would be ok. The file system could then be used to organize the hash buckets as does git. File comparision would of course first compare compressed and uncompressed file size. Or use other hashes or longer hash values to detect different files. When all these values are identical, then a file comparison must be performed to detect if we have a collision. File compression can only get better and faster. So basically git would only need to add hash collision detection and the capacity to support different objects with the same hash identifier.
- vbezhenar 10y ago
  With reasonably long cryptographically strong hashes it's not a weak point (or you could call almost all cryptography a weak point). Weak point is hard-coded algorithms and sizes into Git (if I understood the problem correctly). Software should be written with more generic approach, so algorithms could be changed and migrated when necessary. SHA-1 is considered weak for many years, git should've migrated from it already.
  - DougBTX 10y ago
    Git could have been written with a pluggable hash system, but for something that needs to be changed let's say once every ten years, is the up front cost really worth it?
    - adrianN 10y ago
      How hard is it to introduce a global constant for the number of bits in your hash instead of writing char hash[40] everywhere?
xiphias 10y ago
I just went to the github blog and I see this: ,,GitHub GDC Party 2017''. While security of git is broken, they are partying. Gitlab blog: working on UX Bitbucket: branch permissions All of the teams should handle this issue as an emergency, and at least have a blog entry about their points of view.
- nicky0 10y ago
  And I see you commenting on Hacker News instead of getting important work done.
- ageofwant 10y ago
  That may be appropriate if it was an "emergency". It's not.
  - xiphias 10y ago
    Luckily there's a long thread on bitcoin-dev mailing list about how disastorous the consequences can be if somebody is able to change the git-tree because of this attack scenario, so I'm not the only one who thinks that signing only the commit can make billions of dollars worth of damage. And this doesn't take into account that almost all companies use open source software developed on github, so I believe that any remote possibility of adding a malware to open source software is emergency situation.
StreamBright 10y ago
I am not sure how serious this is compare to: https://github.com/amoffat/masquerade/commit/9b0562595cc479ac8696110cb0a2d33f8f2b7d29 https://github.com/amoffat/masquerade/commit/9b0562595cc479a...
- wyldfire 10y ago
  That's not a problem with git. If anything it's an issue with github, but it's a pretty insignificant one IMO. Yes, if you say you are billg@microsoft.com and make a commit to some repo on github, github will look up the username associated with billg@microsoft.com and show that user as the committer. Should it do that? Eh, probably not but this has come up a few times and github hasn't changed it. So by now we should just start to educate ourselves that this is how github is intended to work.
ioquatix 10y ago
When I designed fingerprint (https://github.com/ioquatix/fingerprint https://github.com/ioquatix/fingerprint) I allowed multiple checksums, which means you CAN migrate from one checksum to another pretty easily. However, I didn't use a Merkle tree in the initial design and so I hope to revisit it at some point to improve it. It should be trivial to add an additional checksum to git. Not to replace how SHA1 is currently used, but to add essentially per-commit checksum, which is a checksum of the entire commit contents (including the checksum of the previous commit). It wouldn't be as elegant as using SHA256 in place of SHA1, but at least you could, with some effort, validate the source tree in a cryptographically secure way.
- stirner 10y ago
  Hacker News doesn't support Markdown comments like Reddit. There are a couple Markdown-like features like italics, but that's it.
9gunpi 10y ago
Git should have been written with pluggable hashes, right. Also, SHA1 could have been invented stronger against collisions in the first place. In the retrospect many decisions which might have simplified current moment's problems are obvious, but in reality of those decisions in the past they never are. This feeling (it's called the retrospective predictability) is not a function of current problem or previous wrong decisions, but the random reality of events in complex systems, open source software implementing fresh ideas in a new way is being random and complex enough for this.
ifdefdebug 10y ago
From the same thread (Peter Gutmann, Fri Feb 24 00:42:36 EST 2017): "After sitting through an endless flood of headless-chicken messages on multiple media about SHA-1 being fatally broken, I thought I'd do a quick writeup about what this actually means. In short: Reports of SHA-1's demise are considerably exaggerated. What CWI/Google have done is confirmed what we've known for a long time, that SHA-1 is shaky. Using a nation-state's worth of resources and a year of time (https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html https://security.googleblog.com/2017/02/announcing-first-sha...), they've shown that, with a very carefully-crafted document, you can create a collision. Their presentation of the results is detailed and accurate, it's the panicked misinterpretation of those results that are the problem." Continues here: http://www.metzdowd.com/pipermail/cryptography/2017-February/031604.html http://www.metzdowd.com/pipermail/cryptography/2017-February... [edit: typo]
- simias 10y ago
  110,000$ is not "a nation-state's worth of resources". I agree with the rest though, the sky is not falling but people shouldn't react to baseless alarmist claims with baseless overconfident claims.
  - StreamBright 10y ago
    Security is quite often about the amount of money you have to put in to get something or somebody hacked. 110,000 USD is in the ballpark of state level players when we are talking about forging documents to avoid any sort of tampering detection. It has practically zero use of small time hackers or script kiddies. Why would anybody invest 110K into a collision? What is the practical use of it?
    - userbinator 10y ago
      In other words, SHA-1 is still nowhere near as insecure as MD5, the latter for which collisions can be generated in seconds on hardware everyone already has.
moonshinefe 10y ago
This reads like a giant "I told you so." circa 2005 "In the next few years, nasty people will teach him the threat model" I'd like to see those very forceful claims substantiated. Git hasn't said moving forward it will never change from sha-1 and 2005 was a far different era than 2017 for crypto. Let's keep that in perspective.
baby 10y ago
1) Yes, Git should move to a better hash function at some point. 2) No, even easy "malicious" collisions in SHA-1 will still not break most of Git's usages. You're already trusting the repo you're pulling because of TLS, you're already trusting the commits you're getting because of peer-review (you read the commit) and a web-of-trust (you trust your collaborators). (And you're trusting commits even more when they're signed.)
junke 10y ago
Found another detailed explanation from Mike Gerwitz: https://forums.whonix.org/t/security-git-general-verification-verifying-whonix-submodules/513/12 https://forums.whonix.org/t/security-git-general-verificatio...
bandrami 10y ago
I don't get why the discovery of a non-preimage attack is causing so much consternation. If the mere existence of collisions is not acceptable to your VCS, then your VCS can't use a hash, period. If you're worried about an intentional attack, it's no closer today than it was last week: the attacker doesn't control the output hash of the collision, or either input.
- Taek 10y ago
  > If the mere existence of collisions is not acceptable to your VCS, then your VCS can't use a hash, period What? It could use a secure hash. Collisions take more energy than the universe has to discover.
  - bandrami 10y ago
    "Secure" is a time-constrained term. But any hash, whatsoever, has collisions, so if collisions are unacceptable, your VCS can't use them. (The point being that a VCS should handle collisions gracefully no matter what has is used.)
    - lmm 10y ago
      No VCS is 100% secure against the possibility of catastrophic failure. If an asteroid wiped out all life on earth there is no VCS that can handle that gracefully. So as long as a hash collision is less likely than that, using a hash and not handling collisions gracefully doesn't make the VCS substantially less safe.
Pharylon 10y ago
Linus in 2005: "But the _real_ security comes from the fact that git is distributed, which means that a developer should never actually use a public tree for his development." And then GitHub happened.
ericfrederich 10y ago
Look at these SHA-1 sums... https://github.com/ericfrederich/sillygit/commits/master https://github.com/ericfrederich/sillygit/commits/master
- tokenizerrr 10y ago
  That's just brute forcing the first few characters.
- cespare 10y ago
  28 bits is easy. 160 bits is not easy.
chmike 10y ago
SHA1 is still OK for identifying files. The probability of random collision is still very low. The only problem is for forged collisions. The object store could be modified to support file collision. One way to disambiguate collision is to use a randomly generated byte sequence as SHA1 seed or hashed before the file data. This random byte sequence would behave like a salt and disable any forged collisions. A single seed for the whole repository would be enough. It should remain secret to prevent forging a collision with the two hashes. It's harder but not impossible. To test if a given file is in the object store, one first compute the SHA1 key to use as file name. If no collisions ever occured with an object a file with that SHA1 name will be present in the store. That file contains the usual data plus the second hash computed with the random seed. This second hash could be added as needed to keep backward compatibility and provide silent automatic upgrade. When one need to test if the file is present in the store, one computes the normal SHA1 key and the secondary hash with the seed. We locate the object in the store uisng the first SHA and test for file equality with the randomly seeded hash. Using a faster hash like blacke2 to compute the random seeded hash could mitigate the price to compute two hashes. It should be parameterized this time and the hash size should be variable. If a collision is detected, that is the secondary hash differ, the file is replaced by a directory with the common SHA1 as name. The colliding files would be stored in the directory using the secondary hash as name. Or the files could be packed in a single tar like file with the secondary hash used as file identifier. This should be enough to protect against forged collisions which is the only real problem. The required change to git would be limited. The only serious disadvantage is the need to compute the randomly seeded hash.
crystalmeph 10y ago
Forgive my ignorance. I don't understand the threat model being worried about here. If someone breaks into your CVS/SVN server and rewrites project history, how is that less bad than someone breaking into your remote git repo and rewriting project history? Don't both attacks require a break-in at the server/remote? Or does CVS/SVN have a better method of detecting such a break-in?

171 points by wyldfire 10y ago

This argument still assumes that Git uses SHA1 for security. Linus points that out and John doesn't attempt to refute it, simply ignoring it. Linus should have used Murmur, CityHash or something - a SHA1 collision was going to happen eventually. By using a content identification hash function we could have avoided this argument entirely.

jcoffland 10y ago
A SHA1 collision has happened and it has broken at least one (SVN) repo already. https://arstechnica.com/security/2017/02/watershed-sha1-collision-just-broke-the-webkit-repository-others-may-follow/ https://arstechnica.com/security/2017/02/watershed-sha1-coll...
- zamalek 10y ago
  SHA1 is not used for security in Git, the session layer (SSH, HTTPS) is. Edit: The broken repo was caused by SVN and not Git.
  - deleted 10y ago
    [deleted]
  - kpcyrd 10y ago
    > SHA1 is not used for security in Git -S[<keyid>], --gpg-sign[=<keyid>] GPG-sign commits. The keyid argument is optional and defaults to the committer identity; if specified, it must be stuck to the option without a space. Yes it is.
    - zamalek 10y ago
      Fair enough, clearly I was mistaken.
    - junke 10y ago
      I don't know much cryptography. Wouldn't an attack require you to forge a commit object which is a good-looking patch, along with a valid signature (signed from someone you trust), which has the same identity (SHA1 hash)?
      - nicky0 10y ago
        No need to forge the signature. The signature will still verify since your forged object has the same hash as the genuine one.
      - cyphar 10y ago
        The attack is not as difficult as that. If you can create a valid git object which collides with another git object, signatures for the previous object tree (which is identified by SHA-1 hash) will be valid for the new object tree (which has the same hash). So a collision in a blob that represents a file (or any other internal git object) will cause in your old signature still being valid for the new file that corresponds to the git collision.
    - baby 10y ago
      Yup. But Signatures rely on the hash pre-image resistance. Not on the collision resistance of the hash.
- jfoutz 10y ago
  I could be crazy, but aren't the hashes the diffs of checkins? It's certainly possible to create a valid patch file that causes a collision, but it seems really hard to make a collision that looks like a valid pull request. I understand your concern (I think) but consider all the extra stuff that has to happen for someone to accept a pr. Edit. I do agree it's time to start thinking about moving to the fire exits
  - RichardCA 10y ago
    No, that's not how Git works. There are multiple objects in Git that use SHA-1 for identification. A common point of confusion is when someone thinks a commit is essentially a diff. It's not, each commit is a snapshot that can be used to reconstruct the entire work tree. You get the diff when you compare the commit to its parent. Here, this is a good read: https://github.com/git/git/commit/e83c5163316f89bfbde7d9ab23ca2e25604af290 https://github.com/git/git/commit/e83c5163316f89bfbde7d9ab23...
  - kpcyrd 10y ago
    No, the commit hash is a hash of the commit object, which holds a hash of the tree object, which holds hashes of the file objects.
  - grandalf 10y ago
    As long as the first part of the diff shown appeared not to be abnormal, some users might be fooled. For example, a file could be created that appears to be a normal source file at the front but contains some other behavior further down.
chopin 10y ago
Just a nitpick: Git predates Murmur and CityHash.
kzrdude 10y ago
That's just some mantra to shape the discussion in the way they like. Git allows signing tags and commits, and those features are now broken because all object names use SHA1.
- moonshinefe 10y ago
  So wait, when is SHA-1 ever used for signing tags and commits in git? that's new to me.. My understanding was you're using a public key type of encryption such as PGP at that point. I feel I may be missing the point here. (apologies if so)
  - zamalek 10y ago
    My original statement is slightly incorrect; you can. The commit hash is probably used as part of the signature. It would have been better to sign the commit blob directly, as Git stores the length alongside the hash from that point down in the DAG (making prefix attacks impossible).
  - daurnimator 10y ago
    I sign all my commits. Github even make it easy to see: https://github.com/blog/2144-gpg-signature-verification https://github.com/blog/2144-gpg-signature-verification And I also use it in a few places e.g. for http://hashbang.sh/ http://hashbang.sh/, we only allow signed commits into master However, as far as I know, when you sign a git commit you are actually sign the hash of the commit. With SHA-1 broken in the current way it essentially means someone with 110K to burn could forge a commit and reuse my PGP signature.
    - moonshinefe 10y ago
      Well holy smokes. I don't know which repository you contribute to, but if you're getting undermined by such James Bond-esque deception by super villains, in addition to someone spending 6 figures into breaking your stuff, I'd hope you'd at least review the commits you sign with your key after glancing at it. In addition, you'd have to have everyone else not notice it, all the insanely cheaper exploits not been tried on your current setup, and all the other stars aligning...

ivrrimum 10y ago

Cmon.. Its still very very hard to make a sha1 collision. Sure in theory its possible, but not in the real deal

tgummerer 10y ago

I feel like this still ignores most of what Linus said on why git isn't broken. In particular "it's fairly trivial to detect the fingerprints of using this attack" in his Google+ post. https://plus.google.com/+LinusTorvalds/posts/7tp2gYWQugL https://plus.google.com/+LinusTorvalds/posts/7tp2gYWQugL And there are already patches on the mailing list for that.

strictfp 10y ago
I think the fingerprint argument is pretty weak actually. There is still a lot of unreadable content in git repos, including binary blobs in the kernel.
- moonshinefe 10y ago
  Please PoC a Git exploit then?
  - goodplay 10y ago
    Sure, just wire me 200k.
    - moonshinefe 10y ago
      If you're working on such a massively important git repo with very poor security measures and trust levels at $200k break in status that are practical... yeah, maybe bigger problems.
  - strictfp 10y ago
    I'g glad you're willing to discuss things so freely /s
- baby 10y ago
  There is already danger in accepting unreadable content by itself.
  - 10y ago

luckystarr 10y ago

Well, he was saved by SHA-1 being still cryptographic enough to rely on the head-sha of his tree to know nobody changed anything after somebody broke into kernel.org. Not sure how his fetch/push policy is, but my guess is this would have been more of a headache if it would have been MD5.

baby 10y ago
yup, this was relying on SHA-1 pre-image resistance. Imagine that even MD5 still has pre-image resistance.

wfunction 10y ago

Why does Linux think that the source file in question has to acquire an incomprehensible blob in the middle in order for a commit hash collision to occur? Can't the attacker just make all the changes he wants and then insert a random 1 KiB file somewhere to compensate for the commit hash? It could be totally tucked away somewhere you don't expect... you wouldn't see it just by looking at source code.

Aldo_MX 10y ago
I'm not an expert, but for me an incomprehensible blob that is pretty likely to be overlooked begins with: This program is free software; you can redistribute it and/or modify it under the terms of...
- alkonaut 10y ago
  Haha true, add gibberish below the fold of License.md and no one will ever read it. commit -m "Added dutch license translation"
mattkrause 10y ago
The demonstration is a pair of PDFs that display differently. However, Google didn't find two PDFs that just happen to collide. Instead, they built one PDF that contains two jpegs and a switch that selects one of them for display. The neat bit is that the file has the same hash regardless of the switch's setting. This attack won't work on plain text source because it won't look like source code.

RubyPinch 10y ago

Its possible to go in and replace the hash algorithm with something else, which none of these "git is going to ruin everything with not replacing SHA1 this instant!" people seem to bother with, to prove their points, instead of endless posturing. http://stackoverflow.com/a/34599081 http://stackoverflow.com/a/34599081 has actually gone about doing it, but it has been over a year since that, and as linus says, there has been multiple collision mitigations added as well, so tests should probably be re-done

hvidgaard 10y ago
You can, but they should reengineer Git to use any hash function, and not assume output length.
- mattkrause 10y ago
  I think the bigger problem is that tons of other stuff also assumes the output length.
  - hvidgaard 10y ago
    That can be mitegated, but the sooner steps are made towards changing it, the easier it will be.
CJefferson 10y ago
My git with different hash would be useless. It wouldn't be able to interact with github, bitbucket, or pull/push to anyone else's repositories. I may as well rename the package. Fixing this is going to require breaking backwards compatability with every program that works with git -- it's going to be a huge undertaking, because early in git's design they didn't support multiple hash functions.
- RubyPinch 10y ago
  To clarify, I mean to replace the hash with something that would collide far more often, to simulate collisions, to see how git handles them

chmike 10y ago

The forged hash collision will always be a weak point. Things will get worse with cost reduction of processing power. It's a loosing battle. The only way to detect without error two identical files is by comparing the files. This comparison can be speed up by comparing compressed version of the files. The other functionality of hashes is to build a presumably unique file identifier. The byte sequence of the compressed file could serve as identifer. So instead of using the file system as index with the sha1 name as file name, we would have to build a specific database organized as a set whose values (compressed files) would be the keys. A hash index could be used to speed up the search and equality test. Here a very fast hash would do the trick. Sha1 or a faster hash would be ok. The file system could then be used to organize the hash buckets as does git. File comparision would of course first compare compressed and uncompressed file size. Or use other hashes or longer hash values to detect different files. When all these values are identical, then a file comparison must be performed to detect if we have a collision. File compression can only get better and faster. So basically git would only need to add hash collision detection and the capacity to support different objects with the same hash identifier.

vbezhenar 10y ago
With reasonably long cryptographically strong hashes it's not a weak point (or you could call almost all cryptography a weak point). Weak point is hard-coded algorithms and sizes into Git (if I understood the problem correctly). Software should be written with more generic approach, so algorithms could be changed and migrated when necessary. SHA-1 is considered weak for many years, git should've migrated from it already.
- DougBTX 10y ago
  Git could have been written with a pluggable hash system, but for something that needs to be changed let's say once every ten years, is the up front cost really worth it?
  - adrianN 10y ago
    How hard is it to introduce a global constant for the number of bits in your hash instead of writing char hash[40] everywhere?

xiphias 10y ago

I just went to the github blog and I see this: ,,GitHub GDC Party 2017''. While security of git is broken, they are partying. Gitlab blog: working on UX Bitbucket: branch permissions All of the teams should handle this issue as an emergency, and at least have a blog entry about their points of view.

nicky0 10y ago
And I see you commenting on Hacker News instead of getting important work done.
ageofwant 10y ago
That may be appropriate if it was an "emergency". It's not.
- xiphias 10y ago
  Luckily there's a long thread on bitcoin-dev mailing list about how disastorous the consequences can be if somebody is able to change the git-tree because of this attack scenario, so I'm not the only one who thinks that signing only the commit can make billions of dollars worth of damage. And this doesn't take into account that almost all companies use open source software developed on github, so I believe that any remote possibility of adding a malware to open source software is emergency situation.

StreamBright 10y ago

I am not sure how serious this is compare to: https://github.com/amoffat/masquerade/commit/9b0562595cc479ac8696110cb0a2d33f8f2b7d29 https://github.com/amoffat/masquerade/commit/9b0562595cc479a...

wyldfire 10y ago
That's not a problem with git. If anything it's an issue with github, but it's a pretty insignificant one IMO. Yes, if you say you are billg@microsoft.com and make a commit to some repo on github, github will look up the username associated with billg@microsoft.com and show that user as the committer. Should it do that? Eh, probably not but this has come up a few times and github hasn't changed it. So by now we should just start to educate ourselves that this is how github is intended to work.

ioquatix 10y ago

When I designed fingerprint (https://github.com/ioquatix/fingerprint https://github.com/ioquatix/fingerprint) I allowed multiple checksums, which means you CAN migrate from one checksum to another pretty easily. However, I didn't use a Merkle tree in the initial design and so I hope to revisit it at some point to improve it. It should be trivial to add an additional checksum to git. Not to replace how SHA1 is currently used, but to add essentially per-commit checksum, which is a checksum of the entire commit contents (including the checksum of the previous commit). It wouldn't be as elegant as using SHA256 in place of SHA1, but at least you could, with some effort, validate the source tree in a cryptographically secure way.

stirner 10y ago
Hacker News doesn't support Markdown comments like Reddit. There are a couple Markdown-like features like italics, but that's it.

9gunpi 10y ago

Git should have been written with pluggable hashes, right. Also, SHA1 could have been invented stronger against collisions in the first place. In the retrospect many decisions which might have simplified current moment's problems are obvious, but in reality of those decisions in the past they never are. This feeling (it's called the retrospective predictability) is not a function of current problem or previous wrong decisions, but the random reality of events in complex systems, open source software implementing fresh ideas in a new way is being random and complex enough for this.

ifdefdebug 10y ago

From the same thread (Peter Gutmann, Fri Feb 24 00:42:36 EST 2017): "After sitting through an endless flood of headless-chicken messages on multiple media about SHA-1 being fatally broken, I thought I'd do a quick writeup about what this actually means. In short: Reports of SHA-1's demise are considerably exaggerated. What CWI/Google have done is confirmed what we've known for a long time, that SHA-1 is shaky. Using a nation-state's worth of resources and a year of time (https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html https://security.googleblog.com/2017/02/announcing-first-sha...), they've shown that, with a very carefully-crafted document, you can create a collision. Their presentation of the results is detailed and accurate, it's the panicked misinterpretation of those results that are the problem." Continues here: http://www.metzdowd.com/pipermail/cryptography/2017-February/031604.html http://www.metzdowd.com/pipermail/cryptography/2017-February... [edit: typo]

simias 10y ago
110,000$ is not "a nation-state's worth of resources". I agree with the rest though, the sky is not falling but people shouldn't react to baseless alarmist claims with baseless overconfident claims.
- StreamBright 10y ago
  Security is quite often about the amount of money you have to put in to get something or somebody hacked. 110,000 USD is in the ballpark of state level players when we are talking about forging documents to avoid any sort of tampering detection. It has practically zero use of small time hackers or script kiddies. Why would anybody invest 110K into a collision? What is the practical use of it?
  - userbinator 10y ago
    In other words, SHA-1 is still nowhere near as insecure as MD5, the latter for which collisions can be generated in seconds on hardware everyone already has.

moonshinefe 10y ago

This reads like a giant "I told you so." circa 2005 "In the next few years, nasty people will teach him the threat model" I'd like to see those very forceful claims substantiated. Git hasn't said moving forward it will never change from sha-1 and 2005 was a far different era than 2017 for crypto. Let's keep that in perspective.

baby 10y ago

1) Yes, Git should move to a better hash function at some point. 2) No, even easy "malicious" collisions in SHA-1 will still not break most of Git's usages. You're already trusting the repo you're pulling because of TLS, you're already trusting the commits you're getting because of peer-review (you read the commit) and a web-of-trust (you trust your collaborators). (And you're trusting commits even more when they're signed.)

junke 10y ago

Found another detailed explanation from Mike Gerwitz: https://forums.whonix.org/t/security-git-general-verification-verifying-whonix-submodules/513/12 https://forums.whonix.org/t/security-git-general-verificatio...

bandrami 10y ago

I don't get why the discovery of a non-preimage attack is causing so much consternation. If the mere existence of collisions is not acceptable to your VCS, then your VCS can't use a hash, period. If you're worried about an intentional attack, it's no closer today than it was last week: the attacker doesn't control the output hash of the collision, or either input.

Taek 10y ago
> If the mere existence of collisions is not acceptable to your VCS, then your VCS can't use a hash, period What? It could use a secure hash. Collisions take more energy than the universe has to discover.
- bandrami 10y ago
  "Secure" is a time-constrained term. But any hash, whatsoever, has collisions, so if collisions are unacceptable, your VCS can't use them. (The point being that a VCS should handle collisions gracefully no matter what has is used.)
  - lmm 10y ago
    No VCS is 100% secure against the possibility of catastrophic failure. If an asteroid wiped out all life on earth there is no VCS that can handle that gracefully. So as long as a hash collision is less likely than that, using a hash and not handling collisions gracefully doesn't make the VCS substantially less safe.

Pharylon 10y ago

Linus in 2005: "But the _real_ security comes from the fact that git is distributed, which means that a developer should never actually use a public tree for his development." And then GitHub happened.

ericfrederich 10y ago

Look at these SHA-1 sums... https://github.com/ericfrederich/sillygit/commits/master https://github.com/ericfrederich/sillygit/commits/master

tokenizerrr 10y ago
That's just brute forcing the first few characters.
cespare 10y ago
28 bits is easy. 160 bits is not easy.

chmike 10y ago

SHA1 is still OK for identifying files. The probability of random collision is still very low. The only problem is for forged collisions. The object store could be modified to support file collision. One way to disambiguate collision is to use a randomly generated byte sequence as SHA1 seed or hashed before the file data. This random byte sequence would behave like a salt and disable any forged collisions. A single seed for the whole repository would be enough. It should remain secret to prevent forging a collision with the two hashes. It's harder but not impossible. To test if a given file is in the object store, one first compute the SHA1 key to use as file name. If no collisions ever occured with an object a file with that SHA1 name will be present in the store. That file contains the usual data plus the second hash computed with the random seed. This second hash could be added as needed to keep backward compatibility and provide silent automatic upgrade. When one need to test if the file is present in the store, one computes the normal SHA1 key and the secondary hash with the seed. We locate the object in the store uisng the first SHA and test for file equality with the randomly seeded hash. Using a faster hash like blacke2 to compute the random seeded hash could mitigate the price to compute two hashes. It should be parameterized this time and the hash size should be variable. If a collision is detected, that is the secondary hash differ, the file is replaced by a directory with the common SHA1 as name. The colliding files would be stored in the directory using the secondary hash as name. Or the files could be packed in a single tar like file with the secondary hash used as file identifier. This should be enough to protect against forged collisions which is the only real problem. The required change to git would be limited. The only serious disadvantage is the need to compute the randomly seeded hash.

crystalmeph 10y ago

Forgive my ignorance. I don't understand the threat model being worried about here. If someone breaks into your CVS/SVN server and rewrites project history, how is that less bad than someone breaking into your remote git repo and rewriting project history? Don't both attacks require a break-in at the server/remote? Or does CVS/SVN have a better method of detecting such a break-in?