Basically you collide a hash like SHA-1 or MD5 by getting it into a state where transitions don't twiddle as many bits, and then smashing the remaining bits by brute force trial. But, such states are weird so from inside the hash algorithm you can notice "Huh, this is that weird state I care about" and flag that at a cost of making the algorithm a little slower. The tweaked SHA1 code is publicly available.
If you're thinking "Oh! I should rip out our safe SHA256 code and use this unsafe but then retro-actively safer SHA1" No. Don't do that. SHA-256 is safer and faster. This is an emergency patch for people for whom apparently 20 years notice wasn't enough warning.
In theory the known way to do this isn't the only way, but, we have re-assuring evidence for MD5 that independent forces (probably the NSA) who have every reason to choose a different way to attack the hash to avoid detection do trigger the same weird states even though they're spending the eye-watering sum of money to break hashes themselves not just copy-pasting a result from a published paper.
What is possible now is something that is much easier: if you have enough money and time, you can create 2 commits with the same hash, which start with some different parts, which may be chosen arbitrarily, then they have to include some parts that must be computed to ensure that the hashes will match and which will be gibberish that might be disguised in some constants or some binary blob, if possible.
Then you can commit one of them and presumably you can later substitute the initial commit with the other one without anybody being able to detect the substitution.
How? Which operation would be involved? Will it not show anywhere else(reflog)?
In short, it's a method of storage where object's identity is derived from object's content (usually via hashing it). So the assumption is: same hash => same content => same object.
What you could do however is just host it yourself somewhere else, say put it on a fork. Or if you have access to the actual repository hosting the original version, you could just manually replace it yourself. git clients aren't going to just automatically pull the "new" version though so you'll have some combo of people with the old and people with the new, and it gets a little messier from there.
you need to modify the object store manually, so access to the filesystem
See https://stackoverflow.com/questions/65870508/git-and-sha-256
Even attacking SHA2-256/128 would be quite difficult as I understand it, even though it's the same length as MD5.
Truncated hashes also of course have the great property that they mitigate the length extension in Merkle-Damgard
To be fair, this is totally irrelevant to git, since the attacker knows the whole message and can just recompute the extra bits themselves. That said:
> I was surprise that no one suggested truncating SHA-256 to 160 bits (same as for SHA2-256/224, or SHA2-512/256). The attacks on SHA-1 are not directly based on the length of the hash, they are based on weaknesses in the algorithm.
Very seconded. You could even shove the extra 96 bits in a optional metadata field and have new versions of git throw up a giant air-raid-siren-level error if they don't match (since that will never happen by accident[0]) and still have the full 256-bit-hash worth of security for most purposes. Git already allows (arguably encourages) people to truncate hashes to 28 bits or so at the UI level, so there's precendent for that already.
0: You do not have anywhere near 2^80 commits in the world, much less in the same repo.
To do that, you have to stop generating commit hashes with SHA-1, breaking compatibility with existing git clients.
And if you're going to do that, you might as well just use the whole SHA-256 hash, since compatibility is out the window already.
You need a collision. You also need it to be syntactically correct. You need it to not raise any red flags if you are contributing a patch. And ultimately you need it to do what you want.
That's a pretty tall order.
You could even vary whitespace until it fits, like spaces at the end of lines.
For example, suppose you started with a commit graph that looked like this:
C1 --- C2 --- C3
\ \ \
T1 T2 T3
\ \ \
F1 - - F2 - - F3
C1 --- C2'--- C3
\ \ \
T1 T2' T3
\ \ \
F1 - - \ - - F3
\
F2'
Indeed. I'd add that this is, in my, experience one of the biggest sources of misunderstanding for people new to git. It isn't helped by the fact that a lot of git introductions (well-meaningly) emphasize diffs between commits.
Darcs (http://darcs.net/) is an example of a truly patch-centric DVCS. While I think git is great and that its ubiquitousness has made the world better, I'm always a bit sad when reminded of what could have been with Darcs (for all its problems).
The problem would be if a clone doesn't fetch the new version of the patch and generates a new commit that would conflict with the modified commit. You're changing the base all the future diffs are based off of. It might just jumble the source essentially corrupt the file, but I'm not sure.
There is some work going on to change this, but it's not an easy task:
Just for fun: to get a 5% chance of a hash collision between ANY two numbers in an 160 bit space, you'd have to generate 3.9e23 hashes.
So you'd have to generate 1000 hashes per second for *12 trillion years.*
Formula:
n = sqrt(2 * 2^160 * ln(1/(1-0.05))
https://en.wikipedia.org/wiki/Birthday_problem#Probability_o...
There's also the case for auditing: force pushing into an existing repo triggers an event in GitHub and is logged. While the logging event can be missed, it leaves a paper trail.
With things like reproduce-able builds, this also becomes harder. Distributing (through a means of a fork, or putting it up on a website mytotallylegitgitrepos.com) source code which builds into a binary which doesn't match upstream hash is suspicious.
Auditing helps if they try to force push the original repo, but doesn't protect vs someone redistributing malicious clones of the repo.
Reproduceable builds do help, but only for projects that can take advantage of it...
Instead what you would do is attempt to make a file-object that has a certain SHA1 hash identifying it, and a colliding file-object that has the same SHA1 hash. Then you are free to give people who clone the repository different file contents depending on when/who/how someone requests it (if the file content is hosted on github, how to change the file object identified by a given SHA1 hash is an additional hurdle since it's assumed to be immutable and indefinitely cacheable; if you control the host yourself you can just change it whenever you like).
Git's uses SHA-1 for unique identifiers, which is technically okay as long as they are not considered secure. If git were designed today it would probably use SHA2 or SHA3 but it's probably not going to change due to the massive install base.
Edit: anyone know if git's PGP signing feature creates a larger hash of the data in the repo? If not maybe git should add a feature where signing is done after the computation of a larger hash such as SHA-512 over all commits since the previous signature.