Closed Bug 1317545 Opened 3 years ago Closed 3 years ago

Latent (?) write beyond bounds in nsTString_CharT::ReplaceSubstring()


(Core :: String, defect)

49 Branch
Not set



Tracking Status
firefox52 --- wontfix
firefox53 --- fixed


(Reporter: q1, Assigned: erahm)


(Keywords: sec-audit, Whiteboard: [adv-main53-][post-critsmash-triage])


(2 files)

Attached file bug_629_poc_3.7z
nsTString_CharT::ReplaceSubstring() (xpcom\string\nsTStringObsolete.cpp) can experience an integer overflow. If it does, it writes data beyond the end of its |mData| character array.

The bug appears to be latent because no callers appear to use a sufficiently-long replacement (|aNewValue|) string.

When preparing to replace the instances of string |aTarget| in the destination string with string |aNewValue|, ReplaceSubstring() calculates the character count of the resulting string into |newLength| (lines 493-515). However, |newLength| isa uint32_t, and ReplaceSubstring() does not check whether the calculations used to compute it overflow.

If the destination string is long enough (e.g., 0x10000000 characters; this is permissible for nsAString), and it contains enough substrings equal to |aTarget| (e.g., 0x10000000 1-character substrings) and the ratio |aNewValue.Length() / aTarget.Length()| is large enough (e.g., 16), |newLength| will overflow (in this example, on line 507), causing line 531 to allocate a buffer large enough for only the existing destination string. The code in lines 555-71 then executes, writing beyond the end of the destination string.

This bug appears to be latent because AutoTArray (which lines 493-515 use) implicitly limits the number of replacements to 0x1073ffff (load the attached POC in FF x64 to see this limit in action). Since the largest ratio of |aNewValue.Length() / aTarget.Length()| in existing code appears to be 6 (line 697-8 of dom\base\nsXMLContentSerializer.cpp replaces "\"" with """), the maximum-computed value for |newLength| is ~ 0x62B7FFFA, which is safe.

However, adding an apparently-innocuous call to ReplaceSubstring() with a sufficiently-larger ratio would cause this bug to become exploitable.

485: bool
486: nsTString_CharT::ReplaceSubstring(const self_type& aTarget,
487:                                   const self_type& aNewValue,
488:                                   const fallible_t&)
489: {
490:   if (aTarget.Length() == 0)
491:     return true;
493:   // Remember all of the non-matching parts.
494:   AutoTArray<Segment, 16> nonMatching;
495:   uint32_t i = 0;
496:   uint32_t newLength = 0;
497:   while (true)
498:   {
499:     int32_t r = FindSubstring(mData + i, mLength - i, static_cast<const char_type*>(aTarget.Data()), aTarget.Length(), false);
500:     int32_t until = (r == kNotFound) ? mLength - i : r;
501:     nonMatching.AppendElement(Segment(i, until));
502:     newLength += until;
503:     if (r == kNotFound) {
504:       break;
505:     }
507:     newLength += aNewValue.Length();
508:     i += r + aTarget.Length();
509:     if (i >= mLength) {
510:       // Add an auxiliary entry at the end of the list to help as an edge case
511:       // for the algorithms below.
512:       nonMatching.AppendElement(Segment(mLength, 0));
513:       break;
514:     }
515:   }
517:   // If there's only one non-matching segment, then the target string was not
518:   // found, and there's nothing to do.
519:   if (nonMatching.Length() == 1) {
520:     MOZ_ASSERT(nonMatching[0].mBegin == 0 && nonMatching[0].mLength == mLength,
521:                "We should have the correct non-matching segment.");
522:     return true;
523:   }
525:   // Make sure that we can mutate our buffer.
526:   // Note that we always allocate at least an mLength sized buffer, because the
527:   // rest of the algorithm relies on having access to all of the original
528:   // string.  In other words, we over-allocate in the shrinking case.
529:   char_type* oldData;
530:   uint32_t oldFlags;
531:   if (!MutatePrep(XPCOM_MAX(mLength, newLength), &oldData, &oldFlags))
532:     return false;
533:   if (oldData) {
534:     // Copy all of the old data to the new buffer.
535:     char_traits::copy(mData, oldData, mLength);
536:     ::ReleaseData(oldData, oldFlags);
537:   }
539:   if (aTarget.Length() >= aNewValue.Length()) {
540:     // In the shrinking case, start filling the buffer from the beginning.
555:   } else {
556:     // In the growing case, start filling the buffer from the end.
557:     const uint32_t delta = (aNewValue.Length() - aTarget.Length());
558:     for (i = nonMatching.Length() - 1; i > 0; --i) {
559:       // When we move the i'th non-matching segment into position, we need to
560:       // account for the characters added by the previous |i| replacements by
561:       // adding |i * delta|.
562:       const char_type* sourceSegmentPtr = mData + nonMatching[i].mBegin;
563:       char_type* destinationSegmentPtr = mData + nonMatching[i].mBegin + i * delta;
564:       char_traits::move(destinationSegmentPtr, sourceSegmentPtr,
565:                         nonMatching[i].mLength);
566:       // Write the i'th replacement immediately before the new i'th non-matching
567:       // segment.
568:       char_traits::copy(destinationSegmentPtr - aNewValue.Length(),
569:                         aNewValue.Data(), aNewValue.Length());
570:     }
571:   }
This bug is still present in trunk.
Flags: sec-bounty?
Group: core-security → dom-core-security
Component: XPCOM → String
Keywords: sec-audit
q1, thanks for the thorough report. I agree this is most likely latent, but hardening the code to avoid future issues is certainly I good idea. Patch forthcoming.
Assignee: nobody → erahm
MozReview-Commit-ID: 5Qvusd3twhM
Attachment #8811899 - Flags: review?(nfroyd)
Attachment #8811899 - Flags: review?(nfroyd) → review+
Comment on attachment 8811899 [details] [diff] [review]
Check new length in ReplaceSubstring

This hasn't been rated yet, so requesting approval. My guess is this is probably sec-low.

> [Security approval request comment]
> How easily could an exploit be constructed based on the patch?

We believe it's a latent issue, not currently exploitable.

> Do comments in the patch, the check-in comment, or tests included in the patch paint a bulls-eye on the security problem?

Not specifically, but we're clearly checking for overflow.

> Which older supported branches are affected by this flaw?


> If not all supported branches, which bug introduced the flaw?


> Do you have backports for the affected branches? If not, how different, hard to create, and risky will they be?

Patch should apply to all branches, but not likely to request uplift.

> How likely is this patch to cause regressions; how much testing does it need?

Not likely, just changes an int to a CheckedInt.
Attachment #8811899 - Flags: sec-approval?
Comment on attachment 8811899 [details] [diff] [review]
Check new length in ReplaceSubstring

Attachment #8811899 - Flags: sec-approval? → sec-approval+
Closed: 3 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla53
Group: dom-core-security → core-security-release
Flags: sec-bounty? → sec-bounty+
Should we consider this for backport to Beta52 for the next ESR?
Flags: needinfo?(erahm)
(In reply to Ryan VanderMeulen [:RyanVM] from comment #8)
> Should we consider this for backport to Beta52 for the next ESR?

I don't think it's worth the effort, the issue would be if we added new usage |ReplaceSubstring| which really should only happen in *newer* versions unless we uplifted some shady code recently.
Flags: needinfo?(erahm)
Whiteboard: [adv-main53-]
Flags: qe-verify-
Whiteboard: [adv-main53-] → [adv-main53-][post-critsmash-triage]
Group: core-security-release
You need to log in before you can comment on or make changes to this bug.