Live data from Hacker News

First practical SHA-256 collision for 31 steps. fse2024

twitter.com

61–68 of 68 posts

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

#61

Earlier quoted context omitted.

My point is: why you should change hashing algorithm in GIT ??? Let's elaborate: 1. Do SHA-1 put a security risk in GIT ? 2. Is that practically exploitable in any way? In some application, for example password hashing, SSH MAC, etc, you have good reasons to change hashing algorithm when it became obsolete: because an attacker can be computationally advantaged to crack a password, to compromise the integrity of trans…

I don't need to prove that I can do a thing to prove that a thing is possible and the burden of proof is on you claiming that this isn't an active security problem because that's basically well known and well understood. The only outstanding questions is how-detectable, impactful, and available those attacks are. Specifically the things you need to counter is at least one of the thing in the following list: * Hash se…

If someone can change a committed file inside a git repository , the main problem is that your system is FUBAR. Let's say I'm the attacker and I'm inside I can change committed files and I can generate a collision for each. If my goal is to deface the repository I can insert file with gibberish, i.e. I have a file with source code:

... omissis ...

ptr=calloc(SIZE, sizeof(long));

... etc ...

then I have :

aDjw'pfojqe'rf[24oijgfpoemgl;m,g02ir-9u13]9fu24[efgje2ioprn

Same sha1 hash.

But wait, why should waste 1000 GPU to deface a Git repository when I can simply delete it. I can change the files, I can delete it. It's simply stupid.

An attack with a sense is to change this:

ptr=calloc(SIZE, sizeof(long));

inserting:

ptr=calloc(SIZE-10, sizeof(long));

Now I have a BOF, same hash, only a code review can find the fraudulent change.

This is beyond "I make a collision inserting commented gibberish" , like this:

// adojwqf'pjqeworivhneq;lnvl;dqjnfvljeqrvneljvn

You have to insert a change that works and implement an attack making it invisible.

Good luck with that. I also read in some comments some AI nonsense I find Star Trek bullshit.

> If you still insist on a working example pay me $125k and I'll produce one for you

Even with 100M$ budget, you can't.

But why I even want to do that ? I have access, I can replace the whole repo with one full of exploitable bugs !

So the initial question: "If I change sha-1 in Git with some newer version, is that a security improvement?" . I feel the the answer is "NO".

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

#62
post #61

Earlier quoted context omitted.

I don't need to prove that I can do a thing to prove that a thing is possible and the burden of proof is on you claiming that this isn't an active security problem because that's basically well known and well understood. The only outstanding questions is how-detectable, impactful, and available those attacks are. Specifically the things you need to counter is at least one of the thing in the following list: * Hash se…

If someone can change a committed file inside a git repository , the main problem is that your system is FUBAR. Let's say I'm the attacker and I'm inside I can change committed files and I can generate a collision for each. If my goal is to deface the repository I can insert file with gibberish, i.e. I have a file with source code: ... omissis ... ptr=calloc(SIZE, sizeof(long)); ... etc ... then I have : aDjw'pfojqe'…

Defacing git repositories doesn't even make sense. You won't mess with people's checkouts, its trivial to detect and identify the responsible party. It's the security equivalent of a child throwing a tantrum in their own room. You want to replace it? Everyone that comes after you and tries to push a change will immediately notice like opening the door to the proverbial child's room. You're busted and you've accomplished nothing.

You want to inject malicious code yourself? When it gets caught, or the file is inspected or reviewed you're busted.

This attack has the opportunity to get malicious code injected into a repository that will never show up in a PR, code review, or any existing checkout (so the senior developers that would notice the change most likely will never receive it). This is re-using an existing trusted and known good commit in your history, even the signature on it, to say "yeah this has always been here, this is perfectly safe and hasn't been modified since the author wrote it".

This is far more subtle, sneaky, and extremely valuable as an attack vector (and it gets more juicy, stay tuned) to get targeted vulnerabilities and backdoors into specific software. This isn't a novel attack method, as I mentioned the Linux kernel goes through a very rigorous process just to avoid this kind of attack.

Aside: You keep trying to use gibberish for your bad examples. You don't need to use garbage, that's the point I keep trying to hammer home to you. The added details can be from any generator and isn't constrained to living exclusively in comments. Garbage is what people use as examples for these attacks because its the easiest, and if you can demonstrate it for garbage then it works for any generator. With garbage you've made the point.

Back at the security issue. So now you have a poisoned repo that contains malicious code and is effectively undetectable through normal use. Meanwhile your production artifacts include the unaltered malicious code from the repository. It will remain unchanged and referenced until someone else creates _any_ change to the file you targeted (as once again git doesn't actually store diffs but whole files in a particular commit). That change might be something like a developer adding some print statements to try and diagnose why the CI system is failing.

When another change happens for that file the evidence mostly vanishes or at least is extremely obscured. There will be _some_ object in your repository that has the SHA-1 object, whether its the original or the malicious one depends entirely on when your checkout occurred.

On the receiving end your best case scenario is that the changed code doesn't work and causes weird bugs in your CI system that can't be reproduced in local checkouts and goes away magically as soon as anyone tries to diagnose it. This capability is worth STUPID amounts of money and I would be shocked if this isn't a technique used selectively in the wild by nation states.

SO how do you solve this problem?

* One of the inherent problems is that signatures don't actually cover the content of the commit. This is another regular complaint of git's behavior and would allow you to side-step this issue using the existing signing infrastructure. This is a bandaid but it's what most people argue for as it is significantly less of a lift than changing the hash function. If you're worried about the attack you just have to sign your commits and tags. If you sign your commits NOW without a change to git, you're still 100% vulnerable to this attack. and because the signatures will still be valid is likely to either make someone innocent look guilty of injecting a vulnerability, or will have audits look less closely at the code because it came from a trusted source causing more harm than good.

* Change out SHA-1 to something that isn't as vulnerable to collision attacks. The problem is collision attacks. Let me say that again, the core issue is with collision attacks. If you can create a chosen plaintext or chosen prefix attack the security guarantees of the git ledger goes away. You can't trust it. It needs to be replaced.

* If neither of those are options for you, your third option of protection is to adopt the Linux kernel policies. Releases are done directly from engineer's machines from a trusted known good repo that has patches added by hand by the most senior engineer.

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

#63

Earlier quoted context omitted.

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.

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

#64

It took me a lot of head scratching to exactly understand what this means, so for your information: this is not a full attack and you are safe (for now). If you need a concrete proof: import hashlib m0 = bytes.fromhex(''' c32aef52 512294ba 9db5ed8c 8c8c88ed b2de2765 63a2d14e ec7619cc 93b21182 e5050f50 f0839b60 7b1ee176 aaa06d68 c462343c 67898962 9558f495 04281f2c ''') m1 = bytes.fromhex(''' 5d0f5ae6 05e98311 8fa3c73a…

There was a practical collision attack on 28 rounds in 2016. Only 3 rounds of progress in 8 years is a pretty good sign for sha256. For new code it might be better to use blake2b, blake3 or sha3, but at the same time I don't think there is any rush to migrate existing systems away from sha256.

Indeed. SHA-2 is unexpectedly stronger than the expectation a decade ago.

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

#65
post #46

This is a good time to re-read JP Aumasson's "Too Much Crypto" post: https://eprint.iacr.org/2019/1492.pdf The comparison is probably broken in a variety of ways, but the Keccak team proposed KangarooTwelve, a 12- (1/2 as many) round Keccak variant, after a practical attack on 6-round Keccak was published.

I noticed blake3 uses 7 doublerounds, i.e. 14 chacha rounds. Is it intended due to increased communication or another bug?

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

#66
I understand the definitions of such crypto algorithms but have no idea about differential cryptanalysis. Can someone explain how attacks like this are constructed, and why it took 8 years to advance cryptanalysis by 3 rounds? What insight was needed that took 8 years to discover and formulate as a practical attack?

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

#67

Earlier quoted context omitted.

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

1) yes, I gave you an example of a hash algorithm that is broken right now. SHA1 is only getting there, because the attacks are always only getting stronger. Responsible people don't wait until the attacks are practical and devastating, but instead react by predicting the obvious things that will happen in the future.

Overall I don't think you're arguing in good faith, so I'm going to walk away from this discussion.

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

#68
post #57

Earlier quoted context omitted.

It is used to name a a commit, not to sign it. So the data structure itself will be corrupted if there is a collision, as it relies on the invariant that each commit has a unique name. And the collision has to happen within a single repo.

> It is used to name a a commit, not to sign it. This is bullshit. Really. If you have only to "name a a commit" you can use a sequence from 0 to N. Why someone should waste computation power to calculate an hash that's also a naming system really not user friendly? Think about it. The correct answer is to signing the commit AND for database indexing: "Git uses hashes in two important ways. When you commit a file int…

Earlier systems like perforce used the totally ordered integer naming scheme you describe, but it requires a centralized entity to keep the names globally unique. Using hashes for naming avoids this, and the way they are used in git imposes a partial order.
Post reply on HN