Good that git still use sha1 ;)
[deleted]
First practical SHA-256 collision for 31 steps. fse2024
41–50 of 68 posts
Re: First practical SHA-256 collision for 31 steps. fse2024
#42Earlier 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…
Birthday attach is a real attack and often useful in practice. "Just use brute force" is a huge oversimplification, but the SO link explains it in more detail.
One time pad is not a hash algorithm so obviously a generic attack on a collision function doesn't apply to it.
Re: First practical SHA-256 collision for 31 steps. fse2024
#43Good 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…
I believe there is one more step. You have to somehow get the collision into the repository. Because if you have in your own repo and pull something from another repo with the same , the remote changes will not overwrite your blob for (it will stay the same). Or at least that’s what I seem to remember from something that Torvalds wrote.
Re: First practical SHA-256 collision for 31 steps. fse2024
#44Earlier 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.
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 progra…
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 transmitted packets, etc.
But not because an hashing algorithm became obsolete for some application is obsolete for ALL possible application. Moreover, in some specific application could be DESIRABLE a fasted hashing algorithm.
So why You should change SHA-1 in GIT ?
>> "But a few more of these tricks and I can see those "garbage comments" collision happening"
I don't think so, is computationally astronomically difficult whatever tricks yo u invent. The point here IS NOT to generate a collision adding "garbage comments", again, is to alter the behaviour of committed code in a functional way.
>> "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"
Yeah, prove it!
Re: First practical SHA-256 collision for 31 steps. fse2024
#45Earlier quoted context omitted.
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 c…
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...
Re: First practical SHA-256 collision for 31 steps. fse2024
#46This 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.
Re: First practical SHA-256 collision for 31 steps. fse2024
#47Earlier quoted context omitted.
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?
[deleted]
Re: First practical SHA-256 collision for 31 steps. fse2024
#48“Steps” means “rounds” here. For the general advances see the table under https://en.wikipedia.org/wiki/SHA-2#Cryptanalysis_and_valida... .
In 2016 there was a practical collision attack for 28 rounds. At that rate of progress, a practical collision attack for all 64 rounds would be reached in around 90 years from now.
Re: First practical SHA-256 collision for 31 steps. fse2024
#49It 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.
Re: First practical SHA-256 collision for 31 steps. fse2024
#50Good that git still use sha1 ;)
Good old MDA4. Nothing beats that.