Re: About git and the use of SHA-1

From: Andreas Ericsson <ae@op5.se>
Date: Apr 29, 2008, 12:27 UTC
Message-ID: <48171442.4050707@op5.se>
In-Reply-To: <bd6139dc0804290405w4a7a94a7s15a85285b2122f2f@mail.gmail.com>

Sverre Rabbelier wrote:

Show 15 quoted lines

> On Tue, Apr 29, 2008 at 9:21 AM, Andreas Ericsson <ae@op5.se> wrote:
>> Russ Dill wrote:
>>  If the server is hacked and objects are replaced, they will either
>>  no longer match their cryptographic signature, meaning they'll be
>>  new objects or git will determine that they are corrupt, or they
> 
> We were assuming here that once SHA-1 is broken really determined
> hackers will be able to come up with objects that -do- match the
> SHA-1, so the above is not relevant.
> 
>>  *will* match an existing object, but then that object won't be
>>  propagated to other repositories since git refuses to overwrite
>>  already existing objects. [...]
> 
> What about new users cloning the repo? They're just out of luck?

Only until someone who's already cloned the repository fetches from it, at which point the collision will be detected.

Show 7 quoted lines

> I
> don't think this argument holds, if we want to 'advertise' that git is
> cryptographically secure we can do so only as long as our hashing
> algorithm is. (As such, should SHA-1 ever be fully broken we'd need to
> either switch to another algorithm or stop advertising being
> cryptographically secure.)
>

True. So far though, the only attacks that have been successful requires that the attacker is allowed to create both the colliding data-sets, and so far none has been found that would allow the attacker to follow any kind of syntactical rules what so ever, so from a practical point of view, SHA1 is 100% secure *for sourcecode*.

>From a theoretical point of view, no hash is 100% secure, so changing

algorithm buys us nothing.

Besides, "cryprographically secure" is not the same as "will never ever be broken", because all hashes are obviously susceptible to brute-force attacks. "Cryptographically secure" means, insofar as I've understood it that given a source-file and a key, it would take such an extremely long time to find a different data-set that hashes to the same key that the result is unusable because the original source is obsolete.

That is why legal documents are always signed with the "most secure" (or rather, "least insecure") of all available hashes. For our purposes, SHA1 suffices until someone comes up with a relatively trivial way of creating a collision within the parameters above.

Show 11 quoted lines

>>  [...] Either way, gits refusal to overwrite
>>  objects it already has plays a part in making malicious actions
>>  futile, since malicious code is only worth something if it's
>>  propagated and actually used.
> 
> Of course this is true, it makes it a lot harder to do damage, but it
> doesn't eliminate the problem, it's just a free 'extra protection'.
> Yes, malicious code is only worth something if it's propagated and
> actually used, no, it is not impossible to do so in git if/when SHA-1
> turns out to have collisions every other file.
>

Points of fact so far:
* It possible to create objects with colliding names (SHA1 hash keys).
  This holds true whichever algorithm we use, although it will be more
  difficult with a stronger algorithm.
* It is impossible to distribute the colliding content to already cloned
  repositories. This also holds true for all hash algorithms.

I've been arguing that the value of the first point is so greatly diminished by the second, that even if SHA1 turns out to be horribly broken, projects using git will still have a decent protection against malicious code entering the repository without the knowledge of one of the authors.

You've been arguing that SHA1 is not theoretically secure, which is obviously true since no hash is theoretically secure.

I can think of one way to make git a lot more resilient to hash collisions, regardless of which hash is used, namely: Add the length of the hashed object to the hash.

In order for an evil-minded hacker to succeed in doing any real harm, he/she now has to create a conflicting file which is valid for its type (be it C, PHP, JPEG, AVI, PDF or whatever) and is also the same length as the original source, without being allowed to create the original object.

-- 
Andreas Ericsson                   andreas.ericsson@op5.se
OP5 AB                             www.op5.se
Tel: +46 8-230225                  Fax: +46 8-230231