From: linux@horizon.com
Date: Mon, 13 Jun 2005 17:58:12 GMT
Subject: Re: [zooko@zooko.com: [Revctrl] colliding md5 hashes of human-meaningful
Message-ID: <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.

- 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.