Firefox: ALSR leak and cross-frame oracle via pointer scrambling in Map/Set

I reported this to Mozilla on 2016-10-21 in one bug report; they split it into two bugs and fixed them seperately: While this isn't a particularly severe issue, I think turning a DoS into an easily measurable timing sidechannel is a neat trick.
I reported these bugs privately (before working for my current employer), under a 90-day deadline, so I'm disclosing them on my personal website now.
The following is a slightly edited version of my original report.

download the PoCs

Pointer Leak

Steps to reproduce

In Nightly (non-debug build) on x86-64, open the file attack.html from the PoC tarball and wait around 15 seconds (depending on your CPU) until the displayed result is green or red.

Actual results

In the first PoC, something like this will be shown:

bucket access delay calibration: hit: 0.014999999999993463, miss: 0, limit: 0.0074999999999967315
current char code: 41
number of possible results: 1
result: 0x01f00028


The displayed result (0x01f00028) is the pointer to the atomized string corresponding to '\0', truncated to 32 bits. On Linux, the corresponding mapping is visible in /proc/{plugin-container-pid}/maps:

7f3001400000-7f3002000000 rw-p 00000000 00:00 0


The basic idea here is to perform a hash DoS attack, but with a goal other than Denial of Service. After a single hashtable bucket has been filled with lots of entries, insertions and negative lookups on the hashtable will be much slower for keys that map to the filled hashmap bucket. This means that a timing measurement can be used to determine whether a given key maps to a specific hashtable bucket as follows: Filling a specific hashtable bucket with data is easy because: The reason this can be used to break ASLR is that, for strings and objects, 32-bit truncated pointers are scrambled with ScrambleHashCode() and then used to derive hashmap bucket indexes. Therefore, by measuring lookup times for strings/objects in a hashmap with a known filled bucket, the range of possible pointers can be constrained.

Strings are converted to pointers by atomizing (interning) them, then taking the pointer to the atom. For some strings, atoms are precreated; in particular, atoms exist for single-character strings with charcodes 0-255. Because these are allocated in a loop during runtime initialization (StaticStrings::init()), they form a sequence in memory, so the distance between the atomized strings for String.fromCharCode(i) and String.fromCharCode(i+1) (for i in range(0,255)) is always 0x18.

The algorithm used in the PoC works roughly as follows (this is just the basic idea, the implementation in the exploit is optimized a bit):

find_bucket_precise() attempts to find the bucket index at which a given value will be placed in a Set of size 2^22. This is done as follows: The main code attempts to find a single candidate for the address of the '\0' atom:

(Tiny) Cross-Origin Infoleak

This is not just usable to break ASLR, as demonstrated by the second PoC. Because atoms are shared across frames and an atom can only move in memory if nobody is using it, the ability to determine bucket indexes can be used to determine whether another frame is using an atom with specific contents: If the atom's hash bucket changes over time, no frame is using the atom. I'm not entirely sure, but I think string literals are always atomized? So this can e.g. be used to leak information like usernames embedded in JavaScript code across websites. The PoC determines which one out of a set of possible names was selected in the other frame across origins.
This attack is less reliable than the first one.

Steps to reproduce

To reproduce this issue, unpack leak_interned.html, an attacker, and leak_interned_victim.html, a victim page. Open leak_interned.html in a fresh browser instance, click one of the three name buttons, click the "tell me what I clicked button", and then wait a couple seconds (I think you have to wait for a GC run to happen or so).

Expected results

Firefox should not leak addresses or information about strings in other frames to JavaScript code.

Remarks

In V8, these attacks won't work because: It might make sense to copy V8's behavior here.

This bug is subject to a 90 day disclosure deadline. If 90 days elapse without a broadly available patch, I will post it publicly.