Subject: Re: Re: Merge with git-pasky II.

From: Ingo Molnar <[email-masked]>
Date: Sun, 17 Apr 2005 16:52:32 +0200

* Linus Torvalds <[email-masked]> wrote:

> Almost all attacks on sha1 will depend on _replacing_ a file with a 
> bogus new one. So guys, instead of using sha256 or going overboard, 
> just make sure that when you synchronize, you NEVER import a file you 
> already have.

here is a bit complex, but still practical attack that doesnt rely on 
replacement and which can only be detected if we check the sha1 
uniqueness assumptions.

If you can generate a duplicate sha1 key for an arbitrary 'target' file, 
and Malice sends you a GIT-generated patch that introduces a new file 
(which doesnt exist in the current tree) which you review (in the email) 
and which looks safe to apply & harmless. Maybe the patch has a bit 
weird formatting and some weird comments (which in reality Malice used 
to generate the proper sha1 key) but otherwise the patch is for some 
seldom used arcane driver that no-one used for quite some time and 
no-one really cares about, so you are happy to apply the patch.

The compromise occurs when you apply the patch: the seemingly harmless 
patch has an sha1 key that Malice manufacured to match that of an 
already existing, 'dangerous' object in your database.

With tens of thousands (or hundreds of thousands) of objects expected in 
the repository sooner or later, there's quite a selection to pick from.  
Once you apply the patch, instead of the expected new file that you 
reviewed and found safe, the attacker has the other object included in 
the official kernel.

A dangerous object can be anything: e.g. a debugging hack that allows 
arbitrary kernel-space writes. Or a known-insecure module (which since 
then got fixed, but the buggy code still exists in the DB). The module 
is in a single file and is self-installing (e.g. it has __init code to 
register itself as some driver.)

Malice might even previously plant a dangerous object as some 'firmware 
module' in another arcane driver, which doesnt get compiled by default, 
but still shows up in the DB. Or Malice might plant a dangerous object 
via an innocent-looking documentation file.  (which contains some sample 
code and is called sample.txt)

this type of 'false sharing attack' can only be prevented if an object 
is only 'shared' with another object if it has been memcmp-ed with the 
object in the repository. I.e. if we trust the sharing decision! Once 
the attack has occured it cannot be detected automatically: only people 
will notice it. (why did that weird unrelated module show up in that old 
driver?)

The compromise relies on you having reviewed something harmless, while 
in reality what happened within the DB was far less harmless. And the DB 
remains self-consistent: neither fsck, nor others importing your tree 
will be able to detect the compromise. This attack can only be detected 
when you apply the patch, after that point all the information (except 
Malice's message in your inbox) is gone.

so unless we actively check for collisions, once an sha1 key can be 
generated at will on near-arbitrary input, it's not a secure system 
anymore. We might be lucky and safe, but we wont be secure.

	Ingo