Closed Bug 805121 (CVE-2013-0750) Opened 12 years ago Closed 11 years ago

String Replacement Heap Corruption Remote Code Execution Vulnerability (ZDI-CAN-1473)

Categories

(Core :: JavaScript Engine, defect)

defect
Not set
normal

Tracking

()

RESOLVED FIXED
mozilla20
Tracking Status
firefox16 --- wontfix
firefox17 - wontfix
firefox18 + fixed
firefox19 + fixed
firefox20 + fixed
firefox-esr10 18+ fixed
firefox-esr17 18+ fixed
b2g18 --- fixed

People

(Reporter: reed, Assigned: Waldo)

Details

(Keywords: csectype-intoverflow, sec-critical, testcase, Whiteboard: [adv-main18+][adv-esr17+][adv-esr10+])

Attachments

(4 files, 3 obsolete files)

Attached file PoC
ZDI-CAN-1473: Mozilla Firefox String Replacement Heap Corruption Remote Code Execution Vulnerability

-- CVSS -----------------------------------------
7.5, AV:N/AC:L/Au:N/C:P/I:P/A:P

-- ABSTRACT -------------------------------------
TippingPoint has identified a vulnerability affecting the following products:

  Mozilla Firefox

-- VULNERABILITY DETAILS ------------------------
An integer overflow is possible when calculating the length for a Javascript string concatenation. 

mozilla-release\js\src\jsstr.cpp    

FindReplaceLength(JSContext *cx, RegExpStatics *res, ReplaceData &rdata, size_t *sizep)
    ...
    JSString *repstr = rdata.repstr;
    size_t replen = repstr->length();
    for (const jschar *dp = rdata.dollar, *ep = rdata.dollarEnd; dp;
         dp = js_strchr_limit(dp, '$', ep)) {
        JSSubString sub;
        size_t skip;
        if (InterpretDollar(cx, res, dp, ep, rdata, &sub, &skip)) {
           replen += sub.length - skip;
            dp += skip;
        } else {
            dp++;
        }
    }
    *sizep = replen;
    return true;

The for loop above illustrates the problem: the looped arithmetic operation to add to replen can result in replen wrapping. The code below shows the use of the above function in a vulnerable fashion: 

ReplaceRegExpCallback(JSContext *cx, RegExpStatics *res, size_t count, void *p)
    ...
    size_t replen = 0;  /* silence 'unused' warning */
   if (!FindReplaceLength(cx, res, rdata, &replen))
        return false;

    size_t growth = leftlen + replen;
   if (!rdata.sb.reserve(rdata.sb.length() + growth))
        return false;
    rdata.sb.infallibleAppend(left, leftlen); /* skipped-over portion of the search value */
   DoReplace(cx, res, rdata);


The call to FindReplaceLength can result in a wrapped replen value, which when used for allocation, causes an undersized allocation. Use of the undersized allocation results in memory corruption.

-- CREDIT ---------------------------------------
This vulnerability was discovered by:

   pa_kt / twitter.com/pa_kt
More information from the reporter:
===================================
During string replace, FF first calculates the output's length, and then
does the replacing. 

Problem:

x - letter 'a' repeated 2^16 times
y = x

z = x.replace('a', y);

z will have length equal to 2^32. That's the idea.

file: mozilla-release\js\src\jsstr.cpp    

FindReplaceLength(JSContext *cx, RegExpStatics *res, ReplaceData &rdata, size_t *sizep)
    ...
    JSString *repstr = rdata.repstr;
    size_t replen = repstr->length();
    for (const jschar *dp = rdata.dollar, *ep = rdata.dollarEnd; dp;
         dp = js_strchr_limit(dp, '$', ep)) {
        JSSubString sub;
        size_t skip;
        if (InterpretDollar(cx, res, dp, ep, rdata, &sub, &skip)) {
1           replen += sub.length - skip;
            dp += skip;
        } else {
            dp++;
        }
    }
    *sizep = replen;
    return true;

1 - replen overflow

ReplaceRegExpCallback(JSContext *cx, RegExpStatics *res, size_t count, void *p)
    ...
    size_t replen = 0;  /* silence 'unused' warning */
