Hacker News Reader

Comment by jl6 | Hacker News Reader

I assume “steps” here means rounds? For reference, standard SHA-256 is 64 rounds.

SHA-2, including SHA-256, is constructed using a Davies–Meyer compression function. That compression function starts with a block cipher - so an object like AES, but with wider keys and wider block size. For SHA-2 this block cipher is called SHACAL-2.

Now what we're seeing here is an attack on SHA-2 assuming a very, very significant degradation in SHACAL-2, where we run far fewer rounds than assumed in the standard. This is your typical cryptoanalytical result, interesting, but it is very very far from showing that "SHA-2 is broken".

As a side note I once estimated that the Bitcoin network is likely to produce a collision in SHA-256 sometime in 2050s, assuming the current rate of growth of the hash throughput. Of course that's a big assumption, and also nobody will notice the collision, as nobody is saving all those past hashes :)

Another side note - if you're interested in learning about hash functions then I recommend looking into SHA-3. Not because it's newer and shinier, but because I think it is actually the easiest to understand. It has a very clever design.

I wonder, given the current rate of development when will there be the first collision in the hashes of the Linux kernel git repository. Wait, did git finish the switch to SHA-256 or is it still using SHA-1. Googling... all I can find suggests that everyone is still using it with SHA-1 and SHA-256 repos aren't compatible with SHA-1 repos (whatever that means exactly).

So tldr is "it's in progress".

You can use SHA-256 in production. And you can convert SHA-1 repos into SHA-256 repos.

However:

- SHA-1 repos are not compatible with SHA-256 repos so you can't mix and match the trees (i.e. a SHA-256 fork couldn't upstream their commits to a SHA-1 repo).

- The conversion path from SHA-1 to SHA-256 will break all GPG signatures on the repo.

- There may be breaking changes to the SHA-256 repository implementation in the future however those changes will be guaranteed to come with an upgrade path for any users of the existing SHA-256 implementation.

So it's viable as an option but it's by no means "blessed" like the existing SHA-1 impl is.

Thanks!

I would only add that an organic (accidentally created) hash collision in Git will take an extreme amount of time. However, even today you can download the two PDFs from https://shattered.io/, put them both in your Git repository and watch Git crash. Given the construction of SHA-1 (Merkle-Damgard), it is easy to create an unlimited amount of derivative files that also cause a collision, they just have to have the correct prefixes (and then arbitrary but identical suffixes). Or upload only one of such files, but later pretend that it was the other. Authors were even kind enough to create a file tester on that very website :), but note that a determined adversary can recreate the attack and create a different set of prefixes.

SHA-1 really is broken, and therefore standard Git repositories do not offer integrity protection against someone who is determined to do harm and has some resources.

git has been using the hardened variant of SHA-1 for ages, so the shattered.io files haven't had that effect for a long time.

Edit: Since git 2.13, released about a month after SHAttered was published in 2017: https://github.com/git/git/blob/master/Documentation/RelNote...

A hardened variant which to this day still has not been documented anywhere.

Really disappointing and terrible for interop.

I think IPFS's IPLD facility for integrating git"s blockchain has it documented as part of discussions on how to offer splitting of git objects as they naturally can be gigabytes.

Additionally, AFAIK, none of the major repo hosting services (GitHub, gitlab, Bitbucket) support sha-256 repos.

This is true however that is changing very soon now that SHA-256 is no longer marked experimental.

GitLab has been working on integrating SHA-256 support for a while. According to this comment[1], there's only one major blocker left (which seems to be completed at the time of this comment) before they can start testing SHA256 support on GitLab.org.

1. https://gitlab.com/groups/gitlab-org/-/epics/10981#note_1797...

Yes, the follow-up post (hidden by default) reads:

> Don’t panic, folks. This is very good work, especially given the low memory complexity of this attack. But there are 33 steps left. Your bitcoins are safe.

Reply on news.ycombinator.com