Subject: h2#373 HPACK attack mitigation options

From: Martin Thomson <[email-masked]>
Date: Wed, 5 Mar 2014 10:23:52 +0000

See https://github.com/http2/http2-spec/issues/373

See also http://lists.w3.org/Archives/Public/ietf-http-wg/2014JanMar/0233.html

So, we've been discussing ways forward with this, and I think that
there is a general desire to proceed with HPACK, something we'll
probably confirm today.  But that means that (in Adam's words) we'll
have to "require[s] downstream technologies to maintain more
invariants in order to avoid leaking sensitive information."

I think that we can limit the exposure to this problem to a subset of
HTTP implementations, rather than the full community of HTTP users.
This would allow us to keep compression, which I think is an important
part of the HTTP/2 feature set.  In particular, this would allow us to
keep compression without significantly weakening it, as some people
have suggested.

Firstly, we will need to be super careful about properly identifying
the subset of implementations that might be affected by this.  I do
not want a situation where some implementers think that they can avoid
implementing mitigations for this attack, when in fact they should be.

An implementation is potentially affected by this attack if it allows
multiple actors to influence the creation of HTTP header fields on the
same connection.  It also requires that header fields provided by any
one actor be kept secret from any other actor.  In the canonical
example of a browser, the invariant we want to maintain is that any
origin (the primary class of actor in that context) is unable to
access header fields that are created by other origins, or the browser
itself.

I'll note that this is also potentially an issue for non-browsers that
use proxies.

In terms of mitigation, I have so far heard two options.  There may be
others.  I don't think that we should pick one, but instead describe
the principles underpinning both and what it would take to properly
implement them.  Then allow implementations to decide what works best
for them.

Option 1 - Origin isolation

This solution relies on identifying the actor that is producing each
header field.  Each actor can only access entries in the table that
they themselves have caused to be added.  Fields added by other actors
cannot be seen and referenced.

Browsers can use the web origin model [RFC6454] to identify actors.
Much of the mechanisms needed are already used by browsers in other
areas (image rendering, cross origin requests, script execution,
etc...).

The HTTP stack might mark certain header fields as "safe" and make
these available to all origins.  For instance, in a browser, the
entries for Accept or Accept-Encoding, which is usually fixed in
browsers, and not really secret, so exporting those for reuse by other
actors is a good idea.

I believe that this solves the problem perfectly.  However...

The first drawback is that this has worse utilization of the memory we
allocate for header compression.

When I mentioned this to Nick and Patrick, both basically recoiled in
horror at the notion of having to implement this.  This option widens
the interface to the HTTP stack and all the tracking adds complexity
to what is already the trickiest piece of HTTP/2 to get right.  I can
only imagine that this could be even harder for other implementations
to get right, especially those that don't integrate their HTTP stack
as closely as Firefox does.

Option 2 - Penalize Guessing

(This is really an idea from Adam Barth, relayed to me by Will Chan,
so I will probably miss some nuance.)

This is riskier than the other option, but also goes some way to
address the concerns with the "perfect" option.  It's easier to
implement, and likely better at compression.

The idea here is to attach a "penalty" to attempts to probe the header
table.  The penalty in this case is a loss of compression.

Variant 1 - Self Destruct Counter

Basically, each time a header field is encoded, a search is made for a
header field in the table.  If the name matches, but the value does
not, a penalty counter attached to that header field name is
increased.  A match decreases the counter, potentially by a larger
delta.

If the counter for any given header field name reaches a predefined
threshold, all entries in the header table for that name are removed
(and the counter is reset).  Hence, compression for that header field
name ceases.

Variant 2 - Stochastically Disable Referencing

Basically the above, but higher values on the counter don't trigger a
self-destruct, instead, they introduce an increasing probability that
entries in the header table are ignored even if there is a match.

Other Variants - ?

There are probably other ways to approach this that has approximately
the same properties.

Side note: Limiting SETTINGS_MAX_CONCURRENT_STREAMS

My sense is that this is going to be basically ineffectual.  Since
we're talking about a network attacker, I'm fairly certain that this
attacker can cause a browser to instantiate new connections, simply by
breaking an existing one.

---

From: Roberto Peon <[email-masked]>
Date: Wed, 5 Mar 2014 03:09:33 -0800

On Wed, Mar 5, 2014 at 2:23 AM, Martin Thomson <[email-masked]>wrote:

> See also
> http://lists.w3.org/Archives/Public/ietf-http-wg/2014JanMar/0233.html
>

This adds some complexity, but doesn't increase memory requirements, at
least not in non-attack cases.
Given the mechanism used for expiration of state in HPACK, this mechanism
results in a decrease in compressor efficiency mostly in the attack case,
which seems reasonable.

> There are probably other ways to approach this that has approximately

If no state is carried over from connection-to-connection, then causing the
connection to be torn down refereshes the counter's state, and it becomes
equivalent to limiting MAX_CONCURRENT_STREAMS.
A timer on this state that outlives the connection lifetime would work to
concretely define the number of bits/second which can be probed.
I'm confident that variant 1 with this would work.
#2 is subtle and depends on more variables (how does the probability
compound, decrease, etc. Bleh.).

> breaking an existing one.
Playing with this limits the number of attempts that can occur without the
server being informed of the evidence of the attack.
If there is a timer on reconnects, this ends up limiting the number of
bits/second which can be probed similarly to option 2 above.

