{"thread":{"id":"56873","subject":"[PATCH] packfile: avoid overflowing shift during decode","startedAt":"2021-11-10T23:41:44Z","lastAt":"2022-01-12T20:27:24Z","messageCount":6,"participants":["Jonathan Tan","Junio C Hamano","Marc Strapetz"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"440883","messageId":"20211110234033.3144165-1-jonathantanmy@google.com","threadId":"56873","inReplyTo":null,"subject":"[PATCH] packfile: avoid overflowing shift during decode","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2021-11-10T23:40:33Z","receivedAt":"2021-11-10T23:41:44Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"unpack_object_header_buffer() attempts to protect against overflowing\nleft shifts, but the limit of the shift amount should not be the size of\nthe variable being shifted. It should be the size minus the size of its\ncontents. Fix that accordingly.\n\nThis was noticed at $DAYJOB by a fuzzer running internally.\n\nSigned-off-by: Jonathan Tan \n---\nIn next, d6a09e795d (\"odb: guard against data loss checking out a huge\nfile\", 2021-11-03) (merged as fe5160a170 (\"Merge branch\n'mc/clean-smudge-with-llp64' into next\", 2021-11-03)) ameliorates this\nsituation by dying if the left shift overflows, but this patch is still\nworthwhile as it makes a bad header be reported as a bad header, not a\nfatal left shift overflow.\n---\n packfile.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/packfile.c b/packfile.c\nindex 89402cfc69..972c327e29 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -1068,7 +1068,7 @@ unsigned long unpack_object_header_buffer(const unsigned char *buf,\n \tsize = c & 15;\n \tshift = 4;\n \twhile (c & 0x80) {\n-\t\tif (len <= used || bitsizeof(long) <= shift) {\n+\t\tif (len <= used || (bitsizeof(long) - 7) <= shift) {\n \t\t\terror(\"bad object header\");\n \t\t\tsize = used = 0;\n \t\t\tbreak;\n-- \n2.34.0.rc0.344.g81b53c2807-goog\n\n"},{"id":"440895","messageId":"xmqqpmr7v4gf.fsf@gitster.g","threadId":"56873","inReplyTo":"20211110234033.3144165-1-jonathantanmy@google.com","subject":"Re: [PATCH] packfile: avoid overflowing shift during decode","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-11-11T01:58:08Z","receivedAt":"2021-11-11T01:58:13Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jonathan Tan writes:\n\n> situation by dying if the left shift overflows, but this patch is still\n> worthwhile as it makes a bad header be reported as a bad header, not a\n> fatal left shift overflow.\n\nHmph, I am not sure if I like to see it put that way, but I think\nthe problem is not anything new.\n\nEven when we have a packfile that is in a good shape, the current\nmachine (especially its wordsize) may not be capable of extracting\nthe object we are looking at from the packstream, when the object is\nlarger than the current machine's ulong can express. So it may be\nan indication that your machine cannot use the packed object, but\nmay not be an indication that there is anything _wrong_ in the\nobject header.\n\n Side note. I suspect that this should already be the case; you\n can pack a large object whose size do not fit in u32 on a box\n whose ulong is u64, and you wouldn't be able to use such a\n packfile on a box where ulong is u32. There is no \"bad object\n header\" in the pack stream per-se, but we cannot use it there.\n\nAfter all, the reason why we chose to use the varint encoding is\nbecause we do not have to change the file format when we extend\nbeyond the architectures of prevailing word size of the day.\n\nHaving said all that, I think the patch is correct. We later use\nthe number \"shift\" as the shift count like so\n\n\tsize += (c & 0x7f) << shift;\n\nIn order for the uppermost bit from (c & 0x7f) to be still inside\n\"size\", it is not sufficient that \"shift\" does not exceed the\nbit-size of \"size\". We need to subtract the bitscanreverse of\n(0x7f), which is 7, which is exactly what your patch does.\n\nLooking good. Thanks.\n\n\n> packfile.c | 2 +-\n> 1 file changed, 1 insertion(+), 1 deletion(-)\n>\n> diff --git a/packfile.c b/packfile.c\n> index 89402cfc69..972c327e29 100644\n> --- a/packfile.c\n> +++ b/packfile.c\n> @@ -1068,7 +1068,7 @@ unsigned long unpack_object_header_buffer(const unsigned char *buf,\n> \tsize = c & 15;\n> \tshift = 4;\n> \twhile (c & 0x80) {\n> -\t\tif (len <= used || bitsizeof(long) <= shift) {\n> +\t\tif (len <= used || (bitsizeof(long) - 7) <= shift) {\n> \t\t\terror(\"bad object header\");\n> \t\t\tsize = used = 0;\n> \t\t\tbreak;\n"},{"id":"445885","messageId":"5ab9257c-9eba-a171-86d6-3fe7d3a4faec@syntevo.com","threadId":"56873","inReplyTo":"xmqqpmr7v4gf.fsf@gitster.g","subject":"Re: [PATCH] packfile: avoid overflowing shift during decode","fromName":"Marc Strapetz","fromEmail":"marc.strapetz@syntevo.com","sentAt":"2022-01-10T23:22:04Z","receivedAt":"2022-01-10T23:22:10Z","isPatch":true,"sender":{"key":"marc.strapetz@syntevo.com","avatar":"https://avatars.githubusercontent.com/u/3380730?v=4"},"body":"On 11/11/2021 02:58, Junio C Hamano wrote:\n> Jonathan Tan writes:\n> \n>> diff --git a/packfile.c b/packfile.c\n>> index 89402cfc69..972c327e29 100644\n>> --- a/packfile.c\n>> +++ b/packfile.c\n>> @@ -1068,7 +1068,7 @@ unsigned long unpack_object_header_buffer(const unsigned char *buf,\n>> \tsize = c & 15;\n>> \tshift = 4;\n>> \twhile (c & 0x80) {\n>> -\t\tif (len <= used || bitsizeof(long) <= shift) {\n>> +\t\tif (len <= used || (bitsizeof(long) - 7) <= shift) {\n\nThis seems to cause troubles now for 32-bit systems (in my case Git for \nWindows 32-Bit): `shift` will go through 4, 11, 18 and for 25 it finally \nerrors out. This means that objects >= 32MB can't be processed anymore. \nThe condition should probably be changed to:\n\n+\t\tif (len <= used || (bitsizeof(long) - 7) < shift) {\n\nThis still ensures that the shift can never overflow and on 32-bit \nsystems restores the maximum size of 4G with a final shift of 127<<25 \n(the old condition `bitsizeof(long) <= shift` was perfectly valid for \n32-bit systems).\n\n> Even when we have a packfile that is in a good shape, the current\n> machine (especially its wordsize) may not be capable of extracting\n> the object we are looking at from the packstream, when the object is\n> larger than the current machine's ulong can express. So it may be\n> an indication that your machine cannot use the packed object, but\n> may not be an indication that there is anything _wrong_ in the\n> object header.\n\nI was actually quite confused by the error message \"bad object header\". \nIt made me investigate all sorts of other things before thoroughly \nstepping through this loop.\n\n-Marc\n"},{"id":"446067","messageId":"xmqq8rvku3bq.fsf@gitster.g","threadId":"56873","inReplyTo":"5ab9257c-9eba-a171-86d6-3fe7d3a4faec@syntevo.com","subject":"Re: [PATCH] packfile: avoid overflowing shift during decode","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-01-12T20:06:01Z","receivedAt":"2022-01-12T20:06:38Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Marc Strapetz writes:\n\n> On 11/11/2021 02:58, Junio C Hamano wrote:\n>> Jonathan Tan writes:\n>> \n>>> diff --git a/packfile.c b/packfile.c\n>>> index 89402cfc69..972c327e29 100644\n>>> --- a/packfile.c\n>>> +++ b/packfile.c\n>>> @@ -1068,7 +1068,7 @@ unsigned long unpack_object_header_buffer(const unsigned char *buf,\n>>> \tsize = c & 15;\n>>> \tshift = 4;\n>>> \twhile (c & 0x80) {\n>>> -\t\tif (len <= used || bitsizeof(long) <= shift) {\n>>> +\t\tif (len <= used || (bitsizeof(long) - 7) <= shift) {\n>\n> This seems to cause troubles now for 32-bit systems (in my case Git\n> for Windows 32-Bit): `shift` will go through 4, 11, 18 and for 25 it\n> finally errors out. This means that objects >= 32MB can't be processed\n> anymore. The condition should probably be changed to:\n>\n> +\t\tif (len <= used || (bitsizeof(long) - 7) < shift) {\n>\n> This still ensures that the shift can never overflow and on 32-bit\n> systems restores the maximum size of 4G with a final shift of 127<<25 \n> (the old condition `bitsizeof(long) <= shift` was perfectly valid for\n> 32-bit systems).\n\nJonathan?\n"},{"id":"446069","messageId":"xmqq4k68u30t.fsf@gitster.g","threadId":"56873","inReplyTo":"xmqq8rvku3bq.fsf@gitster.g","subject":"Re: [PATCH] packfile: avoid overflowing shift during decode","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-01-12T20:12:34Z","receivedAt":"2022-01-12T20:12:54Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> Marc Strapetz writes:\n>\n>> On 11/11/2021 02:58, Junio C Hamano wrote:\n>>> Jonathan Tan writes:\n>>> \n>>>> diff --git a/packfile.c b/packfile.c\n>>>> index 89402cfc69..972c327e29 100644\n>>>> --- a/packfile.c\n>>>> +++ b/packfile.c\n>>>> @@ -1068,7 +1068,7 @@ unsigned long unpack_object_header_buffer(const unsigned char *buf,\n>>>> \tsize = c & 15;\n>>>> \tshift = 4;\n>>>> \twhile (c & 0x80) {\n>>>> -\t\tif (len <= used || bitsizeof(long) <= shift) {\n>>>> +\t\tif (len <= used || (bitsizeof(long) - 7) <= shift) {\n>>\n>> This seems to cause troubles now for 32-bit systems (in my case Git\n>> for Windows 32-Bit): `shift` will go through 4, 11, 18 and for 25 it\n>> finally errors out. This means that objects >= 32MB can't be processed\n>> anymore. The condition should probably be changed to:\n>>\n>> +\t\tif (len <= used || (bitsizeof(long) - 7) < shift) {\n>>\n>> This still ensures that the shift can never overflow and on 32-bit\n>> systems restores the maximum size of 4G with a final shift of 127<<25 \n>> (the old condition `bitsizeof(long) <= shift` was perfectly valid for\n>> 32-bit systems).\n>\n> Jonathan?\n\n\n----- >8 --------- >8 --------- >8 --------- >8 --------- >8 -----\nDate: Wed, 12 Jan 2022 12:11:42 -0800\nSubject: [PATCH] packfile: fix off-by-one error in decoding logic\n\nshift count being exactly at 7-bit smaller than the long is OK; on\n32-bit architecture, shift count starts at 4 and goes through 11, 18\nand 25, at which point the guard triggers one iteration too early.\n\nReported-by: Marc Strapetz \nSigned-off-by: Junio C Hamano \n---\n packfile.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/packfile.c b/packfile.c\nindex d3820c780b..667e21ce97 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -1067,7 +1067,7 @@ unsigned long unpack_object_header_buffer(const unsigned char *buf,\n \tsize = c & 15;\n \tshift = 4;\n \twhile (c & 0x80) {\n-\t\tif (len <= used || (bitsizeof(long) - 7) <= shift) {\n+\t\tif (len <= used || (bitsizeof(long) - 7) < shift) {\n \t\t\terror(\"bad object header\");\n \t\t\tsize = used = 0;\n \t\t\tbreak;\n-- \n2.35.0-rc0-170-g6a31d082e5\n"},{"id":"446071","messageId":"20220112202708.324762-1-jonathantanmy@google.com","threadId":"56873","inReplyTo":"xmqq8rvku3bq.fsf@gitster.g","subject":"Re: [PATCH] packfile: avoid overflowing shift during decode","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2022-01-12T20:27:07Z","receivedAt":"2022-01-12T20:27:24Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"Junio C Hamano writes:\n> Marc Strapetz writes:\n> \n> > On 11/11/2021 02:58, Junio C Hamano wrote:\n> >> Jonathan Tan writes:\n> >> \n> >>> diff --git a/packfile.c b/packfile.c\n> >>> index 89402cfc69..972c327e29 100644\n> >>> --- a/packfile.c\n> >>> +++ b/packfile.c\n> >>> @@ -1068,7 +1068,7 @@ unsigned long unpack_object_header_buffer(const unsigned char *buf,\n> >>> \tsize = c & 15;\n> >>> \tshift = 4;\n> >>> \twhile (c & 0x80) {\n> >>> -\t\tif (len <= used || bitsizeof(long) <= shift) {\n> >>> +\t\tif (len <= used || (bitsizeof(long) - 7) <= shift) {\n> >\n> > This seems to cause troubles now for 32-bit systems (in my case Git\n> > for Windows 32-Bit): `shift` will go through 4, 11, 18 and for 25 it\n> > finally errors out. This means that objects >= 32MB can't be processed\n> > anymore. The condition should probably be changed to:\n> >\n> > +\t\tif (len <= used || (bitsizeof(long) - 7) < shift) {\n> >\n> > This still ensures that the shift can never overflow and on 32-bit\n> > systems restores the maximum size of 4G with a final shift of 127<<25 \n> > (the old condition `bitsizeof(long) <= shift` was perfectly valid for\n> > 32-bit systems).\n> \n> Jonathan?\n\nThis analysis makes sense - not sure how I missed that. 0x7f (the number\nbeing shifted) is 7 bits, so it can safely be shifted 25 bits.\n\nThe original condition of `bitsizeof(long) <= shift` works for 32-bit\nbut not for 64-bit (4, 11, 18, 25, 32, 39, 46, 53, 60) since shifting\n0x7f, a 7-bit value, by 60 bits would result in overflow, so we still\nneed to subtract 7. I agree that the inequality should be `<`, not `<=`.\n"}]}