Closed Bug 917841 (CVE-2013-5619) Opened 6 years ago Closed 6 years ago

binary searches use overflow-prone arithmetic

Categories

(Core :: JavaScript Engine, defect)

defect
Not set

Tracking

()

RESOLVED FIXED
mozilla27
Tracking Status
firefox24 --- wontfix
firefox25 --- wontfix
firefox26 + fixed
firefox27 + fixed
firefox-esr17 --- unaffected
firefox-esr24 --- wontfix
b2g18 --- unaffected
b2g-v1.1hd --- unaffected
b2g-v1.2 --- fixed

People

(Reporter: sunfish, Assigned: sunfish)

References

Details

(Keywords: regression, sec-moderate, Whiteboard: [qa-][adv-main26+])

Attachments

(3 files)

An informal search of SpiderMonkey for binary search algorithms turned up several places using (lo+hi)/2, which is prone to overflow in general [0]. Attached is a patch which changes them to use lo+(hi-lo)/2.

While most of them look like they'd be safe in practice -- if numICEntries() or script->nTypeSets approach anything close to SIZE_MAX/2, I assume the program would have far worse problems -- one of them, in js/src/frontend/TokenStream.cpp, is not obviously safe, since it uses uint32_t indices, and there's nothing obvious which would protect them.

This patch changes all of them, to be on the safe side.

[0] http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
Attachment #806669 - Flags: review?
Attachment #806669 - Flags: review? → review?(luke)
Comment on attachment 806669 [details] [diff] [review]
binary-search-overflow.patch

My goodness, how many duplicates of binary search do we have?!  I must confess I'm guilty of adding one of my own (LookupHeapAccess, not on this list, it does low+(high-low)/2).

After you land the fix, perhaps you'd like to file a bug to write a template algorithm to factor these out?
Attachment #806669 - Flags: review?(luke) → review+
Comment on attachment 806669 [details] [diff] [review]
binary-search-overflow.patch

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

I haven't tried, but it may just involve presenting a 2 GiB or so script to the JavaScript parser and then carefully leading it down a particular path, to get an out-of-bounds array access, from which an exploit could theoretically be crafted.

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

Binary-search overflow is a widely understood phenomenon, and it will be evident from the patch. But, there are no testcases showing specifically how to trigger it, much less exploit it.

Which older supported branches are affected by this flaw?

It's present in all branches at least back to mozilla-release.

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

The interesting case was introduced in 1f3587e02361 (bug 747831).

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

I don't at the moment, but it would be trivial to create them for any branch.

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

The patch is very unlikely to cause regressions.
Attachment #806669 - Flags: sec-approval?
(In reply to Luke Wagner [:luke] from comment #1)
> Comment on attachment 806669 [details] [diff] [review]
> binary-search-overflow.patch
> 
> My goodness, how many duplicates of binary search do we have?!  I must
> confess I'm guilty of adding one of my own (LookupHeapAccess, not on this
> list, it does low+(high-low)/2).
> 
> After you land the fix, perhaps you'd like to file a bug to write a template
> algorithm to factor these out?

Sure. I filed bug 917918 to record several other binary-search-like things found in various places.

I thought I had clicked the box to make bug 917918 a protected bug, but apparently I didn't, and I don't seem to have the ability to change it now. Can someone correct this?
Flags: needinfo?
We need to get a security rating on this issue before sec-approval.
Comment on attachment 806669 [details] [diff] [review]
binary-search-overflow.patch

sec-approval+
Attachment #806669 - Flags: sec-approval? → sec-approval+
Thanks, Dan!
Landed on on mozilla-inbound here:
https://hg.mozilla.org/integration/mozilla-inbound/rev/c231777cadca

Should I pursue landing this patch on other affected branches?
Ryan - if this landed on inbound a month ago shouldn't it be on central now? Can you help clarify where this might still need to land?
Flags: needinfo?(ryanvm)
Indeed, looks like the bug was never resolved when it landed on m-c.

https://hg.mozilla.org/mozilla-central/rev/c231777cadca
Flags: needinfo?(ryanvm)
Target Milestone: --- → mozilla27
Whiteboard: [qa-]
Can you please nominate this for uplift to the beta branch if it's a low risk landing?  If not, we can wait until the release of FF27.
Flags: needinfo?(sunfish)
Comment on attachment 808893 [details] [diff] [review]
the patch, ported to the beta branch

Assuming "nominate this for uplift to the beta branch" means "requeset approval-mozilla-beta". Please correct me if I'm wrong. The fix is very low-risk.

[Approval Request Comment]
Bug caused by (feature/regressing bug #): 

The interesting case was introduced in 1f3587e02361 (bug 747831).

User impact if declined: 

There is no known user impact. At this point, all we can say is that we don't know that user impact is impossible.

Testing completed (on m-c, etc.): 

It's been on mozilla-central for almost 2 months now.

Risk to taking this patch (and alternatives if risky): 

Very low. The patch is simple, and it's well tested.

String or IDL/UUID changes made by this patch:

None.
Attachment #808893 - Flags: approval-mozilla-beta?
Flags: needinfo?(sunfish)
Attachment #808893 - Flags: approval-mozilla-beta? → approval-mozilla-beta+
https://hg.mozilla.org/releases/mozilla-beta/rev/0095ca6ac388

Note that it was actually the Aurora patch that was landed given the cycle we were in when these patches were created.
Flags: sec-bounty?
This was never marked for ESR24. From what I can tell, it affects ESR24 as well.
Whiteboard: [qa-] → [qa-][adv-main26+]
Alias: CVE-2013-5619
Status: NEW → RESOLVED
Closed: 6 years ago
Flags: sec-bounty?
Resolution: --- → FIXED
Group: core-security
You need to log in before you can comment on or make changes to this bug.