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
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.
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
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
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:
- Fill the hashtable bucket with data.
- Measure the time needed to look up the key in the hashtable.
The reason this can be used to break ASLR is that, for strings and objects, 32-bit truncated pointers are scrambled with
- int32 numbers are simply mapped with
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.
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+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
- 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.
- Compute the bucket index of
- Let candidates_set be the result of deriving 32-bit truncated pointer candidates
from the bucket index of
'\0' using the inverse of
- For characters
- Compute the character's bucket index with
- Derive 32-bit truncated pointer candidates from the character's bucket index.
current_0candidates be the result of subtracting
from the candidates for the current character.
candidates_set be the values that are contained in both
- Assert that
candidates_set contains exactly one value.
- Return the value in
(Tiny) Cross-Origin Infoleak
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).
In V8, these attacks won't work because:
It might make sense to copy V8's behavior here.
- 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
This bug is subject to a 90 day disclosure deadline. If 90 days elapse without a broadly available patch, I will post it publicly.