1   if (!FindReplaceLength(cx, res, rdata, &replen))
        return false;

    size_t growth = leftlen + replen;
2   if (!rdata.sb.reserve(rdata.sb.length() + growth))
        return false;
    rdata.sb.infallibleAppend(left, leftlen); /* skipped-over portion of the search value */
3   DoReplace(cx, res, rdata);

1 - replen is overflowed
2 - allocated buffer is too small
3 - heap overflow inside. infallibleAppend fails (hehe)

(149c.16ac): Access violation - code c0000005 (first chance)
First chance exceptions are reported before any exception handling.
This exception may be expected and handled.
eax=0dff0158 ebx=00370031 ecx=0046c000 edx=0e100000 esi=00100000 edi=0037bde0
eip=69a5ec57 esp=0037bd08 ebp=0c920000 iopl=0         nv up ei pl nz na pe nc
cs=0023  ss=002b  ds=002b  es=002b  fs=0053  gs=002b             efl=00210206
mozjs!DoReplace+0xb7:
69a5ec57 668919          mov     word ptr [ecx],bx        ds:002b:0046c000=????
0:000> k
ChildEBP RetAddr  
0037bd28 69a5ed64 mozjs!DoReplace+0xb7 [e:\builds\moz2_slave\rel-m-rel-w32-bld\build\js\src\jsstr.cpp @ 1836]
0037bd44 69a5eac4 mozjs!ReplaceRegExpCallback+0xa4 [e:\builds\moz2_slave\rel-m-rel-w32-bld\build\js\src\jsstr.cpp @ 1866]
0037bd80 69a608dc mozjs!DoMatch+0xc4 [e:\builds\moz2_slave\rel-m-rel-w32-bld\build\js\src\jsstr.cpp @ 1474]
0037bdb4 69a61566 mozjs!str_replace_regexp+0x5c [e:\builds\moz2_slave\rel-m-rel-w32-bld\build\js\src\jsstr.cpp @ 2043]
0037bee8 00310031 mozjs!js::str_replace+0x396 [e:\builds\moz2_slave\rel-m-rel-w32-bld\build\js\src\jsstr.cpp @ 2200]
WARNING: Frame IP not in any known module. Following frames may be wrong.
0037bef8 00310031 0x310031
0:000> !analyze -v
*******************************************************************************
*                                                                             *
*                        Exception Analysis                                   *
*                                                                             *
*******************************************************************************

*************************************************************************
***                                                                   ***
***                                                                   ***
***    Your debugger is not using the correct symbols                 ***
***                                                                   ***
***    In order for this command to work properly, your symbol path   ***
***    must point to .pdb files that have full type information.      ***
***                                                                   ***
***    Certain .pdb files (such as the public OS symbols) do not      ***
***    contain the required information.  Contact the group that      ***
***    provided you with these symbols if you need this command to    ***
***    work.                                                          ***
***                                                                   ***
***    Type referenced: kernel32!pNlsUserInfo                         ***
***                                                                   ***
*************************************************************************
*************************************************************************
***                                                                   ***
***                                                                   ***
***    Your debugger is not using the correct symbols                 ***
***                                                                   ***
***    In order for this command to work properly, your symbol path   ***
***    must point to .pdb files that have full type information.      ***
***                                                                   ***
***    Certain .pdb files (such as the public OS symbols) do not      ***
***    contain the required information.  Contact the group that      ***
***    provided you with these symbols if you need this command to    ***
***    work.                                                          ***
***                                                                   ***
***    Type referenced: kernel32!pNlsUserInfo                         ***
***                                                                   ***
*************************************************************************

FAULTING_IP: 
mozjs!DoReplace+b7 [e:\builds\moz2_slave\rel-m-rel-w32-bld\build\js\src\jsstr.cpp @ 1836]
69a5ec57 668919          mov     word ptr [ecx],bx

EXCEPTION_RECORD:  ffffffff -- (.exr 0xffffffffffffffff)
ExceptionAddress: 69a5ec57 (mozjs!DoReplace+0x000000b7)
   ExceptionCode: c0000005 (Access violation)
  ExceptionFlags: 00000000
NumberParameters: 2
   Parameter[0]: 00000001
   Parameter[1]: 0046c000
