Subject: Re: Review: http://www.ietf.org/id/draft-mbelshe-httpbis-spdy-00.txt

From: Brian Pane <[email-masked]>
Date: Thu, 1 Mar 2012 08:22:55 -0800

On Wed, Feb 29, 2012 at 11:40 PM, Willy Tarreau <[email-masked]> wrote:
> On Wed, Feb 29, 2012 at 07:52:04PM -0800, Brian Pane wrote:
>> On Wed, Feb 29, 2012 at 5:40 PM, Amos Jeffries <[email-masked]> wrote:
>> > On 01.03.2012 13:39, Mike Belshe wrote:
>> >>
>> >> If the protocol is allowed to be slower than HTTP/1.1, then you could do
>> >> this.  But, a lot of server operators that care about performance aren't
>> >> going to want to take that hit.
>> >
>> >
>> > That is what bothers me about all the arguments against Upgrade: based on
>> > extra RTT and lag.
>> >
>> >  today: HTTP/1.1 request + HTTP/1.1 response   == 1 RTT
>> >
>> > versus
>> >
>> >  tomorrow: HTTP/1.1 request /w Upgrade header + XYZ response /w 200 status
>> > prefix   == 1 RTT
>>
>> I use a different comparison:
>>
>> HTTP/1.1 today:
>>     TCP handshake: 1 RTT
>>     HTTP/1.1 request for resource 1: 1 RTT
>>     Total == 2 RTT
>> ...meanwhile, the same thing happens on m-1 other connections that the
>> browser is using in parallel
>>
>> HTTP/1.1 with Upgrade to 2.0:
>>     TCP handshake: 1 RTT
>>     HTTP/1.1. request for resource 1: 1 RTT
>>     HTTP/2.0 requests for resources 2, ..., n-1, n: 1 RTT
>>     Total == 3 RTT
>
> No this one above is wrong. You're still at 2 RTT for HTTP/2.0 with
> Upgrade :
>
>  HTTP/1.1 with Upgrade to 2.0:
>     TCP SYN ----------------------->
>             <----------------------- TCP SYN/ACK           => 1 RTT
>     HTTP/1.1 GET+Upgrade ---------->
>              <---------------------- HTTP/1.1 101+Upgrade
>              <---------------------- HTTP/2.0 200 response => 1 RTT
>
> Total = 2 RTT. Doesn't change anything compared to 1.1.

You're omitting something fundamental.  In your example, a single
request is finished after 2 RTT, but the remaining m-1 requests take
an additional round trip.

> To be precise, the only difference is that the sender has
> to emit "Upgrade: HTTP/2.0" in the first request and that
> the server prepends an intermediate response "HTTP/1.1 101"
> followed by "Upgrade: HTTP/2.0". It's just a few extra bytes
> in the first connection setting up.

There's a much bigger difference: if the client starts with HTTP/1.1,
it can only issue one request on the connection and must wait at least
1 RTT for the server to respond to that request before the client can
begin to issue HTTP/2.0 requests.  That puts an Upgrade-based approach
at a disadvantage compared to connections that start out talking SPDY.

-Brian

---

From: Willy Tarreau <[email-masked]>
Date: Thu, 1 Mar 2012 17:34:18 +0100

> an additional round trip.

This is already the case with HTTP. If you enable pipelining, you'll notice
that the first connection only has one object. The first thing that comes to
mind is that you'd like the browser to know that the server supports pipelining
and it should send more requests at once. But in fact in order to know what to
ask for, the browser first needs to retrieve the object to discover what's
referenced there. So performing only one request in the first round trip of
a connection is not a showstopper and what happens most of the time already
for the first connection. Parallel connections generally see several pipelined
requests but we should not need those parallel connections with something like
SPDY.

Regards,
Willy

---

From: Brian Pane <[email-masked]>
Date: Thu, 1 Mar 2012 08:39:40 -0800

On Wed, Feb 29, 2012 at 11:18 PM, Willy Tarreau <[email-masked]> wrote:
> On Wed, Feb 29, 2012 at 03:16:22PM -0800, Mike Belshe wrote:

