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:
- Fill the hashtable bucket with data.
- Measure the time needed to look up the key in the hashtable.
Filling a specific hashtable bucket with data is easy because:
- int32 numbers are simply mapped with
ScrambleHashCode(number),
no unknown values are involved
- the inverse of
ScrambleHashCode() is just a modular multiplication with
the multiplicative inverse of the constant scrambling factor, so it is possible
to compute a series of int32 numbers that map to adjacent hash codes.
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:
- Locate the value in a
Set with 64 buckets (find_bucket64()) by testing with 64 different
Set instances that have different filled buckets and checking with which Set the operation is slow
- Repeatedly create new
Sets with doubled bucket counts (128, 256, 512, ...) and test
whether the access at the doubled old bucket index is slow. Basically, determine the 22-bit bucket index
bit by bit.
The main code attempts to find a single candidate for the address of the '\0' atom:
- Compute the bucket index of
'\0' with find_bucket_precise().
- Let candidates_set be the result of deriving 32-bit truncated pointer candidates
from the bucket index of
'\0' using the inverse of ScrambleHashCode().
- For characters
'\1', '\2', '\3', ...:
- Compute the character's bucket index with
find_bucket_precise().
- Derive 32-bit truncated pointer candidates from the character's bucket index.
- Let
current_0candidates be the result of subtracting character_code*0x18
from the candidates for the current character.
- Let
candidates_set be the values that are contained in both candidates_set
and current_0candidates.
- Assert that
candidates_set contains exactly one value.
- Return the value in
candidates_set.
(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:
- Objects can have private, random 32-bit members ("hash_code_symbol") specifying their hashmap buckets. The member is set when the object is used in a hashtable the first time.
- Strings are not interned for usage in hashtables; instead, when a string is used in a hashtable for the first time, a hash of its contents is computed and stored in the string by
String::ComputeAndSetHash().
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.