UPDATE 2015-01-21: Since writing this post, Chrome and FF 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
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.
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
background-color:red. It was totally evil and awesome and ready to go!
Since I didn't know when the square was red I was always displaying a score, even on misfires. I'd broken the game.
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.
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.
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.
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.
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.
And if you made it this far, just play the damn game already!
- 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)
A noble effort, but it's difficult to plug all the holes.↩︎
True under the assumption that the dataset is sparsely populated with↩︎
:visitedlinks. If there is a high percentage of
:visitedlinks 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.↩︎
getComputedStylecould 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.↩︎