>> The problem with upgrade is that it costs a round trip of latency.
>
> Not for the first request since the server responds to this request.
> And since in HTTP you need the first request anyway to fetch the page
> to discover the objects you'll have to request next, it's not an issue
> for the first request of the keep-alive connection.

I think you're making the assumption that the page and the objects it
requires are served from the same FQDN, right?  In my experience, it's
common for a page served from example.com to reference static objects
served from example.org.  Thinking about the various reasons people
serve resources from different hostnames today,

- Domain sharding: not needed if HTTP/2.0 allows parallel requests on
one TCP conn
- Cookie-free domains: not needed if HTTP/2.0 provides header compression
- Resources served by third parties: still needed under HTTP/2.0
- Resources served by a CDN: still needed under HTTP/2.0 (even though
parallelization of requests will reduce the number of round trips
needed to fetch n resources, there's still value in reducing the
length of each round trip; and people will continue to use CDNs for
scalable/elastic traffic handling)

Thus I think it's essential for HTTP/2.0 to handle the following use
case efficiently:
- The client has a list of n resources it knows it needs
- Those n resources are all available under the same scheme:host:port
- The resources are independent of each other and can be fetched in any order

Brian

---

From: Willy Tarreau <[email-masked]>
Date: Thu, 1 Mar 2012 18:26:42 +0100

> serve resources from different hostnames today,

Oh I fairly agree, but right now if your browser opens a connection to
a different domain for any of the reasons below, it still doesn't pipeline
before the first round trip which ensures that HTTP/1.1 is supported.

> - The resources are independent of each other and can be fetched in any order

I too agree and don't think that anything proposed till now was against
these principles.

Regards,
Willy

---

From: Mike Belshe <[email-masked]>
Date: Fri, 2 Mar 2012 04:01:43 -0800

On Wed, Feb 29, 2012 at 11:30 PM, Willy Tarreau <[email-masked]> wrote:

> Hi Mike,
>
> On Wed, Feb 29, 2012 at 03:00:58PM -0800, Mike Belshe wrote:
> > Overall, I'm not sure how much to worry about DoS.  In the end, I think
> its
> > something you figure out how to mitigate in implementations - just like
> > we've done it before at every level from DNS to TCP to SSL to HTTP.
> >
> > I don't think its as dire as you've made it out to be.  It's not like
> this
> > amplification attack is difficult to mitigate.  A server wanting to limit
> > it, would probably do the following:
> >
> >    a) First off, because SPDY tries to limit connections to
> one-per-domain,
> > there is a new element of information at the transport layer which can be
> > used for DoS countermeasures.  This needs some experimentation, and I bet
> > it will be useful.
> >
> >    b) Also note that for SPDY over SSL, you've got DoS countermeasures
> from
> > the SSL layer at your disposal.  These are certainly going to slow down
> > many attackers.  (It will also make some sites nervous - especially those
> > that haven't hardened port 443 yet!)
> >
> >    c) If they get through both of those layers, the amplification attack
> is
> > easy to detect, and not a consumption of massive memory, bandwidth, or
> CPU
> > on the server; an implementation looking to conservatively block DoS
> could
> > check for expansions of 2-4KB and probably thwart most everything right
> > there.  Cheap.
>
> I disagree on exactly this point, because in order for the server to know
> that it doesn't want to process this 4 kB request, it first has to
> decompress
> it. Using plain old HTTP, in order for the server to reject a 4 kB request,
> the attacked had to upload it, which would have limited its ability to
> knock
> the server down. Now with just a few bytes an attacker can build a 4 kB
> request
> that the server will have to parse before deciding to reject it. A 4kB
> request
> would fit in 6 bytes from what I've seen, maybe less.

Hi Willy,

Thanks for your thoughtful answer again.  I think we need to look deeper to
settle this.

Let's examine the details of zlib and its format.  I believe there is no
practical amplification attack.  Maybe you'll prove me wrong.