Attempt to write to address 0046c000

FAULTING_THREAD:  000016ac

PROCESS_NAME:  firefox.exe

ERROR_CODE: (NTSTATUS) 0xc0000005 - The instruction at 0x%08lx referenced memory at 0x%08lx. The memory could not be %s.

EXCEPTION_CODE: (NTSTATUS) 0xc0000005 - The instruction at 0x%08lx referenced memory at 0x%08lx. The memory could not be %s.

EXCEPTION_PARAMETER1:  00000001

EXCEPTION_PARAMETER2:  0046c000

WRITE_ADDRESS:  0046c000 

FOLLOWUP_IP: 
mozjs!DoReplace+b7 [e:\builds\moz2_slave\rel-m-rel-w32-bld\build\js\src\jsstr.cpp @ 1836]
69a5ec57 668919          mov     word ptr [ecx],bx

NTGLOBALFLAG:  0

APPLICATION_VERIFIER_FLAGS:  0

ADDITIONAL_DEBUG_TEXT:  Followup set based on attribute [Is_ChosenCrashFollowupThread] from Frame:[0] on thread:[ffffffff]

LAST_CONTROL_TRANSFER:  from 69a5ed64 to 69a5ec57

BUGCHECK_STR:  APPLICATION_FAULT_INVALID_POINTER_WRITE_STACKIMMUNE

PRIMARY_PROBLEM_CLASS:  INVALID_POINTER_WRITE_STACKIMMUNE

DEFAULT_BUCKET_ID:  INVALID_POINTER_WRITE_STACKIMMUNE

STACK_TEXT:  
00000000 firefox+0x0


SYMBOL_NAME:  firefox

FOLLOWUP_NAME:  MachineOwner

MODULE_NAME: firefox

IMAGE_NAME:  C:\Program Files (x86)\Mozilla Firefox 8\firefox.exe

DEBUG_FLR_IMAGE_TIMESTAMP:  4eb4a985

STACK_COMMAND:  ** Pseudo Context ** ; kb

BUCKET_ID:  APPLICATION_FAULT_INVALID_POINTER_WRITE_STACKIMMUNE_firefox

FAILURE_BUCKET_ID:  INVALID_POINTER_WRITE_STACKIMMUNE_c0000005_C:_Program_Files_(x86)_Mozilla_Firefox_8_firefox.exe!Unknown

Followup: MachineOwner
---------
Tentatively taking, although I'll need to page the "".replace code back into memory before I'll be confident in a complete fix.
Assignee: general → jwalden+bmo
Attached patch Patch and testSplinter Review
This string replace code is all a bit messy, but I think this addresses everything.  I skimmed the rest of jsstr.cpp and think these might have been the only bad places, but it's really hard to say.

Fortunately, this bug doesn't bite in 64-bit builds, because it's going to be really hard (perhaps impossible) to overflow a 64-bit value.  If only we cared enough about 64-bit to ship 64-bit browsers (he said, passive-aggressively)...

I have a feeling this patch isn't trivially back-portable as it's written, but I guess I'll cross that bridge when I get to it.
Attachment #678530 - Flags: review?(terrence)
Comment on attachment 678530 [details] [diff] [review]
Patch and test

Review of attachment 678530 [details] [diff] [review]:
-----------------------------------------------------------------

