Last Comment Bug 711043 - (CVE-2013-1693) SVG Filter Timing Attack
(CVE-2013-1693)
: SVG Filter Timing Attack
Status: RESOLVED FIXED
[sg:high][adv-main22+][adv-esr1707+]
: csectype-disclosure, sec-high
Product: Core
Classification: Components
Component: SVG (show other bugs)
: Trunk
: All All
: -- normal (vote)
: mozilla24
Assigned To: Cameron McCormack (:heycam)
:
Mentors:
Depends on: 812890 layers-refactoring
Blocks: 726246
  Show dependency treegraph
 
Reported: 2011-12-15 06:35 PST by Paul Stone
Modified: 2015-07-04 04:33 PDT (History)
33 users (show)
rforbes: sec‑bounty+
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---
-
wontfix
-
wontfix
wontfix
+
wontfix
+
wontfix
wontfix
+
verified
+
fixed
+
fixed
wontfix
22+
fixed
22+
fixed
wontfix
affected
fixed


Attachments
random noise image (65.89 KB, image/png)
2011-12-15 06:37 PST, Paul Stone
no flags Details
PoC (3.47 KB, text/html)
2011-12-15 06:38 PST, Paul Stone
no flags Details
remove feMorphology min/max calculation optimisation (3.91 KB, patch)
2012-03-18 20:14 PDT, Cameron McCormack (:heycam)
roc: review+
Details | Diff | Splinter Review
minimise differences in filter computations between valid and invalid input image values (6.83 KB, patch)
2012-03-18 22:03 PDT, Cameron McCormack (:heycam)
roc: review+
Details | Diff | Splinter Review
Screenshot of PoC after patch (42.19 KB, image/png)
2012-03-22 07:55 PDT, Paul Stone
no flags Details
Screenshot of PoC in try build, erode radius 10 (43.58 KB, image/png)
2012-03-23 02:43 PDT, Paul Stone
no flags Details
Slightly updated PoC - coloured links and more URLs (3.83 KB, text/html)
2012-03-28 06:09 PDT, Paul Stone
no flags Details
Screenshot of PoC on latest try build (70.72 KB, image/png)
2012-03-28 06:18 PDT, Paul Stone
no flags Details
don't branch when computing pixel value extrema (1.04 KB, patch)
2013-05-07 21:19 PDT, Cameron McCormack (:heycam)
roc: review+
Details | Diff | Splinter Review
don't branch when computing pixel value extrema (v2) (5.63 KB, patch)
2013-05-18 19:40 PDT, Cameron McCormack (:heycam)
no flags Details | Diff | Splinter Review
don't branch when computing pixel value extrema (v2.1) (5.63 KB, patch)
2013-05-18 23:35 PDT, Cameron McCormack (:heycam)
roc: review+
bajaj.bhavana: approval‑mozilla‑aurora+
bajaj.bhavana: approval‑mozilla‑beta+
abillings: sec‑approval+
Details | Diff | Splinter Review
screenshot (432.62 KB, image/png)
2013-06-13 07:16 PDT, Mihaela Velimiroviciu (:mihaelav)
no flags Details
patch rebased for mozilla-esr17 (5.81 KB, patch)
2013-06-17 15:35 PDT, Cameron McCormack (:heycam)
bajaj.bhavana: approval‑mozilla‑esr17+
Details | Diff | Splinter Review
patch rebased for mozilla-b2g18 (5.94 KB, patch)
2013-06-17 15:37 PDT, Cameron McCormack (:heycam)
bajaj.bhavana: approval‑mozilla‑b2g18+
Details | Diff | Splinter Review
Firefox 17.0.7esr (422.83 KB, image/png)
2013-06-19 07:59 PDT, Mihaela Velimiroviciu (:mihaelav)
no flags Details

Description Paul Stone 2011-12-15 06:35:45 PST
The SVG filter code has various optimisations which mean that different inputs images will take varying amounts of time for the same filter. It's possible to time this difference to read pixel values.

The feMorphology filter in particular has an optimisation that means that it will process an image of uniform colour (e.g. all black) much quicker than one containing varying pixel values. 

The PoC I've attached is very simple and just tries to tell if some links are :visited. Of course it could be extended to read pixel values from iframes to try and read text cross-domain. 

On my PC (WinXP, Intel Core 2 Duo E8400) with the default settings of the PoC, the difference between a positive and negative result is about 70ms. If it doesn't work for you, try altering the filterRes or radius variables in steps of 10.
Comment 1 Paul Stone 2011-12-15 06:37:02 PST
Created attachment 581947 [details]
random noise image
Comment 2 Paul Stone 2011-12-15 06:38:24 PST
Created attachment 581948 [details]
PoC
Comment 3 Paul Stone 2011-12-15 09:05:35 PST
Some notes about the practicality of applying this to iframe-attacks:

- There's lots of optimisations left that could speed up the attack and increase the reliability of the timings. I've only explored a few of the dials that could be tweaked.
- To read text from an iframe, you don't need to read all the pixels, just enough to identify a particular letter (assuming you know something about the font family and size)
Comment 4 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2011-12-15 13:55:59 PST
The question is, what can we do about this. We can disable that particular feMorphology optimization. Is that helpful or do we just get into a wack-a-mole game we can't win?

Paul, do you have any idea how many other openings there are for this kind of attack?
Comment 5 Paul Stone 2011-12-16 01:39:54 PST
After looking at the source code, feMorphology seemed like the biggest win (best case w*h*1*ry, worst case w*h*rx*ry) and that's the only filter I've tried so far.

Some other filters have conditional processing that depends on the source image. For example feDisplacementMap checks that a displaced pixel is within the bounds of the image, and the specular/diffuse lighting calculations check if a pixel is lit before calculating its value. Those would probably give smaller timing differences, however by stacking filters you could amplify the effect.

