{"thread":{"id":"922","subject":"Re: [zooko@zooko.com: [Revctrl] colliding md5 hashes of human-meaningful","startedAt":"2005-06-13T17:58:12Z","lastAt":"2005-06-13T21:01:22Z","messageCount":6,"participants":["linux@horizon.com","Linus Torvalds","Jason McMullan","Junio C Hamano","Radoslaw Szkodzinski"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"4915","messageId":"20050613195038.9191.qmail@science.horizon.com","threadId":"922","inReplyTo":null,"subject":"Re: [zooko@zooko.com: [Revctrl] colliding md5 hashes of human-meaningful","fromName":"","fromEmail":"linux@horizon.com","sentAt":null,"receivedAt":"2005-06-13T17:58:12Z","isPatch":false,"sender":{"key":"linux@horizon.com","avatar":null},"body":"> So the problem is totally different from the way git uses a hash. In the \n> git model, an attacker by definition cannot control both versions of a \n> file, since if he controls just _one_ version, he doesn't need to do the \n> attack in the first place!\n\nYou are insufficiently paranoid, Grasshopper.\n\nThe basic attack goes like this:\n\n- I construct two .c files with identical hashes.  One is something\n  useful; perhaps a device driver for some piece of hardware that my\n  desired target has.  The other is similar, but includes a remote\n  root explot.\n\n  (With an n-bit hash and an automated way to make harmless changes\n  to source files, I can generate 2^(n/2) variants of each and expect to\n  get a match, even in the absence of a better attack.)\n\n- I submit the first one to the Linux kernel.  It's valid and gets\n  merged.\n\n- A kernel release, including the \"interesting\" driver, gets made and\n  sprinkled with holy penguin pee.  Signatures, hashes, and all that.\n\n- Through various means (possibly just running a kernel download mirror,\n  or possibly by splicing into my target's upstream Internet connection),\n  I substitute the malware file for the real source code.\n\n- My target verifies all the hashes and signatures, decides that this \"Linus\"\n  person signing it is trustworthy, and compiles and installs the kernel.\n\n- I walk in my back door and do suitable rude things.\n\n\nThe point is, it *is* possible for an attacker to control both versions of\na file.  The reason he needs to do the attack is that one version looks\nlegitimate and the other includes a Nasty Surprise.\n"},{"id":"4916","messageId":"Pine.LNX.4.58.0506131305550.8487@ppc970.osdl.org","threadId":"922","inReplyTo":"20050613195038.9191.qmail@science.horizon.com","subject":"Re: [zooko@zooko.com: [Revctrl] colliding md5 hashes of human-meaningful","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-06-13T20:08:21Z","receivedAt":"2005-06-13T20:08:21Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 13 Jun 2005 linux@horizon.com wrote:\n> \n> You are insufficiently paranoid, Grasshopper.\n\nNo, I just am not lettign paranoia mean that I sit around shivering all \nday long.\n\n> The basic attack goes like this:\n> \n> - I construct two .c files with identical hashes.\n\nOk, I have a better plan.\n\n - you learn to fly by flapping your arms fast enough\n - you then learn to pee burning gasoline\n - then, you fly around New York, setting everybody you see on fire, until \n   people make you emperor.\n\nSounds like a good plan, no?\n\nBut perhaps slightly impractical. \n\nNow, let's go back to your plan. Why do you think your plan is any better \nthan mine?\n\n\t\tLinus\n"},{"id":"4917","messageId":"1118693822.7564.59.camel@jmcmullan.timesys","threadId":"922","inReplyTo":"Pine.LNX.4.58.0506131305550.8487@ppc970.osdl.org","subject":"Re: [zooko@zooko.com: [Revctrl] colliding md5 hashes of human-meaningful","fromName":"Jason McMullan","fromEmail":"jason.mcmullan@timesys.com","sentAt":"2005-06-13T20:17:01Z","receivedAt":"2005-06-13T20:17:01Z","isPatch":false,"sender":{"key":"jason.mcmullan@timesys.com","avatar":null},"body":"On Mon, 2005-06-13 at 13:08 -0700, Linus Torvalds wrote:\n> Ok, I have a better plan.\n> \n>  - you learn to fly by flapping your arms fast enough\n>  - you then learn to pee burning gasoline\n>  - then, you fly around New York, setting everybody you see on fire,\n> until \n>    people make you emperor.\n\nCan't... stop... laughing....\n\n\n\"Cryptology - It's a comedy goldmine!\"\n\n-- \nJason McMullan <jason.mcmullan@timesys.com>\nTimeSys Corporation\n\n"},{"id":"4918","messageId":"7vd5qqf0ii.fsf@assigned-by-dhcp.cox.net","threadId":"922","inReplyTo":"20050613195038.9191.qmail@science.horizon.com","subject":"Re: [zooko@zooko.com: [Revctrl] colliding md5 hashes of human-meaningful","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-06-13T20:46:29Z","receivedAt":"2005-06-13T20:46:29Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":">> So the problem is totally different from the way git uses a hash. In the \n>> git model, an attacker by definition cannot control both versions of a \n>> file, since if he controls just _one_ version, he doesn't need to do the \n>> attack in the first place!\n\n> You are insufficiently paranoid, Grasshopper.\n\n> The basic attack goes like this:\n\n> - I construct two .c files with identical hashes.  One is something\n>   useful; perhaps a device driver for some piece of hardware that my\n>   desired target has.  The other is similar, but includes a remote\n>   root explot.\n\n>   (With an n-bit hash and an automated way to make harmless changes\n>   to source files, I can generate 2^(n/2) variants of each and expect to\n>   get a match, even in the absence of a better attack.)\n\n> - I submit the first one to the Linux kernel.  It's valid and gets\n>   merged.\n\nI doubt that this part would work in practice.\n\nWouldn't you have to have some \"garbage\" in the early part of\nthat driver source, probably in a C comment block or an\notherwise unused string constant, that serves no apparent\npurpose, which is inserted by your \"automated harmless changes\"\nmachinery?\n\nWouldn't that catch people's attention and cause them to\nquestion and reject that patch in the first place?\n\nWouldn't that mean you do not have control over even _one_\nversion, let alone _both_ versions?\n\n"},{"id":"4919","messageId":"42ADF1F2.1070008@gorzow.mm.pl","threadId":"922","inReplyTo":"20050613195038.9191.qmail@science.horizon.com","subject":"Re: [Revctrl] colliding md5 hashes of human-meaningful","fromName":"Radoslaw Szkodzinski","fromEmail":"astralstorm@gorzow.mm.pl","sentAt":"2005-06-13T20:52:02Z","receivedAt":"2005-06-13T20:52:02Z","isPatch":false,"sender":{"key":"astralstorm@gorzow.mm.pl","avatar":null},"body":"linux@horizon.com wrote:\n\n>>So the problem is totally different from the way git uses a hash. In the \n>>git model, an attacker by definition cannot control both versions of a \n>>file, since if he controls just _one_ version, he doesn't need to do the \n>>attack in the first place!\n>>    \n>>\n>\n>You are insufficiently paranoid, Grasshopper.\n>\n>The basic attack goes like this:\n>\n>- I construct two .c files with identical hashes.  One is something\n>  useful; perhaps a device driver for some piece of hardware that my\n>  desired target has.  The other is similar, but includes a remote\n>  root explot.\n>\n>  (With an n-bit hash and an automated way to make harmless changes\n>  to source files, I can generate 2^(n/2) variants of each and expect to\n>  get a match, even in the absence of a better attack.)\n>\n>  \n>\nAnd you get lots of nonsense in the new file.\n\n>- I submit the first one to the Linux kernel.  It's valid and gets\n>  merged.\n>\n>  \n>\nAnd funny as it is, when the hole is found you're busted. Or at least\nthe first person responsible.\nYou probably couldn't shadow yourself enough not to get caught.\n\n>- A kernel release, including the \"interesting\" driver, gets made and\n>  sprinkled with holy penguin pee.  Signatures, hashes, and all that.\n>\n>  \n>\nWhich mean that you can't change your name on the project. See above.\n\n>- Through various means (possibly just running a kernel download mirror,\n>  or possibly by splicing into my target's upstream Internet connection),\n>  I substitute the malware file for the real source code.\n>\n>  \n>\nIf you can splice into the connection, you can put there anything you want,\nincluding another kernel and any amount of exploits. Even with SSH.\nEver heard of man-in-the-middle attacks?\n\nWith high-grade security you won't be able to splice into the connection,\nas it'll be fully encrypted (with HTH key exchange) and/or randomised using things like EFF's Tor.\nThen they can check with kernel.org or any other mirror.\n\n>- My target verifies all the hashes and signatures, decides that this \"Linus\"\n>  person signing it is trustworthy, and compiles and installs the kernel.\n>  \n>\nAnd they're so unforseeing that they don't check the sources of the\ndrivers they use.\nFunny. And if they don't use it, you'll have a problem with enabling\nyour exploit.\nYour best target would be a scheduler, but that's heavily scrutinised.\n\n>- I walk in my back door and do suitable rude things.\n>\n>  \n>\nLike going to jail.\n\n>The point is, it *is* possible for an attacker to control both versions of\n>a file.  The reason he needs to do the attack is that one version looks\n>legitimate and the other includes a Nasty Surprise.\n>  \n>\nIt is in theory. Tell someone when you mount such an attack on anybody.\n\nAstralStorm\n"},{"id":"4921","messageId":"20050613210318.18965.qmail@science.horizon.com","threadId":"922","inReplyTo":"Pine.LNX.4.58.0506131305550.8487@ppc970.osdl.org","subject":"Re: [zooko@zooko.com: [Revctrl] colliding md5 hashes of human-meaningful","fromName":"","fromEmail":"linux@horizon.com","sentAt":null,"receivedAt":"2005-06-13T21:01:22Z","isPatch":false,"sender":{"key":"linux@horizon.com","avatar":null},"body":"> No, I just am not letting paranoia mean that I sit around shivering all \n> day long.\n\nI'm sorry if I implied that.  I meant \"paranoid\" in the sense of\n\"imagining attack\"; you were saying there is no way to attack git via\na collision attack on the underlying hash, and I objected.\n\nI agree with you that:\n- The attack is still wildly impractical, and\n- Anything is better than the unauthenticated TCP we use these days!\n\n>> The basic attack goes like this:\n>> \n>> - I construct two .c files with identical hashes.\n\n> Ok, I have a better plan.\n>\n> - you learn to fly by flapping your arms fast enough\n> - you then learn to pee burning gasoline\n> - then, you fly around New York, setting everybody you see on fire, until \n>   people make you emperor.\n>\n> Sounds like a good plan, no?\n\nROFL!  Oh my.  That's worthy of reprinting.  I was pleased with myself\nfor making fun of the \"what if there's an accidental hash collision\"\ntheory by assuming that kernel development would continue uninterrupted\nuntil the sun went nova, but this is truly masterful scorn.\n\n> But perhaps slightly impractical.\n\nThere are just few laws of physics it violates.\n\nNot to mention that New York is still a trifle touchy about the combination\nof flying and burning fossil fuels, and this poses problems for step 3.\n\n> Now, let's go back to your plan. Why do you think your plan is any better \n> than mine?\n\nI was trying to point out that a collision attack is possible.  That is,\n*if* we assume that someone can has the ability to find a hash collision,\n*then* they can use that to break git's authenticity guarantees.\n\nI wasn't addressing the plausibility of the \"if\" part.  I agree that\nrequiring the hashed text to be plausible C source makes all current\nattacks (including the MD5 ones) irrelevant, and reduces you to straight\nbrute force, which is quite implausible.\n\nBut it *is* a collsion attack, not a preimage attack, and it *is* at\nleast consistent with all known laws of physics.\n\nI did *not* say, or mean to imply, that there was anything wrong with\ngit's hashing.\n"}]}