(In reply to Jeff Walden [:Waldo] (remove +bmo to email) from comment #3)
> Created attachment 678530 [details] [diff] [review]
> Patch and test
> 
> This string replace code is all a bit messy, but I think this addresses
> everything.  I skimmed the rest of jsstr.cpp and think these might have been
> the only bad places, but it's really hard to say.
> 
> I have a feeling this patch isn't trivially back-portable as it's written,
> but I guess I'll cross that bridge when I get to it.

At least I haven't ported jsstr over to Range<jschar> yet, so it could be worse.  Speaking of which, note to self: use CheckedInt for the length in Range.
Attachment #678530 - Flags: review?(terrence) → review+
Does the test in the patch reveal the security problem, or is it just a "correctness" test?

Note: the fact that a bug has been reported to us is public, although the details are not
http://www.zerodayinitiative.com/advisories/upcoming/
Given comment 3, we'll wontfix for beta and hope for an uplift nomination to aurora. If a safe backport to beta *is* available, please nominate that as well, but we're ok with skipping 17 here.
(In reply to Jeff Walden [:Waldo] (remove +bmo to email) from comment #3)
> I have a feeling this patch isn't trivially back-portable as it's written,
> but I guess I'll cross that bridge when I get to it.

Time to cross... If this is do-able in Firefox 17 we want it, but even if it's risky we'll want it soon in Firefox 18 (and ESR 10? does this affect that one?).
Comment on attachment 678530 [details] [diff] [review]
Patch and test

[Security approval request comment]
How easily can the security issue be deduced from the patch?
Pretty easily, CheckedInt screams integer-overflow, and the places that are changed naturally flow into out-of-range-ish-looking code.

Do comments in the patch, the check-in comment, or tests included in the patch paint a bulls-eye on the security problem?
The checkin comment is moderately obfuscatory (no comment seems like it'd be a bigger bullseye), but anyone who looks is going to see through it.

Which older supported branches are affected by this flaw?
Everything; this code dates back a very long time.  find_replen/do_replace in CVS source have the problem, if you squint a little through C++-ification in the meantime:

http://mxr.mozilla.org/mozilla/source/js/src/jsstr.c#1543

Heck, at a very brief glance at CVS revision 1.1, I think the problem exists even there.  (!)

If not all supported branches, which bug introduced the flaw?
N/A

Do you have backports for the affected branches? If not, how different, hard to create, and risky will they be?
I haven't done it yet, but it shouldn't be too bad; I'll start on that now.  I expect it'll require backporting CheckedInt to mfbt, but we've backported other additions to mfbt in the last month, and it's not too tricky (particularly as CheckedInt is very close to self-contained).

How likely is this patch to cause regressions; how much testing does it need?
I don't think it's particularly likely.  We've got a bunch of automatic testing of the CheckedInt code, so that seems pretty reliable.  The uses of it here seem reasonably straightfoward.  That said, a little targeted fuzzing of replace with dollar-sign-heavy replacement patterns would not go amiss here.  Probably the biggest risk is that this patch somehow misses another instance of this sort of issue in jsstr.cpp, and someone will look through the file and find such a case that I didn't see when I looked through it.  I *did* look through for such cases, so there's some protection against that possibility.  But it'd be easy to miss something, as evidenced by this issue going back to the dawn of time with nobody seeing it til now.
Attachment #678530 - Flags: sec-approval?
(Oh, sorry for the delay on responding here, my laptop was broken for a couple weeks, and secure bugmail made it too difficult to read comments on all secure bugs I'm following for me to do it on the backup computer I was using.  :-\ )
Attached patch Aurora-ready patch (obsolete) — Splinter Review
No particular backporting pain here; I think this just applied without changes.
Attachment #680281 - Flags: review+
Attached patch Beta-ready patch (obsolete) — Splinter Review
No changes from the trunk patch necessary.  I assume this won't get taken just right now, but since beta's also esr17, it'll be needed eventually.
Attached patch esr10-ready patch (obsolete) — Splinter Review
This patch requires effb4811409b, 87a5ed480992, eaea2f2c083a, and ad167725cba5 be backported for me to be able to test/build this with the gcc 4.7 compiler I have easily available to me.  The first two are just extra header inclusions, the third is inserting spaces in some printf format specifiers to not cause errors compiling as C++11, and the fourth (this one took some trivial rebasing) is a hackaround for a linker issue; nothing interesting in any of them.  If I'm the one who ends up pushing this patch to esr10, I'll be pushing those cherrypicked revisions as well.  If I'm not, well, whoever pushes should be running the test added here and making sure it works, and they're on the hook for bustage in this patch.  :-)
We're going to maintain the wontfix for FF17 here given the fact that we're past code freeze and we're going to build with our final beta in a couple of hours. Marking for first landing in FF18 on all branches. Please wait for sec-approval before landing.
When we give sec-approval+, we will *not* want tests to go in yet.
Comment on attachment 678530 [details] [diff] [review]
Patch and test

sec-approval+ but please don't check it in (without a test too) until December 15.
Attachment #678530 - Flags: sec-approval? → sec-approval+
Keywords: testcase
(In reply to Al Billings [:abillings] from comment #15)
> Comment on attachment 678530 [details] [diff] [review]
> Patch and test
> 
> sec-approval+ but please don't check it in (without a test too) until
> December 15.

Al and I discussed - we're going to target this for December 10 to hit beta 4.
December 10 for me will be a workday, but one where I'll be flying on planes likely without net access, for most of it.  So odds are I won't be able to push anything that day -- day after should return to normal.

Anyway, guess it's time for branch approvals now.  With the uplift that happened recently, there are only two meaningful versions of the patch, one for nightly/aurora/beta/esr17 and one for esr10.  How long after the corresponding releases happen should I be waiting to land the tests?  I'm happy to wait, of course, I'd just like to not have to wait forever on it.
[Approval Request Comment]
Bug caused by (feature/regressing bug #): 1.1 ltabb 1998-03-27 18:33 Free the lizard
User impact if declined: Buffer overflows
Testing completed (on m-c, etc.): Test provided in original patch (not to be landed yet)
Risk to taking this patch (and alternatives if risky): Mostly that other, similar places were missed during a more general audit, and someone who sees this change will find something I missed.  The patch is simple enough that I'm pretty unworried about it itself being buggy.
String or UUID changes made by this patch: N/A

[Approval Request Comment]
If this is not a sec:{high,crit} bug, please state case for ESR consideration: sec-critical
User impact if declined: Buffer overflows
Fix Landed on Version: Not landed yet, trying to land everywhere
Risk to taking this patch (and alternatives if risky): See above.
String or UUID changes made by this patch: N/A
Attachment #680281 - Attachment is obsolete: true
Attachment #680294 - Attachment is obsolete: true
Attachment #680302 - Attachment is obsolete: true
Attachment #690137 - Flags: review+
Attachment #690137 - Flags: approval-mozilla-esr10?
Attachment #690137 - Flags: approval-mozilla-beta?
Attachment #690137 - Flags: approval-mozilla-aurora?
In the meantime since I first spun up an esr10 patch I've had reason to build gcc 4.6.  With gcc 4.6 in hand there seemed no reason not to test this with gcc 4.6; the patch works with it with no other changes, and I made sure it passed the separated-out testcase.  So I won't need to land anything else beyond this when I push this to esr10, a change from what I said in comment 12.

[Approval Request Comment]
If this is not a sec:{high,crit} bug, please state case for ESR consideration: sec-critical
User impact if declined: Buffer overflows
Fix Landed on Version: Nowhere yet -- trying to land everywhere at the same time to minimize reverse-engineering risk/time to do so
Risk to taking this patch (and alternatives if risky): See above.
String or UUID changes made by this patch: N/A
Attachment #690138 - Flags: approval-mozilla-esr10?
Syncing up flags to checkin-pending, if I understand https://wiki.mozilla.org/Release_Management/ESR_Landing_Process right...
Attachment #690137 - Flags: approval-mozilla-esr10? → approval-mozilla-esr17?
(In reply to Jeff Walden [:Waldo] (remove +bmo to email) from comment #17)
> December 10 for me will be a workday, but one where I'll be flying on planes
> likely without net access, for most of it.  So odds are I won't be able to
> push anything that day -- day after should return to normal.

Sounds good - please land tomorrow in that case. We'll be going to build with the beta at EOD.
Attachment #690137 - Flags: approval-mozilla-esr17?
Attachment #690137 - Flags: approval-mozilla-esr17+
Attachment #690137 - Flags: approval-mozilla-beta?
Attachment #690137 - Flags: approval-mozilla-beta+
Attachment #690137 - Flags: approval-mozilla-aurora?
Attachment #690137 - Flags: approval-mozilla-aurora+
Attachment #690138 - Flags: approval-mozilla-esr10? → approval-mozilla-esr10+
Backed out of esr10 for test failures. (Yes, I landed the esr10 patch :)...)
https://hg.mozilla.org/releases/mozilla-esr10/rev/9c034c148d8a
Okay, this is kind of rich:

Breakpoint 2, FindReplaceLength (cx=0xf1a870, res=0xf1e900, rdata=..., sizep=0x7fffffffb750) at /home/jwalden/moz/slots/js/src/jsstr.cpp:2031
2031	    CheckedInt<uint32_t> replen = repstr->length();
(gdb) p repstr
$1 = "$1"
(gdb) n
2032	    for (const jschar *dp = rdata.dollar, *ep = rdata.dollarEnd; dp;
(gdb) p replen
$2 = {mValue = 2, mIsValid = true}
(gdb) n
2036	        if (InterpretDollar(res, dp, ep, rdata, &sub, &skip)) {
(gdb) n
2037	            replen += sub.length - skip;
(gdb) n
2038	            dp += skip;
(gdb) p replen
$3 = {mValue = 0, mIsValid = false}
(gdb) p sub.length
$4 = 0
(gdb) p skip
$5 = 2
(gdb) p repstr->length()
$6 = 2
(gdb) p sub.length - skip
$7 = 18446744073709551614
(gdb) pt sub.length
type = unsigned long
(gdb) pt skip
type = unsigned long

So we're relying on this not to overflow one way...and relying on it to overflow in another.  (Specifically, |sub.length - skip| has unsigned overflow semantics and so turns into a super-huge number, and adding it to a CheckedInt causes that CheckedInt to become invalid.)  Not sure on first glance exactly what the right fix is for this -- maybe adding sub.length and subtracting skip in separate steps.  But that's just an eyeballed guess; I need to re-page this code in (again) to be sure.  I'll think about it and come up with something more carefully thought about later today, perhaps between legs of travel.
This extra delta should fix the issue I noticed in the first test failure I looked at.  I suspect this fixes all the failures, but I haven't checked.

diff --git a/js/src/jsstr.cpp b/js/src/jsstr.cpp
--- a/js/src/jsstr.cpp
+++ b/js/src/jsstr.cpp
@@ -2029,17 +2029,20 @@ FindReplaceLength(JSContext *cx, RegExpS
 
     JSString *repstr = rdata.repstr;
     CheckedInt<uint32_t> replen = repstr->length();
     for (const jschar *dp = rdata.dollar, *ep = rdata.dollarEnd; dp;
          dp = js_strchr_limit(dp, '$', ep)) {
         JSSubString sub;
         size_t skip;
         if (InterpretDollar(res, dp, ep, rdata, &sub, &skip)) {
-            replen += sub.length - skip;
+            if (sub.length > skip)
+                replen += sub.length - skip;
+            else
+                replen -= skip - sub.length;
             dp += skip;
         } else {
             dp++;
         }
     }
 
     if (!replen.isValid()) {
         js_ReportAllocationOverflow(cx);

I pushed this to try:

https://tbpl.mozilla.org/?tree=Try&rev=8bd76756edce

If it comes back good, I think you're probably good to push the existing patches, with this change, to all trees.  (I won't be able to because, well, time to line up for the second flight now.  :-) )  Apologies in advance if this fails somehow, and thanks in advance for dealing with this for me.  :-)
Try run looks good, lets get this re-landed.
https://hg.mozilla.org/integration/mozilla-inbound/rev/09f572ba2eea

I'm about to board a plane for home (thanks for the good time yesterday MV :)...), but I'll push this to the branches tonight assuming it sticks on inbound in the mean time.
Target Milestone: --- → mozilla20
https://hg.mozilla.org/mozilla-central/rev/09f572ba2eea
Status: ASSIGNED → RESOLVED
Closed: 11 years ago
Resolution: --- → FIXED
Hmm.  Did we not get this on branches?  :-\  I don't see it on beta, didn't look at any others.  (And I guess now we need this on esrb2g or whatever it's called, too.  Sigh.)
Sorry I didn't get to it last night. I'll get it today. Also, we'll be doing regular m-b -> b2g18 merges, so it won't need to land there separately.
Whiteboard: [adv-main18+][adv-esr17+][adv-esr10+]
Alias: CVE-2013-0750
Landed the test, it's been a good long while since this was fixed everywhere:

https://hg.mozilla.org/integration/mozilla-inbound/rev/6c636853b5a3
Group: core-security
You need to log in before you can comment on or make changes to this bug.