There is a further option, which is "perfect" against this style of attack,
and is arguably simple. One can think of it as a variant of #1.
Option #4
Requests originating from a domain which is not the origin to which the
request is ultimately directed are disallowed to use *any* dynamic
compressor state.
-=R

---

From: Martin Thomson <[email-masked]>
Date: Wed, 5 Mar 2014 11:29:09 +0000

> request is ultimately directed are disallowed to use *any* dynamic

That would be a strict subset of #1 and thus perfectly good.

---

From: Roberto Peon <[email-masked]>
Date: Wed, 5 Mar 2014 03:43:07 -0800

Yup. "One can think of it as a variant of #1."
-=R

---

From: Roland Zink <[email-masked]>
Date: Wed, 05 Mar 2014 12:47:33 +0100

What does this mean for proxies? Should proxies open a new outgoing 
connection for each incoming?

HPACK can do a diff to the previous request. If the previous request is 
from a different client then the diff might be rather large. Should 
HPACK be extended to allow several reference sets and switch between them?

Roland

---

From: Roberto Peon <[email-masked]>
Date: Wed, 5 Mar 2014 04:22:19 -0800

The issue isn't the reference set in this case, rather it is that the
originator of the request != the destination for the request, which allows
the originator to probe the compressor dynamic state-table.
If options 1 or 4 are taken, then grouping or some similar signaling may
need to be reintroduced. Opening an outgoing connection for each incoming
connection is not the greatest thing in the world as it defeats several of
the nice properties of HTTP/2.

Option #2 doesn't require this.

HPACK/HTTP2 is not currently well optimized for intermediaries. This was a
conscious decision to reduce protocol complexity at the tradeoff of some
optimality.
-=R

On Wed, Mar 5, 2014 at 3:47 AM, Roland Zink <[email-masked]> wrote:

> from a different client then the diff might be rather large. Should HPACK
> be extended to allow several reference sets and switch between them?
>
> Roland
>
>

---

From: Eric Rescorla <[email-masked]>
Date: Wed, 5 Mar 2014 12:49:42 +0000

> results in a decrease in compressor efficiency mostly in the attack case,

Maybe I am misunderstanding. It seems like in the case where you
have (a) sharding and (b) shared cookies across shards, doesn't
this create a lot of replicas of those across the shards for each
origin?

> If no state is carried over from connection-to-connection, then causing
> the connection to be torn down refereshes the counter's state, and it
> becomes equivalent to limiting MAX_CONCURRENT_STREAMS.
> There is a further option, which is "perfect" against this style of
> attack, and is arguably simple. One can think of it as a variant of #1.
> Option #4

So this would be the same evaluation as with same origin policy but
more strict? I.e., I have a connection to site A, and then site B
pulls in a GIF from A vs. <img src>, but the second request doesn't
get to use the compressor state?

-Ekr

---

From: Roberto Peon <[email-masked]>
Date: Wed, 5 Mar 2014 04:58:39 -0800

Yup.
-=R

On Wed, Mar 5, 2014 at 4:49 AM, Eric Rescorla <[email-masked]> wrote:

>> Playing with this limits the number of attempts that can occur without
>> the server being informed of the evidence of the attack.

---

From: Michael Sweet <[email-masked]>
Date: Wed, 05 Mar 2014 08:12:45 -0500

Roberto,

On Mar 5, 2014, at 7:22 AM, Roberto Peon <[email-masked]> wrote:
> The issue isn't the reference set in this case, rather it is that the originator of the request != the destination for the request, which allows the originator to probe the compressor dynamic state-table.
> If options 1 or 4 are taken, then grouping or some similar signaling may need to be reintroduced. Opening an outgoing connection for each incoming connection is not the greatest thing in the world as it defeats several of the nice properties of HTTP/2.

FWIW, it wouldn't be the end of the world as you are still reducing the connection load from N connections per client to 1 per client - probably an order of magnitude difference with today's browsers.

_________________________________________________________
Michael Sweet, Senior Printing System Engineer, PWG Chair

---

From: Roberto Peon <[email-masked]>
Date: Wed, 5 Mar 2014 05:14:20 -0800

I have use-cases where I'd like to mux many connections onto one, e.g. when
I may not have enough ephemereal port space to serve that number of
connections.
The advantage is not theoretical there :)
-=R

On Wed, Mar 5, 2014 at 5:12 AM, Michael Sweet <[email-masked]> wrote:

> FWIW, it wouldn't be the end of the world as you are still reducing the
> connection load from N connections per client to 1 per client - probably an
> order of magnitude difference with today's browsers.
>

---

From: Michael Sweet <[email-masked]>
Date: Wed, 05 Mar 2014 08:18:31 -0500

Roberto,

On Mar 5, 2014, at 8:14 AM, Roberto Peon <[email-masked]> wrote:
> I have use-cases where I'd like to mux many connections onto one, e.g. when I may not have enough ephemereal port space to serve that number of connections.

:)

I think I've voiced my opposition to the current HPACK enough times...  Between stream management, HPACK, and priority management, proxies are going to have a lot more work to do when muxing...

---

From: Martin Thomson <[email-masked]>
Date: Wed, 5 Mar 2014 13:19:00 +0000

> I may not have enough ephemereal port space to serve that number of

You are not the only one.