Storage quota side-channel attacks in the browserRequest and you will conquer

At the Black Hat USA 2016 conference, we presented “HEIST”. In a nutshell, HEIST is a set of techniques that exploit timing side-channels in the browser to determine the exact size of an authenticated cross-origin response. These side-channels allow an adversary to determine whether a response fitted into a single TCP window or whether it needed multiple. Combined with having content of the request reflected into the response, or by leveraging HTTP/2’s parallel requests, an attacker can determine the exact amount of bytes that were needed to send the response back to the client, all from within the browser. It so happens to be that knowing the exact size of a cross-origin resource is just what you need to launch a compression-based attack, which can be used to extract content (e.g. CSRF tokens) from any website using gzip compression. If you are interested in knowing all the details, I gladly invite you to have a look at the whitepaper, slides, or video of the talk.

The week after Black Hat, we went to the USENIX Security conference, to present our paper titled “Request and Conquer: Exposing Cross-Origin Resource Size”. As the title already gives away, in the paper we explore various methods that can be used to expose the size of cross-origin resources. An interesting technique that we discovered as part of our analysis, was to leverage the browser’s storage mechanisms, and more precisely the quota that is applied to it. In this post, I will discuss a small part of the techniques that we discovered (have a look at the paper if you want to know the full details). I will also discuss something that we discovered after the paper was published, namely how these techniques can be used to launch compression-based attacks (similar to HEIST, but even more stable).

Storage quota side-channel attacks

To provide web developers with fine-grained control over which resources are cached, the Cache API was brought to life. This interface can be used to add, retrieve and delete arbitrarily chosen resources into/from the cache. In a previous post I showed how this API can be used directly to estimate the size of a cross-origin response by leveraging it as a timing side-channel. Of course timing is not the only side-channel that can be abused. Whenever quota is applied to a certain resource, chances are that this introduces a side-channel information leak. The short video below illustrates how an attacker can abuse this side-channel to infer the size of an authenticated cross-origin resource, for the full details, please read on.

So how does all of this work? Let’s go step by step. First, the attacker completely fills the cache. This is probably the most arduous and (depending on the size of the victim’s hard disk) time-consuming task. However, if you take into account that other mechanisms such as localStorage or IndexedDB fall under the same per-site quota as the Cache API, you can easily leverage one of those APIs to fill up the cache. By playing around with IndexedDB, I found that I could fill the hard disk at 50-100MB/s, thereby reaching the quota in a few seconds. As soon as the quota is reached, any attempts to store new items will result in an error. At this point, the attacker will free up a specific amount of bytes (referred to as x in the video). These two steps are required because the attacker does not know in advance the size of the cache (in case it’s a percentage of a percentage of the global available disk space, it should be considered random by the attacker). By freeing up a certain number of bytes, the attacker knows exactly how many bytes it will take before the quota is reached again.

In the next step, the attacker will use the Fetch API to download the target resource, using the options {mode: "no-cors", credentials: "include"} to make sure the victim’s cookies are included. As soon as the resource has been downloaded and added to the cache, the adversary can start filling the cache again. However, this time the attacker will need to take note of the number of bytes he put in the cache before reaching the quota limit (referred to as y in the video). By computing x - y, the attacker discovers the exact size of the resource.

Quota Management APIs

Next to leveraging the per-site quota limit, there are some related attacks as well. A little-known API named Quota Management, which has only been adopted by Chrome, allows you to query the current storage usage. Considering that attackers can store authenticated cross-origin resources, and query storage usage as often as they like, it becomes ridiculously easy to find the size of a cross-origin resource:

function getEstimate(url) {
    return new Promise(function(resolve) {
        var resp;
        var oldSize;
        caches.delete('bogus-cache').then(function() {
            return fetch(url, {mode: "no-cors", credentials: "include"})
        }).then(function(response) {
            resp = response;
            return navigator.storageQuota.queryInfo('temporary');
        }).then(function(estimate) {
            oldSize = estimate.usage;
            return caches.open('bogus-cache');
        }).then(function(cache) {
            return cache.put(new Request('/bogusReq'), resp.clone());
        }).then(function() {
            return navigator.storageQuota.queryInfo('temporary');
        }).then(function(estimate) {
            resolve(estimate.usage - oldSize);
        });
    });
}

