Stealing history with CSS binary trees

Update 2015-01-21

Since writing this post, Chrome and Firefox have changed their alpha-blending functions. Demos likely won’t work anymore. This is good news!

History-sniffing attacks let front-end code peek at other sites you’ve visited. They can be used to target ads, steal information, or discern your identity. Creepy.

Historically, one of the most popular history-sniffing techniques was to style :visited links using CSS and check their color with JavaScript. Major browsers started implementing privacy changes to address this attack in 2010.1 As a result, JavaScript’s getComputedStyle now returns unvisited styles for visited sites.

Even with these limitations there are a number of ways to scrape a user’s history. The remainder of this article describes a combination of tricks used to do so. The outcome is a proof-of-concept history-sniffing game.

Trick #1: Clicking colors

Though getComputedStyle is a dead-end, sniffers can trick users into telling a script which links they’ve visited. This demo is the clearest implementation that I’ve seen; the site shows a grid of styled links and asks you to click the red ones.

I saw the demo above while working on an unrelated game. The game asked players to hit the spacebar when a box turned red.

Interface for a simple reaction game

“Hey”, I thought to myself, “this game could be so much more sneaky!”

I swapped the box out for a stack of links and styled :visited to background-color:red. It was totally evil and awesome and ready to go!

Score displaying with red background

…almost.

Score displaying with white background

Since I didn’t know when the square was red I was always displaying a score, even on misfires. I’d broken the game.

Trick #2: Like a polar bear in a snowstorm

Another popular history-sniffing trick is to hide non-:visited links by making them appear the same color as the background. This paper shows some clever examples, as does this game. By simply flipping this technique we can hide score text over the white non-:visited links. For extra fanciness, we add a red text layer to indicate failure.

Text blending in with same-colored backgrounds
White and red text are appropriately hidden on their respective backgrounds

With just the first two tricks we have a functioning game. Probing one link at a time covers ~60 links per minute and provides solid user insight. Tricks #3 and #4 improve our search algorithm,2 increasing read-speed by ~10x.

Trick #3: CSS decoders

This paper builds an n-input OR gate in CSS using alpha-blending rounding errors. I’ve embedded my own cross-browser version below; click Result to see it in action:

An OR gate is on if any of its inputs are on. We can use this to probe n links3 at once by stacking them together. Now if a user sees red and hits the spacebar we know that one of the links in the group has been visited.

Trick #4: Slow recursion

This trick figures out which of a group’s links have been visited. We can divide each group into a binary tree for searching but can’t rely on simple conditional search algorithms4 since we’re rate-limited by the user’s reaction time.5 This means that we must maintain state in our own stack.

If you’re curious about specifics, the whole project is on GitHub. Since the code’s cluttered with game logic I’ve written a stripped-down version of Trick #4.

Trick #5: Automation

Despite the gains achieved in Tricks #3 and #4, relying on user input will never be as fast as the old getComputedStyle method.6 Since we can no-longer automate color tests, is it possible to avoid looking at color altogether?7 Testing 16 links requires alpha-blending 4,096 elements at each step.8 This is a non-trivial operation; can we infer what the browser is drawing by testing render and redraw times?

This is a timing attack and I’m not the first to apply it to this context. Pixel Perfect Timing Attacks with HTML5 is a fantastic white paper by Context Information Security on the subject. They were able to successfully implement timing attacks using CSS’s text-shadow property and SVG filters.9 So, there’s the answer. Now go read that paper.

Conclusion

I won’t be taking over the world with this project10 but it demonstrates some interesting vectors. More security patches will be released, more creative hacks will arise; all it takes is a toehold and some creativity. Powerful new features make room for novel vulnerabilities. And so it goes.

Regarding browsing history, reaction games probably aren’t your biggest concern anyway. I’ll just leave these here.

And if you made it this far, just play the damn game already!

References

Footnotes

  1. A noble effort, but it’s difficult to plug all the holes.

  2. True under the assumption that the dataset is sparsely populated with :visited links. If there is a high percentage of :visited links in the set you’re actually better off with the linear algorithm. Good news: counting on a sparse dataset is a very safe bet.

  3. I settled on n = 16 unique links per stack. Adding more links gives a performance hit, as it’s not easy for the browser to composite that many layers (each unique link requires 256 elements). 16 seems to be a sweet-spot.

  4. We can win the same O(logn) complexity with a small optimization: if spacebar is hit on level n and then not on the left branch of level n + 1, we can immediately skip to level n + 2 since we know that our result is on the right side. This works because we only need to check for existence.

  5. Average human reaction time is just over 250ms, so we can safely budget 1s per frame-change.

  6. getComputedStyle could process 200k-3.4M URLs/min. Our test is lucky to get 800 URLs/min.

  7. Some history-sniffing attacks focus on entirely different vectors; a common example is to request external resources and time the response, probabilistically determining whether the result was cached. All current approaches that I’ve found (including the ones discussed above) are timing attacks.

  8. I created a quick demo here to inspect painting times in DevTools.

  9. The coolest part of this paper is the second half; they implement OCR for cross-origin iframes using SVG filters. If you enjoyed my article at all (I assume you did since you made it this far) I highly recommend giving Pixel perfect timing attacks with HTML5 a read. It’s at least 2 orders of magnitude cooler than my article.

  10. …but just wait until you see the next one.