Hash collision in git

by

Picking atoms on 10 Moons

An SHA-1 hash is a 40 hex character string… that’s 4 bits per character times 40… 160 bits. Now we know 10 bits is approximately 1000 (1024 to be exact) meaning that there are 1 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 different SHA-1 hashes… 1048.

What is this equivalent of? Well the Moon is made up of about 1047 atoms. So if we have 10 Moons… and you randomly pick one atom on one of these moons… and then go ahead and pick a random atom on them again… then the likelihood that you’ll pick the same atom twice, is the likelihood that two given git commits will have the same SHA-1 hash.

Expanding on this we can ask the question…

How many commits do you need in a repository before you should start worrying about collisions?

This relates to so called “Birthday attacks”, which in turn refers to the “Birthday Paradox” or “Birthday Problem”, which states that when you pick randomly from a given set, you need surprisingly few picks before you are more likely than not to have picked something twice. But “surprisingly few” is a very relative term here.

Wikipedia has a table on the probability of Birthday Paradox collisions. There is no entry for a 40 character hash. But an interpolation of the entries for 32 and 48 characters lands us in the range of 5*1022 git commits for a 0.1% probability of a collision. That is fifty thousand billion billion different commits, or fifty Zettacommits, before you have reached even a 0.1% chance that you have a collision.

The byte sum of the hashes alone for these commits would be more data than all the data generated on Earth for a year, which is to say you would need to churn out code faster than YouTube streams out video. Good luck with that. 😀

The point of this is that unless someone is deliberately causing a collision, the probability of one happening at random is so staggeringly small you can ignore this issue

“But when a collision does occur, then what actually happens?”

Ok, suppose the improbable does happen, or suppose someone managed to tailor a deliberate SHA-1 hash collision. What happens then?

In that case there is an excellent answer where someone experimented on it. I will quote from that answer:

  1. If a blob already exists with the same hash, you will not get any warnings at all. Everything seems to be ok, but when you push, someone clones, or you revert, you will lose the latest version (in line with what is explained above).
  2. If a tree object already exists and you make a blob with the same hash: Everything will seem normal, until you either try to push or someone clones your repository. Then you will see that the repo is corrupt.
  3. If a commit object already exists and you make a blob with the same hash: same as #2 – corrupt
  4. If a blob already exists and you make a commit object with the same hash, it will fail when updating the “ref”.
  5. If a blob already exists and you make a tree object with the same hash. It will fail when creating the commit.
  6. If a tree object already exists and you make a commit object with the same hash, it will fail when updating the “ref”.
  7. If a tree object already exists and you make a tree object with the same hash, everything will seem ok. But when you commit, all of the repository will reference the wrong tree.
  8. If a commit object already exists and you make a commit object with the same hash, everything will seem ok. But when you commit, the commit will never be created, and the HEAD pointer will be moved to an old commit.
  9. If a commit object already exists and you make a tree object with the same hash, it will fail when creating the commit.

As you can see some cases are not good. Especially cases #2 and #3 mess up your repository. However, it does seem that the fault stays within that repository, and the attack or bizarre improbability does not propagate to other repositories.

Also, it seems that the issue of deliberate collisions is being recognised as a real threat, and so for instance GitHub is taking measures to prevent it.

More Related Contents:

  1. How does Git compute file hashes?
  2. How does the newly found SHA-1 collision affect Git?
  3. How would Git handle a SHA-1 collision on a blob?
  4. How to assign a Git SHA1’s to a file without Git?
  5. Git – finding a filename from a SHA1
  6. How can I pass git SHA1 to compiler as definition using cmake?
  7. Git – finding the SHA1 of an individual file in the index
  8. How does Git track history during a refactoring?
  9. Git is moving to new hashing algorithm SHA-256 but why git community settled on SHA‑256
  10. How is the Git hash calculated?
  11. In Git, what is the difference between long and short hashes?
  12. A Regex to match a SHA1
  13. Break a previous commit into multiple commits
  14. git status shows modifications, git checkout — doesn’t remove them
  15. Git merge reports “Already up-to-date” though there is a difference
  16. How do I diff the same file between two different commits on the same branch?
  17. How can I get Git to follow symlinks?
  18. Prevent commits in master branch
  19. Install npm module from gitlab private repository
  20. What does ^{} mean in git?
  21. Visual Studio Code cannot detect installed git
  22. How to update a git shallow clone?
  23. How to handle a large git repository?
  24. gitolite push error -> remote: ENV GL_RC not set
  25. How to merge specific files from Git branches
  26. Error: Cannot pull with rebase: You have unstaged changes
  27. Git refuses to reset/discard files
  28. How to find the N largest files in a git repository?
  29. What’s the difference between git stash save and git stash push?
  30. Telling if a Git commit is a Merge/Revert commit

Leave a Comment