zlib is quite simple.  You can scan it.  You can sanity check it.  You can
verify lz77 dictionary entries and ban any sequences that grow too long
(100B?).  On top of that we're compressing highly structured data, so we
know what the decompressed data must look like.  So if the decompressed
data ever falls out of whack, you can nuke it there too, as you stream it.

Short input sequences will be discardable off the bat - none of this "give
me 6 bytes to make me process 5KB" is going to be possible - you'll have to
send a sizable request to get us to process much out of it.  Then, if
individual dictionary entries grow unreasonably large in the first chunk of
headers (100B?), we'll drop you.  If the expanded name value pairs grow too
large, we'll drop you.  Or if it looks like you're sending junk headers or
unreasonable values, we'll drop you there too.  An attacker might be able
to convince a server to decompress 1000B on a 200B input before detecting
the fraud, but even that seems unlikely if we verify at all the levels I
mentioned already.

For argument's sake, lets be generous and pretend its even a 10x attack on
a 100B input.  Note well that the attack does not scale - even if you can
turn 100 bytes into 1000 bytes processed, it does not mean that you can
send us 10K to get 100K processed.   Because the length caps are going to
be really small, as soon as we see too many bytes, we'll be dropping you,
decreasing your amplification.

All in all, to get our SPDY server to process 1KB of amplified data on your
100B sent, you had to do a full 3 way handshake, plus a full SSL handshake
(with PK op on your *client*, and we got to pick which type of PK op -
8192bit RSA anyone?).  Mice nuts!  You'd be better off attacking with
legitimate requests - most servers will use far more resources trying to
process legit requests than deflating that extraneous 1KB of data.

See what I mean?  Because the size is bounded and because the amplification
is easily capped, the attack is not an attack at all.

Mike

> This means that by
> filling the pipe with 6-bytes requests, a client can make a server parse
> 800
> times that amount of traffic. Filling a pipe at 1 Mbps means the server has
> to process 800 Mbps of requests it will decide to drop in the end. This is
> my precise concern. And more importantly, I doubt that a 4kB limit will
> last
> long. I've used 4kB as a request size limit in haproxy 10 years ago, and I
> quickly had to push it to 8kB to satisfy most sites. In enterprise, it's
> worse, sometimes people configure it up to 32 kB but that's another story.
>
> > Overall, I just don't see how DoS is a silver-bullet against the zlib
> > compressor.
>
> Note that I'm not trying to find a silver buller against zlib, I'm worried
> about zlib making DoS much easier. I have a great respect for all the work
> you have done in optimizing the use of zlib for header compression and I
> don't want to dismiss any of your findings. I just think that one point has
> been overlooked and this point in my opinion is a real problem.
>
> > Almost any new feature has DoS potential (e.g. we haven't even
> > talked about frame flooding or syn_streams yet :-)
>
> Every design choice that makes DoS easier needs to be addressed even if
> it slightly reduces optimizations. DoS is far too common these days, we
> should focus on protecting the internet *before* making it faster for
> mobile users.

---

From: Henrik Nordström <[email-masked]>
Date: Fri, 02 Mar 2012 13:04:48 +0100

fre 2012-03-02 klockan 02:11 -0800 skrev Mike Belshe:

> Alright, I overstated.  You can't get any HTTP/2.0 *advantages* until
> you take a round trip.  On the first load of a web page, that might be
> good enough, as the browser often only has one resource to fetch
> initially.

Yes, until you somehow know the server is HTTP/2.0 capable you would
prefer to keep sending HTTP/1.1 to it. Which is sending the initial
HTTP/1.1 request with an Upgrade token and immediately getting a 101
Switching Protocol intermediary response back, at which point you can
start hammer the server with following HTTP/2.0 requests.

The response to the initial request would be HTTP/2.0.

> No, on secondary connections, it is normal for the browser to have
> multiple resources ready to be fetched immediately.  Assuming HTTP/2.0
> wants to pick up multiplexing, this means that you want to be able to
> issue both requests right away.

What is secondary connections?

Secondary as in concurrent connections? (which I thought we should
avoid?)

Or connections taking place some time in future?

