Live data from Hacker News

First practical SHA-256 collision for 31 steps. fse2024

twitter.com

31–40 of 68 posts

Re: First practical SHA-256 collision for 31 steps. fse2024

#31
post #21

Earlier quoted context omitted.

You can find this in any introduction to cryptography textbook/course. "Generic attack" is a common term for "just use brute force" [1]. It's called "generic" because it works regardless of the implementation of the primitive. For pre-image resistance the generic attack just hashes messages until it finds the right image, for collision resistance you can get a quadratic speedup via the so called birthday problem / bi…

I don't think that "look, raw brute force has this property" is at all useful in this context where you'd obviously actually compare a real attack not brute force. There's no reason to believe (and every reason not to) that the same property somehow applies. That Stack Exchange answer also immediately set off alarm bells in my head because it pretends to be entirely generic, but the obvious thing to do with entirely…

[deleted]

Re: First practical SHA-256 collision for 31 steps. fse2024

#32
post #22

Earlier quoted context omitted.

For the choices after your "OR at least" line, just consider that most of the collision material could be padded into a comment, so achieving a), b) and d) would be "trivial."

IMHO "be padded into a comment" is included in "is valid code", still 1 in is a good approximation of that probability. Please, correct me if I'm wrong.

Do you mean with the current public knowledge or hypothetically? For md5 all of these are doable right now (except maybe code that "makes sense"for human reader). Also in practice it's much easier to do this with a data file, as demonstrated for SHA1 with a "backdoored" certificate.

Re: First practical SHA-256 collision for 31 steps. fse2024

#33
post #28
post #9

Earlier quoted context omitted.

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.…

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.

Re: First practical SHA-256 collision for 31 steps. fse2024

#34

Earlier quoted context omitted.

IMHO "be padded into a comment" is included in "is valid code", still 1 in is a good approximation of that probability. Please, correct me if I'm wrong.

Do you mean with the current public knowledge or hypothetically? For md5 all of these are doable right now (except maybe code that "makes sense"for human reader). Also in practice it's much easier to do this with a data file, as demonstrated for SHA1 with a "backdoored" certificate.

1) We are talking about sha1, md5 is out of topic

2) This is the main topic ! Being able to generate >>valid code>specific purpose3) A.K.A your answer is total nonsense.

Everyone else, ok, I'm listening, give proof that you can change code on GitHub stealthy messing with hashing, moreover inserting a "payload" creating a SHA-1 collision in a reasonable computational time, everything else is BS.

Re: First practical SHA-256 collision for 31 steps. fse2024

#35
post #28

Earlier quoted context omitted.

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…

Thanks!

Re: First practical SHA-256 collision for 31 steps. fse2024

#36
post #22

Earlier quoted context omitted.

For the choices after your "OR at least" line, just consider that most of the collision material could be padded into a comment, so achieving a), b) and d) would be "trivial."

IMHO "be padded into a comment" is included in "is valid code", still 1 in is a good approximation of that probability. Please, correct me if I'm wrong.

Even without comments your additional requirements aren't relevant, but not in the way I think you're assuming.

When you're searching for a practical collision you only need a way to generate systematic output that semantically will be interpreted with your intent. The easiest way to do this is to include semantically irrelevant data to something that was manually produced that is semantically relevant.

In the programming domain, source code specifically, comments are the easiest way to include semantically irrelevant information but you could also include unused functions, variable names etc. You are literally limited by the constraints of your imagination and your ability to dodge CI failure checks.

Aha! You might say, but any human that saw that change or PR would immediately notice the garbage produced and catch the collision attempt! (this is your argument) Unfortunately no, that assumes your search space that I talked about is over semantic garbage. It's a bit more work, but your search space for a collision could be "Shakespearean sonnet's that would make a literary buff cry" as long as you had a generator that could produce it and produced different outputs from different seeds.

We now have access to a generator that can take an incrementing seed number, and produce both semantically meaningful and meaningful semantically irrelevant content. The language models. Interestingly this moves the compute cost to the generator (usually the compute restriction is on the hash being attacked).

It's definitely not practical with our current compute capabilities to attack a search space of 2^256 through brute force for a simple hash much less including waiting for a language model to produce an output using a different input seed for each check but that's not what this article is about either...

What these collision attacks (such as the linked article) do is _decrease the search space_. Without any algorithmic tricks the search space for sha2-256 is 2^256. These tricks are eating away at that exponent. This work results in a reduction of a collision to 2^49.8. That is a massive drop in the search space. Is it still feasible to attack today? Absolutely not. But a few more of these tricks and I can see those "garbage comments" collision happening, but wait a tiny little fraction of a time beyond that and include language models for your search space?

Hell your changes could be _productive_ and produced incrementally through a series of commits if you really wanted to limit your search space and get creative about it.

With SHA-1 collisions attacks using semantic garbage are already considered practical. We're still probably computationally constrained in using language models to produce semantically viable collisions but we're not that far off either. Those comments won't be garbage. You will not be able to distinguish it from any other AI generated code being committed which is rapidly improving in quality and efficiency to generate.

Even without language models you could use something like a language's EBNF grammar as a token generator for source code which would probably pass any glance checks, but definitely not dedicated inspection like a code review. That is probably something that IS PRACTICAL TODAY for SHA1.

Re: First practical SHA-256 collision for 31 steps. fse2024

#37
post #12

Good that git still use sha1 ;)

Is it used to sign a commit, right ? Which are the probabilities to have a collision that: a) is still code b) is still code AND is code similar to a previous commit c) is still code AND is code similar to a previous commit AND is valid d) is still code AND is code similar to a previous commit AND is valid AND makes sense for something OR at least a) is still code b) is still code AND is valid d) is still code AND is…

Doesn't it also have to be the same size in bytes?

Re: First practical SHA-256 collision for 31 steps. fse2024

#38
post #12

Good that git still use sha1 ;)

Is it used to sign a commit, right ? Which are the probabilities to have a collision that: a) is still code b) is still code AND is code similar to a previous commit c) is still code AND is code similar to a previous commit AND is valid d) is still code AND is code similar to a previous commit AND is valid AND makes sense for something OR at least a) is still code b) is still code AND is valid d) is still code AND is…

Due to the way hashing works, any change is equivalent to any other one for the purpose of finding a collision.

So you can just alter the formatting to a different convention, alter spacing, add a comment, reorder equivalent lines.

So you can insert a comment and continue altering it until you get a match by varying the line breaking, switching words with synonyms.

Re: First practical SHA-256 collision for 31 steps. fse2024

#39
post #28
post #9

Earlier quoted context omitted.

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.…

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).

[deleted]

Re: First practical SHA-256 collision for 31 steps. fse2024

#40
post #28

Earlier quoted context omitted.

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…

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.

Post reply on HN