1379411 - Latent write beyond bounds in MakeCompressedIndexDataValues()

Status: RESOLVED FIXED

(Core :: Storage: IndexedDB, defect, P2)

Description

[q1]

Due to an incorrect overflow test, MakeCompressedIndexDataValues() (dom\indexedDB\ActorsParent.cpp) could cause data to be written beyond bounds if the maximum length of writable data increased by only 2 bytes.

The bug is that the the overflow test on lines 783-90 does not include the value |sortKeyBufferLength|, but the sum on lines 792-97 -- that the test was meant to protect -- *does* include it:

750: nsresult
751: MakeCompressedIndexDataValues(
752:                              const FallibleTArray<IndexDataValue>& aIndexValues,
753:                              UniqueFreePtr<uint8_t>& aCompressedIndexDataValues,
754:                              uint32_t* aCompressedIndexDataValuesLength)
755: {
...
771:   // First calculate the size of the final buffer.
772:   uint32_t blobDataLength = 0;
773: 
774:   for (uint32_t arrayIndex = 0; arrayIndex < arrayLength; arrayIndex++) {
775:     const IndexDataValue& info = aIndexValues[arrayIndex];
776:     const nsCString& keyBuffer = info.mKey.GetBuffer();
777:     const nsCString& sortKeyBuffer = info.mSortKey.GetBuffer();
778:     const uint32_t keyBufferLength = keyBuffer.Length();
779:     const uint32_t sortKeyBufferLength = sortKeyBuffer.Length();
780: 
781:     MOZ_ASSERT(!keyBuffer.IsEmpty());
782: 
783:     // Don't let |infoLength| overflow.
784:     if (NS_WARN_IF(UINT32_MAX - keyBuffer.Length() <
785:                    CompressedByteCountForIndexId(info.mIndexId) +
786:                    CompressedByteCountForNumber(keyBufferLength) +
787:                    CompressedByteCountForNumber(sortKeyBufferLength))) {
788:       IDB_REPORT_INTERNAL_ERR();
789:       return NS_ERROR_DOM_INDEXEDDB_UNKNOWN_ERR;
790:     }
791: 
792:     const uint32_t infoLength =
793:       CompressedByteCountForIndexId(info.mIndexId) +
794:       CompressedByteCountForNumber(keyBufferLength) +
795:       CompressedByteCountForNumber(sortKeyBufferLength) +
796:       keyBufferLength +
797:       sortKeyBufferLength;
798: 
799:     // Don't let |blobDataLength| overflow.
800:     if (NS_WARN_IF(UINT32_MAX - infoLength < blobDataLength)) {
801:       IDB_REPORT_INTERNAL_ERR();
802:       return NS_ERROR_DOM_INDEXEDDB_UNKNOWN_ERR;
803:     }
804: 
805:     blobDataLength += infoLength;
806:   }
807: 
808:   UniqueFreePtr<uint8_t> blobData(
809:     static_cast<uint8_t*>(malloc(blobDataLength)));
810:   if (NS_WARN_IF(!blobData)) {
811:     IDB_REPORT_INTERNAL_ERR();
812:     return NS_ERROR_OUT_OF_MEMORY;
813:   }

The bug is (barely) latent because of various maximum length limits:

   1. The maximum length of an nsCString is 0x7ffffff5, so |keyBufferLength + sortKeyBufferLength| must be <= 0xffffffea;
   2. The maximum value of |info.mIndexId| is 0x7fffffffffffffff, so the maximum value of |CompressedByteCountForIndexId(info.mIndexId)| is 0xa; and
   3. The maximum values of |CompressedByteCountForNumber(keyBufferLength)| and |CompressedByteCountForNumber(sortKeyBufferLength)| are 0x5.

so the sum on lines 792-97 can be, at most, 0xfffffffe.

If the maximum sizes, above, increased only trivially, or some other value, having a maximum of >= 2, were added into line 792 without the test being fixed, the addition could overflow, causing an underallocation on lines 808-09, and a subsequent write beyond bounds.

Comment 1

[Andrew McCreight [:mccr8]]

Can you take a look, Jan? Thanks.

Comment 2

[Hsin-Yi Tsai (she/her) [:hsinyi]]

Shawn may be able to help once he finishes work on bug 1389561.

Comment 3

[Shawn Huang [:shawnjohnjr][:shuang] (as a happy gecko contributor)]

(In reply to Hsin-Yi Tsai [:hsinyi] from comment #2)
> Shawn may be able to help once he finishes work on bug 1389561.

Sorry. I will revisit here after bug 1389561 and bug 1402581 done. If anyone is interested in, feel free to take it.

Comment 4

[q1]

(In reply to Shawn Huang [:shawnjohnjr] (as a happy contributor) from comment #3)
> (In reply to Hsin-Yi Tsai [:hsinyi] from comment #2)
> > Shawn may be able to help once he finishes work on bug 1389561.
> 
> Sorry. I will revisit here after bug 1389561 and bug 1402581 done....

I just re-found this bug while reviewing FF source. Do you plan to fix it?

Comment 5

[Shawn Huang [:shawnjohnjr][:shuang] (as a happy gecko contributor)]

Ouch! Sorry. I guess this is something I missed 11 months ago after I quit, it doesn't show on my dashboard.

Forward ni to tt, janv, and mdaly.

Maybe tt has the bandwidth to fix this sec-bounty bug.

Comment 6

[Marion Daly [:mdaly]]

Tom, can you take a look at this?

Comment 7

[Tom Tung [:tt, :ttung]]

Sure. I'll take a look at this bug

Comment 8

[Tom Tung [:tt, :ttung]]

Attachment: bug1379411.patch

Comment 9

[Tom Tung [:tt, :ttung]]

Attachment: Bug 1379411: Make the test for boundary checks in MakeCompressedIndexDataValues be what it should be.

Hi Jan,

This patch is only to correct the overflow check. Could you help me to review that? Thanks!

I'll try to find someone to review the commit message as well since I'm not so sure about if the commit message is appropriate or if it genuinely meets requirements for a security issue.

Comment 10

[Jan Varga [:janv]]

AFAIK, if it's a patch for security issue, there shouldn't be any commit message, just bug number.

Comment 11

[Tom Tung [:tt, :ttung]]

(In reply to Jan Varga [:janv] from comment #10)
> AFAIK, if it's a patch for security issue, there shouldn't be any commit
> message, just bug number.

I see! I'll remove them after the review.

Comment 12

[Ryan VanderMeulen [:RyanVM]]

Generic commit messages which don't give away the problem are also fine (and preferable IMHO, since "Bug XYZ" commit messages scream "HEY, I'M A SECURITY FIX, LOOK AT ME!").

Comment 13

[q1]

I suggest using CheckedInt, since the sum on the RHS is, also, potentially susceptible of overflow. Also, using CheckedInt eliminates the chance of mismatches between the checks and the functional code.

Comment 14

[Marion Daly [:mdaly]]

Tom: can you loop back to this?

Comment 15

[Tom Tung [:tt, :ttung]]

Sorry for the late reply. I switched my context to other issues...

(In reply to Ryan VanderMeulen [:RyanVM] from comment #12)
> Generic commit messages which don't give away the problem are also fine (and
> preferable IMHO, since "Bug XYZ" commit messages scream "HEY, I'M A SECURITY
> FIX, LOOK AT ME!").

Thank you for the suggestion! That makes sense to me and that's what I wanted to do. I was not really sure I make it generic enough, though. I'll put that in my note and decide what to do after r+.

(In reply to q1 from comment #13)
> I suggest using CheckedInt, since the sum on the RHS is, also, potentially
> susceptible of overflow. Also, using CheckedInt eliminates the chance of
> mismatches between the checks and the functional code.

Thanks for the suggestion! CheckedInt provides a much better check and seems to be more powerful, but I'm not really sure if we want to apply that in this issue since it's a security bug. We don't want to let it be found easily. Personally, I prefer to do that in another bug. I put my thoughts below inline:

First, this is a security issue, so I prefer to make a change as tiny as possible and match the style with other overflow checks in ActorsParent.cpp. I tend to open another bug and discuss whether we want to change the overflow checking style in this file to use Checkedint. 

Second, please correct me if I am wrong. If your analynsis at comment #0 still valid and if I understand correctly, |UINT32_MAX| is guaranteed greater than the value of |max(keyBufferLength + sortKeyBufferLength) + max(CompressedByteCountForIndexId(info.mIndexId)) + max(|CompressedByteCountForNumber(keyBufferLength)| + max(CompressedByteCountForNumber(sortKeyBufferLength)))|.

=> 0xffffffff > 0xffffffea + 0xa + 0x5 + 0x5 = 0xfffffffe

So, the RHS (some value at most less than 0xfffffffe because keyBufferLength is at LHS) shouldn't be overflow. Correcting the overflow check to ensure someone, in the future, won't accidentally cause overflow by adding value into it (even they reckon they add the value into the overflow check) is enough to fix the potential issue. Therefore, the patch seems to work fine for me.

Comment 16

[q1]

(In reply to Tom Tung [:tt] from comment #15)
> Sorry for the late reply. I switched my context to other issues...
> > I suggest using CheckedInt, since the sum on the RHS is, also, potentially
> > susceptible of overflow. Also, using CheckedInt eliminates the chance of
> > mismatches between the checks and the functional code.
> 
> Thanks for the suggestion! CheckedInt provides a much better check and seems
> to be more powerful, but I'm not really sure if we want to apply that in
> this issue since it's a security bug. We don't want to let it be found
> easily....

That's certainly a possibility. Thank you for considering the change. Please open a nonsecurity bug for it if/when you think it advisable.

> Second, please correct me if I am wrong....

Yes, as writ in the patch, the RHS of lines 792-6 can't overflow because the maximum size of the |nsCString| |sortKeyBuffer| is 0x7ffffff5, and all the other values on the RHS are small.

Comment 17

[Tom Tung [:tt, :ttung]]

(In reply to q1 from comment #16)
> That's certainly a possibility. Thank you for considering the change. Please
> open a nonsecurity bug for it if/when you think it advisable.

File the bug 1489408 for it.

I planned to file that after this issue is resolved. However, I found I actually don't need to do that so late.

Comment 18

[Jan Varga [:janv]]

Given the various maximum length limits described in comment 0, there's no security issue at the moment, but there's a risk that if some of the limits increase or a new values is added, the overflow becomes a real possibility.

The current check is:
if (NS_WARN_IF(UINT32_MAX - keyBuffer.Length() <
               CompressedByteCountForIndexId(info.mIndexId) +
               CompressedByteCountForNumber(keyBufferLength) +
               CompressedByteCountForNumber(sortKeyBufferLength))) {
  IDB_REPORT_INTERNAL_ERR();
  return NS_ERROR_DOM_INDEXEDDB_UNKNOWN_ERR;
}

The proposed check is:
if (NS_WARN_IF(UINT32_MAX - keyBuffer.Length() <
               CompressedByteCountForIndexId(info.mIndexId) +
               CompressedByteCountForNumber(keyBufferLength) +
               CompressedByteCountForNumber(sortKeyBufferLength) +
               sortKeyBufferLength)) {
  IDB_REPORT_INTERNAL_ERR();
  return NS_ERROR_DOM_INDEXEDDB_UNKNOWN_ERR;
}

Well, the current check is not 100% correct (all those helper functions return uint32_t), but I think the proposed checks makes it even worse.

I guess, we want something like this:
uint32_t infoLength = keyBufferLength;
if (NS_WARN_IF(UINT32_MAX - sortKeyBufferLength < infoLength)) {
  IDB_REPORT_INTERNAL_ERR();
  return NS_ERROR_DOM_INDEXEDDB_UNKNOWN_ERR;
}
infoLength += sortKeyBufferLength;
if (NS_WARN_IF(UINT32_MAX - CompressedByteCountForIndexId(info.mIndexId) <
               infoLength)) {
  IDB_REPORT_INTERNAL_ERR();
  return NS_ERROR_DOM_INDEXEDDB_UNKNOWN_ERR;
}
infoLength += CompressedByteCountForIndexId(info.mIndexId);
if (NS_WARN_IF(UINT32_MAX - CompressedByteCountForNumber(keyBufferLength) <
               infoLength)) {
  IDB_REPORT_INTERNAL_ERR();
  return NS_ERROR_DOM_INDEXEDDB_UNKNOWN_ERR;
}
infoLength += CompressedByteCountForNumber(keyBufferLength);
if (NS_WARN_IF(UINT32_MAX - CompressedByteCountForNumber(sortKeyBufferLength) <
               infoLength)) {
  IDB_REPORT_INTERNAL_ERR();
  return NS_ERROR_DOM_INDEXEDDB_UNKNOWN_ERR;
}
infoLength += CompressedByteCountForNumber(sortKeyBufferLength);

But it looks terrible, if this were a real security issue, I would also prefer a simple fix here and file a new bug for CheckedInt.
Anyway, we have the time to do it cleanly, directly in this bug.

We don't have to use CheckedInt everywhere in ActorsParent.cpp for now, just here for infoLength computation.
Tom, if you feel that there are other places that need to use CheckedInt, you can propose it in bug 1489408.
Thanks.

Comment 19

[Tom Tung [:tt, :ttung]]

Attachment: bug1379411.patch

The previous patch didn't really prevent the potential overflow issue in the future. It just aligned the value in the overflow check with the computing result below. For instance, RHS in the check still has a chance to overflow if someone puts more parameters |infoLength| and adds them into the current overflow check rather than creating additional overflow checks.

This patch tries to utilize CheckedInt to fix the potential overflow issue without having a few more checks.

Comment 20

[Tom Tung [:tt, :ttung]]

Attachment: bug1379411.patch

Shorten the patch a bit.

Comment 21

[Tom Tung [:tt, :ttung]]

(In reply to Jan Varga [:janv] from comment #18)
Thanks for the feedback!

> Well, the current check is not 100% correct (all those helper functions
> return uint32_t), but I think the proposed checks makes it even worse.

I'm not really sure if I genuinely catch this. I thought additional overflow checks should be added when the |infoLength| is updated a few more parameters in the future and current length shouldn't overflow so that aligning the parameters was ok enough for this issue.

However, after reading Jan's comment #18, I found that it's not right and a little too over to assume that. But, I still not so sure I really got it.

Jan, did you mean the patch ignored the case like I described in comment 19 or there is another issue I might overlook? I want to make sure I fully understand all the reasons and avoid stepping into the same case in the future.

> We don't have to use CheckedInt everywhere in ActorsParent.cpp for now, just
> here for infoLength computation.
> Tom, if you feel that there are other places that need to use CheckedInt,
> you can propose it in bug 1489408.

Will do. Thanks!

Comment 22

[Jan Varga [:janv]]

In your original patch, you added |+ sortKeyBufferLength| to rhs. The max for nsCString length is currently 0x7ffffff5, so it would be ok. However, the max can change in theory to 0xffffffff and then it wouldn't be ok.
This was already pointed out in comment 13.

Here's a small test, just in case it's still not clear.

#include <stdio.h>
#include <stdint.h>

#define UINT_MAX 0xffffffff

bool
test(uint32_t l2)
{
  printf("in test, l2: %u\n", l2);

  uint32_t l1 = 0x7ffffff5;

  if (UINT_MAX - l1 < 10 + 5 + 5 + l2) {
    printf("overflow\n");
    return false;
  }

  printf("rhs: %u\n", 10 + 5 + 5 + l2);

  uint32_t len = 10 + 5 + 5 + l1 + l2;
  printf("len: %u\n", len);

  printf("ok\n");
  return true;
}

int
main()
{
  test(0x7ffffff5); // OK
  test(0x7ffffff5 + 1); // still OK (len is at the maximum)
  test(0x7ffffff5 + 2); // still OK, we catch the overflow
  test(UINT_MAX); // NOT OK, rhs overflow and len is wrong too

  return 0;
}

Comment 23

[Jan Varga [:janv]]

If you want to safely add an uint32_t to other uint32_t you have to do this:
if (UINT32_MAX - v2 < v1)) {
  // overflow
  return;
}
v1 += v2;

If there are more values, you have to check each one separately, you can't do this:
if (UINT32_MAX - v2 - v3 < v1)) {
  // overflow
  return;
}
v1 += v2 + v3;

you can't do this either:
if (UINT_MAX - v2 < v1 + v3) {
  // overflow
  return;
}
v1 += v2 + v3;

Comment 24

[Tom Tung [:tt, :ttung]]

(In reply to Jan Varga [:janv] from comment #22)
> In your original patch, you added |+ sortKeyBufferLength| to rhs. The max
> for nsCString length is currently 0x7ffffff5, so it would be ok. However,
> the max can change in theory to 0xffffffff and then it wouldn't be ok.
> This was already pointed out in comment 13.

I see. Thanks for clarifying and the example as well! That's what I wanted to describe in comment #19 and #21. I wanted to shorten the code because they should be fine but I made an assumption too far away. I was trying to say that I falsely assumed if someone wants to add a new variable(says, v5), they would have another overflow check like, in the example:

// Current check
if (UINT_MAX - v1 < v2 + v3 + v4) {
  printf("overflow\n");
  return false;
}

infoLength =  v1 + v2 + v3 + v4;

// Add an addtional overflow check below if v5 is updated to infoLength
if (UINT_MAX - infoLength < v5) {
  printf("overflow\n");
  return false;
}

infoLength += v5;

However, actually, I shouldn't have assumed that. I made an assumption too far away and as you commented that might make the code look terrible even if they follow what I imagined.

Sorry for not explaining that clearly. I'll try to state them more clearly.

Comment 25

[q1]

(In reply to Jan Varga [:janv] from comment #22)
> In your original patch, you added |+ sortKeyBufferLength| to rhs. The max
> for nsCString length is currently 0x7ffffff5, so it would be ok. However,
> the max can change in theory to 0xffffffff and then it wouldn't be ok.
> This was already pointed out in comment 13.

Yes, but changing |nsCString| in this way would create a likely overflow and read/write beyond bounds in the (probably hundreds) of places in which a construct similar to the following is used:

   // s1 and s2 are |nsCString|s

   uint32_t len = s1.Length() + s2.Length() + 1; // potential overflow ->
   char *pResult = new char [len];               // potential underallocation ->
   memcpy (pResult, s1, s1.Length());            // UGH! Potential write beyond bounds!
   ...

There really should be warnings on all security-sensitive constants (like maximum |nsCString| and |nsString| length, maximum |nsTArray| length, etc.) to avoid this possibility.

Comment 26

[Jan Varga [:janv]]

(In reply to q1 from comment #25)
> Yes, but changing |nsCString| in this way would create a likely overflow and
> read/write beyond bounds in the (probably hundreds) of places

Of course, it was just a theoretical example.
Anyway, CheckedInt is very easy to use, the final code looks good and it should be also fast.
I don't see a reason to use something else.

Comment 27

[Tom Tung [:tt, :ttung]]

Attachment: Bug 1379411 - Apply CheckedInt to infoLength for preventing it from overflowing in the future;

Modified commit message.

Jan, this patch applies CheckedUint32 (CheckedInt<uint32_t>) to |infoLength| for the overflow check. Would you mind reviewing it? Thanks!

Comment 28

[Tom Tung [:tt, :ttung]]

Attachment: Bug 1379411 - Apply CheckedInt to infoLength for preventing it from overflowing in the future;

Thanks for the review!

Comment 29

[Tom Tung [:tt, :ttung]]

try: https://treeherder.mozilla.org/#/jobs?repo=try&revision=f6d93dcc89f05ba85c0bb8a016a3d84a6dc54cea

Comment 30

[Tom Tung [:tt, :ttung]]

Try looks okay (I cannot find any failure related to indexedDB and it shouldn't be) and based on it's a potential security issue, I reckon it's okay to push the patch with current commit message (not mentioning infoLength may leak in the future).

Comment 31

[Tom Tung [:tt, :ttung]]

Check-in: mozilla-inbound/4ffdf21d17fa - Tom Tung - Bug 1379411 - Apply CheckedInt to infoLength for preventing it from overflowing in the future; r=janv

Comment 32

[Sebastian Hengst [:aryx] (needinfo me if it's about an intermittent or backout)]

https://hg.mozilla.org/mozilla-central/rev/4ffdf21d17fa

Comment 33

[Ryan VanderMeulen [:RyanVM]]

Doesn't seem like there's much need to backport this if it's just preventing a theoretical issue from happening, but I guess a Beta uplift can't hurt?

Comment 34

[Tom Tung [:tt, :ttung]]

Comment on attachment 9008388 [details] [diff] [review]
Bug 1379411 - Apply CheckedInt to infoLength for preventing it from overflowing in the future;

Approval Request Comment
[Feature/Bug causing the regression]: Bug 871846. It's actually just an overflow check mismatching with actual calculated value, but, theoretically, it shouldn't overflow given even the overall value of max size of all parameters shouldn't overflow.

[User impact if declined]: No, but might be strange if someone read the code of that since the overflow check doesn't align with the actual calculated value.

[Is this code covered by automated tests?]: No, since it simply aligns the checks and the result and utilizes functions of CheckedInt which have been tested.

[Has the fix been verified in Nightly?]: Yes

[Needs manual test from QE? If yes, steps to reproduce]: No

[List of other uplifts needed for the feature/fix]: Just this patch

[Is the change risky?]: I don't think so.

[Why is the change risky/not risky?]: Because, the patch only uses a well-tested class in mfbt to overwrite the overflow check and correct the value of it.

[String changes made/needed]: No

Comment 35

[Pascal Chevrel:pascalc]

Comment on attachment 9008388 [details] [diff] [review]
Bug 1379411 - Apply CheckedInt to infoLength for preventing it from overflowing in the future;

Uplift approved for 63 beta 7, thanks.

Comment 36

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/releases/mozilla-beta/rev/e565eaca9472