> However, if you're going to be compatible with HTTP/1.1 servers that
> could issue 505 responses as you suggest here, you're going to need
> the first header block to be 100% compatible with HTTP/1.1 header
> parsers, otherwise that poor HTTP/1.1 server will get confused and
> likely hang.  

Yes, the first request needs to be in a format such that the request
line, delimiting and a few other basic parameters is compatible with
HTTP/1.1 parsers.

> You could argue this is an edge case (downgrading), and that it is ok
> to hang the browser for 30 secs (or whatever it takes before the
> server gets tired of waiting for data that isn't coming from the
> browser).  This answer was never palatable enough to get pipelining
> turned on by default, though.

HTTP/1.1 pipelining have a number of issues.

> I didn't assume HTTP/2.0 would need to be parse-compatible with
> HTTP/1.1.  Maybe that's what you meant by "then it isn't HTTP".

Edge definition case.

HTTP is from HTTP/1.0 onwards designed with an immediate upgrade path
based on protocol version. This path requires the request line and most
likely header delimiting to be compatiblewith HTTP/1.x parsers.

HTTP/1.1 adds another upgrade path using the Upgrade token. This path
allows upgrading the connection to any protocol entirely

Both upgrade paths are hop-by-hop, not end-to-end.

Regards
Henrik

---

From: Willy Tarreau <[email-masked]>
Date: Fri, 2 Mar 2012 15:11:16 +0100

Hi Mike,

[ sorry to bother you while you're traveling ]

> data ever falls out of whack, you can nuke it there too, as you stream it.

I'm not contesting this point.

> large, we'll drop you.

At this point this means we have to set up some complexe defensive measures
in the decoder to avoid some of the risks.

> Or if it looks like you're sending junk headers or
> unreasonable values, we'll drop you there too.

This is the point where you need to decompress the stream to parse the
headers. Even if zlib may be used as a stream, I think you'll agree that
in the sake of efficiency, you'll try to decompress as much of it as
possible at once, you won't call inflate() many times with a short output.

> An attacker might be able

This is the point where I disagree, because as long as the requests are
valid you uhave no reason to drop anything. For instance, if I send the
following 72 bytes :

  78 f9 e3 c6 a7 c2 43 24  d3 aa 01 f3 02 5a 26 80
  95 4d 17 e9 90 be 41 d9  08 96 bd f8 36 d1 c1 c2
  51 2b 46 ad 18 b5 62 d4  8a 51 2b 46 ad 18 b5 62
  d4 8a 51 2b 46 ad 18 b5  62 d4 8a 51 2b 46 ad 20
  a7 ff 0a 00 4f b2 66 6f  

they decompress to a (hopefully) valid 4032 bytes request which barely
looks like the SPDY encoding of :

  get /html,image/png,image/jpg,image/gif,application/xml,application/xhtml+xml,text/plain,text/javascript,publicprivatemax-age HTTP/1.1
  host: origin100101201202205206300302303304305306307402405406407408409410411412413414415416417502504505203
  cookie: origin... repeated 38 times

Adding the 18 bytes header to this, this means that I can produce 4032 bytes
of request to parse with only 90 bytes of input stream (ratio of 45x). The 
ratio even increases a lot if larger requests are accepted by the recipient
(eg: 94x for common 8kB buffer).

Since these requests are valid, the connection has no reason for being
dropped. The attacker will simply emit a stream of many such requests
and will receive a stream of "404 not found" for instance. At one megabit
of upstream bandwidth, I can then make and intermediary gateway have to :
  - decompress 1 Mbps (cheap)
  - parse and process 94 Mbps of headers (expensive)
  - recompress 94 Mbps of headers (expensive)

And in fact it's even worse than that because only the first request takes
spaces, the next ones benefit from the updated dictionary and are much
smaller. I've checked I can compress 10 8kB requests into 200 bytes, meaning
that each next request takes 13 bytes (+ 18 of header = 31 bytes). So after
the first request, the http-to-wire ratio is more like 264 for 8kB requests
(8190/31) or 122 for 4kB request (4032/33).

At 264, you just need 4 ADSL lines to make a SPDY-to-HTTP gateway fill its
gigabit link to the servers.

Another concern with this high compression ratio coupled with pipelining is
that it becomes easier to send a huge number of requests to a server in just
a few bytes. With the example above, we're saying that both the gateway and
the server may have to process 10000 8kB requests per second from a single
ADSL line. As of today, doing this for an attacker still requires at least
260 Mbps of upstream bandwidth.

> 8192bit RSA anyone?).  Mice nuts!

