Citation needed. When SHA1 was cracked, it cost $110k worth of cloud computing. And there was some restriction on the two files which matched checksums. IIRC it was like the Birthday Paradox — you don’t pick one and find another sharing the same match, but you generate billions of mutations of similar binaries and statistically two would have the same checksum.
Not exactly easy, fast, cheap, or work with all use cases.
I know. That's why I mentioned the difference in difficulty between getting a collision in binary files and git commit objects themselves, and textual sourcecode.
Mutate and check.
That said, no, finding a collision and finding a preimage are very different things, and well the collision attacks on sha1 will involve a lot of guessing and checking, they are not generic birthday or bruteforce attacks but rely on weaknesses in sha-1 to be practical. They also do not make preimage attacks practical.
If the hash function is reversible - as may be discovered through e.g. mutation and selection - that would help find hashes that are equal and maybe also less than.
Practically, there are "rainbow tables" for very many combinations of primes and stacked transforms: it's not necessary to search the whole space for simple collisions and may not be necessary for preimages; we don't know and it's just a matter of time. "Collision attack" https://en.wikipedia.org/wiki/Collision_attack
Crytographic nonce > hashing: https://en.wikipedia.org/wiki/Cryptographic_nonce#Hashing
The attack being discussed is not a brute force attack (or not purely). If the best attack on sha1 was bruteforce than we would still be using it.
> to find `hash(data_1+nonce) == hash(data_0)` differs very little from ``hash(data_1+nonce) < difficulty_level`.
Neither of those are collision attacks (assuming you dont control the data variable). The first is a second pre-image and the second (with equality) would be a normal preimage.
The attack for sha1 under discussion (chosen prefix collision) is finding hash(a+b) == hash(c+d) where you control b and d (but not neccesarily a and c)
> Practically, there are "rainbow tables" for very many combinations of primes and stacked transforms:
What do primes or rainbow tables have to do with any of this? Primes especially. Rainbow tables are at least related to reversing hashes, if totally irrelavent to the subject at hand, but how did you get to primes?
In context to finding a valid cert with a known good hash fingerprint, how many prime keypairs could there be to precompute and cache/memoize when brute forcing.
"SHA-1 > Cryptanalysis and validation " does list chosen prefix collision as one of many weaknesses now identified in SHA-1: https://en.wikipedia.org/wiki/SHA-1#Cryptanalysis_and_valida...
This from 2008 re: the 200 PS3s it took to generate a rogue CA cert with a considered-valid MD5 hash: https://hackaday.com/2008/12/30/25c3-hackers-completely-brea...
... Was just discussing e.g. frankencerts the other day: https://news.ycombinator.com/item?id=26605647
So to get a nefarious file that puts in an exploit or something useful for an attacker AND causes a SHA1 collision is a very very high bar to meet, currently.
Hopefully they replace SHA1 with SHA256/etc before the capability becomes feasible.
Of course, that only gives you about 40 bits to play with (assuming the further you move the timestamp, the easier it is to detect) so it wouldn't be completely sufficient on its own.
Thankfully most source code is plain text. There are mostly trivial ways to encode information in whitespace/etc, but again, the ability to carry some useful information AND commit a SHA1 collision is currently non-trivial. Plus Git has specifically put in some hardening for the existing SHA1 hashes to make this even less feasible in the particular application of a git repo.
A pipe wrench to the back of the head(or social engineering) of some random committer is probably a LOT easier to accomplish.
That said, if your primary nemesis is one the giant nation states(US, China, Russia, Etc) AND you were very high target for them, then all bets are off, as they can pretty much accomplish whatever they want against any individual/small group on the planet. I would imagine most of us are not even remotely in this situation.
a) you can definitively generate content that will be hashed to the same value - this is a given since anything that compresses a source into a much shorter representation allows that by definition (lets ignore feasibility/time/cost)
b) Making a) in a way that the contents are usable for a given purpose, doesn't introduce severe noticeable changes, and plays ball with the remaining stuff (OS, build chains, the context where it's included in, etc) seems to be the actual difficult part
So my conclusion was at the time that in terms of feasibility it's probably easier to hack the chain itself replacing the hash. But again, if there's a master "hash" for whatever artefact is produced that relies on all those hashes it would also need to be replaced?
For a chosen prefix collision you need to be able to hide a few bytes of binary data in the file. Sometimes that is prohibitive but in most file formats that is do-able.
Just because you have a SHA1 collision doesn't mean you can put any bits wherever you want and still have it be a SHA1 collision.
The really hard part is being able to flip whatever bits you want(to achieve some goal, like a RCE or whatever) AND make it a SHA1 collision. This is currently very much an open problem, nobody has been able to demonstrate(that we are aware of).
I think the last time I saw this come up the response was that git will just ignore your attempt to merge a new file if the checksum is the same. So you would have to compromise the repo server directly to replace it.
Similarly, the git commits you merge themselves could have that done - the actual git commit serialization gives you a fair bit of ability to append stuff to it that isn't shown in the UI. That wouldn't affect the signed git commits. But it's still dubious to have the ability to change old history in a checkout.
Anyway, Git is apparently moving towards SHA256 support, so hopefully this problem will be fixed soon: https://lwn.net/Articles/823352/