Beyond the source code, there's also things like compiler optimisations and the CPU cache that could affect timings in non-obvious ways. For example, while creating the PoC I was getting timing differences of about 10ms (stable enough to use, but I wasn't sure it would work for other people). However by increasing the filterRes value by only a small amount, I suddenly got a difference closer to 100ms. 

So while I've only got one example at the moment, I would bet that there's a lot more to find. 

(Also, how well did the PoC work for other people? It seems to work great on my WinXP work PC and my home Linux PC)
Comment 6 Daniel Veditz [:dveditz] 2012-01-11 17:55:19 PST
I'm assuming we can't take the WebGL approach and make people use CORS in order to use cross-origin images in SVG Filters?
Comment 8 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2012-01-11 18:17:27 PST
(In reply to Daniel Veditz from comment #6)
> I'm assuming we can't take the WebGL approach and make people use CORS in
> order to use cross-origin images in SVG Filters?

No, because SVG filters can be applied to any kind of page content.
Comment 9 Daniel Veditz [:dveditz] 2012-01-20 11:47:49 PST
(In reply to Paul Stone from comment #5)
> (Also, how well did the PoC work for other people? It seems to work great on
> my WinXP work PC and my home Linux PC)

Forgot to answer that: PoC worked fine on my Mac laptop.
Comment 10 Alex Keybl [:akeybl] 2012-03-05 16:00:14 PST
This bug has been tracked for a number of releases - can we find an assignee for this bug or make the case for untracking?
Comment 11 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2012-03-18 17:53:22 PDT
Not sure who to assign this to, partly because it's not clear what we should do to fix it.

Cameron, you might want to try just taking out optimizations in feMorphology and elsewhere that look usable this way. We should see how far that gets us.
Comment 12 Cameron McCormack (:heycam) 2012-03-18 18:18:57 PDT
I'll do that and see if any other source image value based optimisations stand out.
Comment 13 Cameron McCormack (:heycam) 2012-03-18 20:06:50 PDT
Removing the conditional from nsSVGFEMorphologyElement::Filter seems to work, at the expense of the filter being significantly slower on certain kinds of input (with lots of flat areas, like you might imagine could be the input if the input is some SVG content).  Patch coming up.

Another small conditional based on the input image is http://hg.mozilla.org/mozilla-central/file/58a2cd0203ee/content/svg/content/src/nsSVGFilters.cpp#l5122.

Should I try and write up a PoC for the lighting and displacement cases?  (I can probably get rid of the conditional in those cases and have them perform the same operations reasonably easily.)
Comment 14 Cameron McCormack (:heycam) 2012-03-18 20:14:53 PDT
Created attachment 607049 [details] [diff] [review]
remove feMorphology min/max calculation optimisation

Note I also changed the <= and >= in the innermost loop to < and >.
Comment 15 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2012-03-18 20:49:01 PDT
(In reply to Cameron McCormack (:heycam) from comment #13)
> Should I try and write up a PoC for the lighting and displacement cases?  (I
> can probably get rid of the conditional in those cases and have them perform
> the same operations reasonably easily.)

Let's just get rid of the special cases now. Writing up POCs isn't that helpful because maybe if you can't, someone else still could.

Thanks!
Comment 16 Cameron McCormack (:heycam) 2012-03-18 22:03:51 PDT
Created attachment 607067 [details] [diff] [review]
minimise differences in filter computations between valid and invalid input image values

This reduces the differences between the branches for the lighting and displacement filters, but doesn't eliminate them entirely.  At least we will invoke pow() and do the multiplications in all cases now.
Comment 17 Cameron McCormack (:heycam) 2012-03-19 18:51:14 PDT
https://hg.mozilla.org/integration/mozilla-inbound/rev/47e84e1cc50f
Comment 18 Cameron McCormack (:heycam) 2012-03-19 18:52:09 PDT
Which branches should I be requesting approval for here?
Comment 20 Cameron McCormack (:heycam) 2012-03-19 22:30:11 PDT
+  static PRUint8 dummyData[1] = { 0 };

Should've been a length 4 array.  Will land with this fix after a try run.
Comment 21 Cameron McCormack (:heycam) 2012-03-20 04:22:23 PDT
Also the switch between using the "dummy" data and the real source image data in feDisplacementMap was the wrong way around.

https://hg.mozilla.org/integration/mozilla-inbound/rev/f56c30e4aa17
Comment 22 Robert Kaiser 2012-03-21 04:00:20 PDT
mounir merged this to m-c:
http://hg.mozilla.org/mozilla-central/rev/f56c30e4aa17

I see two patches here, is this bug FIXED with that merge?
Comment 23 Cameron McCormack (:heycam) 2012-03-21 04:06:13 PDT
I rolled them both into that one commit.  But we should wait to see if people have opinions on whether it should land on other branches.  Somebody with more experience than me in judging the severity of bugs like this should chime in.  The feMorphology fix closes the specific timing attack from the reporter, but I feel like it would be a fair bit harder to use the small timing differences that the second patch reduces.
Comment 24 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2012-03-21 16:11:49 PDT
Paul, it would be great to have a bash on the nightly builds to see if you think this bug is fixed.
Comment 25 Paul Stone 2012-03-22 07:55:28 PDT
Created attachment 608332 [details]
Screenshot of PoC after patch

I tested this in the 2012-03-22 nightly and the PoC still works for me, unmodified. The performance of the filter is now incredibly bad - it takes almost 3 seconds to apply to a 150x150px square, up from tens of milliseconds on the previous nightly. This seems really slow, even considering the optimisation has been taken out. The browser becomes pretty much unusuable while the page is being displayed because of this.

The difference between the visited/not visited times is now about 500ms (see screenshot). I've not really had time to look into what's going on here - could it be compiler optimisations or the CPU cache or something?
Comment 26 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2012-03-22 10:05:10 PDT
:-( I don't know. Cameron, can you look into it?
Comment 27 Cameron McCormack (:heycam) 2012-03-22 15:24:17 PDT
Yeah I'll have another look.
Comment 28 Cameron McCormack (:heycam) 2012-03-22 22:46:08 PDT
Refreshing a couple of times with the current patch, yeah the PoC still works.  Not sure why I missed it the other day.

I pushed another change to try -- inspecting the object code in my local build (with clang on OS X) there is one instruction difference between the two branches of the test in the inner loop, which I've changed to:

 +              if (extrema[i] > pixel) {
 +                extrema[i] = pixel;
 +              } else {
 +                extrema[i] = extrema[i];
 +              }

Surprisingly, my compiler doesn't optimise the else branch out (which might be an indication this is a fragile fix).

I pushed a build to try, diff here:

  https://hg.mozilla.org/try/rev/c1878236b654

Windows build here:

  https://ftp.mozilla.org/pub/mozilla.org/firefox/try-builds/cmccormack@mozilla.com-561475405e80/try-win32/

Could you try this one Paul?
Comment 29 Paul Stone 2012-03-23 02:43:39 PDT
Created attachment 608637 [details]
Screenshot of PoC in try build, erode radius 10

This time an erode radius of 46 gave timings of around 2380ms, and the PoC couldn't differentiate between visited/not visited. Changing the radius to 10 gave a fairly consistent 185ms for visited and 180ms for not visited  (worked 4 times out of 5).

I guess the try server uses optimisations that you don't get in a debug build.
Comment 30 Cameron McCormack (:heycam) 2012-03-23 16:35:58 PDT
OK, thanks.  I'm not convinced then we'll reliably eradicate the timing difference without hand writing assembly.

Can we instead prevent filters from applying when there are differences in :visited style in the target element or its children?  Or make :visited styles not apply to elements that are being filtered?
Comment 31 Paul Stone 2012-03-24 00:50:49 PDT
You'd need to prevent filters on iframes, file inputs and probably some other elements too. The CSS filter spec suggests this - https://dvcs.w3.org/hg/FXTF/raw-file/tip/filters/index.html
Comment 32 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2012-03-25 17:09:21 PDT
That approach gets really complicated, will be a nightmare for authors, and will be difficult to fully secure. I don't want to go down it. Maybe we'll have to...

If you write code that uses arithmetic instead of if/else, does that help? How about
extrema[i] = NS_MIN(pixel, extrema[i])?
Comment 33 Paul Stone 2012-03-26 01:30:09 PDT
The NS_MIN macro is basically just an if/else statement, so wouldn't that be equivalent to the code snippet in comment 28?
Comment 34 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2012-03-26 01:49:07 PDT
Possibly.
Comment 35 Cameron McCormack (:heycam) 2012-03-26 02:51:30 PDT
The other day I tried using the ?: operator to assign the extrema variables and found that my compiler locally still produced code that could be timed.  I'll try with a multiplication by 0 or 1 tomorrow and see what the try server compilers come up with.
Comment 37 Paul Stone 2012-03-28 06:09:15 PDT
Created attachment 610101 [details]
Slightly updated PoC - coloured links and more URLs

A slightly updated PoC. The filters and timing code are the same, I've just added some more links and actually made them <a> elements to make it easier to see if it's worked correctly.
Comment 38 Paul Stone 2012-03-28 06:18:31 PDT
Created attachment 610109 [details]
Screenshot of PoC on latest try build

The timing difference is slightly smaller (between about 3-5ms), but it's still there. I was able to reliably reproduce it with an erode radius as small as 10.
Comment 39 Robert Longson 2012-11-21 13:41:53 PST
This may have caused this issue: https://longsonr.wordpress.com/2012/11/18/new-svg-filter-pseudo-inputs-for-firefox-17/#comment-271
Comment 40 Jonathan Kew (:jfkthame) 2012-11-27 15:07:00 PST
The de-optimization here seems to have contributed pretty significantly to the poor reftest-analyzer performance noted in bug 815617. Combining this with the increased number of device pixels involved on a hidpi screen makes for a painful user experience with that tool. :(
Comment 41 Paul Stone 2012-12-09 02:22:02 PST
Given that the de-optimization hasn't really fixed the info leak and has caused other problems, is it worth backing out the patch?
Comment 42 Al Billings [:abillings] 2013-01-03 13:17:56 PST
Can we get an update here on what will be done with this? - Critsmash Triage
Comment 43 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2013-01-03 19:25:20 PST
We plan to reimplement filters in a way that makes them more timing-attack-resistant, but we don't have a schedule for that yet.
Comment 44 Mats Palmgren (vacation) 2013-02-20 07:20:09 PST
Jet tells me this work depends on getting the layers refactoring done first.
Adding dependency on bug 825928.
Comment 45 Mats Palmgren (vacation) 2013-04-16 16:47:20 PDT
It looks like the blocking bug has now been fixed and this bug is actionable.
Do we have a plan and schedule for this work?
Comment 46 Cameron McCormack (:heycam) 2013-04-16 17:01:19 PDT
Correct me if I'm wrong roc, but I believe the plan is to implement SVG filters with shaders on the GPU, and that the layer refactoring was just one thing that needed to be done before we could start to do that.  I don't really know what else needs to be done before we're in a position to start converting the filter implementations.  It's not going to be a small job.  I don't think a schedule for this has been discussed, or whether it should be a priority, AFAIK.
Comment 47 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2013-04-17 03:41:48 PDT
IMHO implementing accelerated filters is a high-priority feature. But I think it's lower priority than enabling OMTC on all platforms, which is the next big layers/graphics task after the layers refactoring. (In fact it's already under way, we're close to turning on OMTC for Mac.) We are getting closer and if we had someone available who wasn't working on OMTC for whatever reason, they could start work on accelerated filters.
Comment 48 Benoit Jacob [:bjacob] (mostly away) 2013-05-07 09:05:11 PDT
Can someone please give a detailed update on this bug? What vulnerabilities are still present, what is the short-term plan to fix them?

Having a sec-high unfixed and hidden for almost 1.5 years is very unusual.
Comment 49 Benoit Jacob [:bjacob] (mostly away) 2013-05-07 09:20:52 PDT
I'm also concerned reading above (e.g. comment 47) that OMTC seems to have been considered a fix for this bug.

OMTC would at best somewhat reduce the bitrate at which information can be extracted.

An attacker would write their payload in a requestAnimationFrame callback, allowing them to know quite precisely the time interval between consecutive frames, given proper frame scheduling by the browser. The only thing that OMTC does here is that an attacker could not know when exactly a frame was composited, but that doesn't matter as long as they can measure differences between consecutive frames.

So an attacker having calibrated their payload so that in average half of frames take roughly 1/60 seconds and half of frames take roughly 1/30 seconds would be able to obtain in average one bit of information every 1/40 second (the average between 1/60 and 1/30), so they would obtain up to 5 bytes of information per second.

As OMTC is not a fix here, there also was, as far as I can see, no reason to block this bug on layers-refactoring.
Comment 50 Milan Sreckovic [:milan] (PTO July 28-29) 2013-05-07 10:30:42 PDT
I didn't read comment 47 that way - I read that the "fix" is GPU accelerated filters, which should be done after we do OMTC on all platforms.
Comment 51 Milan Sreckovic [:milan] (PTO July 28-29) 2013-05-07 10:32:14 PDT
And OMTC on all platforms was only going to be done after layers-refactoring, thus the dependency.  So, more of a "we don't want to do it until after layers-refactoring".
Comment 52 Benoit Jacob [:bjacob] (mostly away) 2013-05-07 11:14:06 PDT
How would the vulnerability be mitigated by running filters on the GPU?

The other question is how is it OK to block fixing a sec-high on a sequence of long-term projects (layers-refactoring -> OMTC -> running filters on GPU).

From comment 5 it sounds like we have a simple fix: just disable feMorphology.

According to http://caniuse.com/svg-filters , SVG filter support is not yet universal (not yet supported in the Android browser and only supported in Safari in the latest version) so it would be surprising if it were already deeply encroached; and we're only talking about disabling feMorphology at this point. That is only one of the 16 different SVG filter effects listed at http://www.w3.org/TR/SVG/filters.html . How bad would that be?

(Side note: still according to http://caniuse.com/svg-filters, it seems that at the time when this bug was reported, only Firefox, Chrome and Opera supported SVG filters, so disabling a filter back then would have been less painful).
Comment 53 Benoit Jacob [:bjacob] (mostly away) 2013-05-07 14:38:56 PDT
jwatt kindly pointed me to where this is now implemented (moved recently):

http://dxr.mozilla.org/mozilla-central/content/svg/content/src/SVGFEMorphologyElement.cpp#l170

  uint8_t* sourceData = aSources[0]->mImage->Data();
  uint8_t* targetData = aTarget->mImage->Data();
  int32_t stride = aTarget->mImage->Stride();
  uint8_t extrema[4];         // RGBA magnitude of extrema
  uint16_t op = mEnumAttributes[OPERATOR].GetAnimValue();

  // Scan the kernel for each pixel to determine max/min RGBA values.
  for (int32_t y = rect.y; y < rect.YMost(); y++) {
    int32_t startY = std::max(0, y - ry);
    // We need to read pixels not just in 'rect', which is limited to
    // the dirty part of our filter primitive subregion, but all pixels in
    // the given radii from the source surface, so use the surface size here.
    int32_t endY = std::min(y + ry, instance->GetSurfaceHeight() - 1);
    for (int32_t x = rect.x; x < rect.XMost(); x++) {
      int32_t startX = std::max(0, x - rx);
      int32_t endX = std::min(x + rx, instance->GetSurfaceWidth() - 1);
      int32_t targIndex = y * stride + 4 * x;

      for (int32_t i = 0; i < 4; i++) {
        extrema[i] = sourceData[targIndex + i];
      }
      for (int32_t y1 = startY; y1 <= endY; y1++) {
        for (int32_t x1 = startX; x1 <= endX; x1++) {
          for (int32_t i = 0; i < 4; i++) {
            uint8_t pixel = sourceData[y1 * stride + 4 * x1 + i];
            if ((extrema[i] > pixel &&
                 op == SVG_OPERATOR_ERODE) ||
                (extrema[i] < pixel &&
                 op == SVG_OPERATOR_DILATE)) {
              extrema[i] = pixel;
            }
          }
        }
      }
      targetData[targIndex  ] = extrema[0];
      targetData[targIndex+1] = extrema[1];
      targetData[targIndex+2] = extrema[2];
      targetData[targIndex+3] = extrema[3];
    }
  }

I don't see a lot there that take a variable amount of time depending on source pixels. The only place I can see from a quick glance is the if() in the inner loop:

            if ((extrema[i] > pixel &&
                 op == SVG_OPERATOR_ERODE) ||
                (extrema[i] < pixel &&
                 op == SVG_OPERATOR_DILATE)) {
              extrema[i] = pixel;
            }

Especially as && and || are sequence points, some conditions may not be evaluated at all depending on the values of previous expressions.
Comment 54 Benoit Jacob [:bjacob] (mostly away) 2013-05-07 15:07:58 PDT
Hm. After reducing the if() in the inner loop to

  if (extrema[i] > pixel) {
    extrema[i] = pixel;
  }

or

  if (extrema[i] < pixel) {
    extrema[i] = pixel;
  }

, the problem boils down to: how to implement constant-time min(a, b) and max(a, b) in C++?

volatile? memory barriers? or is this something that should be written in assembly? the problem must have been solved somewhere before...
Comment 55 Cameron McCormack (:heycam) 2013-05-07 15:18:14 PDT
(In reply to Benoit Jacob [:bjacob] from comment #54)
> volatile? memory barriers? or is this something that should be written in
> assembly? the problem must have been solved somewhere before...

Hmm, yeah, what about something like:

  volatile uint8_t a[2] = { extrema[i], pixel };
  volatile uint8_t index = extrema[i] < pixel ? 1 : 0;
  extrema[i] = a[index];

I tried something like this earlier on without the volatile, and I think that got optimised too much.
Comment 56 Cameron McCormack (:heycam) 2013-05-07 15:18:55 PDT
(If that doesn't pan out, we could also try severely limiting radius="" values, e.g. to 2.)
Comment 57 Benoit Jacob [:bjacob] (mostly away) 2013-05-07 15:26:37 PDT
(In reply to Cameron McCormack (:heycam) from comment #55)
> (In reply to Benoit Jacob [:bjacob] from comment #54)
> > volatile? memory barriers? or is this something that should be written in
> > assembly? the problem must have been solved somewhere before...
> 
> Hmm, yeah, what about something like:
> 
>   volatile uint8_t a[2] = { extrema[i], pixel };
>   volatile uint8_t index = extrema[i] < pixel ? 1 : 0;
>   extrema[i] = a[index];

That seems like it has a fair chance of working, but it relies on int(extrema[i] < pixel) taking constant time, which seems reasonable to rely on, but non-standard and depends on CPU architecture details.

A form that makes it more obviously and architecture-independently constant-time might be:

volatile uint8_t index = (extrema[i] - pixel) >> 7;

But then, I wonder if compilers could be so tricksy as to optimize that back into the form you proposed...

> I tried something like this earlier on without the volatile, and I think
> that got optimised too much.

Yes, optimization is the reason why we might end up having to do this in assembly (I hope not).
Comment 58 Benoit Jacob [:bjacob] (mostly away) 2013-05-07 15:31:40 PDT
Hm, on second thought I think my worries about int(extrema[i] < pixel) not necessarily taking constant time on all archs are probably unfounded. Give it a try? And check with someone like :jrmuizel or :derf who knows assembly.
Comment 59 Cameron McCormack (:heycam) 2013-05-07 16:11:33 PDT
That seemed to work on my Mac build, playing around with some different numbers for erode/filterRes.  (Inspecting clang's assembly, it looks like volatile did the trick, and is not doing anything clever with the array access.)
Comment 60 Benoit Jacob [:bjacob] (mostly away) 2013-05-07 18:19:32 PDT
That's great news. I would still like to hear the opinion of an expert.
Comment 61 Cameron McCormack (:heycam) 2013-05-07 18:30:17 PDT
Tim, would you be able to say whether the assumption in comment 57 -- that a statement

  uint8_x = uint8_y < uint8_z ? 1 : 0;

should, on architectures we're on, run in time constant regardless of the values -- is valid?
Comment 62 Timothy B. Terriberry (:derf) 2013-05-07 18:51:21 PDT
(In reply to Cameron McCormack (:heycam) from comment #61)
> Tim, would you be able to say whether the assumption in comment 57 -- that a
> statement
> 
>   uint8_x = uint8_y < uint8_z ? 1 : 0;
> 
> should, on architectures we're on, run in time constant regardless of the
> values -- is valid?

Yes.

On 80386's and higher, gcc will compile this to
xorl %edx, %edx
cmpl %eax, %edi
setl %dl
(even on -Os and -O0)

On ARM, gcc will compile this to
cmp r1, r0
movge r1, #0
movlt r1, #1
(again, even on -Os and -O0)

I don't have MSVC to test on right here, but I can't imagine they'd use jumps for this.
Comment 63 Cameron McCormack (:heycam) 2013-05-07 18:59:04 PDT
Great, thanks Tim.

Paul, if you are still about, could you try this build and see if you are able to tweak your PoC so that it still works?

http://ftp.mozilla.org/pub/mozilla.org/firefox/try-builds/cmccormack@mozilla.com-a1dbd84eae10/try-win32/firefox-23.0a1.en-US.win32.zip
Comment 64 Cameron McCormack (:heycam) 2013-05-07 21:19:08 PDT
Created attachment 746755 [details] [diff] [review]
don't branch when computing pixel value extrema
Comment 65 Timothy B. Terriberry (:derf) 2013-05-07 21:48:35 PDT
Comment on attachment 746755 [details] [diff] [review]
don't branch when computing pixel value extrema

Review of attachment 746755 [details] [diff] [review]:
-----------------------------------------------------------------

::: content/svg/content/src/SVGFEMorphologyElement.cpp
@@ +195,5 @@
> +            volatile uint8_t values[2] = { extrema[i], pixel };
> +            volatile uint8_t index = op == SVG_OPERATOR_ERODE ?
> +                                       extrema[i] < pixel :
> +                                       pixel < extrema[i];
> +            extrema[i] = values[index];

FWIW, I would have written this as:

extrema[i] -= (pixel - extrema[i]) & (-(extrema[i] < pixel) ^ -(op == SVG_OPERATOR_ERODE));

Array lookups like you're doing are generally slow, plus I wouldn't put it past gcc to branch on the op == SVG_OPERATOR_ERODE test in your version.
Comment 66 Timothy B. Terriberry (:derf) 2013-05-07 21:51:02 PDT
(In reply to Timothy B. Terriberry (:derf) from comment #65)
> extrema[i] -= (pixel - extrema[i]) & (-(extrema[i] < pixel) ^ -(op ==

Sorry, that should have been (extrema[i] - pixel), not the other way around.
Comment 67 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2013-05-07 22:03:24 PDT
Comment on attachment 746755 [details] [diff] [review]
don't branch when computing pixel value extrema

Review of attachment 746755 [details] [diff] [review]:
-----------------------------------------------------------------

I don't expect this to solve all our SVG filter timing issues, but if it does, great.
Comment 68 Benoit Jacob [:bjacob] (mostly away) 2013-05-08 06:47:55 PDT
(In reply to Timothy B. Terriberry (:derf) from comment #65)
> Comment on attachment 746755 [details] [diff] [review]
> don't branch when computing pixel value extrema
> 
> Review of attachment 746755 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: content/svg/content/src/SVGFEMorphologyElement.cpp
> @@ +195,5 @@
> > +            volatile uint8_t values[2] = { extrema[i], pixel };
> > +            volatile uint8_t index = op == SVG_OPERATOR_ERODE ?
> > +                                       extrema[i] < pixel :
> > +                                       pixel < extrema[i];
> > +            extrema[i] = values[index];
> 
> FWIW, I would have written this as:
> 
> extrema[i] -= (pixel - extrema[i]) & (-(extrema[i] < pixel) ^ -(op ==
> SVG_OPERATOR_ERODE));
> 
> Array lookups like you're doing are generally slow, plus I wouldn't put it
> past gcc to branch on the op == SVG_OPERATOR_ERODE test in your version.

I would take the (op == SVG_OPERATOR_ERODE) condition entirely out of this inner loop:
 - this will make this code simpler, hence easier to guarantee to be constant time
 - this will also make this code a little bit faster.
Comment 69 Benoit Jacob [:bjacob] (mostly away) 2013-05-08 06:49:50 PDT
(In reply to Robert O'Callahan (:roc) (Mozilla Corporation) from comment #67)
> I don't expect this to solve all our SVG filter timing issues, but if it
> does, great.

This would fix our feMorphology timing issues. Separate follow-up bugs should be filed to review and, if needed, fix other filters.
Comment 70 Benoit Jacob [:bjacob] (mostly away) 2013-05-08 06:55:05 PDT
Another comment: |index| probably doesn't need to be volatile --- only |values| needs volatile, right?

By the way Tim, do you know if there is a risk that a compiler might ignore volatile on local stack variables (whose address has not been taken), on the basis that they couldn't be referenced from anywhere else?
Comment 71 Timothy B. Terriberry (:derf) 2013-05-08 07:13:05 PDT
(In reply to Benoit Jacob [:bjacob] from comment #70)
> By the way Tim, do you know if there is a risk that a compiler might ignore
> volatile on local stack variables (whose address has not been taken), on the
> basis that they couldn't be referenced from anywhere else?

Most compilers I've seen become super-conservative about optimizing volatile accesses. It's not something I'd worry about, personally.

(In reply to Benoit Jacob [:bjacob] from comment #54)
> , the problem boils down to: how to implement constant-time min(a, b) and
> max(a, b) in C++?

The forms I've been using for branchless min/max for years are:
#define MIN(a,b) ((a)^(((b)^(a))&-((b)<(a))))
#define MAX(a,b) ((a)^(((b)^(a))&-((b)>(a))))

You can use - instead of ^ for unsigned values, which conveniently sets the flags needed by the comparison. Not that gcc is smart enough to figure this out: it still does the comparison again.
Comment 72 Paul Stone 2013-05-08 07:26:12 PDT
I'll take a look at this once the patch has been finalized - the try build is a bit out of date now.
Comment 73 Cameron McCormack (:heycam) 2013-05-13 18:22:59 PDT
Please try this build Paul, which has Benoit's and Tim's suggested changes: http://ftp.mozilla.org/pub/mozilla.org/firefox/try-builds/cmccormack@mozilla.com-a444e020e92d/try-win32/firefox-23.0a1.en-US.win32.zip
Comment 74 Robert Longson 2013-05-14 05:39:04 PDT
Wouldn't it be better if we had one function for erode and another for dilate?

if (erode) {
    all the loops applying the erode thing
}

if (dilate) {
    all the loops applying the dilate thing
}
Comment 75 Benoit Jacob [:bjacob] (mostly away) 2013-05-17 14:22:50 PDT
(In reply to Cameron McCormack (:heycam) from comment #73)
> Please try this build Paul, which has Benoit's and Tim's suggested changes:
> http://ftp.mozilla.org/pub/mozilla.org/firefox/try-builds/cmccormack@mozilla.
> com-a444e020e92d/try-win32/firefox-23.0a1.en-US.win32.zip

Don't wait for the original reporter to verify it; if you can verify that this fixes the bug for you on at least your own machine, just land the fix, mark the bug FIXED, and put qa-wanted.
Comment 76 Al Billings [:abillings] 2013-05-17 14:55:41 PDT
This needs sec-approval before landing since it is sec-high or greater and affects multiple releases.
Comment 77 Benoit Jacob [:bjacob] (mostly away) 2013-05-18 10:55:40 PDT
Ah, right. Cameron: as the patch author it's typically your turn to require sec-approval. IIRC.
Comment 78 Cameron McCormack (:heycam) 2013-05-18 19:40:48 PDT
Created attachment 751419 [details] [diff] [review]
don't branch when computing pixel value extrema (v2)

New patch to address longsonr's feedback.  The patch has gotten a bit different from the last one uploaded, so r? again.
Comment 79 Cameron McCormack (:heycam) 2013-05-18 19:46:23 PDT
Comment on attachment 751419 [details] [diff] [review]
don't branch when computing pixel value extrema (v2)

Oh, getting some reftest failures locally with this.  Stand by...
Comment 80 Cameron McCormack (:heycam) 2013-05-18 23:35:58 PDT
Created attachment 751430 [details] [diff] [review]
don't branch when computing pixel value extrema (v2.1)
Comment 81 Cameron McCormack (:heycam) 2013-05-19 02:58:21 PDT
And here's the build with that latest patch: http://ftp.mozilla.org/pub/mozilla.org/firefox/try-builds/cmccormack@mozilla.com-66843ed35a56/try-win32/firefox-24.0a1.en-US.win32.zip
Comment 82 Cameron McCormack (:heycam) 2013-05-19 08:21:49 PDT
Comment on attachment 751430 [details] [diff] [review]
don't branch when computing pixel value extrema (v2.1)

[Security approval request comment]
How easily could an exploit be constructed based on the patch?

Not so easily; the main change in timing of this function changed in a previous patch, and this just tweaks things.  You'd need to guess that this is a feature you could use for timing :visited renering.


Do comments in the patch, the check-in comment, or tests included in the patch paint a bulls-eye on the security problem?

I don't believe so.


Which older supported branches are affected by this flaw?

All.


If not all supported branches, which bug introduced the flaw?


Do you have backports for the affected branches? If not, how different, hard to create, and risky will they be?

Not currently.  The backports might need to include the previous patches on this bug that landed, depending on which branch we're talking about.


How likely is this patch to cause regressions; how much testing does it need?

Low.  We have tests for the functionality of feMorphology which still pass.
Comment 83 Benoit Jacob [:bjacob] (mostly away) 2013-05-19 16:33:55 PDT
(In reply to Cameron McCormack (:heycam) from comment #82)
> You'd need to guess that this
> is a feature you could use for timing :visited renering.

FWIW, the impact of this class of security bugs is more general than just :visited; think cross-origin images, tainted canvases...
Comment 84 Al Billings [:abillings] 2013-05-20 12:21:51 PDT
Comment on attachment 751430 [details] [diff] [review]
don't branch when computing pixel value extrema (v2.1)

sec-approval+ for m-c. Please create patches for branches and nominate them after m-c checkin.
Comment 85 Paul Stone 2013-05-21 02:28:21 PDT
I tested the build from comment #81. I couldn't see any timing differences between applying feMorphology to a flat or noisy image. So this bug does seem to be fixed for that filter.

I expect there are other filters that have timing differences. I do intend to test these at some point, and I will file bugs when I can.
Comment 86 Cameron McCormack (:heycam) 2013-05-21 02:30:10 PDT
Thanks for confirming, Paul, and for the original bug report.
Comment 87 Cameron McCormack (:heycam) 2013-05-22 23:09:22 PDT
https://hg.mozilla.org/integration/mozilla-inbound/rev/4611d43d18aa
Comment 88 Ed Morley [:emorley] 2013-05-23 04:59:53 PDT
https://hg.mozilla.org/mozilla-central/rev/4611d43d18aa
Comment 89 Al Billings [:abillings] 2013-06-11 11:20:10 PDT
If we want this on Beta for the 22 release in two weeks, this needs to be uplifted today.
Comment 90 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2013-06-11 14:21:19 PDT
Comment on attachment 751430 [details] [diff] [review]
don't branch when computing pixel value extrema (v2.1)

[Approval Request Comment]
Bug caused by (feature/regressing bug #): none
User impact if declined: possible timing attack collecting data such as link visitedness (relatively low impact)
Testing completed (on m-c, etc.): landed on m-c for a while, no known issues
Risk to taking this patch (and alternatives if risky): very low risk. This is a seldom-used feature anyway.
String or IDL/UUID changes made by this patch: none
Comment 91 Benoit Jacob [:bjacob] (mostly away) 2013-06-11 14:27:39 PDT
For what it's worth, link visitedness is just a tiny special case of the vulnerability here, and another more general exploit case is leakage of cross-origin information (by applying the SVG filter to a cross-origin image). Although it is true that the present testcase does not demonstrate the effectiveness of this particular timing vulnerability to read generic image data.
Comment 92 bhavana bajaj [:bajaj] 2013-06-11 14:33:15 PDT
(In reply to Robert O'Callahan (:roc) (Mozilla Corporation) from comment #90)
> Comment on attachment 751430 [details] [diff] [review]
> don't branch when computing pixel value extrema (v2.1)
> 
> [Approval Request Comment]
> Bug caused by (feature/regressing bug #): none
> User impact if declined: possible timing attack collecting data such as link
> visitedness (relatively low impact)
> Testing completed (on m-c, etc.): landed on m-c for a while, no known issues
> Risk to taking this patch (and alternatives if risky): very low risk. This
> is a seldom-used feature anyway.
> String or IDL/UUID changes made by this patch: none


Approving on beta/aurora as we need this low risk patch for FF21.0b5 which is going to build today.Please land asap. Thanks !

Also, please add qawanted if we need any addtional targeted SVG filter testing here given the verification completed in comment# 85.
Comment 93 Paul Stone 2013-06-11 14:40:10 PDT
It's also possible to read pixels from cross origin iframes. I have a PoC that performs OCR on a view-source: iframe. This can be used to read sensitive text such as CSRF tokens from other domains
Comment 94 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2013-06-11 14:44:39 PDT
Guys, I said "such as".
Comment 95 Benoit Jacob [:bjacob] (mostly away) 2013-06-11 14:46:23 PDT
I mostly reacted to "relatively low impact" --- I wanted to stress that while the present testcase may be considered as such, there is potential for worse exploits, as comment 93 also suggests.
Comment 96 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2013-06-11 15:07:02 PDT
https://hg.mozilla.org/releases/mozilla-aurora/rev/90920d7e96b5
https://hg.mozilla.org/releases/mozilla-beta/rev/cd634aafced6
Comment 97 Mihaela Velimiroviciu (:mihaelav) 2013-06-13 06:22:33 PDT
I am still getting significant differences between the numbers when running the updated PoC test from comment #37 on the latest beta build (Firefox 22 beta 5) on Mac 10.8.3 and Ubuntu 12.10 x64 (see attached screenshot). On win 7, the numbers vary from 818 to 823.
Is this expected?
Comment 98 Paul Stone 2013-06-13 06:59:08 PDT
It only matters if the numbers are consistently different between visited and unvisited links. Did the PoC manage to determine which links were visited?
Comment 99 Mihaela Velimiroviciu (:mihaelav) 2013-06-13 07:16:28 PDT
Created attachment 762022 [details]
screenshot

(In reply to Paul Stone from comment #98)
> It only matters if the numbers are consistently different between visited
> and unvisited links. Did the PoC manage to determine which links were
> visited?

I forgot to add the screenshot in my previous comment, sorry. There are some URLs for which the difference is significantly higher.
Comment 100 Paul Stone 2013-06-13 07:37:54 PDT
From the screenshot it doesn't look like there's a problem. The first two links (which it uses to calibrate the timings against visited and non-visited) took the same amount of time. Other things can affect the timings (e.g. other processes, switching away from the tab) so it doesn't matter if the numbers vary a bit.
Comment 101 Mihaela Velimiroviciu (:mihaelav) 2013-06-13 07:45:09 PDT
Mozilla/5.0 (Windows NT 6.1; WOW64; rv:22.0) Gecko/20100101 Firefox/22.0
Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:22.0) Gecko/20100101 Firefox/22.0
Mozilla/5.0 (X11; Linux x86_64; rv:22.0) Gecko/20100101 Firefox/22.0
Build ID: 20130612084701

Thanks Paul, I'm marking this verified based on that.
Comment 102 bhavana bajaj [:bajaj] 2013-06-14 16:25:23 PDT
needsinfo on Al here, to see if there was any reason we didn't track this for a specific esr release here.

Since this is a sec-high fixed in 22 and esr/b2g are affected, we should have those branch specific patches uplifted here.
Comment 103 Al Billings [:abillings] 2013-06-14 16:39:19 PDT
I marked ESR tracking as + instead of 22+ by mistake, I assume.
Comment 104 bhavana bajaj [:bajaj] 2013-06-14 16:41:57 PDT
Changing tracking to 22+ instead.
Comment 105 bhavana bajaj [:bajaj] 2013-06-14 16:43:03 PDT
(In reply to Cameron McCormack (:heycam) from comment #87)
> https://hg.mozilla.org/integration/mozilla-inbound/rev/4611d43d18aa

can you please help with esr/b2g branch patches here ?
Comment 106 Cameron McCormack (:heycam) 2013-06-17 14:32:22 PDT
I'll get on this today.
Comment 107 Cameron McCormack (:heycam) 2013-06-17 15:35:18 PDT
Created attachment 763846 [details] [diff] [review]
patch rebased for mozilla-esr17

[Approval Request Comment]
If this is not a sec:{high,crit} bug, please state case for ESR consideration:
User impact if declined: as above
Fix Landed on Version: 24
Risk to taking this patch (and alternatives if risky): as above
String or UUID changes made by this patch: n/a
Comment 108 Cameron McCormack (:heycam) 2013-06-17 15:37:48 PDT
Created attachment 763849 [details] [diff] [review]
patch rebased for mozilla-b2g18

[Approval Request Comment]
Bug caused by (feature/regressing bug #): none
User impact if declined: as above
Testing completed: landed on central/beta/aurora, manual testing verified the fix
Risk to taking this patch (and alternatives if risky): low
String or UUID changes made by this patch: n/a
Comment 111 Mihaela Velimiroviciu (:mihaelav) 2013-06-19 07:59:20 PDT
Created attachment 764755 [details]
Firefox 17.0.7esr

Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8; rv:17.0) Gecko/20100101 Firefox/17.0

I'm getting very different values for visited and not visited URLs on Firefox 17.0.7ESR/Mac 10.8.3 by running the updated PoC. Paulm do you have any suggestions?
Note that on Ubuntu 12.10 x86 and Win 7 x64 the behavior seems right, the numbers for visited and not visited are similar (620-630 for win7, 710-720 for ubuntu)
Comment 112 Paul Stone 2013-06-19 08:13:39 PDT
Mihaela, the numbers in that screenshot seem all over the place. Normally that indicates that some other process (or another FF tab) is hogging the CPU which means the timing isn't reliable. You could try re-running the PoC a few times to see if the numbers settle.

The main thing you're looking for is that the PoC can't identify which links are visited. In your screenshot it's identified links as visited when they aren't, so it's not a cause for concern.
Comment 113 Mihaela Velimiroviciu (:mihaelav) 2013-06-20 08:04:25 PDT
I ran the PoC again several times, on 2 distinct Minimac machines, only one Firefox process with one tab on each and the results are still similar with the ones in comment #111.
Comment 114 Matt Wobensmith [:mwobensmith][:matt:] 2013-06-24 13:07:54 PDT
I see the same results as Mihaela does on Mac 17esr.

I've tried builds both pre- and post-patch and there isn't much difference. In essence, this exploit just doesn't appear to work on this particular config.

So based on that, we are going to assume this bug is verified for 17.0.7esr and ship it. Thank you.
Comment 115 Raymond Forbes[:rforbes] 2013-07-19 18:30:38 PDT
rforbes-bugspam-for-setting-that-bounty-flag-20130719
Comment 116 Daniel Veditz [:dveditz] 2013-08-02 18:57:39 PDT
This bug was demonstrated as part of Paul's BlackHat USA 2013 talk on timing attacks.
Comment 117 Mathias Bynens 2013-08-07 04:41:42 PDT
For future reference, here’s a link to Paul’s excellent white paper on these timing attacks: http://contextis.co.uk/files/Browser_Timing_Attacks.pdf

Note You need to log in before you can comment on or make changes to this bug.