That's assuming that requests are identified as undesirable and also that
the site only runs over SSL. Attackers select the easiest way to take a
site down, not the hardest one :-)

> You'd be better off attacking with

Yes... that was precisely my point, sorry if that wasn't clear from my
examples. An attack is always an optimization of the harm vs cost ratio.
Sometimes it can take long to establish, but once the weak points are
found, they're smartly exploited.

Regards,
Willy

---

From: Henrik Nordström <[email-masked]>
Date: Fri, 02 Mar 2012 21:22:32 +0100

> possible at once, you won't call inflate() many times with a short output.

No, but most will be using zlib, and there the output buffer is
allocated by the caller and any output will not explode beyond what the
caller is accepts to handle.

> and will receive a stream of "404 not found" for instance.

Can even be valid requests for valid resources, with compression applied
to standard "junk" headers such as Accept, making it even harder to
notice what is going on.

> 260 Mbps of upstream bandwidth.

It will in most cases get throttled by the downstream bandwidth and to
some extent by how much the server accept to process concurrently per
client. But yes, for example a highly compressed stream of HEAD requests
for similar resources would result in a as highly compressed stream of
responses.

Regards
Henrik

---

From: "Roy T. Fielding" <[email-masked]>
Date: Fri, 2 Mar 2012 13:32:22 -0800

I would chalk it up as a concern and place this (very nice) advice
in the Security Considerations section.

....Roy

On Mar 2, 2012, at 4:01 AM, Mike Belshe wrote:
> Let's examine the details of zlib and its format.  I believe there is no practical amplification attack.  Maybe you'll prove me wrong.
> 
> zlib is quite simple.  You can scan it.  You can sanity check it.  You can verify lz77 dictionary entries and ban any sequences that grow too long (100B?).  On top of that we're compressing highly structured data, so we know what the decompressed data must look like.  So if the decompressed data ever falls out of whack, you can nuke it there too, as you stream it.
> 
> Short input sequences will be discardable off the bat - none of this "give me 6 bytes to make me process 5KB" is going to be possible - you'll have to send a sizable request to get us to process much out of it.  Then, if individual dictionary entries grow unreasonably large in the first chunk of headers (100B?), we'll drop you.  If the expanded name value pairs grow too large, we'll drop you.  Or if it looks like you're sending junk headers or unreasonable values, we'll drop you there too.  An attacker might be able to convince a server to decompress 1000B on a 200B input before detecting the fraud, but even that seems unlikely if we verify at all the levels I mentioned already.  
> 
> For argument's sake, lets be generous and pretend its even a 10x attack on a 100B input.  Note well that the attack does not scale - even if you can turn 100 bytes into 1000 bytes processed, it does not mean that you can send us 10K to get 100K processed.   Because the length caps are going to be really small, as soon as we see too many bytes, we'll be dropping you, decreasing your amplification.
> 
> All in all, to get our SPDY server to process 1KB of amplified data on your 100B sent, you had to do a full 3 way handshake, plus a full SSL handshake (with PK op on your *client*, and we got to pick which type of PK op - 8192bit RSA anyone?).  Mice nuts!  You'd be better off attacking with legitimate requests - most servers will use far more resources trying to process legit requests than deflating that extraneous 1KB of data.
> 
> See what I mean?  Because the size is bounded and because the amplification is easily capped, the attack is not an attack at all.
> 
> Mike

---

From: Mike Belshe <[email-masked]>
Date: Fri, 2 Mar 2012 13:45:40 -0800

> > decreasing your amplification.

Thanks for the cool response!  :-)

