{"thread":{"id":"390","subject":"Val Henson's critique of hash-based content storage systems","startedAt":"2005-04-29T00:06:01Z","lastAt":"2005-04-29T20:47:17Z","messageCount":8,"participants":["Rob Jellinghaus","Linus Torvalds","Tom Lord","C. Scott Ananian","H. Peter Anvin","Morten Welinder"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"2132","messageId":"loom.20050429T015434-928@post.gmane.org","threadId":"390","inReplyTo":null,"subject":"Val Henson's critique of hash-based content storage systems","fromName":"Rob Jellinghaus","fromEmail":"robj@unrealities.com","sentAt":"2005-04-29T00:06:01Z","receivedAt":"2005-04-29T00:06:01Z","isPatch":false,"sender":{"key":"robj@unrealities.com","avatar":null},"body":"I assume most people here have read this, but just in case:\n\nhttp://www.usenix.org/events/hotos03/tech/full_papers/henson/henson.pdf\n\nIs git vulnerable to attacks in the event that SHA-1 is broken?\n\nIf an attacker used an SHA-1 attack to create a blob that matched the hash of\nsome well-known git object (say, the tree for Linux 2.7-rc1), and spammed public\ngit repositories with it ahead of Linus's release, what would be the potential\nfor mischief, and what would the recovery process be?\n\nIt seems that git is optimized to support networks of trust, so provided you\naccept only signed commits from people you trust, it's likely that corruption\nand mischief can be mostly avoided.  But probably not completely; there is still\na window of vulnerability.\n\nIt seems that git repositories could (at great expense) be regenerated to use a\nnew hash algorithm.  Is that the plan if SHA-1 is compromised (or comes so close\nto compromise as to make Linus nervous ;-)?\n\nCheers,\nRob\n\n\n"},{"id":"2161","messageId":"Pine.LNX.4.58.0504291221250.18901@ppc970.osdl.org","threadId":"390","inReplyTo":"loom.20050429T015434-928@post.gmane.org","subject":"Re: Val Henson's critique of hash-based content storage systems","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-04-29T19:45:07Z","receivedAt":"2005-04-29T19:45:07Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 29 Apr 2005, Rob Jellinghaus wrote:\n> \n> If an attacker used an SHA-1 attack to create a blob that matched the hash of\n> some well-known git object (say, the tree for Linux 2.7-rc1), and spammed public\n> git repositories with it ahead of Linus's release, what would be the potential\n> for mischief, and what would the recovery process be?\n\nI really think people should not consider the sha1 the \"security\". \n\nThe real security is in distribution. \n\nWith the distributed setup, developers don't use public trees. They use \ntheir own _private_ trees, and the public ones are just staging areas for \nsynchronization.\n\nSo in order to actually replace a blob, let's say that you can create an \nobject with the right sha1 trivially. What then?\n\nYou now have to break into _every_ repository that has that object, and \nreplace it silently. Because if you don't, the good one will still be \naround.\n\nThat's just not going to happen.\n\nSo let's say that you break into kernel.org, and replace one of the blobs\nin my repository.  What happens?\n\nFirst off, I'll never notice, because it's not actually my repository, so \nI won't even have the corrupt copy. So what _will_ happen?\n\nWhat will happen is that people who download new stuff from kernel.org\nwill get the \"evil\" object. Not all of them, though - just the ones that\nhadn't downloaded the proper one. So first off, in order to be really\n_effective_, the attack really has to not just replace an object, it\nreally wants to replace a pretty _recent_ object, because replacing an old\njust just doesn't do a whole lot.\n\nSo they get the evil object. What happens? NOTHING. Absolutely nada.  \nEither they use that evil object, or they don't. Not using it might be\nbecause it's not even top-of-tree any more, and you really just replaced\nsome old version of a file. Or it might be because it's a object for a\ndriver that you don't have, so you'd never see it.\n\nSo let's ignore that case, and say that the attacker has successfully\nreplaced an object that is (a) recent enough to matter and (b) actually\nused.\n\nWhat now? You'll get a compile error. Big deal. People will notice that\nsomething is wrong, complain about it, we'll think they have disk\ncorruption for a while, and then we'll figure it out, and replace the\nobject. Done.\n\nWhy? Because even if you successfully find an object with the same SHA1, \nthe likelihood that that object actually makes _sense_ in that conctext is \npretty damn near zero. \n\nThink about it. We've had this before: people whose files got flipped\naround due to driver bugs or just hardware problems, and even just a\nsingle bit error most of the time results in real honest-to-God compiler\nerrors.\n\nAnd because we found the bad one, and we have the good one somewhere else, \nwho cares? The security industry will be all atwitter about somebody \nfinding a matching SHA1 object, and it will be _huge_ news, but did it \nactually hurt the kernel integrity? No.\n\nSo let's say that somebody breaks in to _my_ personal machine. I'm behind \na few firewalls and a NAT setup, and I don't accept even incoming ssh, but \nhey, they could crowbar my door and break in that way. \n\nONLY A TOTAL IDIOT would then replace an object in my database with\nsomething else. That would be _stupid_. He'd just guarantee that all the \nsame problems as above were true, except now we'd have to find the \ngood object in some _other_ database than mine.\n\nSo if you actually wanted to corrupt the kernel tree, you'd do it by just\nfooling me into accepting a crap patch. Hey, it happens all the time.  \nPeople send me buggy stuff. We figure out the bugs. What's so different\nhere?\n\nIn other words, the security isn't in the hash. The hash is an added level \nto make it much harder to fool, but it's not \"the security\". \n\nAnd if we are really really unlucky, and a meteorite hits us, and we get\nan object collision that has the same sha1 for _real_, and actually makes\nsense, then hey, shit happens. We can fix it by \"poisoning\" that sha1, and\nmodifying both files trivially so that they don't match any more, and then\nwe add a list of \"illegal\" sha1's to fsck, and we'll make that list be ten\nentries long, just in case the meteorite strikes ten times, but the fact\nis it's simply not going to happen.\n\n(It's going to be very very obvious, very very quickly, btw: the person\nwho actually created the object that happened to collide will not write\nthe new SHA1 out, because he already \"had\" the same object, so next time\nsomebody updates the tree, the file that matches will now have the \"old\ncontents\" from some other colliding file, and the new code simply won't do\nwhat it was supposed to. So don't worry about it - collisions, even if\nthey happen, will be noticed as quite obvious _bugs_ in the end result,\nthe same way we find the common source of bugs - bad programming).\n\nIn other words: don't depend on hashes if you only have one copy of the\ndata. But if you have backups of old versions (which essentially the\ndistribution guarantees as long as we have \"stupid\" mirrors that just look\nat the filename) having a hash collision doesn't mean that you lost any\nreal data.\n\nSo anybody who thinks that a hash collision is a fundamental problem just\nhasn't thought things through. It's an _annoyance_, nothing more. But we\nhave tons of much more pressing annoyances, and pretty much all of them\nare a hell of a lot more likely than a collission, whether intentional or\nunintentional.\n\n\t\t\tLinus\n"},{"id":"2165","messageId":"200504291952.MAA27541@emf.net","threadId":"390","inReplyTo":"Pine.LNX.4.58.0504291221250.18901@ppc970.osdl.org","subject":"Re: Val Henson's critique of hash-based content storage systems","fromName":"Tom Lord","fromEmail":"lord@emf.net","sentAt":"2005-04-29T19:52:43Z","receivedAt":"2005-04-29T19:52:43Z","isPatch":false,"sender":{"key":"lord@emf.net","avatar":null},"body":"\n\nI wouldn't expect outright successful attacks like forged replacements\nfor arbitrary files.\n\nI would expect someone to have on hand a small number of blobs that are\ndifferent but have different hashes and, eventually, to drop said files\ninto a blob-based infrastructure to wreak havoc.\n\nSo: a way to locally mark a given checksum as \"controversial\" seems \nprudent, to me (hence, support for such in my blob-db code/spec).\n\n-t\n"},{"id":"2174","messageId":"42729591.8020108@zytor.com","threadId":"390","inReplyTo":"loom.20050429T015434-928@post.gmane.org","subject":"Re: Val Henson's critique of hash-based content storage systems","fromName":"H. Peter Anvin","fromEmail":"hpa@zytor.com","sentAt":"2005-04-29T20:14:09Z","receivedAt":"2005-04-29T20:14:09Z","isPatch":false,"sender":{"key":"hpa@zytor.com","avatar":null},"body":"Rob Jellinghaus wrote:\n> I assume most people here have read this, but just in case:\n> \n> http://www.usenix.org/events/hotos03/tech/full_papers/henson/henson.pdf\n> \n\nI have to pull out the big flamethrower, especially against someone I \nconsider a friend, but that paper is a classic example on how many \npeople don't understand probability.\n\nThe *only* valid criticism in it is that we may not know enough about \nthe future validity of cryptographic hash function, however, she also \ndoes not analyze the failure scenarios applicable to those kinds of \nfailures barely at all.\n\nIn the end, the whole paper centers around \"this makes me feel nervous\", \nwithout really justifying it in any reasonable way.\n\nIt is just one of many papers on cryptoanalysis written by someone with \nno real background in the field.  It really saddens me to see someone \nlike Val fall into that particular trap.\n\n\t-hpa\n"},{"id":"2171","messageId":"Pine.LNX.4.61.0504291608410.32145@cag.csail.mit.edu","threadId":"390","inReplyTo":"200504291952.MAA27541@emf.net","subject":"Re: Val Henson's critique of hash-based content storage systems","fromName":"C. Scott Ananian","fromEmail":"cscott@cscott.net","sentAt":"2005-04-29T20:17:25Z","receivedAt":"2005-04-29T20:17:25Z","isPatch":false,"sender":{"key":"cscott@cscott.net","avatar":"https://gravatar.com/avatar/3551c2aefb299a0c45807f7677f5b26d8a5be4a4af359b4bf4fabbdd1f2b990e?d=mp&s=160"},"body":"On Fri, 29 Apr 2005, Tom Lord wrote:\n\n> I would expect someone to have on hand a small number of blobs that are\n> different but have different hashes and, eventually, to drop said files\n> into a blob-based infrastructure to wreak havoc.\n\nThis is just ridiculous.  The number of known collisions in SHA1 is \n*exactly zero* at this point in time --- not guaranteed to stay that way, \nof course, but generating collisions is likely to remain relatively \nexpensive for some time.  The collisions are highly structured; they are \nnot just arbitrary blobs.  If, after doing your 2^69 work or so to \ngenerate a real honest-to-goodness SHA-1 collision, you think an \nattacker would \"DROP THEM IN A REPOSITORY TO CREATE HAVOC\"?  You'd have to \nbreak into the repository, etc, and then you'd find that *NOTHING \nREFERENCED THEM* and so *ABSOLUTELY NOTHING WOULD HAPPEN*.\n\nIt's far more likely that SHA1 collisions will be used to generate forged \nX509 certificates, for a number of highly technical reasons.\n\nGit's highly constrained and derided 'brittle' file formats also serve\nto protect against the collision attacks against SHA-1 which are beginning \nto look possible.\n\n> So: a way to locally mark a given checksum as \"controversial\" seems\n> prudent, to me (hence, support for such in my blob-db code/spec).\n\nArguably that's what *upgrades* to the spec might be for -- git has a \nsolid philosophy of not creating 'features' unless it is sure that they \nare needed/will be used, and I think this is always the wise route in \nsoftware development.  Of much specification comes no code.\n\nAnd, if you actually create a 'flexible' blob-db spec with 'room for \nexpansion' -- congratulations, you've just made yourself more vulnerable \nto collision attacks.\n  --scott\n\nterrorist MI5 SKILLET hack AMLASH security KMPLEBE KUFIRE SCRANTON \nD5 SLBM LINCOLN KUDESK SMOTH Kojarena Moscow HTAUTOMAT WSBURNT Chechnya\n                          ( http://cscott.net/ )\n"},{"id":"2179","messageId":"200504292037.NAA28344@emf.net","threadId":"390","inReplyTo":"Pine.LNX.4.61.0504291608410.32145@cag.csail.mit.edu","subject":"Re: Val Henson's critique of hash-based content storage systems","fromName":"Tom Lord","fromEmail":"lord@emf.net","sentAt":"2005-04-29T20:37:47Z","receivedAt":"2005-04-29T20:37:47Z","isPatch":false,"sender":{"key":"lord@emf.net","avatar":null},"body":"\n  lord:\n\n  > I would expect someone to have on hand a small number of blobs that are\n  > different but have different hashes and, eventually, to drop said files\n  > into a blob-based infrastructure to wreak havoc.\n\n  cscott:\n  \n  This is just ridiculous.  The number of known collisions in SHA1 is \n  *exactly zero* at this point in time --- not guaranteed to stay that way, \n  of course, but generating collisions is likely to remain relatively \n  expensive for some time.\n\nBlob-dbs and the low-level object system (trees, file-contents, and\nchangesets) are pretty fundamental things.  It is likely (and\ndesirable) -- not guaranteed but likely (and desirable) -- that people\nwill invest heavily in building infrastructure that operates solely at\nthat level of abstraction.  Arguably, that is already happening.\n\nSimultaneously, it is very desirable that some mathemetican somewhere\nwill discover two bitstrings which are different but have SHA1\nchecksums, and then tell everyone in the world about their discovery.\n\nMy point is simply that blob-db implementations should assume that the\nmathemeticians will succeed and take the small steps necessary to make\nsure that those bitstrings can't be used to crash a distributed\nblob-db infrastructure.\n\n-t\n\n\n"},{"id":"2180","messageId":"Pine.LNX.4.61.0504291639590.32145@cag.csail.mit.edu","threadId":"390","inReplyTo":"200504292037.NAA28344@emf.net","subject":"Re: Val Henson's critique of hash-based content storage systems","fromName":"C. Scott Ananian","fromEmail":"cscott@cscott.net","sentAt":"2005-04-29T20:41:23Z","receivedAt":"2005-04-29T20:41:23Z","isPatch":false,"sender":{"key":"cscott@cscott.net","avatar":"https://gravatar.com/avatar/3551c2aefb299a0c45807f7677f5b26d8a5be4a4af359b4bf4fabbdd1f2b990e?d=mp&s=160"},"body":"On Fri, 29 Apr 2005, Tom Lord wrote:\n\n> My point is simply that blob-db implementations should assume that the\n> mathemeticians will succeed and take the small steps necessary to make\n> sure that those bitstrings can't be used to crash a distributed\n> blob-db infrastructure.\n\nAnd my point is that you haven't *begun* to describe how one might use an \narbitrary hash collision to \"crash a distributed blob-db infrastructure\".\n\nRemember, first you've got to get some reference to your collision into \nthe db...  (and if you can do that, why are you mucking around with hash \ncollisions?)\n   --scott\n\nPhiladelphia PBPRIME STANDEL for Dummies milita Richard Tomlinson \nESSENCE SUMAC Nader KUCLUB WSHOOFS QKENCHANT AK-47 AMQUACK supercomputer\n                          ( http://cscott.net/ )\n"},{"id":"2184","messageId":"118833cc0504291347ea1a3fa@mail.gmail.com","threadId":"390","inReplyTo":"loom.20050429T015434-928@post.gmane.org","subject":"Re: Val Henson's critique of hash-based content storage systems","fromName":"Morten Welinder","fromEmail":"mwelinder@gmail.com","sentAt":"2005-04-29T20:47:17Z","receivedAt":"2005-04-29T20:47:17Z","isPatch":false,"sender":{"key":"mwelinder@gmail.com","avatar":null},"body":"On 4/28/05, Rob Jellinghaus <robj@unrealities.com> wrote:\n> I assume most people here have read this, but just in case:\n> \n> http://www.usenix.org/events/hotos03/tech/full_papers/henson/henson.pdf\n\nThe math in section 3 is bogus.  1-(1-2^-b)^n  isn't hard to compute and\neven if it was, it is the wrong formula.  (Set n==2^b; you obviously should\nget probability 1 for collision.)\n\nThe right formula is 1-B!/B^n/(B-n)! where B=2^n.  For n=2^80 and b=160\nyou get about 39%.\n\nMorten\n"}]}