# Re: [zooko@zooko.com: [Revctrl] colliding md5 hashes of human-meaningful 6 messages from 2005-06-13 to 2005-06-13. Participants: linux@horizon.com, Linus Torvalds, Jason McMullan, Junio C Hamano, Radoslaw Szkodzinski. Thread: https://gitlist.dev/t/922 ## linux@horizon.com, 2005-06-13 17:58 Subject: Re: [zooko@zooko.com: [Revctrl] colliding md5 hashes of human-meaningful Message-ID: <20050613195038.9191.qmail@science.horizon.com> URL: https://gitlist.dev/e/20050613195038.9191.qmail%40science.horizon.com ``` > So the problem is totally different from the way git uses a hash. In the > git model, an attacker by definition cannot control both versions of a > file, since if he controls just _one_ version, he doesn't need to do the > attack in the first place! You are insufficiently paranoid, Grasshopper. The basic attack goes like this: - I construct two .c files with identical hashes. One is something useful; perhaps a device driver for some piece of hardware that my desired target has. The other is similar, but includes a remote root explot. (With an n-bit hash and an automated way to make harmless changes to source files, I can generate 2^(n/2) variants of each and expect to get a match, even in the absence of a better attack.) - I submit the first one to the Linux kernel. It's valid and gets merged. - A kernel release, including the "interesting" driver, gets made and sprinkled with holy penguin pee. Signatures, hashes, and all that. - Through various means (possibly just running a kernel download mirror, or possibly by splicing into my target's upstream Internet connection), I substitute the malware file for the real source code. - My target verifies all the hashes and signatures, decides that this "Linus" person signing it is trustworthy, and compiles and installs the kernel. - I walk in my back door and do suitable rude things. The point is, it *is* possible for an attacker to control both versions of a file. The reason he needs to do the attack is that one version looks legitimate and the other includes a Nasty Surprise. ``` ## Linus Torvalds, 2005-06-13 20:08 Subject: Re: [zooko@zooko.com: [Revctrl] colliding md5 hashes of human-meaningful Message-ID: URL: https://gitlist.dev/e/Pine.LNX.4.58.0506131305550.8487%40ppc970.osdl.org In-Reply-To: <20050613195038.9191.qmail@science.horizon.com> ``` On Mon, 13 Jun 2005 linux@horizon.com wrote: > > You are insufficiently paranoid, Grasshopper. No, I just am not lettign paranoia mean that I sit around shivering all day long. > The basic attack goes like this: > > - I construct two .c files with identical hashes. Ok, I have a better plan. - you learn to fly by flapping your arms fast enough - you then learn to pee burning gasoline - then, you fly around New York, setting everybody you see on fire, until people make you emperor. Sounds like a good plan, no? But perhaps slightly impractical. Now, let's go back to your plan. Why do you think your plan is any better than mine? Linus ``` ## Jason McMullan, 2005-06-13 20:17 Subject: Re: [zooko@zooko.com: [Revctrl] colliding md5 hashes of human-meaningful Message-ID: <1118693822.7564.59.camel@jmcmullan.timesys> URL: https://gitlist.dev/e/1118693822.7564.59.camel%40jmcmullan.timesys In-Reply-To: ``` On Mon, 2005-06-13 at 13:08 -0700, Linus Torvalds wrote: > Ok, I have a better plan. > > - you learn to fly by flapping your arms fast enough > - you then learn to pee burning gasoline > - then, you fly around New York, setting everybody you see on fire, > until > people make you emperor. Can't... stop... laughing.... "Cryptology - It's a comedy goldmine!" -- Jason McMullan TimeSys Corporation ``` ## Junio C Hamano, 2005-06-13 20:46 Subject: Re: [zooko@zooko.com: [Revctrl] colliding md5 hashes of human-meaningful Message-ID: <7vd5qqf0ii.fsf@assigned-by-dhcp.cox.net> URL: https://gitlist.dev/e/7vd5qqf0ii.fsf%40assigned-by-dhcp.cox.net In-Reply-To: <20050613195038.9191.qmail@science.horizon.com> ``` >> So the problem is totally different from the way git uses a hash. In the >> git model, an attacker by definition cannot control both versions of a >> file, since if he controls just _one_ version, he doesn't need to do the >> attack in the first place! > You are insufficiently paranoid, Grasshopper. > The basic attack goes like this: > - I construct two .c files with identical hashes. One is something > useful; perhaps a device driver for some piece of hardware that my > desired target has. The other is similar, but includes a remote > root explot. > (With an n-bit hash and an automated way to make harmless changes > to source files, I can generate 2^(n/2) variants of each and expect to > get a match, even in the absence of a better attack.) > - I submit the first one to the Linux kernel. It's valid and gets > merged. I doubt that this part would work in practice. Wouldn't you have to have some "garbage" in the early part of that driver source, probably in a C comment block or an otherwise unused string constant, that serves no apparent purpose, which is inserted by your "automated harmless changes" machinery? Wouldn't that catch people's attention and cause them to question and reject that patch in the first place? Wouldn't that mean you do not have control over even _one_ version, let alone _both_ versions? ``` ## Radoslaw Szkodzinski, 2005-06-13 20:52 Subject: Re: [Revctrl] colliding md5 hashes of human-meaningful Message-ID: <42ADF1F2.1070008@gorzow.mm.pl> URL: https://gitlist.dev/e/42ADF1F2.1070008%40gorzow.mm.pl In-Reply-To: <20050613195038.9191.qmail@science.horizon.com> ``` linux@horizon.com wrote: >>So the problem is totally different from the way git uses a hash. In the >>git model, an attacker by definition cannot control both versions of a >>file, since if he controls just _one_ version, he doesn't need to do the >>attack in the first place! >> >> > >You are insufficiently paranoid, Grasshopper. > >The basic attack goes like this: > >- I construct two .c files with identical hashes. One is something > useful; perhaps a device driver for some piece of hardware that my > desired target has. The other is similar, but includes a remote > root explot. > > (With an n-bit hash and an automated way to make harmless changes > to source files, I can generate 2^(n/2) variants of each and expect to > get a match, even in the absence of a better attack.) > > > And you get lots of nonsense in the new file. >- I submit the first one to the Linux kernel. It's valid and gets > merged. > > > And funny as it is, when the hole is found you're busted. Or at least the first person responsible. You probably couldn't shadow yourself enough not to get caught. >- A kernel release, including the "interesting" driver, gets made and > sprinkled with holy penguin pee. Signatures, hashes, and all that. > > > Which mean that you can't change your name on the project. See above. >- Through various means (possibly just running a kernel download mirror, > or possibly by splicing into my target's upstream Internet connection), > I substitute the malware file for the real source code. > > > If you can splice into the connection, you can put there anything you want, including another kernel and any amount of exploits. Even with SSH. Ever heard of man-in-the-middle attacks? With high-grade security you won't be able to splice into the connection, as it'll be fully encrypted (with HTH key exchange) and/or randomised using things like EFF's Tor. Then they can check with kernel.org or any other mirror. >- My target verifies all the hashes and signatures, decides that this "Linus" > person signing it is trustworthy, and compiles and installs the kernel. > > And they're so unforseeing that they don't check the sources of the drivers they use. Funny. And if they don't use it, you'll have a problem with enabling your exploit. Your best target would be a scheduler, but that's heavily scrutinised. >- I walk in my back door and do suitable rude things. > > > Like going to jail. >The point is, it *is* possible for an attacker to control both versions of >a file. The reason he needs to do the attack is that one version looks >legitimate and the other includes a Nasty Surprise. > > It is in theory. Tell someone when you mount such an attack on anybody. AstralStorm ``` ## linux@horizon.com, 2005-06-13 21:01 Subject: Re: [zooko@zooko.com: [Revctrl] colliding md5 hashes of human-meaningful Message-ID: <20050613210318.18965.qmail@science.horizon.com> URL: https://gitlist.dev/e/20050613210318.18965.qmail%40science.horizon.com In-Reply-To: ``` > No, I just am not letting paranoia mean that I sit around shivering all > day long. I'm sorry if I implied that. I meant "paranoid" in the sense of "imagining attack"; you were saying there is no way to attack git via a collision attack on the underlying hash, and I objected. I agree with you that: - The attack is still wildly impractical, and - Anything is better than the unauthenticated TCP we use these days! >> The basic attack goes like this: >> >> - I construct two .c files with identical hashes. > Ok, I have a better plan. > > - you learn to fly by flapping your arms fast enough > - you then learn to pee burning gasoline > - then, you fly around New York, setting everybody you see on fire, until > people make you emperor. > > Sounds like a good plan, no? ROFL! Oh my. That's worthy of reprinting. I was pleased with myself for making fun of the "what if there's an accidental hash collision" theory by assuming that kernel development would continue uninterrupted until the sun went nova, but this is truly masterful scorn. > But perhaps slightly impractical. There are just few laws of physics it violates. Not to mention that New York is still a trifle touchy about the combination of flying and burning fossil fuels, and this poses problems for step 3. > Now, let's go back to your plan. Why do you think your plan is any better > than mine? I was trying to point out that a collision attack is possible. That is, *if* we assume that someone can has the ability to find a hash collision, *then* they can use that to break git's authenticity guarantees. I wasn't addressing the plausibility of the "if" part. I agree that requiring the hashed text to be plausible C source makes all current attacks (including the MD5 ones) irrelevant, and reduces you to straight brute force, which is quite implausible. But it *is* a collsion attack, not a preimage attack, and it *is* at least consistent with all known laws of physics. I did *not* say, or mean to imply, that there was anything wrong with git's hashing. ```