Re: [zooko@zooko.com: [Revctrl] colliding md5 hashes of human-meaningful

[linux@horizon.com]

Oh, for heaven's sake.  This is getting to be entirely too big
an issue.  For the record, I believe:

- There are far easier ways to back-door the public Linux kernel.
  (See the recent "subtly malicious code" contest.)
- There are far easier ways to back-door a particular target's
  kernel.
- There are easier ways than back-dooring their kernel to attack
  a particular target's computer.
- A 2^80 work factor is sufficient protection for quite a few
  years, especially as the processor speed growth curve finally
  seems to be flattening.

All I was trying to point out is that a sqrt(n) hash collision
attack *exists*.  Not that it's practical or anything.

For the quantity of computers required, it would be *cheaper* to start a
factory making my own line of PCI bus master network cards that included
remote memory sniffing features on-board!

> Yeah, yeah. You avoided a few laws of phsyics of your own.
>
> For example, when you say
>
>  "(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.)"
>
> you kind of ignore the fact that "n" here is 160, and so you're going to 
> be searching for quite a few versions of each. Also, you have to compare 
> the sha's of all of those 2**80 versions against each other which is a lot 
> of work in itself.

I am most definitely NOT ignoring it.  That's what makes the attack infeasible.
(But I insist that 2^80 is a hell of a long way from violating any laws
of physics.)

As for the comparison, if the two texts have the same form, there are
well-known ways to reduce the storage requirements by large factors
like 2^40.  For texts of different form, regular Pollard's rho doesn't
work, but maybe something ingenious is possible.

All I was trying to say is that a sqrt(2^160) attack exists.  Remember
the original statement?

>>> 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!
>>>
>>> Put another way: you could use this exact example for a version of git
>>> that uses md5-sums instead of sha1's, but it wouldn't show anything at all 
>>> about a git vulnerability even so.

*That's* what I was responding to.  It basically says "there is no
collision attack on the way git uses the hash", a statement I disagree
with.  I didn't say it was a realistic attack, because the whole reason
that SHA is 160 bits is so that it's resistant to a hash collision attack!


> Finally, you have to make sure that al the versions make sense, and that 
> people will take them 100% unmodified. 

Making them all make sense isn't hard; I can come up with 80 binary
variants on a piece of code by changing order of helper functions,
order of variable declarations, order of statements, comments,
spacing, and whatnot without even having to get into trailing
or redundant whitespace.

Making sure that nobody messes with it is trickier.  That would be
easier with a small patch, but that would in turn make the problem
of generating 2^80 plausible variants harder.

I'm reaching a bit, but hey, it was a quick description, not a
fully-fledged Cunning Plan.

> My plan was more interesting, I feel.

Oh for you, sure.  But as the one you had nominated to carry it
out, I'd like to object!

For plausibility, I prefer mine for manufacturing network cards with
built-in back doors.  There's a chance I could even get the Chinese
government to help fund it.