Random collisions in 160-bit space are incredibly unlikely. This is talking about intentional collision, and means that it's entirely feasible for someone with significant compute power to create a git commit that has the exact same hash as another git commit. This could allow someone to silently modify a git commit history to e.g. inject malware or a known "bug" into a piece of software. The modified repository would be indistinguishable if you're only using git hashes.
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.
The defence used by GitHub specifically defends against these intentional collisions, not some mirage of random collisions.
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.
So, if I understand correctly: the patched SHA-1 code generates the same hash, but is has checks on the internal state so that it will flag inputs which are likely to be intentionally colliding?
It is not yet possible "to create a git commit that has the exact same hash as another git commit" in the sense that if someone else has already done a commit you can make another commit with the same hash.
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.
It doesn't take any money or time. Google's break of SHA-1 was fully reusable. So long as committing a PDF to the repo counts, there's a script that will trivially concat two PDFs in such a way as that they each render to their original (different) contents, but both have the same SHA-1 hash. Put in a repo and `git add foo.pdf` and you're done.
Nope. Google's break of SHA-1 was reusable in the sense that you can add an arbitrary (identical) suffix to both PDFs and keep the collision. But Git does not use raw SHA-1 hashes, it adds a prefix before computing object hashes. Therefore, Google's break of SHA-1 cannot be reused to break Git.
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.
I would think it's not that simple because `git push --force` doesn't do anything if it thinks the histories are the same, and in this case we've created a history that appears to be the same. You'd likely need a custom git client (which isn't a problem) but I don't know enough about the internals of a git push to know if the server would even accept objects if they match hashes of objects it already has (it may just go "I don't need that" and ignore it, because what's the point in doing anything with it?). Presumably it would depend on the exact server implementation whether you could get it to replace an existing object with a "new" one which is actually the same hash, but frankly I think that's unlikely because it would be pointless work from the view of the server. If it does happen I'm not sure what auditing you would actually be able to see, webhooks and such might not be triggered because the history didn't actually "change".
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.
If you can force push, why would you then not push a different commit before pushing your updated commit with the same, original hash, or does that also not work?
I wouldn't expect that to work reliably because git doesn't actively remove unused objects from the store, hence why you can do `git reflog` to go find stuff that's not actually referenced anywhere anymore. `git gc` is necessary to make them actually go away, and whether that ever happens and how often is up to the server. I know for example that Github practically never does it, and even if it did happen it would be hard to reliably ensure no references to the relevant object still exist anywhere on the server. For example, you would have to force push every branch on the server that references the object, and if the git server creates branches for internal use you might not be able to touch those or convince the server the object is unused. And even if all the references are gone if the object is never actually deleted from the server then it should just get used again if you try to do a `git push`.
As of January 2021, SHA256 repositories are supported, but experimental. They can be created with `git init --object-format sha256`. If I understand correctly, they don't mix at all with SHA1 repositories (i.e. you can't pull/push from/to between SHA1 and SHA256 repos).
Here is discussion [1] on the issue on the Git mailing list at the time with some useful context WRT git. Unsure what current status is. Git 2.29 Had experimental support for sha256.. not sure what it’s current status is, but that was a year ago.
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.
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
> 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.
Yep. GitHub is saying they would block an object that looked like it was crafted to produce a collision using SHAttered, and hasn't seen it, intentionally or otherwise, in the wild.
> This could allow someone to silently modify a git commit history to e.g. inject malware or a known "bug" into a piece of software.
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.
All you need is one variable sufficiently large that you can change until you find a collision, such as a comment (which about all languages allow) or a meaningless number.
You could even vary whitespace until it fits, like spaces at the end of lines.
Commits aren't patches. They contain the whole tree. Retroactively changing a commit can't possibly introduce conflicts with other commits on top of it, the worst it can do is introduce big funny-looking diffs.
It's true that semantically git commits store the whole tree but doing that naively would be inefficient. Instead, packfiles will store some objects as deltas which could either result in inconsitencies or noticeable knock-on changes if the original object contents are changed.
While that's true, I'd be very surprised if git delta-compressed the commit objects themselves. Changing a commit to point at a different tree wouldn't impact the delta-compressed packings of any file blobs, it would just change the actual file the commit points to.
For example, suppose you started with a commit graph that looked like this:
Where C1, C2 and C3 are commits; T1, T2 and T3 are the trees they reference; and F1, F2 and F3 are three versions of a file blob stored delta-compressed in your packfile. Then if you had a malicious version of C2 with the same hash you could replace C2 with a new commit C2' pointing at a new tree T2' with a new file object F2', and nothing would break. The resulting commit graph would look like this, and F1, F2 and F3 would all still be in your packfile delta-compressed and accessible, just with nothing referencing T2/F2:
Regardless, this is all moot to some extent. The attack most everyone talks about is that if you were in control of a central git repository (for example if you were hosting a mirror of an open source repository), you could give two different versions of that repository to different people without them being able to tell, even if they were checking PGP signatures or referencing specific git hashes. For example you could serve the non-malicious files to human developers, and when a user-agent that looks like a CI/CD pipeline such as Jenkins or the Ubuntu/Debian/RedHat packager's build machine or someething clones the repository to build a specific hash requested by the user, give it a malicious version of the source tree that builds a backdoor into the binaries it creates. In this sort of attack you never have to "change" a git object on someone's machine which is something the git protocol naturally isn't designed to do because it never happens naturally.
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).
Well, the contents of the commit is a patch plus metadata. They point to a parent commit, and layer themselves in the tree.
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.
Contents of a commit is not a patch, it's the whole tree. The got ui presents it as a patch, but that's generated at runtime by the "git diff" command.
It does internally use delta compression to save storage space, but it's not necessarily a straight delta between a commit and its direct ancestor (and that's just an internal optimisation).
From a practical point of view, how would injecting malware happen? If you're trying to insert a malicious diff somewhere deep in the git history, you would need to recompute all the other commits after the injected commit - which would most certainly change their commit ids too if they are touching the same file. When other commit ids change, the malicious change becomes detectable.
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.
Presumably the attacker would modify the most recent commit which edits the file that they are targeting. It is true that the attack becomes more difficult if you try to target an older commit.
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...
Every commit references every file. If you change the content of an old commit you would only affect people who check out the old commit. So this is utterly pointless and not what someone would do.
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).
> A higher probability exists that every member of your programming team will be attacked and killed by wolves in unrelated incidents on the same night.
Just to nitpick, I don't think that formula is valid. We're primarily interested in "unrelated" wolf attacks, but it counts the total fatalities, not the total number of fatal incidents. If we count each fatal attack as only one incident, regardless of the casualties, we get 2^-258 instead.
But of course we also need to take into account where the 6-member team lives. If they all live in West Bengal, India, the consideration is much different than if our developers live in Atlanta. Atlanta doesn't have any wild wolves. There is a Wolf's guenon in the zoo, but that probably doesn't count as a risk because they mostly eat small animals and also are monkeys.
This is why I always get mad when people say something like "you are more likely to be struck by lightning than eaten by a shark!".... we'll, that REALLY depends on where you are.
There's only 10 fatal shark attacks per year. What's your calculation for the sharkiest area to live? It has to be something like 100+ times sharkier than average for your claim to be true. And keep in mind that half the US population can easily day trip to the ocean.
Edit: Actually, that's using a number of 2000 lightning fatalities which might be 10x too low. And lightning injuries are another 10x higher than that. So you'd need somewhere that shark attacks are a thousand or ten thousand times more likely than average. That's also without interpreting "eaten" literally...
You focused on the shark side and not on the lightning side. You will never get struck by lightning in a city, so there the probability is 0. Similarly if you go out swimming in the ocean on a sunny day the probability of getting struck by lightning is also 0, but the probability of getting eaten by a shark is not 0.
You're going too granular. This is about populations that live in certain areas, not specific people on specific days. "depends on where you are" when talking about an over-time risk ratio. The goal isn't to find some dude with weird habits.
And while a population that mostly stays inside a city has a reduced lightning chance, it also has a reduced shark chance. I don't think that's anywhere near the point of equalizing the rate.
If you have an idea for a factor that dramatically reduces lightning risk but doesn't reduce shark risk much, I'm interested.
Like I said in my other comment, it's not about finding one specific guy. Picking a place where people live is a reasonable starting point for making a rebuttal to a general statement like that. I don't think pointing at Fisherman Sam is.
> And if I live in a place where there is very rarely lightning, that chance gets really low as well.
How low can that number go? The numbers I picked made consideration for some amount of variation in lightning. Does lightning have a huge variance?
It's important to have real numbers when you're making the claim that there are places where the lightning:shark ratio is multiple orders of magnitude lower than the average. That's not a claim you can justify by merely pointing out that the risks will vary by ___location.
That's a good point! I didn't think about either of those issues. The second one raises the average team's chances of such a spate of unrelated attacks significantly, if anything related to this formula could be said to be significant, because the increase in risk to teams in West Bengal and Ukraine is enormously larger than the decrease in risk to teams in Atlanta.
This is problematic because it must be 2774 years ago, when wolve attacks were substantially more common. I'm also not thrilled that a good chunk of my dev team lives near the Lupercal. The one good piece of news is that at least one of my headcount is fated to die by the hand of man, which might bring the odds of simultaneous wolf attack deaths down to zero unless he quits beforehand.
> Aside from being bullshit, it's also irrelevant, since we're discussing a collision being generated on purpose, not by accident.
I think you just pointed out the error in your own reasoning. This is defending against a deliberate attack. Therefore, your proper odds would be that your programming team is deliberately set upon by 6 different wolves. So, have they offended people who have access to 6 wolves, and the time and inclination to train them (or hire others to) in an effort to pull off a murder spree?
Edit: Actually, the hash attack already assumes motivation and skill. So, I don't know what the odds would have to be computed. That at least one programmer on your team could fight off a trained attack wolf (to whatever level of "training" is the current state of the art for attack wolves)?
This is stupid. The probability of any attack happening at random is close to zero. E.g. the probability of a buffer overflowing just right to give you a shell through random chance is less than being eaten by wolves.
The question is about the risk of someone intentionally performing the attack, not the probability it will accidentally happen at random.
I wonder how much money in Bitcoin they would have made if they had used those hashes to mine instead.
Speaking of which, it would be funny if they were pretending to do security research but added a secret backdoor to mine bitcoin instead, somehow exporting those hashes or using the partial results of SHA-1 calculations (BTC isn't SHA-1).
I'm just joking, but I wonder if that's possible. If anyone is Machiavellian enough for that, it's security researchers.
> When disagreeing, please reply to the argument instead of calling names. "That is idiotic; 1 + 1 is 2, not 3" can be shortened to "1 + 1 is 2, not 3."
I only half joke when I ask, when you break a cryptogrpahic hash, does it mean that now it's just a really amazing compression algorithm, but with a very heavy compute requirement? The non-joking half is speculating what data compression in a post-quantum compute world looks like.
The compression joke evokes a misconception (as STEM jokes often do) which, in this case, is that breaking a hash means finding a way to recover the full text of a multi-megabyte document, from a 100-something byte hash.
Whereas all it means is that it's become feasible for someone to produce a fake document with the same hash as the genuine one; the attack depends on the existence of collisions, which depend on the hash being one-way, such that an infinite set of documents could be "recovered" from the hash.
Most of the documents you could "decompress" from a hash are going to be gibberish, but some of them are going to be legit. If a hash is "broken", that means it's somehow unduly easy to search that ocean of gibberish collisions to find a chosen text which goes to a certain desired hash.
Nothing quantum can redefine a function that isn't one-to-one and onto into one that is. The hashing function remains ever the mathematical object that it is: a one-way function. But calculations of or searches through that function can be faster.
In a post-quantum world, pre-quantum crypto and hashing could well turn out to be "for shit" as such, but not due to ruses like suddenly reversing irreversible functions.
Not saying that the joke isn't funny! We can imagine some hard-core computer science or math sitcom in which the fall characters say things like this, and only the very narrow target audience gets it.
These hashes, regardless of their actual cryptographic strength, are intended to be indistinguishable from a random generator keyed with the input, kind of. Assuming that they succeed in that, hashes should be quite well distributed. That means that that for each hash n-bit hash output, there will be about two (n+1)-bit input strings that produce that hash, about four (n+2)-bit input strings, eight (n+3)-bit input strings, etc. So while there are probably few ASCII input strings that map to one particular hash, for example, there will be loads and loads of arbitrary bitstrings that map to that hash.
Compression algorithms must encode data in a reversible way, which hash functions can't do in general.
For example, SHA-1 outputs a 160 bit hash, which means some input of 161 or more bits will definitely have the same hash as some other input of the same size. Even smaller inputs may have collisions too.
Not so simple. A hash corresponds to infinitely many messages, but how many of them are in ASCII charset under 1KB long? It may happen that each hash has a unique message within these constraints.
The pigeonhole principle forbids it, since the hash itself is an ASCII message under 1KB long. Even within your message constraints, the message can contain contain any possible hash, and more besides. Therefore there are more valid messages than hashes.
Most of them will be gibberish; English text has only about 2.3 bits of entropy per letter. So there are only on the order of 2²³⁵⁵ 1KiB messages that look pretty much like English text, of which one in 2¹⁶⁰ will have any particular SHA-1 hash, leaving about 2²¹⁹⁵ more or less English messages of 1 KiB, which is a much more manageable 5 765 546 543 805 391 543 300 385 245 067 897 407 469 008 380 207 694 434 170 981 314 369 415 226 086 245 896 005 497 410 349 176 911 651 361 357 544 908 126 864 379 940 776 407 262 468 025 247 520 821 365 392 566 254 691 849 336 550 399 984 742 144 883 696 325 495 839 942 505 506 308 529 294 485 245 435 346 088 288 415 306 782 152 045 986 880 430 505 821 218 111 120 701 594 573 419 855 327 199 586 861 839 630 511 065 600 663 692 968 681 473 384 074 002 850 142 261 291 497 547 545 795 867 600 142 345 188 353 358 006 378 705 229 284 788 565 040 964 509 510 302 568 387 814 225 873 737 552 804 109 763 080 706 434 267 888 314 149 674 523 819 024 312 546 837 031 915 917 556 591 511 424 773 862 591 940 658 144 814 461 877 029 111 670 089 356 835 845 931 924 493 084 507 666 309 424 365 148 038 224 615 440 025 478 945 269 023 101 615 392 514 882 287 817 384 451 162 838 663 168 messages.
It is unlikely that it would be apparent upon inspection which one was correct, since most of them differ from other messages by only a couple dozen subtle changes.
Not it's not. You can't distinguish the complete works of Shakespeare from the complete works of Shakespeare with the words changed a bit, or switching to Harry Potter for a bit in the middle, or a completely dazzling and original work of fiction. Any hash might generate all three of these, and essentially boundless other works. It's a library of Babel.
Forgive me if I've misunderstood - the premise was that, out of the infinite set of data that hashes to a particular hash/checksum, there is a unique data set that is "obviously" the real one? Or at least, that the set is meaningfully bounded? My reply is that this is not the case. There will be infinitely many "plausible" data sets as well.
You could collide every hash in existence merely by making undetectably tiny alterations to Shakespeare.
Not obviously, no. - Just a very high probability. Perhaps that provides noise immunity to some degree. If it does, it is a form of AI.
This admittedly open question presumes a very large fuzzy 'code book' with which it can re-assemble the data. The length of the input in cleartext is valuable metadata that speeds up the search.
You still seem to be missing the point. The problem is that the SHA-1 hash is one of 2^160 possible values, while a 1GB plaintext is one of 2^8000000000 possible values. That means that the hash disambiguates your message down to one of 2^7999999840 values.
Let's go smaller. Let's say our plaintext is a single kilobyte. One 80x25 terminal's worth of ASCII. Knowing the SHA-1 hash narrows our search space, yes, but the search space is so absurdly large that it only solves 0.0000... (insert over two thousand zeros here) ..0001% of the problem.
Say you have a 32 byte hash, that's 2^(328) possible values, right? Now say your input is 128 bytes, that means that (on average) each 32 byte hash maps to 2^(968) values.
"Natural looking" data will occur an astronomical number of times in a search space that large - which is, again, only 96 bytes larger than your hash.
Only if you count all natural looking data of which there is way more than you could possibly imagine.
It is of course likely that humanity hasn't yet created more than 2^100 (~10^30) files, so in theory given a registry of all files in existence you might be able to identify it by its hash. However while this is simple it's definitely not easy.
But this is technically an invalid answer to the problem of file compression. An easy (!) way for data to be losslessly compressed would just be to have a registry of all files in existence, and to refer to each file by its index in the registry. (Like the prisoners who had told each other all their jokes so many times that now they could just quote them by number and everyone would laugh.) Data compression is supposed to be able to deal with novel but likely documents without needing to add them to a global registry.
I can imagine the output of program space. That's pretty big. All possible universes in fact.
It's an issue of probability and bins. While natural data is infinite, there is vastly more unnatural data. At some point you have enough metadata (e.g. natural vs. random) to know that the original data came from Earth to pick out the right needle from the needle stack.
Unless the data is from a completely alien source, we are close enough to that source for our heuristics to be of a manageable size.
I understand your confusion, because it took me a minute to think about it and confirm that this doesn't work. It might be surprising that even a machine with complete information and infinite compute power couldn't pick out the needle; after all, SHA-1 is a 160 bit hash. Are there really 2^160 ≈ 10^48 different texts in English that could reasonably have been written by someone living on Earth (add as much additional metadata as you like)? The answer is yes: there are simply too many needles.
Take your favorite book with 160 or more characters. (Probably a large book, but such a book could certainly exist.) Now, for each character, create version of the book with their name swapped out for exactly one other name which does not already appear in the book. So if a character is named Alex, in some other edition of the book that character is named Jason.
Now, consider how many editions of the book there are. There are two combinations (for each character) that are exactly alike other than that character's name being swapped out. So there are 2×2 = 4 combinations where two characters' names are swapped. And 2×2×2 = 8 combinations where 3 characters' names are swapped. If you think about how many versions of the book there are in total, it's 2^C, where C is the number of characters whose names can be swapped for only one other name.
In other words, it's guaranteed that you can generate SHA-1 collisions using one book alone, using only entirely reasonable alternative names for its characters.
Taking a book and randomly swapping words means you are introducing noise. This is high-entropy and really it's outside the scope of what I'm comfortable speculating on.
Image data is much simpler to think about in this paradigm, but the obvious AI applications of natural language are of course fascinating.
It's somewhat irrelevant how many unnatural data there is. The point is that there's way more plausible data (or sentences if we're restricting ourselves to natural language) than there are possible 160; 256 or 512 bit hashes.
Unless of course you enumerate all of human communication, but like I said that doesn't count as 'easy'.
But let's say every paragraph only offers 1 bit of entropy. Then a 160 bit hash gives you fuzzy accuracy up to 160 paragraphs. After that you'll have to extend the hash with hints to guide which sequence of paragraphs you're looking for, & hints for where the typos are
This is very abstract, but I believe that since both input and output are very close in program space compared to the total size of PS, the heuristics to map between them are going to be of a manageable size. This is based on an intuition about a single source for all activity in this universe.
For the sake of argument I figured I'd be highly optimistic. The linked prize shows practical evidence of 1GB of Wikipedia being compressed below 1 bit per character (& that's with a limit of 50 hours cpu time, 10GB memory, & 100GB disk)
This is what made it a funny thought experiement to me. I was doing some space related stuff a while back and when you're dealing with something as small as 100mb, and you add the constraint of up to a light-year or more of latency, which makes error correction immensely costly, having a quantum processor reciever find the collision of a unique hash could be faster than transmitting the data with errors.
There's probably a distance where the latency in light years is longer than it takes for a quantum processor with some shortcuts to exhaust the search space for the collision on the hash - and potential hashing algorithms that contain information and hints about a hyperplane that generates the original data over the field of possibilities. To a quantum computer with sufficient qbits at a long enough latency distance away, the 32-bit hash of a 2048bit RSA key may "arrive" faster than transmitting the whole key.
It feels like a fundamental misunderstanding of something in communication theory, but this was the thinking that prompted it.
Using the pigeonhole principle, consider how many 100 megabit values must, on average, hash to the same 32 bit value. The answer is a huge number (I could be wrong but it seems to me it might be 2 ^ (100,000,000 - 32)?). This is a bit of a paradox in cryptographic hashing, where finding a collision is difficult, but the number of collisions is enormous.
Yeah, you're fundamentally missing what I wrote, as well as pigeonhole principle and the basics of information theory.
Let's say you replace the quantum computer with an oracle. You have an infinitely long dictionary, and you can turn to any page and see your hash, as well as every possible input that could form that hash. There's billions and billions of options that all match your hash - how could you pick which one is definitely the "right" one?
You're no closer to knowing what the transmitted message was, because of the astronomical number of inputs that you now have to sift through.
[ Technically, you're (length of hash in bits) closer. Say you have 10 bits of hash, or 1024 values. There are (on average), 2 11-bit inputs that create that hash, 4 12-bit inputs, 8 13-bit inputs, and so on, following the powers of 2. At input of N=30 bits, you have 2^20 =~ 1 million possible inputs with that exact same hash. 1KB? 2^990, or "one followed by 990 zeroes". ]
This part about a massive number of possible collisions for a given plaintext in a cryptographic hash, but just spread over such a large field and incrememting with the input size so that it is just unlikely you will find another one is the counterintuitive part. I haven't implemented a secure hashing algorithm from scratch, so this aspect would have come out in the exercise.
Even working with security and crypto, the presumption of a cryptographic hash from a standard algorithm is that it is universally unique for the data it hashes - barring someone finding collisions, and then it gets deprecated. Most people deal with them at a higher level of abstraction.
Hash collisions have been used in a few high profile attacks in the last decade, most notably when some SSL certificates were still using MD5, and the most recent smart contract issue where the contract was only validating the last 4 bytes of a cryptographic hash and someone produced a key that exploited that with a collision. Unfortunately the people who don't make those mistakes are both very rare, and often dynamic to work with.
The idea that there are many, many potential collisions for a given input to a cryptographic hash doesn't come up much unless someone manages to find single a collision in one. I'd even posit nobody outside academic cryptography circles is including sha256 collisions in their threat scenarios right now.
However, the absurd/imaginary/hypotehtical/counterfactual I was raising is that a future quantum computer can produce all outputs of that length in a reasonable amount of time. The question was more about what was sufficient to reconstruct the data, and it was funny to know something was specifically wrong but not know why.
However, I appreciate the time taken to illustrate it.
Fortunately, Fossil can now use SHA3-256 as well as SHA-1 (even in the same repository if necessary, perhaps due to upgrading an older repository), and I think it also has a hard mode to detect if SHA-1 collisions seem likely.
(I think git doesn't allow a repository to have multiple kind of hashes; from what I understand, only a single algorithm must be used.)
Since SHA-1 and SHA3-256 have different hash length, you can tell which one it is. It doesn't work so well if the length is the same; one way to fix it would be use a multicodec prefix. (My own implementation (currently incomplete) internally uses the multicodec numbers to identify the hash algorithms, but these multicodec numbers are never stored in the repository; instead, it is only applicable for the argument for the function to compute the hash, which can also be used in other programs.)
Unfortunately Fossil uses a fast SHA hash for the password hashes of user accounts in the database, rather than a key derivation function, which is disappointing.
My fossil knowledge might be a fossil itself, but isn’t the database used for everything?
If someone gets hold of the hashes, they already have everything. So, whats the threat that is enabled by poor pw hashing?
Anyways, passwords should always be hashed with good password hashing functions (not all kdf are good for that) even if it is not strictly necessary. Just in case.
My idea is a different hash construction, which is 2D construction, which has a infinite internal state and infinite output length. Each row and each column also has a sequence number input, and then there are two mixing up functions (each of which has a finite input and output of equal size than the input); part of the result is propagated horizontally and part of it vertically, so each cell has two inputs and the input includes both the message block and the sequence number, which overwrites a part of the internal state (the rest of which has been mixed with the other state). Each output block (the output blocks are vertical and the message blocks are horizontal, which is why it is slow) is then truncated and concatenated to produce the final output, after adding padding at the end of the message (including the length of the message) to mix it up even more. If the message length is m and the hash length is h, then it requires O(h) space and O(mh) time. If ChaCha20 is in use, then it is easy to see (by the kind of calculations made by ChaCha20) that if the input is zero then the output will also be zero; therefore, the initial sequence number should be 1 and not 0. You can also compute a secondary hash which must be misaligned with the first one, so that in case a collision is found in one block that the collision will not be propagated with the other blocks too (unless a collision can be found within two consecutive blocks, in which case you would hope that the extra dimension (since it is a 2D construction) can avoid the collision).
Reading your post I’m sure you know far more about information theory than I do, so forgive me if this is a stupid question, but…
1. How is infinite internal state and output size possible? There has to be some actual limit for internal state, at least, right? Or else you’ll just run out of memory?
2. Wouldn’t a larger output size risk leaking data? The chance of collision becomes lower, but it also seems to toy with what I understand about why we use cryptographic hashes without ridiculous output size.
3A. What happens if you want a 1 MB hash of a 1 KB file?
3B. How predictable does a super long hash become?
1. Because you will probably be truncating the output to a short finite hash, and because each block of internal state only leads in one direction (it affects all later ("up") blocks of internal state for all later ("right") message blocks, but not previous ("left" and "down")), you can optimize it by only implementing the part that you need. So, yes, an actual implementation will be limited, but if you have enough memory and enough time then the limit can be as high as you want to be. (Maybe a diagram might explain it better; I am not sure that this explanation is any good.) (SHAKE also has infinite output (but finite internal state), and when using SHAKE also you would truncate the output to a finite size.)
2. A larger output size might risk leaking data, although I would think it would be difficult.
3A. Like I described, it then needs O(1MB) space and O(1GB) time, so it will be slow. However, I do not expect you should need a hash that long.
3B. I don't know; probably about as predictable as any random number generator, if the hash is designed correctly. (I only describe a construction, and the hash algorithm design involves more than that.)
Git was created 16 years ago. The impending breakage of SHA-1 was known even at that time, just like how MD5 had been broken before it.
I'm honestly still shocked that updating the hashing algorithm wasn't built into Git from day one. I really wonder why. Did people think this wouldn't happen? Were they so in love with the performance of C/C++ being able to pass around 20 byte hashes on the stack without worrying about a more complicated structure (eg a collection of variable length hashes)?
It just seems like such a massive and foreseeable oversight that's going to cause pain for some time to come for really no reason at all.
SHA-1 will still work fine for the purpose of git. It is just no longer considered secure for cryptographic operations, such as digital signature, that doesn't mean that you can't use it for other purposes, like git does. Using it is still fine and will ever be fine.
Making the hashing algorithm exchangeable would have introduces complexity in a software that is already complex, and also less efficient (one of the reasons git was created was speed for large project like the Linux kernel) for no real purpose. If you want to change the algorithm, given that you will break compatibility with all existing repositories, tools, and clients, you make a fork of git because you are changing too much.
I don't see why migrating to SHA-256. The collisions are still very unlikely to generate accidentally, and sure, if you want to do damage to a repository you can create one on purpose, as you can as well commit some hooks that contains malware, or alter the git history in any way you want, so what's the point?
Collisions definitely do matter for git security: many people pin explicit git hashes for their dependancies, and thus they can be tricked in running malicious forks. This requires placing a chosen commit in the git repo (so unlike second preimage break it does not mean that you could attack repos you have no control over) but that's not an unrealistic threat model overall.
1bis) You can use an existing collision to create new collisions. People seem to think you need to generate all the work again from scratch; this is not true. See PoC||GTFO for proof by example.
1cis) The files do not need to be gigantic. See PoC||GTFO for proof by example.
2) You can do the collision in advance, and publish the malicious version later. What it accomplishes is that the concept of "this Git hash unambiguously specifies a revision" no longer works, and one of them can be malicious.
3) The standard should be "obviously safe beyond a reasonable doubt", not "not obviously unsafe to a non-expert". By the latter standard, pretty much any random encryption construction is fine. (The examples I gave use MD5, not SHA-1, but that's a matter of degrees.)
4) SHA-256 was published years before git first was.
It's just a subdivision; it might as well have said 1a, 1b... -- but "bis" and "cis/tris" (and possibly tetrakis) tend to emphasize that they're addenda, not equal points.
The possible attack is to prepare 2 versions of a commit, both resulting in the same commit id. Then later on, after the project is successful/etc, swap out the commit with the second version, while keeping the other commits intact.
Granted, the file that the commit touches would need to be not touched in other commits. That's not out of question in a typical software project - maybe a file in the utils folder which is only written once and never changed?
> I don't think it's possible to create a collision that's also executeable code
You can include an unreadable binary blob in the commit. Tweak the blob to find the collision while keeping the code the way attack requires.
What's the method for doing this? Does a "git push" replace objects with identical hashes on the remote? Or a "git pull" replace identical hashes on the local repo?
I suspect finding a hash collision is only the first difficult part of actually pulling this off. You may need direct write access to the file system of the target. And even then everyone else that has already fetched the repo may not be impacted. At which point collisions becomes moot because you can rewrite the entire git history however you want.
The history teaches us: If any system isn't hardened against something, we can assume it's possible. If Git server isn't specifically hardened against that, it might still be tricked to update the file by adversary client. Or attacker can temporarily add hooks that will replace the file on server. Or integration testing system might have write access to the server repo.
> Granted, the file that the commit touches would need to be not touched in other commits.
That's not how git works. The commit contains the entire tree. You could prepare two separate repositories such that `git checkout deadbeef0001deadbeef` in one checks out the linux kernel and in the other checks out ILOVEYOU.exe.
You're right. Commit id points to a commit object, that points to a tree object and subsequently to individual blob objects. Then it is sufficiently harder, you need to find a collision between 2 blob objects, both of which are executable and don't look suspicious.
The files don't need to be gigantic. You could, for example, have a binary config file which in one colliding version encodes a potentially dangerous debugging setting, e.g., "allow_unauthenticated_rpc = false" but in other has it to "true".
The part about the 2nd pre-image chances being effectively zero may be true, but the nasty cases described upthread don't need a 2nd pre-image. (You could do a lot worse with one, granted!)
In addition to the attack described in a sibling comment, when a hashing algorithm has been broken in some way, it is safe to assume that other more advanced collision attacks will be soon discovered.
> It is just no longer considered secure for cryptographic operations, such as digital signature, that doesn't mean that you can't use it for other purposes, like git does.
Git effectively uses its hashes as a component of a digital signature scheme, in the form of signed tags and signed commits. The GPG signature covers the commit object, which identifies the content (tree) by its hash.
> SHA-1 will still work fine for the purpose of git. It is just no longer considered secure for cryptographic operations, such as digital signature, that doesn't mean that you can't use it for other purposes, like git does. Using it is still fine and will ever be fine.
This suggests git does not rely on its hash for security properties, which seems false? What is the purpose of pinning revisions or signing git tags?
Honestly I find these rationalizations around the use of SHA-1 annoying and counter-productive. The rule is simple: don't use SHA-1. If you already use SHA-1 migrate away from it. You know that plenty of software out there that interfaces with git expecting that the commit hash will be unique. Is it a security risk? Maybe, maybe not. I don't care to find out.
It doesn't matter until it starts mattering. If the Git devs had done the right thing over a decade ago we wouldn't be having this discussion. The longer they wait the more painful the migration will be.
SHA-2 was published in 2001, git was released in 2005 and now we're in 2021 and we're having this discussion again. The first concrete attack was released in "early 2005" according to wikipedia, so there's really no excuse.
Just do it, make a major change where you replace SHA-1 with SHA-256 and call it a day. It's going to be painful for a few months and then we'll move on.
For me these discussions demonstrate the immaturity of software engineering. In other industries regulators would've banned the use of SHA-1 and you couldn't get certified if you used it.
Do electronic engineers regularly try to argue "well ok RoHS says we can't have lead solder in this product but frankly for this one it's fine the casing is completely waterproof and there are no risks for the customer"? No, they don't. If the spec says no lead, then either it's no lead or you can't sell your product. End of story.
SHA-1 is the lead solder of software engineering. Only acceptable for military use.
> You know that plenty of software out there that interfaces with git expecting that the commit hash will be unique
You also know that plenty of software out there that interfaces with git has hardcoded assumptions (like, for example, the assumption that the commit hash will be exactly 40 characters long). Some tools parse the output of git log and other commit-bearing commands to make decisions. Will changing git to SHA-256 create new unforeseen security risks due to breakage of those tools (for example, by only grabbing the first 40 characters of a SHA-256 digest instead of all 64 or by just outright crashing)? Maybe, maybe not.
IMO I think you would create more security risks with the git integration breakage that would accompany migrating to sha256 vs. staying with sha1.
At this point it's almost like you want a new tool/new command. `git` vs. `git2`. New projects use git2, existing projects use git (or something like that). Otherwise confusion and backwards-compatibility breakage will abound.
The current plan is for Git to essentially use SHA-1 hashes as aliases for SHA-256, using a lookup table. This would mean that any given SHA-1 hash would, in a particular repository, map to one and only one SHA-256 hash, which is then used to retrieve the object. Eventually the SHA-1 hashes would be deprecated (via a per-repository mode switch, so every Git user or host would migrate according to their preferences).
The difference is that this breakage would be immediately visible. All code that mishandles these hash would immediately break. With collisions it can remain undetected for a long time, and potentially until somebody smart and with bad intentions finds a way to break your system in some creative way.
And again, if we had done this when it should have been done, i.e. pre-2010, we wouldn't be having this discussion. The longer we wait the more painful the migration will be whenever somebody manages to actually bruteforce collisions for git commits. We're not there. Yet.
If the lead solder is actually functional in some way then they may have to attempt to find an exception under RoHS. They could attempt to define the usage so as to have an application not covered by RoHS for example.
This analogy is kind of confusing because RoHS is an imposed standard. A user of SHA1 is expected to make their own decision about appropriate usage. They might reasonably continue the usage of SHA1 for their specific use case. The real world is full of such compromises.
> SHA-1 will still work fine for the purpose of git.
So why are they changing it? That's pretty strong evidence it's not fine. I found this Stackoverflow question, "Why does Git use a cryptographic hash function?" [1], which points to [2]. Note: pretty much every DVCS uses a cryptographic hash function. That doesn't seem like an accident.
Reading through some of these old posts and threads it seems like performance was the main factor combined with the expectation that SHA1 collisions just wouldn't be an issue. The latter I find to be surprisingly naive.
And, to that point, I'm not really convinced that a cryptographic hashing algorithm is really a great choice for git.
It is nice that it checks off the boxes for even distribution of hashes, but there's a bunch of other hashing algorithms that can do that without the performance penalty inherent in crypto hashes. For example, FNV seems like a good fit for something like git.
FNV is really cool and has a reasonable quality given its simplicity. But it does have issues (sticky state, and I think the avalanche characteristics also weren't great) that are solved by only slightly more complex hashing algorithms.
For someone to be able to break your repo using sha1 collisions, they need to be able to commit to it.
If you don't trust someone, don't let them commit to your repo.
> Were they so in love with the performance of C/C++ being able to pass around 20 byte hashes on the stack without worrying about a more complicated structure (eg a collection of variable length hashes)?
The hashes show up everywhere. They're how every object in git is identified. They make it onto disk. They're not just commit ids.
They might not need to commit to your repo to break it using SHA-1 collisions.
They might, for example, compute a collision, commit the malicious version to a private GitHub repository, and then send you a patch with the non-malicious version via email, or by sending you a merge request on GitLab. When you accept and merge in their changes and then push to GitHub, perhaps GitHub will recognize the hash of one of your blobs as a hash that it already knows the blob for (from the private commit), and so it will ignore whatever data you send it for that blob.
Maybe that particular scenario won't work — I haven't tried it — but there are hundreds of possible angles of attack. Fundamentally the security of Git is based on the idea that hashes don't collide.
If I'm looking at a PR which contains a hash collision with code that does a `sudo rm -rf --no-preserve-root /` and I don't accept the malicious code, the hash collision becomes irrelevant.
Git is designed around content-addressed storage and while you can cater for hash migrations, it gets pretty messy design-wise. Gits core data structures were also designed really quickly to patch a very urgent need of the kernel hackers. I doubt it has anything to do with being in love passing 20 byte strings on the stack. The fine git folks have produced a rather detailed document about the hash migration (https://git-scm.com/docs/hash-function-transition/) and it is not particularly simple to do this.
No - after all, the most common use of digital signatures is to sign documents that can be easily tampered. All the security is in the signature, not the content being signed.
This makes no sense. Sure: you can generate an X.509 certificate that says whatever you want, but the point is that you can validate the signature and see that it's a forgery. In the case of a hash-addressed system like git, the problem is that the signature is over a collision, so it no longer certifies the thing its supposed to certify. Git uses the hash as a shorthand for a revision, including its entire history--so yes, it is using the hash that way.
A digital signature usually signs (~encrypts) a hash of the content. So asking what exactly signing a commit or tag entails is a very valid question. I would expect that signing a tag is only as strong as SHA-1, since a tag is essentially a label for a commit hash. For signing commits I have no clue, but would be quite interested as well.
Linus posted about it on google plus in 2017. I haven't re-read it yet, but I remember one of the ideas floating around hn at the time was to just have two hashes per commit. That is, two insecure hashes may be secure together for git's purposes. Even though we can generate collisions for md5, and sha1, it would be much more difficult to have a file generate an arbitrary collision for both at the same time.
Here is a link to Linus's post on the internet archive
> That is, two insecure hashes may be secure together for git's purposes.
Generally that's not true for Merkle–Damgård (e.g. sha1, sha2) hashes - afaik the difficulty of finding a collision in the more difficult hash is the same (up to big-oh) as finding it in both hashes.
In git I don't know, but in fossil, it already does that if the file that the collision is generated for is not the manifest file. The manifest file and all other files are identified by the SHA-1 hash (in newer versions SHA3-256 is also supported), although the manifest file also has a R card which is the MD5 hash of the all of the other files. This means that if there is a collision, it will be detected and the file would be rejected.
> I'm honestly still shocked that updating the hashing algorithm wasn't built into Git from day one. I really wonder why.
The first basically functional version of Git was created in less than a month by Linus Torvalds, immediately after Bitkeeper revoked the license/permission for linux kernel developers to use that proprietary source control tool for free. Linus took a look at Monotone and Mercurial IIRC, but they were not nearly fast enough at that time, so he created Git to just do what the linux kernel development community needed.
This isn't the first time Linus did something that academics said was a terrible mistake, and then his creation took over the freaking world, because it works so freaking well. (And it still does today, 16 years later. Maybe tomorrow it won't, I dunno. But it probably will.)
> Linus took a look at Monotone and Mercurial IIRC, but they were not nearly fast enough at that time
That's incorrect for Mercurial, it was started by another kernel developer (Matt Mackall) at the same time, for the same reasons (but they ended-up with different trade-offs, which makes mercurial still very interesting and relevant in a post-github world).
Is it not possible to create a good cryptographic hashing algorithm that results in 128bit or 160bit hash?
It seems all the modern, secure ones are 256 bits or larger. Is that because 160 bits is too easy to compute collisions for any algorithm, or are we just not able to fully realize the entropy that can be recorded into 160 (or even 128) bits?
> Is it not possible to create a good cryptographic hashing algorithm that results in 128bit or 160bit hash?
No, it is provably not possible to do that. A N-bit hash function has maximum N/2-bits of collision resistance. So a 128-bit hash function (like MD5) has a maximum of 2^64 bits of security against a classical attacker, even if it wasn't broken in other ways (as MD5 is). A 160-bit hash function like SHA-1 would have 2^80 bits of security against collision attacks on a classical computer.
Both MD5 and SHA-1 are broken in other ways, but you could for example use SHA-2 or SHA-3 in truncated mode if you wanted a "secure" 128-bit or 160-bit hash output. Indeed there are standard operating modes for doing so, meant for when you need a drop-in replacement for MD5 or SHA-1.
But fundamentally, 64-bit or 80-bit security is too low for any except some highly specified use cases. And even then the extra bits of a stronger hash will rarely kill you, so why bother? Just use SHA-2 or SHA-3 and not worry about it.
In cases where you can demonstrate that you only care about preimage resistance and not collision resistance, then a 128-bit hash would be sufficient. However often collision attacks crop in in unexpected places or when your protocol is used in ways you didn't design for. Better to just double the hash size and not worry about it.
This a common lay-person approach to "strengthening" cryptography, but is not as effective as using a better algorithm instead.
For example, SHA256 and SHA512 require approximately the same number of "cycles per byte" when using modern CPU instruction sets. So 2× SHA256 is 2× slower than 1× SHA512. On some processor models, 1× SHA512 is faster than 1× SHA256!
Of course, things aren't always this simple, but you get the idea.
Similarly, for some class of attacks, it's only 2× as much work to crack 2× SHA256 as it would take to crack 1×SHA256. However, for these attacks it is (2^256)× more work to crack SHA512, which takes the difficulty increase from "slightly more" to "absolutely impossible in this physical universe".
If the hash function does its job at mixing input, this is no different than applying just the final hash.
(With the technical caveat that doing at least two serial hashes does improve the properties of the hash function by defending against length extension attacks. That's why things like HMAC do multiple chained hashes. But it does zilch for collision or preimage resistance.
https://github.blog/2017-03-20-sha-1-collision-detection-on-...