{"thread":{"id":"7326","subject":"New index-pack \"keep\" violates \"never overwrite\"","startedAt":"2007-03-20T05:38:13Z","lastAt":"2007-03-20T19:32:35Z","messageCount":3,"participants":["Shawn O. Pearce","Nicolas Pitre"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"37591","messageId":"20070320053813.GC29288@spearce.org","threadId":"7326","inReplyTo":null,"subject":"New index-pack \"keep\" violates \"never overwrite\"","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-03-20T05:38:13Z","receivedAt":"2007-03-20T05:38:13Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"This is something that has been bothering me for several weeks now.\n\nWaaaaaaay back Git was considered to be secure as it never overwrote\nan object it already had.  This was ensured by always unpacking the\npackfile received over the network (both in fetch and receive-pack)\nand our already existing logic to not create a loose object for an\nobject we already have.\n\nLately however we keep \"large-ish\" packfiles on both fetch and push\nby running them through index-pack instead of unpack-objects.  This\nwould let an attacker perform a birthday attack. \n\nHow?  Assume the attacker knows a SHA-1 that has two different\ndata streams.  He knows the client is likely to have the \"good\"\none.  So he sends the \"evil\" variant to the other end as part of\na \"large-ish\" packfile.  The recipient keeps that packfile, and\nindexes it.  Now since this is a birthday attack there is a SHA-1\ncollision; two objects exist in the repository with the same SHA-1.\nThey have *very* different data streams.  One of them is \"evil\".\n\nCurrently the poor recipient cannot tell the two objects apart,\nshort of by examining the timestamp of the packfiles.  But lets\nsay the recipient repacks before he realizes he's been attacked.\nWe may wind up packing the \"evil\" version of the object, and deleting\nthe \"good\" one.  This is made *even more likely* by Junio's recent\nrearrange_packed_git patch (b867092f).\n\nSHA-1 is generally considered to be broken, as there have been some\nattacks implemented where a massive amount of garbage is injected\ninto a comment, producing a source file that a compiler/interpreter\ncan still process just fine, but that contains \"evil bits of code\"\nand has the same hash as a \"non-evil\" version of that same file.\nYes, of course, if you look at the comment you would immediately\nrealize its crap.  You probably would even realize the file is crap\njust by looking at the file size, as typically several megabytes\nof garbage is required.\n\nBut how likely are you to look at a file content, or even size,\nduring say git-bisect?  Especially on a large project?  Would you\nreally notice that \"usb.c\" took 3 seconds longer than normal to\ncompile because the preprecessor had to wade through a gigantic\ngarbage comment?\n\n\nWe broke a fundemental assumption in the Git security model, and I\ndon't think anyone blinked.  Oops.  Either the SHA-1 birthday attack\nI just described is still thought to be a non-issue for at least\nthe next few years (due to current computing power limitations),\nor we all missed that one, big time.\n\nThe fix does appear to be simple.  Just don't write the existing\nobject to the output packfile.  But really that is a lot more like\nwhat unpack-objects does: buffer deltas we cannot resolve yet, and\nonly write out what we cannot find through our ODB.  The logic in\nindex-pack ain't built for that...\n\n\nFor those that are really paranoid about this, you can disable the\npack keeping by setting transfer.unpackLimit to a *huge* value,\none that is far larger than any packfile you might receive.\n\n-- \nShawn.\n"},{"id":"37636","messageId":"alpine.LFD.0.83.0703201454280.18328@xanadu.home","threadId":"7326","inReplyTo":"20070320053813.GC29288@spearce.org","subject":"Re: New index-pack \"keep\" violates \"never overwrite\"","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-03-20T19:07:22Z","receivedAt":"2007-03-20T19:07:22Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 20 Mar 2007, Shawn O. Pearce wrote:\n\n> This is something that has been bothering me for several weeks now.\n> \n> Waaaaaaay back Git was considered to be secure as it never overwrote\n> an object it already had.  This was ensured by always unpacking the\n> packfile received over the network (both in fetch and receive-pack)\n> and our already existing logic to not create a loose object for an\n> object we already have.\n> \n> Lately however we keep \"large-ish\" packfiles on both fetch and push\n> by running them through index-pack instead of unpack-objects.  This\n> would let an attacker perform a birthday attack. \n\nThis has been nagging me as well since I made the index-pack changes.  \nBut I dismissed that possibility as pure paranoia.\n\n[...]\n> The fix does appear to be simple.  Just don't write the existing\n> object to the output packfile.  But really that is a lot more like\n> what unpack-objects does: buffer deltas we cannot resolve yet, and\n> only write out what we cannot find through our ODB.  The logic in\n> index-pack ain't built for that...\n\nNah.  You would have to fix every delta base offsets up etc. and make \nthe whole thing into a complex mess.\n\nInstead, we only have to check for the local presence of every objects \nin the pack, and when one packed object does exist locally and \ndoesn't match the pack content we simply need to bail out with great \ndistress.  If we really get a SHA1 collision, evil or not, we simply \njust cannot continue as if nothing happened.\n\nPatch to follow...\n\n\nNicolas\n"},{"id":"37637","messageId":"alpine.LFD.0.83.0703201508190.18328@xanadu.home","threadId":"7326","inReplyTo":"20070320053813.GC29288@spearce.org","subject":"[PATCH] don't ever allow SHA1 collisions to exist by fetching a pack","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-03-20T19:32:35Z","receivedAt":"2007-03-20T19:32:35Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"Waaaaaaay back Git was considered to be secure as it never overwrote\nan object it already had.  This was ensured by always unpacking the\npackfile received over the network (both in fetch and receive-pack)\nand our already existing logic to not create a loose object for an\nobject we already have.\n\nLately however we keep \"large-ish\" packfiles on both fetch and push\nby running them through index-pack instead of unpack-objects.  This\nwould let an attacker perform a birthday attack. \n\nHow?  Assume the attacker knows a SHA-1 that has two different\ndata streams.  He knows the client is likely to have the \"good\"\none.  So he sends the \"evil\" variant to the other end as part of\na \"large-ish\" packfile.  The recipient keeps that packfile, and\nindexes it.  Now since this is a birthday attack there is a SHA-1\ncollision; two objects exist in the repository with the same SHA-1.\nThey have *very* different data streams.  One of them is \"evil\".\n\nCurrently the poor recipient cannot tell the two objects apart,\nshort of by examining the timestamp of the packfiles.  But lets\nsay the recipient repacks before he realizes he's been attacked.\nWe may wind up packing the \"evil\" version of the object, and deleting\nthe \"good\" one.  This is made *even more likely* by Junio's recent\nrearrange_packed_git patch (b867092f).\n\nIt is extremely unlikely for a SHA1 collisions to occur, but if it\never happens with a remote (hence untrusted) object we simply must\nnot let the fetch succeed.\n\nNormally received packs should not contain objects we already have.\nBut when they do we must ensure duplicated objects with the same SHA1\nactually contain the same data.\n\nSigned-off-by: Nicolas Pitre <nico@cam.org>\n---\n\nExplanation text for the log message shamelessly stolen from Shawn's \nemail on this issue.\n\nI also provided a test for this otherwise it might never get exercised.\n\ndiff --git a/index-pack.c b/index-pack.c\nindex b405864..4effb2d 100644\n--- a/index-pack.c\n+++ b/index-pack.c\n@@ -345,7 +345,8 @@ static int find_delta_children(const union delta_base *base,\n }\n \n static void sha1_object(const void *data, unsigned long size,\n-\t\t\tenum object_type type, unsigned char *sha1)\n+\t\t\tenum object_type type, unsigned char *sha1,\n+\t\t\tint test_for_collision)\n {\n \tSHA_CTX ctx;\n \tchar header[50];\n@@ -367,6 +368,18 @@ static void sha1_object(const void *data, unsigned long size,\n \tSHA1_Update(&ctx, header, header_size);\n \tSHA1_Update(&ctx, data, size);\n \tSHA1_Final(sha1, &ctx);\n+\n+\tif (test_for_collision && has_sha1_file(sha1)) {\n+\t\tvoid *has_data;\n+\t\tenum object_type has_type;\n+\t\tunsigned long has_size;\n+\t\thas_data = read_sha1_file(sha1, &has_type, &has_size);\n+\t\tif (!has_data)\n+\t\t\tdie(\"cannot read existing object %s\", sha1_to_hex(sha1));\n+\t\tif (size != has_size || type != has_type ||\n+\t\t    memcmp(data, has_data, size) != 0)\n+\t\t\tdie(\"SHA1 COLLISION FOUND WITH %s !\", sha1_to_hex(sha1));\n+\t}\n }\n \n static void resolve_delta(struct object_entry *delta_obj, void *base_data,\n@@ -387,7 +400,7 @@ static void resolve_delta(struct object_entry *delta_obj, void *base_data,\n \tfree(delta_data);\n \tif (!result)\n \t\tbad_object(delta_obj->offset, \"failed to apply delta\");\n-\tsha1_object(result, result_size, type, delta_obj->sha1);\n+\tsha1_object(result, result_size, type, delta_obj->sha1, 1);\n \tnr_resolved_deltas++;\n \n \thashcpy(delta_base.sha1, delta_obj->sha1);\n@@ -444,7 +457,7 @@ static void parse_pack_objects(unsigned char *sha1)\n \t\t\tdelta->obj_no = i;\n \t\t\tdelta++;\n \t\t} else\n-\t\t\tsha1_object(data, obj->size, obj->type, obj->sha1);\n+\t\t\tsha1_object(data, obj->size, obj->type, obj->sha1, 1);\n \t\tfree(data);\n \t\tif (verbose)\n \t\t\tpercent = display_progress(i+1, nr_objects, percent);\n@@ -565,7 +578,7 @@ static void append_obj_to_pack(void *buf,\n \twrite_or_die(output_fd, header, n);\n \tobj[1].offset = obj[0].offset + n;\n \tobj[1].offset += write_compressed(output_fd, buf, size);\n-\tsha1_object(buf, size, type, obj->sha1);\n+\tsha1_object(buf, size, type, obj->sha1, 0);\n }\n \n static int delta_pos_compare(const void *_a, const void *_b)\ndiff --git a/t/t5300-pack-object.sh b/t/t5300-pack-object.sh\nindex eacb1e9..75e7276 100755\n--- a/t/t5300-pack-object.sh\n+++ b/t/t5300-pack-object.sh\n@@ -255,4 +255,14 @@ test_expect_success \\\n \n      :'\n \n+test_expect_success \\\n+    'fake a SHA1 hash collision' \\\n+    'test -f\t.git/objects/c8/2de19312b6c3695c0c18f70709a6c535682a67 &&\n+     cp -f\t.git/objects/9d/235ed07cd19811a6ceb342de82f190e49c9f68 \\\n+\t\t.git/objects/c8/2de19312b6c3695c0c18f70709a6c535682a67'\n+\n+test_expect_failure \\\n+    'make sure index-pack detects the SHA1 collision' \\\n+    'git-index-pack -o bad.idx test-3.pack'\n+\n test_done\n"}]}