{"thread":{"id":"29042","subject":"Re: [PATCH] Implement fast hash-collision detection","startedAt":"2011-11-29T09:07:33Z","lastAt":"2011-12-02T17:00:40Z","messageCount":20,"participants":["Jeff King","Ævar Arnfjörð Bjarmason","Nguyen Thai Ngoc Duy","Shawn Pearce","Bill Zaumen","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"180076","messageId":"20111129090733.GA22046@sigill.intra.peff.net","threadId":"29042","inReplyTo":"1322546563.1719.22.camel@yos","subject":"Re: [PATCH] Implement fast hash-collision detection","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-11-29T09:07:33Z","receivedAt":"2011-11-29T09:07:33Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"[Your original message was almost certainly bounced by git@vger because\n it surpassed the 100K limit; I'll try to quote liberally for those who\n missed the original. You may want to split your content and repost.]\n\nOn Mon, Nov 28, 2011 at 10:02:43PM -0800, Bill Zaumen wrote:\n\n> Maintains a database of CRCs of Git objects to allow SHA-1 hash\n> collisions to be detected with high probability (1 - 1/2^32) and with\n> little computational overhead. The CRCs cover the content of Git\n> objects, but not the header. For loose objects, these are stored in\n> subdirectories of GIT_DIRECTORY/objects/crcs, with each subdirectory's\n> name consisting of the first two hexadecimal digits of the\n> corresponding object's SHA-1 hash. For each pack file, FILE.pack, the\n> CRCs are stored in a FILE.mds, in the same order as the SHA-1 hashes\n> that appear in FILE.idx. Checks for hash collisions are made whenever\n> a new loose object is created.\n\nI'm confused. Is this about avoiding accidental collisions, or about\navoiding malicious collision attacks?\n\nLet's assume the former for a minute. The usual way of considering\ncollision likelihood is not by probabilities, but by the number of items\nthat must be selected to achieve a >50% probability that there is a\ncollision. Which is the square root of the number of total items, or\nhalf the bit-space.\n\nSo we expect to see a collision in 160-bit SHA-1 after writing about\n2^80 objects. The linux-2.6 repository has about 2.2 million objects\nafter 6.5 years of development. If development continues at this pace,\nwe would expect a collision in a mere 10^18 years.\n\nAssuming your 32-bit CRC is statistically independent of the SHA-1\nvalue, it adds 32 bits to the hash, or 16 bits to the number of objects\nwe expect to generate (i.e., 2^96). That bumps us up to 10^23 years.\n\nHowever, it may be of interest that the Sun is expected to burn out in a\nmere 10^10 years[1].\n\nSo I'm not sure there is really any point in adding a few bits to the\nhash length to detect an accidental collision. It's already\nfantastically unlikely. Adding another probability on top does make it\nless likely, but in the same ballpark of fantastic.\n\nYou can argue about whether linux-2.6 is a representative sample, or\nwhether the pace of object creation might increase. But the simple\nanswer is that we're many orders of magnitude away from having to care.\n\nHowever, in your patch you write:\n\n> +Security-Issue Details\n> +----------------------\n> +\n> +Without hash-collision detection, Git has a higher risk of data\n> +corruption due to the obvious hash-collision vulnerability, so the\n> +issue is really whether a usable vulnerability exists. Recent research\n> +has shown that SHA-1 collisions can be found in 2^63 operations or\n> +less. While one result claimed 2^53 operations, the paper claiming\n> +that value was withdrawn from publication due to an error in the\n> +estimate. Another result claimed a complexity of between 2^51 and 2^57\n> +operations, and still another claimed a complexity of 2^57.5 SHA-1\n> +computations. A summary is available at\n> +. Given the\n> +number of recent attacks, possibly by governments or large-scale\n> +criminal enterprises\n> +(,\n> +,\n> +),\n> +which include botnets with an estimated 30 million computers, there is\n> +reason for some concern: while generating a SHA-1 collision for\n> +purposes of damaging a Git repository is extremely expensive\n> +computationally, it is possibly within reach of very well funded\n> +organizations. 2^32 operations, even if the operations are as\n> +expensive as computing a SHA-1 hash of a modest source-code file, can\n> +be performed in a reasonably short period of time on the type of\n> +hardware widely used in desktop or laptop computers at present. With\n> +sufficient parallelism, 30 million personal computers sufficient for\n> +playing the latest video games could perform 2^56 operations in a\n> +reasonable time.\n\n...which makes me think that you do care about malicious collisions. All\nof what you wrote above seems fairly accurate. Let's leave aside that\nthose numbers are for a collision attack as opposed to a pre-image\nattack (collision attacks are hard to execute, as they require you to\ngenerate two \"matched\" objects, one good and one evil, and then convince\nsomebody to first accept your good object, only to later replace it with\nthe evil one).\n\nI have two concerns with this as a security mechanism:\n\nFirst, let us assume that the implementation details of your scheme\nwork, and that git users will effectively be checking not just a SHA-1,\nbut now a SHA-1 plus your additional digest.\n\nIn that case, why use crc32 as the digest? It seems like a terrible\nchoice. Assuming it's cryptographically secure, then it's adding a mere\n16 bits to the numbers you mentioned above. IOW, it's at best a band-aid\nthat pushes attacks off for a few years. But more importantly, it's\n_not_ secure, and can be trivially forged.\n\nBut that's a relatively simple problem. crc32 could be replaced in your\nscheme with any of the SHA-2 family, or the upcoming SHA-3, or whatever.\n\nThat brings me to my second concern: how does this alternative message\ndigest have any authority?\n\nFor example, your patch teaches the git protocol a new extension to pass\nthese digests along with the object sha1s. But how do we know the server\nisn't feeding us a bad digest along with the bad object?\n\nThe \"usual\" security model discussed in git is that of verifying a\nsigned tag. Linus signs a tag and pushes it to a server. I fetch the\ntag, and can verify the signature on the tag. I want to know that I have\nthe exact same objects that Linus had. But I can't assume the server is\ntrustworthy; it may have fed me a bad object with a collided sha1.\n\nBut what's in the signed part of the tag object? Only the sha1 of the\ncommit the tag points to, but not the new digest. So an attacker can\nreplace the commit with one that collides, and it can in turn point to\narbitrary trees and blobs.\n\nYou can fix this by including an extra header in the signed part of the\ntag that says \"also, the digest of the commit I point to is X\". Then you\nknow you have the same commit that Linus had. But the commit points to a\ntree by its sha1. So you have to add a similar header in the commit\nobject that says \"also, the digest of the tree I point to is X\". And\nditto for all of the parent pointers, if you want to care about signing\nhistory. And then you have the same problem in the tree: each sub-tree\nand blob is referenced by its sha1.\n\nIn other words, authority flows from the gpg-signed tag portion, and\nlinks in the chain to each object are made by referencing sha1s. Every\ntime such a link is made, you need to also include the digest of the\nobject, or you are giving the attacker a place to insert a collided\nobject.\n\nFor tag and commit objects, this actually isn't that hard; they have a\nrelatively small number of links, and they have room for arbitrary\nheaders. I.e., add a \"tree-md-sha256\" header that gives the expected\nsha-256 of the tree object referenced by sha-1 in the \"tree\" header.\nOlder versions of git will skip over this header (though obviously they\nwon't be smart enough to do the more-secure verification).\n\nHowever, it's harder for trees. Each entry needs to have the new digest\nadded, but there simply isn't room in the format. So we would have to\nchange the tree format, breaking interoperability with older versions of\ngit. And all of your tree sha1's would change as soon as you wrote them\nwith the new format. That's only slightly better than just swapping\nsha1 out for a better algorithm.\n\nOne trick you could do is to include the digest of each blob in the\ncommit object itself. This really bloats the size of commit objects,\nthough. You can store a digest of their digests instead (which your\npatch actually calculates, but AFAICT does not actually insert into the\ncommit object). That is small and relatively cheap (it turns commit from\nan O(1) operation into an O(number of files) operation, but the per-file\nconstant is pretty inexpensive). But it comes at the expense of not being\nable to tell which of the constituent blobs was actually attacked.\n\nSo I think all of that would work for verification starting at a signed\ntag that points to a commit or a blob. For a tag pointing straight to a\ntree, it could include the same \"digest of digests\" that the commit\nwould.\n\nBut it can never handle direct sha1 references outside of git. For\nexample, a bug tracker or CI system that references a commit in git will\ndo so by sha1. But that's an insecure link in the chain; you really need\nit to refer to both the sha1 _and_ the digest, and then you can verify\nthat the object you have under that sha1 matches the digest. So you'd\nhave to teach a whole generation of tools that they can't trust git sha1\nids, and that you need an \"extended\" id that includes the digest.\n\nAt that point, I really wonder if a flag day to switch to a new\nrepository format is all that bad. You'd have to either rewrite existing\nhistory (which means re-signing tags if you care about them!), or just\ndecide to leave the new and old histories disconnected. Whereas a\nscheme based around an added-on digest could keep the old history\nconnected. But at the same time, the old history will have zero value\nfrom a security perspective. If sha1 is broken, then those old\nsignatures are worthless, anyway. And just switching to a new algorithm\nmeans the implementation remains very simple.\n\n-Peff\n\n[1] Fun fact of the day: if linux development continues at the same\n rate until the Sun burns out, there is a 1/2^60 chance of a\n collision!\n"},{"id":"180080","messageId":"CACBZZX59PiO0GGfPg=Gn0h_yWFnAMxmtDtecv9Yd_Pu8Jz0gzg@mail.gmail.com","threadId":"29042","inReplyTo":"20111129090733.GA22046@sigill.intra.peff.net","subject":"Re: [PATCH] Implement fast hash-collision detection","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2011-11-29T10:24:18Z","receivedAt":"2011-11-29T10:24:18Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"On Tue, Nov 29, 2011 at 10:07, Jeff King wrote:\n\n> However, it may be of interest that the Sun is expected to burn out in a\n> mere 10^10 years[1].\n\nOff topic, but it's a a lot sooner than that. The total age of the sun\nis is around 10^10 (10 billion) years, but we're already ~4.6 billion\nyears along that line.\n\nHowever the Sun is currently in a stage of gradual heating until it\nturns into a red giant in ~5 billion years. In around 500 million\nyears the earth will be uninhabitable as we know it, and in around 1\nbillion years the surface will be hot enough to have boiled all the\noceans. In other words the earth in a billion years will probably look\nsimilar to how Venus looks now.\n"},{"id":"180082","messageId":"20111129102929.GA28024@sigill.intra.peff.net","threadId":"29042","inReplyTo":"CACBZZX59PiO0GGfPg=Gn0h_yWFnAMxmtDtecv9Yd_Pu8Jz0gzg@mail.gmail.com","subject":"Re: [PATCH] Implement fast hash-collision detection","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-11-29T10:29:29Z","receivedAt":"2011-11-29T10:29:29Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Nov 29, 2011 at 11:24:18AM +0100, Ævar Arnfjörð Bjarmason wrote:\n\n> On Tue, Nov 29, 2011 at 10:07, Jeff King wrote:\n> \n> > However, it may be of interest that the Sun is expected to burn out in a\n> > mere 10^10 years[1].\n> \n> Off topic, but it's a a lot sooner than that. The total age of the sun\n> is is around 10^10 (10 billion) years, but we're already ~4.6 billion\n> years along that line.\n\nYeah, I checked Wikipedia, but rounded up for simplicity. I did use 5\nbillion for my fun fact at the end of the email, which is close to\naccurate.\n\n> However the Sun is currently in a stage of gradual heating until it\n> turns into a red giant in ~5 billion years. In around 500 million\n> years the earth will be uninhabitable as we know it, and in around 1\n> billion years the surface will be hot enough to have boiled all the\n> oceans. In other words the earth in a billion years will probably look\n> similar to how Venus looks now.\n\nGood point. If we want an accidental collision in the next 500 million\nyears, we'd better step up the pace of development!\n\n-Peff\n"},{"id":"180087","messageId":"CACsJy8BRhoYM+Lb8afp=3rKzYNOEq0JY8uS9mD1ovz3uyJVWOA@mail.gmail.com","threadId":"29042","inReplyTo":"20111129090733.GA22046@sigill.intra.peff.net","subject":"Re: [PATCH] Implement fast hash-collision detection","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2011-11-29T13:17:36Z","receivedAt":"2011-11-29T13:17:36Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Nov 29, 2011 at 4:07 PM, Jeff King wrote:\n> However, it's harder for trees. Each entry needs to have the new digest\n> added, but there simply isn't room in the format. So we would have to\n> change the tree format, breaking interoperability with older versions of\n> git. And all of your tree sha1's would change as soon as you wrote them\n> with the new format. That's only slightly better than just swapping\n> sha1 out for a better algorithm.\n\nI think we could hide the new digest after NUL at the end of path\nname. C Git at least does not seem to care whatever after NUL.\n-- \nDuy\n"},{"id":"180089","messageId":"CACsJy8DboVU4kSbJSV=8NP08OyLYVgOKsm8tt=koZ0=JcGSE=A@mail.gmail.com","threadId":"29042","inReplyTo":"20111129090733.GA22046@sigill.intra.peff.net","subject":"Re: [PATCH] Implement fast hash-collision detection","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2011-11-29T14:04:06Z","receivedAt":"2011-11-29T14:04:06Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Nov 29, 2011 at 4:07 PM, Jeff King wrote:\n> That brings me to my second concern: how does this alternative message\n> digest have any authority?\n>\n> For example, your patch teaches the git protocol a new extension to pass\n> these digests along with the object sha1s. But how do we know the server\n> isn't feeding us a bad digest along with the bad object?\n>\n> The \"usual\" security model discussed in git is that of verifying a\n> signed tag. Linus signs a tag and pushes it to a server. I fetch the\n> tag, and can verify the signature on the tag. I want to know that I have\n> the exact same objects that Linus had. But I can't assume the server is\n> trustworthy; it may have fed me a bad object with a collided sha1.\n>\n> But what's in the signed part of the tag object? Only the sha1 of the\n> commit the tag points to, but not the new digest. So an attacker can\n> replace the commit with one that collides, and it can in turn point to\n> arbitrary trees and blobs.\n>\n> You can fix this by including an extra header in the signed part of the\n> tag that says \"also, the digest of the commit I point to is X\". Then you\n> know you have the same commit that Linus had. But the commit points to a\n> tree by its sha1. So you have to add a similar header in the commit\n> object that says \"also, the digest of the tree I point to is X\". And\n> ditto for all of the parent pointers, if you want to care about signing\n> history. And then you have the same problem in the tree: each sub-tree\n> and blob is referenced by its sha1.\n>\n> ..\n\n(Security ignorant speaking)\n\nCan we just hash all objects in a pack from bottom up, (replacing\nsha-1 in trees/commits/tags with the new digest in memory before\nhashing), then attach the new top digest to tag's content? The sender\nis required by the receiver to send new digests for all objects in the\npack together with the pack. The receiver can then go through the same\nprocess to produce the top digest and match it with one saved in tag.\n\nI do agree that we should use stronger digests, not weaker, preferably\na combination of them.\n-- \nDuy\n"},{"id":"180091","messageId":"CAJo=hJvavm6feUjxOZ-qvJjs0nT=uKtFqs1Z82rcyEqazFxUOg@mail.gmail.com","threadId":"29042","inReplyTo":"CACsJy8BRhoYM+Lb8afp=3rKzYNOEq0JY8uS9mD1ovz3uyJVWOA@mail.gmail.com","subject":"Re: [PATCH] Implement fast hash-collision detection","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2011-11-29T15:23:19Z","receivedAt":"2011-11-29T15:23:19Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Tue, Nov 29, 2011 at 05:17, Nguyen Thai Ngoc Duy wrote:\n> On Tue, Nov 29, 2011 at 4:07 PM, Jeff King wrote:\n>> However, it's harder for trees. Each entry needs to have the new digest\n>> added, but there simply isn't room in the format. So we would have to\n>> change the tree format, breaking interoperability with older versions of\n>> git. And all of your tree sha1's would change as soon as you wrote them\n>> with the new format. That's only slightly better than just swapping\n>> sha1 out for a better algorithm.\n>\n> I think we could hide the new digest after NUL at the end of path\n> name. C Git at least does not seem to care whatever after NUL.\n\nNo, you can't. The next byte after the NUL at the end of a path name\nis the SHA-1 of that entry. After those 20 bytes of SHA-1 data is\nconsumed, the \"mode SP name\\0\" of the next entry is parsed.\n\nThere is not room in the tree format for any additional data. Period.\nAt best you can modify the mode value to be a new octal code that is\nnot recognized by current Git implementations. But that doesn't get\nyou a whole lot of data, and its pretty risky change because its\nrather incompatible.\n"},{"id":"180093","messageId":"CAJo=hJtFT55Ucyij9esr3Hd9yJ6XCxatK7vjPOLMKow57HqBoQ@mail.gmail.com","threadId":"29042","inReplyTo":"1322546563.1719.22.camel@yos","subject":"Re: [PATCH] Implement fast hash-collision detection","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2011-11-29T17:08:27Z","receivedAt":"2011-11-29T17:08:27Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Mon, Nov 28, 2011 at 22:02, Bill Zaumen wrote:\n> Several years ago (in 2006) there was a discussion about the whether\n> SHA-1 is adequate given the very small but non-zero probability of a\n> hash collision, particularly given the possibility of a malicious\n> attempt to generate a collision. At roughly the same time, Git was\n> modified to support \"thin packs\" during data transfers. These allow\n> one to send deltas based on objects that are not in the pack file\n> being transferred. As a result a previously undetected hash collision\n> could result in a corrupted repository when (for example) the same\n> delta is applied to different objects that have the same SHA-1 hash.\n\nI don't think you understand how these thin packs are processed.\n\nIf the pack contains <100 objects, it is inflated to loose objects. If\nthe receiving side (so client in fetch, server in push) already has an\nobject by that SHA-1, the new object is discarded. If the pack\ncontains >=100 objects, and the receiving side already has the object,\nit is compared byte-for-byte to ensure the incoming copy exactly\nmatches the already existing copy.\n\nEither way the first object to arrive always wins.\n\n\nThe recipient has to trust that the remote side is providing it\nsomething reasonable. If the recipient has *ZERO* trust in the sender,\nthen s/he should read the content of all newly arrived objects before\ncompiling or executing them. This is one reason why Git does not run\nhooks that are transported as part of the repository. If the recipient\nthinks reading the content is too onerous or impossible, then they\nhave to make a trust assertion on the remote side.\n\nThis trust assertion should be derived from the community, and not so\nmuch around the machine claiming the content is what it says it is. We\nhave yet to disprove the halting problem, so we have yet to construct\na machine that can verify those Linux kernel sources you downloaded\ndon't contain a local root exploit (for example). Instead we have to\ntrust the community of developers and users who work on and run that\ncode to have confidence that the code works as expected, etc. We base\nour trust off reputable people making statements like \"Linus kernel at\ngit://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git is\npretty good\", and \"kernel.org is where Linus pushes directly to, so\nits reasonable to trust the kernel.org server\".\n\nThe recipient should have some understanding of the remote server's\nsecurity policies, or pay attention to notices posted by others who\nare also fetching and reviewing content from the same repository. At\nsome level, the community using a repository from a given site should\nbe policing that site and establishing trust that the host is not\nproviding garbage content. After an incident, it is possible to pick\nup again by rebuilding the environment from an already known\nrepository that people trust. In the case of the recent kernel.org\nenvironment rebuild, that is exactly what they did, the community\npicked up again from Linus' personal repository.\n\nDNS could be abused to send you the wrong IP for a site, but most\npeople don't use random DNS servers, they have some level of trust in\ntheir DNS provider. DNSSEC is helping to improve the security of the\nname->IP translation process, and using protocols like HTTPS with SSL\ncertificate verification can help to reduce the chances that a forged\nDNS entry sends you to an evil source, rather than the community\ntrusted one. (Although SSL certificates seem to be getting forged left\nand right these days, so again you can't really rely on strong\ncryptography to magically solve security problems when the attacker\nholds the private key you have decided to trust with no further\nverification.)\n\n\nBut trust aside, consider an object C is sent as a delta to the remote\nside. The delta base B is not included in the pack, and is referenced\nby SHA-1. When the remote side processed delta C, it looks up a copy\nof base B from its own repository. We assume this content of B is\ncorrect, due to the \"first to arrive wins\" rule, and the community\nreview/trust/notification process.\n\nThe inflated length of B is checked against a size that is stored in\nthe front of the delta instruction stream that describes C. These\nlengths must match exactly, if they do not match then the delta\napplication aborts, the pack is rejected, and any temporary data is\nremoved from the filesystem. As Peff pointed out elsewhere in this\nthread, the odds of a SHA-1 collision in a project are low, on the\norder of 1/(2^80). Although there are some attacks on message digest\nfunctions like MD-5 or SHA-1 that might be possible to generate a\nduplicate in 2^57 time, any that I have read require producing a\ndifferent length content than the original you are trying to replace.\nAssuming the copy of B on the remote system actually inflates and\ncomputes to the correct SHA-1 B, it probably does not also have the\ncorrect length if it is an object with correct hash but wrong content.\nSo delta application should still be checking for collision with a\n1/(2^80) probability.\n\nAssuming the remote's copy of B passed the size check, the delta is\napplied on top, and the SHA-1 of the result buffer is computed. The\nattacker must craft the delta such that the SHA-1 of C is the result,\notherwise connectivity checks will fail.\n\nAssuming the attacker successfully stores a C' that has the right\nSHA-1, but wrong content... the community around that repository will\neventually notice this and message that the source site cannot be\ntrusted. I refer you back to the statement above about trusting the\nsite you pull from, or trusting the users that you authorize to push\ninto a repository.\n\nBut thin pack aside, this problem exists in any form of a packed\nobject. An attacker can try to send object P' (as a non-delta) in\nplace of P. SHA1(P') = SHA1(P), but the content differs. This is far\neasier to construct than the thin pack delta case you think is a\nproblem, and is the most likely approach for an attacker to take. I\nrefer you back to the statement above about trusting the site you pull\nfrom, or trusting the users that you authorize to push into a\nrepository, or reading every object you receive.\n\n\nEven if you magically fix the hash function somehow to decrease the\nodds of collision (e.g. by switching to a member of the SHA-2 or SHA-3\nfamily), there is no way to prevent a bug or root exploit from\nentering the project except by never adding new code, or by carefully\nreviewing everything that is submitted, and building up a basis of\ntrust around that review method. It is far more likely for an attacker\nto try and submit a plain text patch to the Linux kernel mailing list\nthat reads completely correct, hashes to the correct SHA-1s when\napplied in Git, etc... but just \"happens\" to contain an off by one\npointer bug in some weird case that allows the attacker to overflow a\ncritical memory buffer and later inject some code that can later be\nused to create an exploit. If they are ever \"caught\" they may just\nclaim \"I AM A MORON I AM SORRY I MISSED THAT BUFFER CHECK AND SO DID\nYOU DURING CODE REVIEW SO ITS NOT ALL MY FAULT LEAVE ME ALONE\" and get\naway with it.\n\nTrust. Review. Verify.\n\nI don't know about you, but I don't just pull random code from\narbitrary sites on the Internet. Nor do I compile or execute that code\non my workstation. I do trust some individuals based on their\nreputation on the Internet, or my past experiences working with their\ncode. And I also trust some hosting environments like kernel.org, or\nGitHub, or code.google.com, to provide reasonably secure hosting, and\nto aggressively react to any event that might make it harder for me to\ntrust the content they supply. And I also read a lot of code that I\npull.\n\nIt really isn't the problem you try to claim it is.\n"},{"id":"180111","messageId":"20111129205905.GA1793@sigill.intra.peff.net","threadId":"29042","inReplyTo":"CACsJy8DboVU4kSbJSV=8NP08OyLYVgOKsm8tt=koZ0=JcGSE=A@mail.gmail.com","subject":"Re: [PATCH] Implement fast hash-collision detection","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-11-29T20:59:05Z","receivedAt":"2011-11-29T20:59:05Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Nov 29, 2011 at 09:04:06PM +0700, Nguyen Thai Ngoc Duy wrote:\n\n> > You can fix this by including an extra header in the signed part of the\n> > tag that says \"also, the digest of the commit I point to is X\". Then you\n> > know you have the same commit that Linus had. But the commit points to a\n> > tree by its sha1. So you have to add a similar header in the commit\n> > object that says \"also, the digest of the tree I point to is X\". And\n> > ditto for all of the parent pointers, if you want to care about signing\n> > history. And then you have the same problem in the tree: each sub-tree\n> > and blob is referenced by its sha1.\n> >\n> Can we just hash all objects in a pack from bottom up, (replacing\n> sha-1 in trees/commits/tags with the new digest in memory before\n> hashing), then attach the new top digest to tag's content? The sender\n> is required by the receiver to send new digests for all objects in the\n> pack together with the pack. The receiver can then go through the same\n> process to produce the top digest and match it with one saved in tag.\n\nI think that is conflating two different layers of git. The security for\ntags happens at the conceptual object db layer: you sign a tag, and that\npoints to a commit, which points to a tree, and so on. The authenticity\ncomes from the tag signature, but the integrity of each link in the\nchain is verifiable because of the has property. The pack layer, on the\nother hand, is just an implementation detail about how those conceptual\nobjects are stored. More than just your tag will be in a pack, and the\ncontents of your tag may be spread across several packs (or even loose\nobjects).\n\nSo I don't think it's right to talk about packs at all in the signature\nmodel.\n\nIf you wanted to say \"make a digest of all of the sub-objects pointed to\nby the tag\", then yes, that does work (security-wise). But it's\nexpensive to calculate. Instead, you want to use a \"digest of digests\"\nas much as possible. Which is what git already does, of course; you hash\nthe tree object, which contains hashes of the blob sha1s. Git's\nconceptual model is fine. The only problem is that sha1 is potentially\ngoing to lose its security properties, weakening the links in the chain.\nSo as much as possible, we want to insert additional links at the exact\nsame places, but using a stronger algorithm.\n\nDoes that make sense?\n\n-Peff\n"},{"id":"180119","messageId":"1322603788.1728.190.camel@yos","threadId":"29042","inReplyTo":"20111129090733.GA22046@sigill.intra.peff.net","subject":"Re: [PATCH] Implement fast hash-collision detection","fromName":"Bill Zaumen","fromEmail":"bill.zaumen+git@gmail.com","sentAt":"2011-11-29T21:56:28Z","receivedAt":"2011-11-29T21:56:28Z","isPatch":true,"sender":{"key":"bill.zaumen+git@gmail.com","avatar":null},"body":"Thanks for mentioning the 100K limit, which I didn't know about. Will\nhave to try to see how to split it into two patches.\n\nThe intent is to increase the cost of a malicious attack, which requires\ngenerating two different files with the same SHA-1 value, detect such an\nattack early, and to slow such an attack down - because of Git's rule\nthat the first object with a SHA-1 value is the one the repository has,\nif it takes longer to generate a collision than the time it takes to get\nthe original object into all repositories (which is done manually by\nmultiple individuals), the forged file will never appear in any\n\"official\" repository.\n\nThe additional CRC (easily changed to whatever message digest one might\nprefer) makes a malicious attack far more difficult: the modified file\nhas to have both the same SHA-1 hash (including the Git header) and \nthe same CRC (not including the Git header). An efficient algorithm to\ndo both simultaneously does not yet exist. So, if we could generate a\nSHA-1 collision in one second, it would presumably take billions of\nseconds (many decades of continuous computation) to generate a SHA-1\nhash with the same CRC, and well before a year has elapsed, the original\nobject should have been in all the repositories, preventing a forged\nobject from being inserted. Of course, eventually you might need a\nreal message digest.\n\nThe weakness of a CRC as an integrity check is not an issue since it is\nnever used alone: it's use is more analogous to the few extra bits added\nto a data stream when error-detecting codes are used. I used a CRC in\nthe initial implementation rather than a message digest because it is\nfaster, and because the initial goal was to get things to work\ncorrectly. In any case, the patch does not eliminate any code in which\nGit already does a byte-by-byte comparison. In cases where Git\ncurrently assumes that two objects are the same because the SHA-1 hashes\nare the same, the patch compares CRCs as an additional test.\n\nRegarding your [Jeff's] second concern, \"how does this alternative\ndigest have any authority?\" there are two things to keep in mind. First,\nit is a supplement to the existing digest. Second, any value of the CRC\nthat is stored permanently (baring bugs, in my implementation, of\ncourse) is computed locally - when a loose object is created or when a\npack file's index is created. At no point is a CRC that was obtained\nfrom another repository trusted. While the patch modifies Git so that it\ncan send CRCs when using the git protocol, these CRCs are never stored,\nbut are instead used only for cross checks. If one side or the other\n\"lies\", you get an error. \n\nTo give a concrete example, during a fetch, the git protocol currently\nsends \"have\" messages that contain the SHA-1 hashes of commits. The\nextension allows two CRCs to be sent along with each hash. If these do\nnot match the local values (tested only if the local values exist),\nsomething is wrong and you get an error report that the server sends to\nthe client, but the server never uses these CRCs for any other purpose\nand the server never sends its CRCs to the client because of\nbackwards-compatibility issues. For objects that are transferred, you\nend up with a pack file, with index-pack called to build the index (and\nwith the patch, the corresponding MDS file), but index-pack already does\na byte-by-byte comparison to detect collisions - the comparison is much\nfaster than the SHA-1 computation index-pack has to do anyway.\n\nWhere this helps is when one is using multiple repositories. If you\nfetch a commit from repository B, which we'll assume has a forged blob\n(different content, but the original SHA-1 hash), and then run fetch\nusing repository A, which has has the same commit with the original\nblob, the forged blob will not be transferred from Server A and the\nclient will not be notified that there is an inconsistency - the\nprotocol is \"smart\" enough to know that the client already has the\ncommit and assumes there is nothing to do regarding it.\n\nBTW, regarding your [Jeff's] discussion about putting an additional\nheader in commit messages - I tried that. The existing versions of\nGit didn't like it: barring a bug in my test code, it seems that Git\nexpects headers in commit messages to be in a particular order and\ntreats deviations from that to be an error. I even tried appending\nblank lines at the end of a commit, with spaces and tabs encoding an\nadditional CRC, and that didn't work either - at least it never got\nthrough all the test programs, failing in places like the tests\ninvolving notes. In any case, you'd have to phase in such a change\ngradually, first putting in the code to read the new header if it is\nthere, and subsequently (after ample time so that everyone is running\na sufficiently new version) enabling the code to create the new\nheader.\n\nAlso, regarding \"At that point, I really wonder if a flag day to switch\nto a new repository format is all that bad,\" if that turns out to be\nthe decision, I'd recommend doing it sooner rather than later. The\nreason is cost, which grows with the number of git users and the\nnumber and size of Git repositories.\n\nBill\n"},{"id":"180121","messageId":"20111129220507.GF1793@sigill.intra.peff.net","threadId":"29042","inReplyTo":"CAJo=hJtFT55Ucyij9esr3Hd9yJ6XCxatK7vjPOLMKow57HqBoQ@mail.gmail.com","subject":"Re: [PATCH] Implement fast hash-collision detection","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-11-29T22:05:07Z","receivedAt":"2011-11-29T22:05:07Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Nov 29, 2011 at 09:08:27AM -0800, Shawn O. Pearce wrote:\n\n> As Peff pointed out elsewhere in this thread, the odds of a SHA-1\n> collision in a project are low, on the order of 1/(2^80).\n\nMinor nit: it's actually way less than that. You have to do on the order\nof 2^80 operations to get a 50% chance of a collision. But that's not\nthe probability for a collision given a particular number of\noperations[1].\n\nThe probability for a SHA-1 collision on 10 million hashes (where\nlinux-2.6 will be in a decade or two) is about 1/(2^115).\n\nThat doesn't change the validity of any of your points, of course. 1 in\n2^80 and 1 in 2^115 are both in the range of \"impossibly small enough\nnot to care about\".\n\nTo continue our astronomy analogies, NASA estimates[2] the impact\nprobability of most tracked asteroids in the 10^6 range (around 2^20).\nSo getting a collision in linux-2.6 in the next decade has roughly the\nsame odds as the Earth being hit by 5 or 6 large asteroids.\n\n-Peff\n\n[1] http://en.wikipedia.org/wiki/Birthday_problem#Cast_as_a_collision_problem\n\n[2] http://neo.jpl.nasa.gov/risk/\n"},{"id":"180128","messageId":"1322625705.1728.299.camel@yos","threadId":"29042","inReplyTo":"CAJo=hJtFT55Ucyij9esr3Hd9yJ6XCxatK7vjPOLMKow57HqBoQ@mail.gmail.com","subject":"Re: [PATCH] Implement fast hash-collision detection","fromName":"Bill Zaumen","fromEmail":"bill.zaumen@gmail.com","sentAt":"2011-11-30T04:01:45Z","receivedAt":"2011-11-30T04:01:45Z","isPatch":true,"sender":{"key":"bill.zaumen@gmail.com","avatar":null},"body":"Note: for some reason my email is not showing up on the mailing list.\nI'm trying a different email address - previously my 'From' field\ncontained a subaddress \"+git\" but gmail won't put that in the 'Sender'\nfield, so possibly the email is being filtered for that reason.\n\nOn Tue, 2011-11-29 at 09:08 -0800, Shawn Pearce wrote:\n\n> I don't think you understand how these thin packs are processed.\n\nI think the confusion was due to me being a bit too terse. The\ndocumentation clearly states that thin packs allow deltas to be\nsent when the delta is based on an object that the server and client\nboth have in common, given the commits each already has. If there is\none server and one client, there isn't an issue. The case I meant is\nthe one in which a user does a fetch from one server, gets a forged\nblob, and then fetches from another server with the original blob, and\nwith additional commits along the same branch. If a server bases the\ndelta off of the original blob, and the client applies the delta to the\nforged blob, the client will most likely end up with a blob with a\ndifferent SHA-1 hash than the one expected. Since an object in a tree\nis then missing (no object with the expected SHA-1 hash), the repository\nis corrupted.\n\nThe \"first to arrive wins\" policy isn't sufficient in one specific case:\nmultiple remote repositories where new commits are added asynchronously,\nwith the repositories out of sync possibly for days at a time (e.g.,\nover a 3-day weekend). In this case, the first to arrive at one\nrepository may not be the first to arrive at another, so what happens at\na particular client in the presence of hash collisions is dependent on\nthe sequence of remotes from which updates were fetched. The risk\noccurs in the window where the repositories are out of sync.\n\nRegarding the kernel.org problem that you used as a separate example,\nwhile it was fortunately possible to rebuild things (and git provided\nsignificant advantages), earlier detection of the problem might have\nreduced the time for which kernel.org was down. Early detection of\nerrors in general is a good practice if it can be done at a reasonable\ncost.\n\n> Trust. Review. Verify.\n\nWhile good advice in principle, you should keep in mind that there are\na lot of people out there working at various companies who are not as\ncapable as you are. Some of them are overworked and make mistakes\nbecause they've been working 16 hour days for weeks trying to meet a\ndeadline. Given that, extra checks to catch problems early\nare probably a good idea if they don't impact performance significantly.\n"},{"id":"180134","messageId":"20111130062512.GA5317@sigill.intra.peff.net","threadId":"29042","inReplyTo":"1322603788.1728.190.camel@yos","subject":"Re: [PATCH] Implement fast hash-collision detection","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-11-30T06:25:12Z","receivedAt":"2011-11-30T06:25:12Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Nov 29, 2011 at 01:56:28PM -0800, Bill Zaumen wrote:\n\n> The additional CRC (easily changed to whatever message digest one might\n> prefer) makes a malicious attack far more difficult: the modified file\n> has to have both the same SHA-1 hash (including the Git header) and \n> the same CRC (not including the Git header).\n\nOnly if the attack actually involves creating a collision on both. But I\nthink the important attacks bypass your CRC anyway. Consider this attack\nscenario:\n\n 1. Linus signs a tag (or a commit) and pushes it to kernel.org.\n\n 2. kernel.org gets hacked, and the attacker replaces an object with\n an evil colliding version[1].\n\n 3. I clone from kernel.org, and run \"git tag --verify\". Git says it's\n OK, because the signature checks out, but I have a bogus object.\n\nHow does your CRC help? If I understand your scheme correctly,\nkernel.org will have told me the CRC of all of the objects during the\nclone. But that isn't part of what Linus signed, so the attacker in step\n2 could just as easily have overwritten kernel.org's crc file, and the\nsignature will remain valid.\n\n[1] This is an over-simplification, of course. Because the only even\n remotely feasible attacks on sha1 are birthday attacks, not pre-image\n attacks, there is a step 0 in which the attacker generates a\n colliding pair, convinces Linus to commit it, and then waits.\n\n Which is probably really hard, but for the purposes of this\n discussion, we assume the attacker is capable of inserting a\n colliding object maliciously into a repo you will fetch from.\n Otherwise, the integrity of sha1 isn't an issue at all.\n\n> An efficient algorithm to do both simultaneously does not yet exist.\n> So, if we could generate a SHA-1 collision in one second, it would\n> presumably take billions of seconds (many decades of continuous\n> computation) to generate a SHA-1 hash with the same CRC, and well\n> before a year has elapsed, the original object should have been in all\n> the repositories, preventing a forged object from being inserted. Of\n> course, eventually you might need a real message digest.\n\nThis is wrong, for two reasons.\n\n 1. The method for generating an object that collides in both sha-1 and\n CRC is not necessarily to generate a colliding sha-1 and then do a\n pre-image attack on the CRC. It is to do a birthday attack on the\n sha-1 and the CRC together. Which halves the bit-strength of the\n CRC to 16 bits (just as we can generally find collisions in 160-bit\n sha1s in 2^80). 16 bits isn't a lot to add when you are trying to\n fix a broken cryptosystem (it's not broken yet, obviously, but when\n it does get broken, will it be because computing reaches the 2^57\n or so that sha1 is broken at, or will it be because a new weakness\n is found that drops sha1's bit-strength to something much lower?).\n\n This assumes that you can combine the two in a birthday attack.\n Certainly this analysis works against brute-force 2^80 sha1\n collision attacks. But I haven't actually read the details of the\n sha1 attacks, so maybe some of the tweaking they do to get those\n results makes it harder. On the other hand, attacking CRC is far\n from hard, so I certainly wouldn't stake money that sha1 reseachers\n couldn't tweak their attacks in a way that also allows finding CRC\n collisions. You say that an algorithm to do both simultaneously\n does not yet exist. But is that because it's hard, or simply\n because nobody has bothered trying?\n\n Anyway, all of that is just reiterating that CRC should not be used\n as a security function. It can easily be replaced in your scheme by\n sha-256, which does have the desired properties.\n\n 2. Your attack seems to be \"find the sha-1 collision, publish one of\n your colliding objects (i.e., the innocent-looking half), then try\n to break the CRC\". And then you claim that by the time you find the\n CRC, everybody will already have the object.\n\n But wouldn't a smarter attack be to first find the collision, including\n the CRC, and only _then_ start the attack? Then nobody will have\n the object.\n\n Moreover, it's not true that after a year everyone will have the\n object. People still run \"git clone\" against kernel.org. Those\n repos do not have the object.\n\n> The weakness of a CRC as an integrity check is not an issue since it\n> is never used alone: it's use is more analogous to the few extra bits\n> added to a data stream when error-detecting codes are used. I used a\n> CRC in the initial implementation rather than a message digest because\n> it is faster, and because the initial goal was to get things to work\n> correctly. In any case, the patch does not eliminate any code in\n> which Git already does a byte-by-byte comparison. In cases where Git\n> currently assumes that two objects are the same because the SHA-1\n> hashes are the same, the patch compares CRCs as an additional test.\n\nRight. I don't claim that your scheme makes git any weaker. I just claim\nthat it fails to solve the problems people are actually concerned about,\nand it adds a lot of complexity while doing so.\n\n> Regarding your [Jeff's] second concern, \"how does this alternative\n> digest have any authority?\" there are two things to keep in mind.\n> First, it is a supplement to the existing digest.\n\nRight, but we are assuming that sha1 is broken. That's the whole\nsecurity problem. So the existing digest is not worth much.\n\n> Second, any value of the CRC that is stored permanently (baring bugs,\n> in my implementation, of course) is computed locally - when a loose\n> object is created or when a pack file's index is created. At no point\n> is a CRC that was obtained from another repository trusted. While the\n> patch modifies Git so that it can send CRCs when using the git\n> protocol, these CRCs are never stored, but are instead used only for\n> cross checks. If one side or the other \"lies\", you get an error.\n\nBut if I don't already have the object, then I have nothing to compare\nagainst. So when I get it from kernel.org, I have to simply accept that\nthe object I'm getting is good, and write it into my object db.\n\n> BTW, regarding your [Jeff's] discussion about putting an additional\n> header in commit messages - I tried that. The existing versions of\n> Git didn't like it: barring a bug in my test code, it seems that Git\n> expects headers in commit messages to be in a particular order and\n> treats deviations from that to be an error.\n\nYes, the header has to go at the end of the existing headers. But I\ndon't see any reason that would be a problem for the scheme I described.\n\n> I even tried appending blank lines at the end of a commit, with spaces\n> and tabs encoding an additional CRC, and that didn't work either - at\n> least it never got through all the test programs, failing in places\n> like the tests involving notes.\n\nYes, git will helpfully trim whitespace in commit messages. With the\ncurrent code, you can hide arbitrary bytes in a commit message after a\nNUL, but don't do that. It's not guaranteed to stay that way, and the\nappropriate place to add new information is in a header.\n\n> In any case, you'd have to phase in such a change gradually, first\n> putting in the code to read the new header if it is there, and\n> subsequently (after ample time so that everyone is running a\n> sufficiently new version) enabling the code to create the new header.\n\nCurrent git should ignore headers that it doesn't understand. I haven't\ntested this, but Junio recently has been experimenting with\ngpg-signature lines in commits, and I'm pretty sure he checked that\nolder gits properly ignore them.\n\n-Peff\n"},{"id":"180154","messageId":"CACsJy8A6kGmn0h0xdxfTC4krXgc8hzO1fHTdqfk0YnASGN5K0w@mail.gmail.com","threadId":"29042","inReplyTo":"20111129205905.GA1793@sigill.intra.peff.net","subject":"Re: [PATCH] Implement fast hash-collision detection","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2011-11-30T13:35:02Z","receivedAt":"2011-11-30T13:35:02Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Wed, Nov 30, 2011 at 3:59 AM, Jeff King wrote:\n> If you wanted to say \"make a digest of all of the sub-objects pointed to\n> by the tag\", then yes, that does work (security-wise). But it's\n> expensive to calculate. Instead, you want to use a \"digest of digests\"\n> as much as possible. Which is what git already does, of course; you hash\n> the tree object, which contains hashes of the blob sha1s. Git's\n> conceptual model is fine. The only problem is that sha1 is potentially\n> going to lose its security properties, weakening the links in the chain.\n> So as much as possible, we want to insert additional links at the exact\n> same places, but using a stronger algorithm.\n\nWhat I'm thinking is whether it's possible to decouple two sha-1 roles\nin git, as object identifier and digest, separately. Each sha-1\nidentifies an object and an extra set of digests on the \"same\" object.\nObject database is extended to store all these new digests and mapping\nbetween sha-1 and them. When we need to verify an object, given an\nsha-1, we rehash that object and check the result digest with the ones\nlinked to the sha-1.\n\nThese new digests would be \"digest of digests\" just like how we use\nsha-1. In fact this new digest set could be just sha-1. We just don't\nhash trees/commits/tags as-is when computing these new digests. When a\ntree object is hashed, for example, a new tree object with new digests\nwill be created for hashing (we keep sha-1 <-> new digest mapping on\ndisk). Think of duplicating an entire DAG with new digests as links\ninstead of sha-1, then we keep digests and drop the DAG.\n\nThe day sha-1 is broken, a project can generate new digests from its\nold good repo and enforce developers to use new digests for\nverification instead of sha-1. sha-1 is still used by git as\nidentifier after that day.\n\nComputing these digests is expensive, but for local, day-to-day use,\nwe only need sha-1 as identifier (correct me if I'm wrong here), so we\ncan delay compute/store these new digests until we absolutely need\nthem (e.g. push/fetch). There is also an interesting case, assume\nthese digests are strong enough, we could replace sha-1 as identifier\nin git with a cheaper hash. A new hash must fit in 160-bit space that\nsha-1 takes and should have good distribution, of course. Projects\nwith a lot of data may like it that way.\n-- \nDuy\n"},{"id":"180160","messageId":"7vzkfdqye3.fsf@alter.siamese.dyndns.org","threadId":"29042","inReplyTo":"CACsJy8A6kGmn0h0xdxfTC4krXgc8hzO1fHTdqfk0YnASGN5K0w@mail.gmail.com","subject":"Re: [PATCH] Implement fast hash-collision detection","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-11-30T18:05:24Z","receivedAt":"2011-11-30T18:05:24Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nguyen Thai Ngoc Duy writes:\n\n> What I'm thinking is whether it's possible to decouple two sha-1 roles\n> in git, as object identifier and digest, separately.\n\nWhy it would be a good thing? If you have a collided identifier, somebody\nhas to choose which blob a particular tree wants to have at the path, and\nbecause the tree would not record anything but the identifier, you cannot.\n\n> ...\n> The day sha-1 is broken, a project can generate new digests from its\n> old good repo and enforce developers to use new digests for\n> verification instead of sha-1. sha-1 is still used by git as\n> identifier after that day.\n\nAnd an old blob that is identified with a SHA-1 now has a new blob that\nhas different contents but happens to have the same SHA-1. How does Git\ndecide which blob to use when a particular object is named by the SHA-1?\n"},{"id":"180164","messageId":"1322679604.1710.64.camel@yos","threadId":"29042","inReplyTo":"CACsJy8A6kGmn0h0xdxfTC4krXgc8hzO1fHTdqfk0YnASGN5K0w@mail.gmail.com","subject":"Re: [PATCH] Implement fast hash-collision detection","fromName":"Bill Zaumen","fromEmail":"bill.zaumen+git@gmail.com","sentAt":"2011-11-30T19:00:04Z","receivedAt":"2011-11-30T19:00:04Z","isPatch":true,"sender":{"key":"bill.zaumen+git@gmail.com","avatar":null},"body":"[Will send a reply to Jeff's comment from last night with some \nclarifications and explanations later].\n\n> What I'm thinking is whether it's possible to decouple two sha-1 roles\n> in git, as object identifier and digest, separately. Each sha-1\n> identifies an object and an extra set of digests on the \"same\" object.\n> Object database is extended to store all these new digests and mapping\n> between sha-1 and them. When we need to verify an object, given an\n> sha-1, we rehash that object and check the result digest with the ones\n> linked to the sha-1.\n\nThe patch I created (at least, a reasonable chunk of the code) kind of\ndoes that: it is very easy to change the CRC to whatever message digest\none wants. I used a CRC primarily because I had the impression that\npeople were very concerned about speed, but it is easy to change that to\nthe message digest of your choice. In any case, it might be a good\nstarting point if you want to try something in a different direction.\n\nBasically, when you create a loose object, in addition to getting a\nSHA-1 ID, you get a message digest that gets stored as well (in a\nseparate file). When you index a pack file, you get an IDX file\ncontaining the SHA-1 ID plus a corresponding MDS file containing the\nmessage digest. Index-pack calculates the SHA-1 value from the object\nstored in the pack file, and the (additional) message digest is computed\nat the same time using the same data. Commands like verify-pack check\nboth the IDX file and the MDS file for consistency with the matching\npack file. The new message digest (the CRC in the patch) is used only\nin cases where a repository is being altered (e.g., a loose object or\npack file is being created or a fetch, push, or pull operation) or some\nexplicit verification operation is running (e.g., git verify-pack).\n\nAdding an additional header to the commit message is a good idea (I had\nactually tried that, but something went wrong, although one of you\nsuggested what the problem might have been --- I can try again if there\nis some interest in pursuing that).\n\nIt might be worth pointing out that you can use the SHA-1 hash of the\ncontents of objects (e.g., without the Git object header) as an\nadditional digest: I tried a test using two 128-byte files with the\nsame MD5 hash, differing past the 20th byte, and deleted the first\nfour bytes of each. With those bytes deleted, the hash collision\nwent away. I doubt if there is a known efficient algorithm that can\ngenerate a hash collision for two files and for two other files that\ndiffer from the first set by deleting N bytes from both.\n"},{"id":"180183","messageId":"1322700075.1710.157.camel@yos","threadId":"29042","inReplyTo":"20111130062512.GA5317@sigill.intra.peff.net","subject":"Re: [PATCH] Implement fast hash-collision detection","fromName":"Bill Zaumen","fromEmail":"bill.zaumen+git@gmail.com","sentAt":"2011-12-01T00:41:15Z","receivedAt":"2011-12-01T00:41:15Z","isPatch":true,"sender":{"key":"bill.zaumen+git@gmail.com","avatar":null},"body":"On Wed, 2011-11-30 at 01:25 -0500, Jeff King wrote:\n> On Tue, Nov 29, 2011 at 01:56:28PM -0800, Bill Zaumen wrote:\n> But I\n> think the important attacks bypass your CRC anyway. Consider this attack\n> scenario:\n> \n> 1. Linus signs a tag (or a commit) and pushes it to kernel.org.\n> \n> 2. kernel.org gets hacked, and the attacker replaces an object with\n> an evil colliding version[1].\n> \n> 3. I clone from kernel.org, and run \"git tag --verify\". Git says it's\n> OK, because the signature checks out, but I have a bogus object.\n> \n> How does your CRC help? If I understand your scheme correctly,\n> kernel.org will have told me the CRC of all of the objects during the\n> clone. But that isn't part of what Linus signed, so the attacker in step\n> 2 could just as easily have overwritten kernel.org's crc file, and the\n> signature will remain valid.\n\nFirst, there is a misconception - the server will not tell you the CRC.\nThe CRC will be computed locally by the client instead. \n\nAside from that, suppose the attacker does what you suggests (providing\na valid CRC so that git commands like verify-pack don't have an error\nto detect). You can't tell that something is wrong, but Linus can - \nthe next time he does a fetch. If he fetches, the server sends\nsome SHA-1 hashes and the client responds with 'have' or 'want' in a\nreply. If the client wants it, the client doesn't have a CRC, if the\nclient sends 'have', the CRCs are available so those get sent. The\nserver then checks, notices a mismatch (probably in the CRC of the CRCs\nof all the blobs in the commit's tree), and generates an error.\n\nIt's also possible to write some additional commands to (for example)\nfetch the SHA-1 hashes and CRCs from all remote repositories you use\nand compare these to make sure they are all consistent, something that\ncan be run ocassionally.\n\n\n> > An efficient algorithm to do both simultaneously does not yet exist.\n> > So, if we could generate a SHA-1 collision in one second, it would\n> > presumably take billions of seconds (many decades of continuous\n> > computation) to generate a SHA-1 hash with the same CRC, and well\n> > before a year has elapsed, the original object should have been in all\n> > the repositories, preventing a forged object from being inserted. Of\n> > course, eventually you might need a real message digest.\n> \n> This is wrong, for two reasons.\n> \n> 1. The method for generating an object that collides in both sha-1 and\n> CRC is not necessarily to generate a colliding sha-1 and then do a\n> pre-image attack on the CRC. It is to do a birthday attack on the\n> sha-1 and the CRC together. Which halves the bit-strength of the\n> CRC to 16 bits (just as we can generally find collisions in 160-bit\n> sha1s in 2^80). \n\nThat result for birthday attack assumes the goal is to find two files\nthat will have the same SHA-1 value (or SHA-1 + CRC). The case I was\ntalking about (apologies if I did not state this clearly) is that you\nhave an existing object and an existing CRC and you want to generate\na second object with the same SHA-1 and same CRC as the first. A\nbirthday attack doesn't work so well in that case - the number of tries\nis much higher than half the number of bits in the digest.\n\nhttp://en.wikipedia.org/wiki/Birthday_attack#Digital_signature_susceptibility\nhas a discussion regarding digital signatures. The trick is for a\nperson to create a large number of variations of a \"fair\" and \"unfair\"\ncontract, and use a birthday attack to find a pair that have the same\nhash. The variations are typically inconsequential changes (extra\nspacing, commas, etc.) In the case I was discussing, a developer\ncreates some code, commits it and pushes it to a shared repository -\nthe developer is not given code by the attacker. The attacker can,\nhowever, see the code by fetching it. An attack then consists of\ngenerating a collision, change the object in the attacker's local\nrepository, and then push the original developer's commit (with the\nmodified object) to another shared repository before someone else\nputs the correct objects into that repository. A birthday attack\ndoes not work in this case.\n\nThere one issue that this suggests however - it is not clear if the\n2^57 number given for the best SHA-1 attacks were attempts to generate\na new file with the same SHA-1 hash as an existing file or a pair of\nfiles that have the same SHA-1 hash. If it is the latter, then an\nattack is significantly harder than I assumed as a worst case, but\nstill possibly much, much better than brute force.\n\nhttp://en.wikipedia.org/wiki/Birthday_problem has an analysis of the\nbirthday problem (the basis of a birthday attack) and clearly notes that\nthis is different than the \"same birthday as you\" variation - you don't\ndo nearly so well in that case.\n\n> Anyway, all of that is just reiterating that CRC should not be used\n> as a security function. It can easily be replaced in your scheme by\n> sha-256, which does have the desired properties.\n\nOh, I'm perfectly happy with sha-256 (and indicated that in the\ndocumentation that is in the patch) - there's a tradeoff between error\ndetection and speed, and I simply guessed that the community was more\nconcerned with speed.\n\n> 2. Your attack seems to be \"find the sha-1 collision, publish one of\n> your colliding objects (i.e., the innocent-looking half), then try\n> to break the CRC\". And then you claim that by the time you find the\n> CRC, everybody will already have the object.\n> \n> But wouldn't a smarter attack be to first find the collision, including\n> the CRC, and only _then_ start the attack? Then nobody will have\n> the object.\n\nMy assumption was that legitimate developer wrote some code, put it in\none of the remote repositories, and than an attacker downloaded that\ncode and tried to get a modified version into a different remote\nrepository.\n\n> \n> Moreover, it's not true that after a year everyone will have the\n> object. People still run \"git clone\" against kernel.org. Those\n> repos do not have the object.\n\nThis isn't the problem - a clone is going to be an exact copy of an\nexisting repository. I was referring to the case where a commit made it\ninto one remote repository but not another - to get into the second one,\nsomeone else would have had to review the code, creating a window where\nan attacker with write access to the second repository could put the\nmodified object there.\n\n> Right, but we are assuming that sha1 is broken. That's the whole\n> security problem. So the existing digest is not worth much.\n\nThe assumption was more that \"J Random Hacker's\" code would be\ntrusted far less than code submitted by Linus, so if \"J Random Hacker\"\ncan generate create a replacement file with the same SHA-1 hash as\none in one of Linus' commits, others will initially assume that Linus\nwrote that code. But, Git uses a \"first in wins\" rule so the bad guy\nhas to generate the replacement file and get it inserted before Linus'\ncommit reaches all the shared repositories for the project. A SHA-1\ncollision is harmless if computed too late to get in.\n\n> > Second, any value of the CRC that is stored permanently (baring bugs,\n> > in my implementation, of course) is computed locally \n\n> But if I don't already have the object, then I have nothing to compare\n> against. So when I get it from kernel.org, I have to simply accept that\n> the object I'm getting is good, and write it into my object db.\n\nThe value is computed locally but can be compared remotely.\n\nYou (specifically) won't find anything while talking to kernel.org in\nthis example, but when you try to fetch from a different repository,\ninstead of just noting that you have the object, you'll get a\nnotification that there was a collision, so you'll find the problem\nearlier than you would otherwise. Also, anyone who had the right object\nfrom kernel.org (the object before the repository was 'hacked' would get\na warning when trying to fetch from kernel.org after the change.\n\n> Yes, the header has to go at the end of the existing headers. But I\n> don't see any reason that would be a problem for the scheme I described.\n\nThanks for mentioning it - I tried putting the header in multiple\nlocations and probably missed the one spot where it would work.\n\n> Current git should ignore headers that it doesn't understand. I haven't\n> tested this, but Junio recently has been experimenting with\n> gpg-signature lines in commits, and I'm pretty sure he checked that\n> older gits properly ignore them.\n\nPossibly there was another bug in the test I tried as well - something\nwas preventing the directory cleanup in one of the 'notes' test.\n\nAnyway, thanks for the comments.\n\nBill\n"},{"id":"180190","messageId":"CACsJy8Dmyha-L-iW3KVzAZ6wX+gH4qWSXPUT-XQJX1xYewuzMw@mail.gmail.com","threadId":"29042","inReplyTo":"7vzkfdqye3.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] Implement fast hash-collision detection","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2011-12-01T04:43:23Z","receivedAt":"2011-12-01T04:43:23Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Thu, Dec 1, 2011 at 1:05 AM, Junio C Hamano wrote:\n> Nguyen Thai Ngoc Duy writes:\n>\n>> What I'm thinking is whether it's possible to decouple two sha-1 roles\n>> in git, as object identifier and digest, separately.\n>\n> Why it would be a good thing? If you have a collided identifier, somebody\n> has to choose which blob a particular tree wants to have at the path, and\n> because the tree would not record anything but the identifier, you cannot.\n\nAccidental collision likelihood is small enough we don't have to care about.\n\n>> ...\n>> The day sha-1 is broken, a project can generate new digests from its\n>> old good repo and enforce developers to use new digests for\n>> verification instead of sha-1. sha-1 is still used by git as\n>> identifier after that day.\n>\n> And an old blob that is identified with a SHA-1 now has a new blob that\n> has different contents but happens to have the same SHA-1. How does Git\n> decide which blob to use when a particular object is named by the SHA-1?\n\nAgain, I assume the likelihood that a content happens to have the same\nsha-1 with another one is too low to care about. If they are, it's\nmust be an attack. We do not allow malicious objects to enter in the\nfirst place using other digests. Once objects are in, they are safe to\nuse.\n-- \nDuy\n"},{"id":"180192","messageId":"20111201052615.GA22141@sigill.intra.peff.net","threadId":"29042","inReplyTo":"1322700075.1710.157.camel@yos","subject":"Re: [PATCH] Implement fast hash-collision detection","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-12-01T05:26:15Z","receivedAt":"2011-12-01T05:26:15Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Nov 30, 2011 at 04:41:15PM -0800, Bill Zaumen wrote:\n\n> Aside from that, suppose the attacker does what you suggests (providing\n> a valid CRC so that git commands like verify-pack don't have an error\n> to detect). You can't tell that something is wrong, but Linus can - \n> the next time he does a fetch. If he fetches, the server sends\n> some SHA-1 hashes and the client responds with 'have' or 'want' in a\n> reply. If the client wants it, the client doesn't have a CRC, if the\n> client sends 'have', the CRCs are available so those get sent. The\n> server then checks, notices a mismatch (probably in the CRC of the CRCs\n> of all the blobs in the commit's tree), and generates an error.\n\nOK. I thought your claim was that this would help detect\ncollision-related forgeries in the chain of hashes while verifying a\nsigned tag. But your claim is only that your scheme gives people who\nalready have the objects an additional chance to notice discrepencies in\nwhat the server is serving and what they have. And then they can notify\nother people of the problem in an out-of-band way (i.e., telling\nkernel.org admins that the system is hacked, or telling users not to\nfetch from there).\n\nCryptographically speaking, I think that claim is sound, and you can\ncertainly construct attack scenarios where this detection would help.\nHowever, quantifying the effectiveness is difficult. What is the\nlikelihood of a malicious collided-object replacement being detected\nwithout your scheme? What is it with it?\n\nThere are many questions that factor into guessing the latter.\n\nHow often does Linus fetch from his own kernel.org repository? He would\nusually push, I would think. Even if he does fetch, he wouldn't be\ngetting the old objects that he already has. I guess this is the reason\nfor your digest-of-digests for each commit object sent? But what about\nobjects that are no longer in current commits, but are in older ones?\nE.g., v1.0 of foo.c has sha1 X, and an attacker finds a collision and\nreplaces it. Meanwhile, the tip of development now has replaced foo.c\nwith X'. When Linus talks to the server, git will never care about X (it\nis neither being transmitted, nor is part of a commit that is being\ntransmitted). But people may still be cloning and using the v1.0 tag,\nassuming it is valid.\n\nWhat about the server being more clever about hiding the replacement\nobject? E.g., instead of just breaking into kernel.org and inserting a\nreplacement object, the attacker runs a malicious git-daemon that\nreturns the bogus object to cloners, but the real object to fetchers.\nThus there is nothing for Linus to detect, but new cloners get the\nmalicious object. Or you could give the bogus object to people who are\ngetting the object for the first time (since they presumably have no\ncrc for that object), but otherwise use the real object.\n\nYou could get around this deception by pretending to be a \"victim\";\ni.e., cloning fresh and seeing what the server gives you, comparing it\nto your known-good repository. Which is similar to what you suggest\nhere:\n\n> It's also possible to write some additional commands to (for example)\n> fetch the SHA-1 hashes and CRCs from all remote repositories you use\n> and compare these to make sure they are all consistent, something that\n> can be run ocassionally.\n\nBut we can already do that. Assume you have an existing repo \"foo\". To\nverify the copy at git://example.com/foo.git, do a fresh clone to\n\"bar\", and then compare the objects in \"foo\" to \"bar\", either byte-wise\nor by digest.\n\n> That result for birthday attack assumes the goal is to find two files\n> that will have the same SHA-1 value (or SHA-1 + CRC). The case I was\n> talking about (apologies if I did not state this clearly) is that you\n> have an existing object and an existing CRC and you want to generate\n> a second object with the same SHA-1 and same CRC as the first. A\n> birthday attack doesn't work so well in that case - the number of tries\n> is much higher than half the number of bits in the digest.\n\nYes. This is called a \"pre-image\" attack (to be more specific, it is a\n\"second pre-image attack\", since you have the original object). And\nAFAIK, it's not feasible against SHA-1, nor will it be in the near\nfuture (even MD5, which is considered totally broken, does not have\nfeasible pre-image attacks).\n\n> http://en.wikipedia.org/wiki/Birthday_attack#Digital_signature_susceptibility\n> has a discussion regarding digital signatures. The trick is for a\n> person to create a large number of variations of a \"fair\" and \"unfair\"\n> contract, and use a birthday attack to find a pair that have the same\n> hash. The variations are typically inconsequential changes (extra\n> spacing, commas, etc.)\n\nRight. This is the classic birthday attack. I don't keep up with the\nstate of the art in collision attacks these days, but I think in\npractice they are usually executed by adding arbitrary binary garbage\ninto a \"hidden\" spot in a file. Which makes it much harder to execute\nagainst text files like source code (as opposed to, say, a binary\nfirmware blob). IIRC, the practical MD5 attacks involved postscript\ndocuments (with non-printing garbage sections that printers would\nignore).\n\n> In the case I was discussing, a developer creates some code, commits\n> it and pushes it to a shared repository - the developer is not given\n> code by the attacker. The attacker can, however, see the code by\n> fetching it. An attack then consists of generating a collision,\n> change the object in the attacker's local repository, and then push\n> the original developer's commit (with the modified object) to another\n> shared repository before someone else puts the correct objects into\n> that repository. A birthday attack does not work in this case.\n\nYeah, that is simply not feasible, and is not likely to become so\nanytime soon.\n\n> There one issue that this suggests however - it is not clear if the\n> 2^57 number given for the best SHA-1 attacks were attempts to generate\n> a new file with the same SHA-1 hash as an existing file or a pair of\n> files that have the same SHA-1 hash. If it is the latter, then an\n> attack is significantly harder than I assumed as a worst case, but\n> still possibly much, much better than brute force.\n\nThe 2^57 number is for a collision of two new objects, not for a\npre-image attack. AFAIK, there are currently no pre-image attacks on\nSHA-1 at all.\n\nI don't think there's a need to response individually to the points in\nthe rest of your email; they're all based on the assumption that the\nattacker is replacing a known-good written-by-Linus commit with one\nfound in a pre-image attack.\n\n-Peff\n"},{"id":"180237","messageId":"1322794744.1673.494.camel@yos","threadId":"29042","inReplyTo":"20111201052615.GA22141@sigill.intra.peff.net","subject":"Re: [PATCH] Implement fast hash-collision detection","fromName":"Bill Zaumen","fromEmail":"bill.zaumen+git@gmail.com","sentAt":"2011-12-02T02:59:04Z","receivedAt":"2011-12-02T02:59:04Z","isPatch":true,"sender":{"key":"bill.zaumen+git@gmail.com","avatar":null},"body":"On Thu, 2011-12-01 at 00:26 -0500, Jeff King wrote:\n\n> Cryptographically speaking, I think that claim is sound, and you can\n> certainly construct attack scenarios where this detection would help.\n> However, quantifying the effectiveness is difficult. What is the\n> likelihood of a malicious collided-object replacement being detected\n> without your scheme? What is it with it?\n> \n> There are many questions that factor into guessing the latter.\n> \n> How often does Linus fetch from his own kernel.org repository? He would\n> usually push, I would think. Even if he does fetch, he wouldn't be\n> getting the old objects that he already has. I guess this is the reason\n> for your digest-of-digests for each commit object sent? \n\nYes, - the digest of digests is used to check things that would not be\nsent.\n\n>\n> But what about\n> objects that are no longer in current commits, but are in older ones?\n\nThat's a good question, of course. After Linus pushes a commit, he'll\nnotify others, and if some fetch before the repository is hacked,\nthey will detect an error on a subsequent fetch. For fetches, the\nserver reports a series of commits, and the client responds with 'have'\nfor those it has, with the CRCs added so the server can check for a\nmismatch. I made minimal changes to fetch-pack.c and upload-pack.c:\njust adding the CRC fields to the messages already sent. The server\nasks about more commits than it actually transfers, but all the ones\nit asks about are tested. One could send additional 'have' replies\nif necessary (for ones the server didn't mention) but I didn't do\nthat, partly for simplicity but also because I was looking at the\nfetch-pack.c and update-pack.c code for the first time. If desired,\nsuch changes can be added.\n\nI also do some similar checking when a commit is pushed - the server\ntells the client the last commit it has and the client will send the\nCRCs in its reply to allow the server to cross check those. I didn't\nmention that before because only the latest is really checked. Again,\nI just changed a message format (backwards compatible, of course),\nbut additional checking could be added if desired.\n\nYou could also add options to check tips of branches and all commits\nthat have tags (e.g., a v1.0 tag) All of that simply requires more\nwork on commands such as fetch-pack, upload-pack, send-pack and\nreceive-pack.\n\n> What about the server being more clever about hiding the replacement\n> object? E.g., instead of just breaking into kernel.org and inserting a\n> replacement object, the attacker runs a malicious git-daemon that\n> returns the bogus object to cloners, but the real object to fetchers.\n\nThat's really a server-security issue, not a git one. Perhaps\nrepositories should be configured so that all the executables are on\nread-only partitions. It's an important question in general of\ncourse, but it is probably useful to distinguish attacks that put\nbad data on a server from ones that install new software.\n\n> \n> > It's also possible to write some additional commands to (for example)\n> > fetch the SHA-1 hashes and CRCs from all remote repositories you use\n> > and compare these to make sure they are all consistent, something that\n> > can be run ocassionally.\n> \n> But we can already do that. Assume you have an existing repo \"foo\". To\n> verify the copy at git://example.com/foo.git, do a fresh clone to\n> \"bar\", and then compare the objects in \"foo\" to \"bar\", either byte-wise\n> or by digest.\n\nOf course, but that is an expensive operation - in the case of Git\ntransferring some 50 MBytes of data per repository. A command to\nfetch the SHA-1 ID and a CRC or message digest for each object would\nnot only run faster, but should put a much lower load on the server.\n\nGetting back to the birthday attack question (this is an area where\nyour comments were very useful for me), there's a case I didn't\nconsider.\n\nSuppose two developers bounce code back and forth by email and one of\nthem commits it, but the other developer is a bad guy. The bad guy\nwould then have had an opportunity to use a birthday attack by sending\nback subtly modified code (e.g., changes to how comments are formated,\nadditional blank lines, etc.) He can even put a humorous comment at\nthe end of the file such as \"the first 200 Chinese characters I learned\"\nand then include the Chinese characters (I've tested this with gcc -\nthe Chinese characters, represented in Unicode, print in an editor and\nare ignored by the compiler.) Unicode is a lot closer to binary data\nso you have a lot of bits you can alter in a small amount of space,\nwith each character requiring multiple bytes to represent it. The\ncomment will look silly but innocuous. I think Linus Torvalds once\nsuggested being suspicious of anything that looked like \"line noise\"\nin a patch. Non-western unicode characters can serve the same function\nbut look legitimate, at least to people who don't know the language\nand when coupled with some \"social engineering\" to set expectations.\n\nAs an example of how this attack might work, without breaking into a\nsystem, assume two programmers collaborating on a project both have\nwrite-access to the same shared repository.\n\n1. The project is using Java, with a rule that all classes and methods\nthat are protected or public be documented (so javadoc can create API\ndocumentation).\n\n2. Programmer A emails some Java source code to programmer B with a\nrequest to edit the comments to improve them or fix any obvious\nmistakes.\n\n3. Programmer B fixes the comments, but also creates a modified file\nwith the same SHA-1 hash as the correct file in order to add some bugs\nor security flaws. \n\n4. Programmer B creates a branch from an earlier version, adds some\ntests, puts the contents of the modified file into the directory tree\nunder an obscure name, adds it and does a commit. B then pushes it,\ncreating a new remote branch.\n\n5. Programmer B then tells Programmer A that he'll have the modified\nfile back quickly, but could he please fetch his new remote branch\nand run a test, and answer some questions about what happens as B needs\nthat information to finish his review of the documentation.\n\n6. Programmer A tells B the results, so B knows that A has fetched the\nremote branch, an B then sends A the corrected file (not the modified\none). Programmer A reviews the file, notes that everything seems OK,\nspecifically that only comments were changed, and runs commit -a\nfollowed by a push. Because Git tries to be smart, it will (I think)\nnotice from the SHA-1 hashes and from the remote branches that the\nserver already has the object so there is no need to send it.\n\n8. Programmer B fetches the changes, deletes his temporary branch, both\nlocally and on the shared repository. He tells A that the temporary\nbranch is deleted so that B should run \"git branch update --prune ...\"\n\nSo what happens? Hopefully someone finds the problem, either through a\nsource-code review or some QA testing, but regardless Programmer A may\nget the blame as the evidence of any tampering has pretty much been\nerased. In the worst case, a release with a security hole goes out.\n\nWhy would Programmer B do that? Maybe he's leaving the company because\nhe's hard to work with and is blaming Programmer A for the problem, and\nwants to \"get back\" at Programmer A by harming his career. But in any\ncase he didn't have to break into the repository to get the effect he\nwanted. At least is is extremely hard to do in terms of computational\nresources.\n\nBill\n"},{"id":"180257","messageId":"20111202170040.GA23447@sigill.intra.peff.net","threadId":"29042","inReplyTo":"1322794744.1673.494.camel@yos","subject":"Re: [PATCH] Implement fast hash-collision detection","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-12-02T17:00:40Z","receivedAt":"2011-12-02T17:00:40Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Dec 01, 2011 at 06:59:04PM -0800, Bill Zaumen wrote:\n\n> > What about the server being more clever about hiding the replacement\n> > object? E.g., instead of just breaking into kernel.org and inserting a\n> > replacement object, the attacker runs a malicious git-daemon that\n> > returns the bogus object to cloners, but the real object to fetchers.\n> \n> That's really a server-security issue, not a git one. Perhaps\n> repositories should be configured so that all the executables are on\n> read-only partitions. It's an important question in general of\n> course, but it is probably useful to distinguish attacks that put\n> bad data on a server from ones that install new software.\n\nI don't agree here. You have to assume that the attacker will ignore\nattacks you have blocked, but continue with ones you haven't (just to\ncounter your example, why not replace the running git-daemon\nin-memory?).\n\nYou can target the narrow window of attacks that compromise the on-disk\nrepository without being able to execute arbitrary code. But I don't see\na point. After the kernel.org hack, yes, people are interested in\nhardening kernel.org. But they are much more interested in cryptographic\nsources of authority that let us not have to trust kernel.org at all.\nHaving some weird half-way trust just complicates things.\n\n> > But we can already do that. Assume you have an existing repo \"foo\". To\n> > verify the copy at git://example.com/foo.git, do a fresh clone to\n> > \"bar\", and then compare the objects in \"foo\" to \"bar\", either byte-wise\n> > or by digest.\n> \n> Of course, but that is an expensive operation - in the case of Git\n> transferring some 50 MBytes of data per repository. A command to\n> fetch the SHA-1 ID and a CRC or message digest for each object would\n> not only run faster, but should put a much lower load on the server.\n\nYes, it is more expensive. But again, my threat model is that the server\nis not trusted to serve data accurately or consistently. So you can't\ncome to the server and say \"Hey, I'm doing a security verification. Can\nyou send me the CRCs?\" You _have_ to present yourself as one of the\nvictims to be infected by the bad object, or a smart attacker will send\nyou the unmodified data.\n\n> Getting back to the birthday attack question (this is an area where\n> your comments were very useful for me), there's a case I didn't\n> consider.\n> [elaborate birthday attack scenario]\n\n>From my quick reading of your scenario, yes, that is a possible attack.\nTo me, though, it just highlights the need for either a non-colliding\nalgorithm, or for better trust verification about the authors of objects\n(i.e., cryptographically strong trust).\n\n-Peff\n"}]}