History theft with CSS Boolean algebra

Up until mid-2010, any rogue website could get a good sense of your browsing habits by specifying a distinctive :visited pseudo-class, rendering thousands of interesting URLs off-screen, and then calling the getComputedStyle API to figure out which pages appear in your browser's history.

After some deliberation, browser vendors have closed this loophole by disallowing almost all attributes in :visited selectors, spare for the ability to alter text, foreground, and background colors for such links. The APIs have been also redesigned to prevent the disclosure of this color information via getComputedStyle.

This workaround did not fully eliminate the ability to probe your browsing history, but limited it to scenarios where the user can be tricked into unwittingly feeding the style information back to the website, disclosing information about one URL at a time. Several fairly convincing attack vectors have been demonstrated - my own entry can be found here - but they generally require roughly one click per every visited URL. In other words, the whole thing doesn't scale particularly well.

The practicality of such CSS-based history snooping attacks could be improved greatly if we had a way to design an n-to-2n decoder circuit with the styling elements available on visited links. For a rudimentary explanation of why this matters, let's assume that we want to examine the :visited state of two links in a single try. Further, let's assume that we can divide the screen into four non-overlapping regions, and write CSS that satisfies this criteria:

In this example, the four possible states of the system will unambiguously map to just one illuminated rectangle on the screen. If we can convince the user to click on the lit rectangle - e.g., seemingly to close a pop-up - the location of the click will immediately reveal the information about the state of both of the tested links.

Of course, the scheme becomes more practical when the number of links tested at once is much greater. There are some constraints on what you could pull off, but in a very conservative estimate, by using a grid of 32-by-32 elements, we can probe the state of log2(32 * 32) = 10 links with a single casual click. On your screen, one such element would be about this big - probably comparable to a typical "close" button in a pop-up ad:

The open question is whether it's possible to implement Boolean logic with CSS when we are limited to expressing the state of the link through the colors of the element. The most obvious approach would be to use stacked rectangles in conjunction with background-color: transparent. For example, logical disjunction could be implemented as:

The resulting state table would be:

link_alink_brectangle #1rectangle #2rectangle #3resulting color
00blacktransparenttransparentblack
01blacktransparentwhitewhite
10blackwhitetransparentwhite
11blackwhitewhitewhite

There is only one minor snag: as it turns out, background-color: transparent does not work in conjunction with :visited. Oops, back to the drawing board!

The other possible candidate for a building block in CSS Boolean algebra is the opacity attribute, which allows the color of an element to be blended with whatever happens to be underneath. Unfortunately, the standard mixing mode relies on linear averaging. This makes it seemingly impossible to develop logical conjunction, disjunction, or anything else equivalent. To illustrate the problem, let's say that we're using two stacked rectangles:

This will produce behavior along these lines:

link_alink_bresulting color
00black
0150% gray
1050% gray
11white

That's not a very useful building block for our needs: the 50% outputs are probably not suitable for display, and will also mess up any subsequent Boolean logic we'd want to interface this output to.

Luckily, we can exploit the non-linear "small-signal" behavior that is caused by quantization errors whenever the results of opacity calculations are converted to RGB. The opacity operator works kind of like this:

new_color = orig_color * (1 - opacity) + overlaid_color * opacity

After every operation, the result is quantized to an 8bpp representation suitable for rendering on the screen; in WebKit-based browsers, this conversion involves rounding the value down, while in Internet Explorer and Firefox, the operation rounds to the nearest integer.

To better understand how to leverage this behavior, let's assume that we're dealing with a hypothetical computer where each pixel can have just 10 shades of gray, represented by values ranging from 0 to 9. Further, let's assume that we have two stacked rectangles:

Let's assume that our browser follows the WebKit behavior and always rounds the result of opacity calculations down. If so, and if link A is not visited, the resulting pixels will be always black regardless of the state of link B:

The situation is more interesting if link A is visited; in this case, the outcome will depend on the color of the overlay:

This is interesting because we have managed to break the symmetry of blending and ended up with non-linear behavior. Nevertheless, the result still isn't particularly useful:

link_alink_bresulting color
00black (0)
01black (0)
10light gray (8)
11white (9)

But what would happen if we overlaid link B once more over the result of this computation? Well, if the original output happened to be black or white, the operation would be essentially a repeat of the calculations outlined above, and the color wouldn't change. But if the result was light gray - and the state table tells us that this can happen only if link B is not visited - we would see an interesting progression of quantization errors with each successive overlay:

Hmm, cool... by stacking the overlay, we can bring down the gray color to black, while not affecting any of the other outputs. Our state table is now:

link_alink_bresulting color
00black
01black
10black
11white

Looks awfully like logical conjunction, right?

(In browsers that round to the nearest integer, we would need to use a slightly different approach, but the principle remains the same.)

Well, but does it really work? If you're using a WebKit-based browser, this table - actually rendered using this kind of CSS trickery - should look pretty good:

Update (2015): This proof-of-concept code may no longer work in WebKit-based browsers due to changes to color quantization. I had no time to investigate if the original approach can be still used to pull the attack off.

link_alink_bCSS output
00
01
10
11

Again, in MSIE and Firefox, you will see useless three-state output due to different rounding logic. But for those using non-WebKit browsers, here's a slightly modified version that will do the trick for you:

link_alink_bCSS output
00
01
10
11

Now, for a practical test (this one is just for WebKit-based browsers) - click on the white rectangle below:

Of course, in a real attack, the colors would be chosen so that all but the correct square blend into the background. Extrapolating to a higher number of screen regions and providing some compelling justification for clicking one is left as an exercise for reader :-)

That's it. In a sense, the entire exercise is pointless for at least two reasons:

Update (2015): mix-blend-mode is now available in mainstream browsers and allows this attack to be pulled off more easily. See this for a quick demo.

Nevertheless, this was fun... for some values of fun. Eduardo also pointed out that another interesting application could be the theft of pixels from cross-domain frames: for example, it may be that doing threshold comparisons of ten specific pixels from a person's Facebook profile image is enough to uniquely identify almost anyone.

If you have any other suggestions or thoughts, or can think of better approaches, ping me at lcamtuf@coredump.cx.