Reports of SHA-1's demise are considerably exaggerated

I've done a lot of security reviews of backup solutions over the years and nearly universally they use SHA1 for de-duplication. Security professionals have been providing warnings about this practice, but when you are dealing with a cloud backup solution as an example, speed and low compute requirements are a must and it's hard to win the argument when someone tosses "theoretical" onto the table. Well, we are now past "theoretical" and that's what matters.

I just tried out the SHA1 collider: https://alf.nu/SHA1 and created two PDFs containing entirely different bits of text in JPGs. It took seconds and indeed the output of the files were SHA1 identical. This is no longer nation-state level stuff and computing colliding documents to upload to cloud backup providers who de-dupe across the file system and not just restricted within the boundaries of each account could result in the ability to wipe out and change other people's data. At a minimum that could be an annoyance. At worst, it could result in the intentional change of someone's content to cause significant financial or physical harm.

SVN is probably not the only piece of software where you can create a mess solely with the already released collision. It's more like a DOS, and less like actually injecting a malicious payload, but potentially still destructive.

Edit: Perhaps I'm missing the context of "considerably exaggerated"? Are there some examples of people saying the sky is falling?

- [0] https://github.com/multiformats/multihash

SO BIG. For git, most people don't realize in most cases if the repo isn't giant you can use just 96a as a shortcut. I imagine people would be turned off by the sheer size.

And so much for Google's 90 day disclosure period.

It's safer to "join the headless chicken" route, consider SHA-1 officially broken, and start thinking of alternatives.

Why is the difference between collision and preimage so difficult for people to understand...? I'm genuinely puzzled.

This is mostly correct. The commands git commit -S and git tag -s both sign commits and tags, respectively, using GPG. The signature covers only the commit object: the tree's SHA1, the commit/author data, and the commit message, not the entirety of the data.

git's objects' SHA1 is computed, for "file" objects, as "blob " + ascii decimal size of blob + nul + data in the blob. The two PDFs in Shattered are the same size, and thus, have the same git object header. However, naïvely prefixing the two shattered PDFs with their git header results in different hashes; I presume this is b/c the internal state of SHA1 differs from what the constructed data that causes the collision expects. You can see this yourself:

  % ls -l shatter*.pdf
  -rw-r--r-- 1 - - 422435 Feb 24 19:27 shattered-1.pdf
  -rw-r--r-- 1 - - 422435 Feb 24 19:27 shattered-2.pdf
  % { printf 'blob 422435\0'; cat shattered-1.pdf; } | gsha1sum -
  ba9aaa145ccd24ef760cf31c74d8f7ca1a2e47b0  -
  % { printf 'blob 422435\0'; cat shattered-2.pdf; } | gsha1sum -
  b621eeccd5c7edac9b7dcba35a8d5afd075e24f2  -

This is why the diff[1] is as long as it is: each side of the diff is 128 bytes; the two M blocks.

Thus, if you computed a prefix P that started with the git blob header, then some data for your file, and ran this attack, you should be able to create two files that, when committed to git, collide. The two pieces of data in the header don't cause any trouble: the paper's method allows you to control the output size, mostly, so we can mostly choose any size we want; the type is always "blob" and is thus effectively constant.

Now, from what I can gather from the paper, there doesn't seem to be real control over the portion that differs; that's really what we need to take advantage of this beyond just creating collisions. This is a collision, but it's not what's called a chosen-prefix collision. A chosen-prefix collision lets me choose two different prefixes (which gives the attacker much more control over the differences in content, thus it becomes much easier to craft a "good" and a "bad" version); this attack requires both files to have the same prefix.

Now, here is the worst way I can think of as to how I could get a colliding object to you:

Imagine that I can convince someone you trust to sign a commit; this commit contains, either directly or indirectly via an ancestor commit, an object whose hash we will collide.

Now, if I can later get you to download that commit and all its parents, except I substitute one object's data for another's. The signature is still good: I've not changed the commit object in any way; it references objects by SHA1 hash, and the hash hasn't changed, "only" the data.

Here's another scenario, and you don't need signatures in this scheme; if I push a commit to master w/ the "good" version of the object, but before you pull it, I push to you a branch that contains the bad object, then git writes the bad object to your objects folder, under the colliding hash. You now pull master, but git doesn't pull the "good" version of the object, b/c it already has an object with that hash. Your master is now different; I've effectively poisoned your repo with the bad object.

Now, whether you can pull off this stunt or not, IDK. My point is that a) git's signatures don't cover the entirety of the repository, only a now-very-weak cryptographic hash, and b) git is (I believe) subject to object collision from this. But presently I'm not seeing how it can be maliciously taken advantage of. But then, people are really clever.

[1]: https://news.ycombinator.com/item?id=13721633

IOW, for a criminal organization (or just a single criminal) with a huge botnet the direct cost might be closer to $0. Of course there's opportunity cost--botnets are often rented like a cloud service--but that's the case for everything.