Re: When Will We See Collisions for SHA-1? (An interesting analysis by Bruce Schneier)

["René Scharfe" <rene.scharfe@lsrfire.ath.cx>]

Am 15.10.2012 20:34, schrieb Jeff King:
> On Mon, Oct 15, 2012 at 07:47:09PM +0200, Ævar Arnfjörð Bjarmason wrote:
> 
>> On Mon, Oct 15, 2012 at 6:42 PM, Elia Pinto <gitter.spiros@gmail.com> wrote:
>>> Very clear analysis. Well written. Perhaps is it the time to update
>>> http://git-scm.com/book/ch6-1.html (A SHORT NOTE ABOUT SHA-1) ?
>>>
>>> Hope useful
>>>
>>> http://www.schneier.com/crypto-gram-1210.html
>>
>> This would be concerning if the Git security model would break down if
>> someone found a SHA1 collision, but it really wouldn't.
>>
>> It's one thing to find *a* collision, it's quite another to:
>>
>>   1. Find a collision for the sha1 of harmless.c which I know you use,
>>      and replace it with evil.c.
>>
>>   2. Somehow make evil.c compile so that it actually does something
>>      useful and nefarious, and doesn't just make the C compiler puke.
>>
>>      If finding one arbitrary collision costs $43K in 2021 dollars
>>      getting past this point is going to take quite a large multiple of
>>      $43K.
> 
> There are easier attacks than that if you can hide arbitrary bytes
> inside a file. It's hard with C source code. The common one in hash
> collision detection circles is to put invisible cruft into binary
> document formats like PDF or Postscript. Git blobs themselves do not
> have such an invisible place to put it, but you might be storing a
> format that does.
> 
> But worse, git _commits_ have such an invisible portion. We calculate
> the sha1 over the full commit, but we tend to show only the portion up
> to the first NUL byte. I used that horrible trick in my "choose your own
> sha1 prefix" patch. However, we could mitigate that by checking for
> embedded NULs in git-fsck.

FWIW, I couldn't measure a performance difference for git log with and
without the following patch, which catches commits created with your
hash collision trick, but might be too strict:

diff --git a/commit.c b/commit.c
index 213bc98..4cd1e83 100644
--- a/commit.c
+++ b/commit.c
@@ -262,6 +262,12 @@ int parse_commit_buffer(struct commit *item, const void *buffer, unsigned long s
 	if (item->object.parsed)
 		return 0;
 	item->object.parsed = 1;
+
+	if (memchr(buffer, '\0', size)) {
+		return error("bogus commit contains a NUL character: %s",
+			     sha1_to_hex(item->object.sha1));
+	}
+
 	tail += size;
 	if (tail <= bufptr + 46 || memcmp(bufptr, "tree ", 5) || bufptr[45] != '\n')
 		return error("bogus commit object %s", sha1_to_hex(item->object.sha1));