>  get
> /html,image/png,image/jpg,image/gif,application/xml,application/xhtml+xml,text/plain,text/javascript,publicprivatemax-age
> HTTP/1.1
>  host:
> origin100101201202205206300302303304305306307402405406407408409410411412413414415416417502504505203

Sure, but this would have easily tripped the fraud checks I enumerated.

> (8190/31) or 122 for 4kB request (4032/33).

Not exactly - now you're getting into concurrent stream DoS attacks.  Here
you'll run into a new limit, which is the max concurrent streams limit.  I
don't believe it is contentious that servers will want to have a cap on the
number of streams they'll simultaneously process, and the protocol even
allows for communicating this limit to the client.

> 260 Mbps of upstream bandwidth.

Concurrent stream limits.

> found, they're smartly exploited.

As Roy suggests, I think the concern is worthy, and you've made a good note
of it.  We're probably going to disagree on the magnitude of this and will
have to sort that part out later.

Mike

---

From: Philippe Mougin <[email-masked]>
Date: Sat, 3 Mar 2012 00:50:00 +0100

Le 29 févr. 2012 à 08:45, Roy T. Fielding a écrit :

[...]

> For example, waka is a tokenized protocol for the exact reasons that you
> describe, and it is specifically designed to speed intermediate processing.
> Unfortunately, having no end of potential syntaxes to choose from means
> I keep changing my mind as to which one to choose.  So I have nothing
> to show for it, aside from a ten year old presentation and a lot of
> burned out neurons.  I should have written a draft instead.  Maybe that
> will happen after HTTPbis is complete.  Maybe I'll go sane instead.

I suggest that you delay going sane a little bit longer and write down a draft for waka, on the ground that:
- The slides from ApacheCon were super promising. I'm sold.
- If you don't do it, who will?

Cheers,

Philippe Mougin

---

From: Amos Jeffries <[email-masked]>
Date: Sat, 03 Mar 2012 15:49:26 +1300

Putting on a black hat for today ...

On 3/03/2012 10:45 a.m., Mike Belshe wrote:
>
>
> On Fri, Mar 2, 2012 at 6:11 AM, Willy Tarreau <[email-masked] 
> <mailto:[email-masked]>> wrote:
>
>     Hi Mike,
>
<snip>
> Sure, but this would have easily tripped the fraud checks I enumerated.

You missed the point. The above is a valid request. It SHOULD NOT 
trigger any of the fraud checks.

Little nasty black-hat will come complaining to you about some report 
auto-generator not working through your proxy. Cookies are from partner 
sites, and the URL is a valid input parameter to the report generator. 
GET is more appropriate here then POST to get caching, it is a static 
response for 23 hrs and 59 min of each day.

> Not exactly - now you're getting into concurrent stream DoS attacks. 
>  Here you'll run into a new limit, which is the max concurrent streams 
> limit.  I don't believe it is contentious that servers will want to 
> have a cap on the number of streams they'll simultaneously process, 
> and the protocol even allows for communicating this limit to the client.

How does SPDY deal with the "drop" action then;
   entire TCP connection and every channel inside it,
   or just the one channel/session the attack was sighted on?

If the former, you get a single request from client A terminating a 
connection shared with N other clients.

   Black-hat: free amplification. woohoo!

If the latter,  the compression dictionary has just been seeded. A 
second-stage attack request can make use of that, concurrency is not 
required.

   Black-hat: so I just open two SPDY connections. done!

corollary:  if you try protecting seeding with a per-channel/session 
dictionary you end up consuming RAM resouces with N dictionaries per TCP 
connection.

   Black-hat: more baseline RAM loading. Lower threshold to push it over!

> Concurrent stream limits.

Black-hat: Multiple IPs. Check!

Black-hat: plus serial streams from other IPs to add more setup/teardown 
overheads. check!

(White-hat me wonders if this thread is leading towards a current 0-day 
for SPDY servers?)

> As Roy suggests, I think the concern is worthy, and you've made a good 
> note of it.  We're probably going to disagree on the magnitude of this 
> and will have to sort that part out later.

I hope that happens still while it is in Draft and deep issues can be 
changed.

AYJ