Leaking information with timing attacks on hashtables, part 1
Timing attacks  are an important subclass of side channel attacks used to reveal cryptographic secrets, basing only on time needed by targeted devices or applications to perform specific computations.
It turns out these attacks can be applied in a more prosaic context — instead of encryption keys, they can help us leak pointers to objects on the heap or, if we are lucky, in .code/.data sections of targeted application. Leaking a pointer with fixed RVA reveals the imagebase, so ASLR becomes ineffective (ROP). Leaking a heap pointer makes expoitation of WRITE-ANYWHERE bugs easier, so in both cases it’s a win :).
This post provides a high-level description of a POC implementation of a timing attack on hashtable used in Firefox (tested on v4, v13, v14). POC is quite fast (takes few secs) and leaks a heap pointer to a JS object. A detailed explanation will be provided in a different post (part 2).
Consider a hash table using double hashing . In this scheme, keys are hashed like so: mod , where , are hash functions and is the size of hash table. During insertion, is incremented until a free slot is found, like shown below:
Lookups are performed the same way — is incremented until key value in a slot matches, or the slot is empty.
It’s easy to see that the execution time of is proportional to the length of ‘s chain (number of collisions). In the above example , since there were two collisions. The idea is to use this fact to learn the value of key being looked up. Firefox is nice enough to store pointers and user supplied integers in the same hashtable (not always, but in specific circumstances), so we can control the table’s layout completely. It worth noting that only the object’s pointer is used in hashing, so (contents of strings are not taken into account).
Here’s how we are going to layout keys inside the table (using JS integers):
Yellow slots are taken, white are free. We have to leave some free space, since FF grows / shrinks tables dynamically, basing on the number of taken slots.
If we keep generating JS objects (with different pointers) and trying to look them up in , we will finally find one that takes considerably longer than others to lookup. Let’s call this object (M – max., str – string, since we are using strings (atoms, to be more precise) in POC) and the lookup time of : .
Here’s an example of a long chain for (Firefox uses subtraction instead of addition while hashing):
In this example .
In order to find , we will use the observation that divides for any (this isn’t always true, but I’ll omit the second case for brevity). Indeed, = = . If we collect enough of chain’s elements, we can calculate their differences and take . This equality holds with high probability — chance of failure decreases exponentially with the number of collected elements (the most significant term of the exact formula is ).
How to find elements on ‘s chain? Remember that keys used to fill are integers. We can remove a key and check if changed significantly. If it did, we know for shure that the removed key belongs to the chain.
Here’s an example:
We removed and this caused , so the lookup time after removal () is going to be lower than . In order to deal with inaccuracies of the JS clock (Date object), we will accept only elements for which , so we are reducing our interest to the first half of the chain (red line on the diagram above). Without this restriction we would be unable to distinguish between keys that don’t belong to the chain and keys at the very end of it.
Obviously, removing keys one by one is too slow. Removing them in chunks in a bisect-like manner is better, but still has the running time proportional to . It’s faster to use a randomized algorithm. Let’s say we chose random elements to remove. Probability that we failed to hit any element of ‘s chain is . The exponent is working in our favor, but we need to estimate somehow, so that we don’t waste too much time — is as good as , but the second requires greater , so more elements to test.
We can estimate by collecting integers with increasingly long chains, and using their lookup times to create a linear regression model . Model will provide a linear function that interpolates collected data. Estimating is then a matter of evaluating . Below is an example of collected data points and a linear function that fits them best. Y axis is time and X is the chain’s length.
Having we can pick so that for any . After we finally pick , we chose random keys and remove them. If dropped below , it means that in the set we chose, there’s at least one key that belongs to the first part of the chain — we need to find it. In order to do so, we bisect the set of removed keys until only one is left. Running time: , if we disregard time necessary to add / remove keys from .
After collecting enough (8 in POC) elements of chain, we compute . The only thing left is to find — the starting point.
Recall ‘s layout:
Consider how changes, when removing two keys: and — we remove them separately and then measure .
- if we remove 5 or 7, will not change, since 5, 7 do not belong to ‘s chain,
– removing 4 or 6 will cause , since 4 and 6 are in the first half of chain,
– removing 8 will cause and removing 10 will have no effect on .
These 3 conditions are sufficient to recognize if we are inside, outside, or and the edge of chain.
Algorithm to detect the starting point is simple. Start from element for which is smallest (so it’s the closest element to starting point). With we found earlier, do a binary search using the criteria above (inside, outside, hit) until hitting the edge (starting point).
With and it’s possible to recover , which equals to .
This is a simplified description. There’s quite a lot of details that were omitted in this post for brevity, but are required for this trick to work.
I suspect (this type of) timing attacks will be useful for leaking information not only from browsers. The most likely candidates seem to be kernels and perhaps even remote servers. (EDIT: I mean this in ASLR context, not secret-password context).
Here’s the POC. Download all files and open lol.html (in Firefox ;)) to see how it works. POC was tested on xp, w7 and linux. Send me an email if it doesn’t work for you.