At the time of writing, the above code will only work in Chrome Canary (v54). To achieve the same in the current stable version of Chrome (v52), this API should be used instead: navigator.webkitTemporaryStorage.queryUsageAndQuota (it takes a callback function as argument). Note that this API has been there for ages, at least since Chrome v13.

Real-world attack scenarios

Knowing the exact size of authenticated cross-origin resources, allows an attacker to discover numerous things about a victim. In our paper, we provide a few example scenarios, but since virtually every website is designed to return user-specific content, there are countless other “possibilities”. The attack scenario I personally find most interesting, is the identification of a user on Twitter by leveraging publicly available resources. In this scenario, the attacker first creates a large database of Twitter users and the size of associated resources, e.g. /user/following, /user/followers, … When the victim visits the attacker’s page, the attacker obtains the size of the /following, /followers resources that are returned to the victim. Because the victim’s cookie is attached to these requests, they will be of the same size as /victim/following, /victim/followers, etc. Now the attacker only needs to match the entries in his database to the ones retrieved from the victim, allowing him to determine the victim’s identity.

To analyse the viability of this attack, we performed an experiment where we collected the size of 5 resources of 500,000 random Twitter users. We then grouped together users with the same vector of resource sizes. The group size can be considered the size of the anonymity set: if the size is 2, then the victim can be of any of these 2 users. The graph below shows the distribution of the amount of users per group size (note that the y-axis is logarithmic scale). The most interesting about this graph are those two dots in the top left corner. Knowing the size of just two resources, 81.69% of the 500k Twitter can be uniquely identified. For all 5 resources, this percentage rises to 99.96%. Of course, this only works if the public resources obtained by the attacker remain “fresh”. As soon as the victim gains a new Twitter follower, the response size will change. To counter this, the adversary can re-download the profiles whose resource lengths are close to that of the victim. Given enough effort, I’d say this is well in the range of a motivated attacker. Remember that this is just one of many attack scenarios, in our paper we describe various others, most of which require much less effort.

Compression-based attacks

If you haven’t been living under a rock for the last few years, you have probably heard of CRIME, BREACH, TIME, or HEIST. All these attacks aim to do the same thing: exploit resource compression to reveal secret content. In a nutshell (skipping many important details), it works as follows: the attacker injects secret=a in the request, which will be reflected in the response. If the secret starts with a, the compression algorithm can reference a longer string, and the resulting size will be 1 byte smaller compared to any other character. To launch such a compression-based attack, the first requirement is that a short attacker-controlled string ends up in the response (many web pages reflect the requested URL, so that’s not too difficult). The second requirement is that the attacker needs to know the exact resource size. Of course, only the size of the response after compression matters. Unfortunately, this prevents us from directly applying the size-exposing techniques based on the browser storage quota, as resources are stored without compression.

Of course, you wouldn’t be reading all of this, if there was no other technique that could be applied. Since we can’t learn any information from the response body, it might be interesting to consider the response headers as well. The only header I know of that is related to the response size, is the Content-Length header. What’s important to note, is that the value of the Content-Length header reflects the response size after compression. Of course, we still need a way to discover the value of this header. Interestingly, because the Cache API will store headers as well, we can again use the same quota side-channel attack here. Here we can leverage the fact the value of Content-Length is represented as a decimal value. As such, it takes 3 bytes to store 999, and 4 bytes to store 1000. So all an attacker needs to do, is to find the tipping point, i.e., an incorrect guess of the secret results in an additional byte to represent the Content-Length value. E.g. Content-Length for secret=a is 999, for secret=b it is 1000; so now we know that a is a correct guess. The attacker can reach this tipping point by reflecting more content in the response, or by picking a resource that is much closer to it. So there you have it, an attack that can extract secret content from resources purely in the browser, without needing to worry about how or when they are sent over the network.

Help, I’m doomed

We’ve reported these issues to both browser vendors and spec editors, and proposed a solution based on applying a virtual padding to responses. This degrades the performance of the attacks to that of timing attacks (an evil we will have to live with for the time being). This is because the only attack against random padding is to collect enough measurements and apply some statistical method. By making it difficult to collect many measurements, attackers are significantly hindered when launching this attack. Hopefully, these mitigations will land in browsers soon! For the time being, you might want to consider disabling third-party cookies in your browser, which not only mitigates the attacks mentioned in this post, but also timing and CSRF attacks.