Stealing history with CSS binary trees
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.
“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!
…almost.
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.
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
- Mozilla: privacy-related changes coming to CSS :visited
- Who Am I
- I still know what you visited last summer
- Defend your spaceship!
- getComputedStyle benchmark
- Pixel perfect timing attacks with HTML5
- Fast and somewhat reliable cache timing
- History-sniffing in the news (2012)
Footnotes
-
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. ↩ -
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. ↩
-
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. ↩
-
Average human reaction time is just over 250ms, so we can safely budget 1s per frame-change. ↩
-
getComputedStyle
could process 200k-3.4M URLs/min. Our test is lucky to get 800 URLs/min. ↩ -
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. ↩
-
I created a quick demo here to inspect painting times in DevTools. ↩
-
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. ↩
-
…but just wait until you see the next one. ↩