Mailing List Archive

> -----Original Message-----
> From: Stefan Fritsch [mailto:sf@sfritsch.de]
> Sent: Dienstag, 23. August 2011 13:09
> To: dev@httpd.apache.org
> Subject: DoS with mod_deflate & range requests
>
> http://seclists.org/fulldisclosure/2011/Aug/175
>
> I haven't looked into it so far. And I am not sure I will
> have time today.


After checking the attack script and the code this has IMHO
nothing to do with mod_deflate but only with the byterange filter.

But I admit that haven't run the script to check.

The host is seen as vulnerable if it replies to a range request that requests
the whole entity via a range "0-" with a partial response.
A possible problem is that the output bucket brigade gets transformed
in a "one bucket per byte" brigade and thus into a brigade with many
buckets. Futhermore the created range response has a lot of buckets
with boundaries, strings allocated from r->pool.
So it might be advisable if we limit the number of ranges we accept
contained in a Range header.
As a further optimization we could check for "0-" ranges and once we
hit one just reply with the full response instead of a partial response.

Regards

Rüdiger

2011/8/23 Stefan Fritsch <sf@sfritsch.de>:
> http://seclists.org/fulldisclosure/2011/Aug/175
>
> I haven't looked into it so far. And I am not sure I will have time today.
>

it is sending HEAD requests with lots of ranges
HEAD / HTTP/1.1
Host: xxxx
Range:bytes=0-,5-1,5-2,5-3,.....

the code in
ap_byterange_filter()
http://svn.apache.org/repos/asf/httpd/httpd/branches/2.2.x/modules/http/byterange_filter.c
creates a bucket for every range element,

the number of buckets is limited by the size of the document in
published code but I think it can be enchanced by
using 1-2,1-3,..1-doc_size,2-1,2-2, 2-doc_size

doeas Range in HEAD request have any sense at all ?

2011/8/23 Lazy <lazy404@gmail.com>:
> 2011/8/23 Stefan Fritsch <sf@sfritsch.de>:
>> http://seclists.org/fulldisclosure/2011/Aug/175
>>
>> I haven't looked into it so far. And I am not sure I will have time today.
>>
>
> it is sending HEAD requests with lots of  ranges
> HEAD / HTTP/1.1
> Host: xxxx
> Range:bytes=0-,5-1,5-2,5-3,.....
>
> the code in
> ap_byterange_filter()
> http://svn.apache.org/repos/asf/httpd/httpd/branches/2.2.x/modules/http/byterange_filter.c
> creates a bucket for every range element,
>
> the number of buckets is limited by the size of the document in
> published code but I think it can be enchanced by
> using 1-2,1-3,..1-doc_size,2-1,2-2, 2-doc_size
>
> doeas Range in HEAD request have any sense at all ?

quick fix bellow made it immune to this dos

diff -ru modules/http/byterange_filter.c.org
modules/http/byterange_filter.c |less
--- byterange_filter.c 2011-02-13 15:32:19.000000000 +0100
+++ modules/http/byterange_filter.c 2011-08-23 15:54:37.000000000 +0200
@@ -320,6 +320,7 @@
const char *if_range;
const char *match;
const char *ct;
+ char * tmp;
int num_ranges;

if (r->assbackwards) {
@@ -373,14 +374,13 @@
}
}

- if (!ap_strchr_c(range, ',')) {
- /* a single range */
- num_ranges = 1;
- }
- else {
- /* a multiple range */
- num_ranges = 2;
- }
+ /* count ranges, exit if more then 10 */
+ tmp=range+6;
+ num_ranges=1;
+ while(*++tmp)
+ if(*tmp == ',')
+ if(++num_ranges > 10)
+ return 0;

r->status = HTTP_PARTIAL_CONTENT;
r->range = range + 6;

On Tue, Aug 23, 2011 at 02:15:16PM +0200, Lazy wrote:
> 2011/8/23 Stefan Fritsch <sf@sfritsch.de>:
> > http://seclists.org/fulldisclosure/2011/Aug/175
> >
> > I haven't looked into it so far. And I am not sure I will have time today.
> >
>
> it is sending HEAD requests with lots of ranges
> HEAD / HTTP/1.1
> Host: xxxx
> Range:bytes=0-,5-1,5-2,5-3,.....
…
> doeas Range in HEAD request have any sense at all ?

One /possible/ use is as an equivalent for a conditional GET, ie
GET / HTTP/1.1
Host: xxx
Range: bytes=1024-
If-Range: "foo"

…to which the correct response should I think be either 200 or 206 depending
on whether the document is modified.

But it's a pretty odd case. I can't imagine any published client or proxy
that would make such a request. It would in any case be acceptable to
return a 200 response instead; RFC 2616 states that "A server MAY ignore
the Range header"

Tim Bannister

On 8/23/2011 6:08 AM, Stefan Fritsch wrote:
> http://seclists.org/fulldisclosure/2011/Aug/175
>
> I haven't looked into it so far. And I am not sure I will have time today.

Until range can be completely addressed, avoiding excessive numbers of
ranges (tricky) or overlapping ranges (pretty straightforward)...
what about simply disabling deflate on range requests?

On Tuesday 23 August 2011, William A. Rowe Jr. wrote:
> On 8/23/2011 6:08 AM, Stefan Fritsch wrote:
> > http://seclists.org/fulldisclosure/2011/Aug/175
> >
> > I haven't looked into it so far. And I am not sure I will have
> > time today.
>
> Until range can be completely addressed, avoiding excessive numbers
> of ranges (tricky) or overlapping ranges (pretty
> straightforward)... what about simply disabling deflate on range
> requests?

There is this PR:

https://issues.apache.org/bugzilla/show_bug.cgi?id=49772

"mod_deflate kicks itself out on Content-Range responses but not on
multipart/byteranges"

This may be one of the issues. But as Rüdiger pointed out, there is
also an issue without mod_deflate.

From looking at the code, I think the problem is the bucket structs.
With N the number of requested ranges, the initial brigade is
partitioned into 2*N buckets at the maximum. Then those buckets are
copied into the output brigade N times, which means that O(N^2)
buckets are created. The data is not copied, and only N "A-B" strings
are allocated from the pool. But the sum of those is limited by
LimitRequestFieldSize, so it shouldn't be a problem.

Maybe the byte-range filter should call ap_pass_brigade every 10
ranges or so? Then the buckets should be freed earlier (at least if
all filters down the chain behave correctly).

please tell me how to unsubscribe from this mailing list

On Tue, Aug 23, 2011 at 9:49 PM, Stefan Fritsch <sf@sfritsch.de> wrote:

> On Tuesday 23 August 2011, William A. Rowe Jr. wrote:
> > On 8/23/2011 6:08 AM, Stefan Fritsch wrote:
> > > http://seclists.org/fulldisclosure/2011/Aug/175
> > >
> > > I haven't looked into it so far. And I am not sure I will have
> > > time today.
> >
> > Until range can be completely addressed, avoiding excessive numbers
> > of ranges (tricky) or overlapping ranges (pretty
> > straightforward)... what about simply disabling deflate on range
> > requests?
>
> There is this PR:
>
> https://issues.apache.org/bugzilla/show_bug.cgi?id=49772
>
> "mod_deflate kicks itself out on Content-Range responses but not on
> multipart/byteranges"
>
> This may be one of the issues. But as Rüdiger pointed out, there is
> also an issue without mod_deflate.
>
> From looking at the code, I think the problem is the bucket structs.
> With N the number of requested ranges, the initial brigade is
> partitioned into 2*N buckets at the maximum. Then those buckets are
> copied into the output brigade N times, which means that O(N^2)
> buckets are created. The data is not copied, and only N "A-B" strings
> are allocated from the pool. But the sum of those is limited by
> LimitRequestFieldSize, so it shouldn't be a problem.
>
> Maybe the byte-range filter should call ap_pass_brigade every 10
> ranges or so? Then the buckets should be freed earlier (at least if
> all filters down the chain behave correctly).
>
>


--
Mohamed D. Sulaiman
Farmer's Commercial Bank
Banking Technology Unit
Cell: (+249) 923407600
Website: http://www.mohameddawaina.site40.net

On 8/23/2011 1:49 PM, Stefan Fritsch wrote:
>
> From looking at the code, I think the problem is the bucket structs.
> With N the number of requested ranges, the initial brigade is
> partitioned into 2*N buckets at the maximum. Then those buckets are
> copied into the output brigade N times, which means that O(N^2)
> buckets are created. The data is not copied, and only N "A-B" strings
> are allocated from the pool. But the sum of those is limited by
> LimitRequestFieldSize, so it shouldn't be a problem.
>
> Maybe the byte-range filter should call ap_pass_brigade every 10
> ranges or so? Then the buckets should be freed earlier (at least if
> all filters down the chain behave correctly).

I suggest we should be parsing and reassembling the list before we
start the bucket logic. I'd also suggest the following...

This example from the spec...

- Several legal but not canonical specifications of the second 500
bytes (byte offsets 500-999, inclusive):
bytes=500-600,601-999
bytes=500-700,601-999

does not say the last is 200 bytes and 400 bytes, but is explicitly the
second 500 bytes.

I propose we satisfy range requests in the only sensible manner, returning
the ranges in sequence, using a linked list of buckets and combining all
ranges or another mechanism to work out the applicable ranges.

The range processing is limited to some 4000 parts (consisting entirely
of invalid -, segments), and as a practical matter much less than 2500.
Reassemble the list of ranges in sequence as a pre-parsing step, and we
can much more efficiently generate the response with no duplication.

The spec is ambiguous but nowhere suggested that duplicate ranges would
be legitimate.

On Tue, Aug 23, 2011 at 3:32 PM, William A. Rowe Jr. <wrowe@rowe-clan.net>wrote:

>
> I suggest we should be parsing and reassembling the list before we
> start the bucket logic.
>


> I propose we satisfy range requests in the only sensible manner, returning
> the ranges in sequence,
>

yeah, overlapping ranges should be merged up front. That ought to completely
fix the issue.

fwiw, I played with the script to create the attack and noticed this:

Content-Length: 950883

That's probably the sum of the overlapping ranges. My original file is 3929
bytes long.

Greg

On 8/23/2011 4:00 PM, Greg Ames wrote:
>
> On Tue, Aug 23, 2011 at 3:32 PM, William A. Rowe Jr. wrote:
>
> I suggest we should be parsing and reassembling the list before we
> start the bucket logic.
>
> I propose we satisfy range requests in the only sensible manner, returning
> the ranges in sequence,
>
> yeah, overlapping ranges should be merged up front. That ought to completely fix the issue.

So the only remaining question; are we free to reorder them into sequence?

Even in the most pedantic case, I believe that the total array shouldn't
ever exceed 1024, because in those cases a large number of the acceptable
expected ranges should be in the nnn-nnn, format, or 8 characters long,
out of our MAX_LINE_LENGTH of some 8190. If we argue that asking for
single bytes is simply wrong, we should probably allocate some 16 ranges
and grow the list by a power of four, resulting in a max of some 4 allocs
and maximum memory consumption of less than 64k per request.

Am 23.08.2011 20:52, schrieb Mohamed Dawaina:
> please tell me how to unsubscribe from this mailing list

what about looking in the mail-header or login with your acount
you have registered?

Precedence: bulk
Reply-To: dev@httpd.apache.org
list-help: <mailto:dev-help@httpd.apache.org>
list-unsubscribe: <mailto:dev-unsubscribe@httpd.apache.org>
List-Post: <mailto:dev@httpd.apache.org>
List-Id: <dev.httpd.apache.org>

On Tuesday 23 August 2011, William A. Rowe Jr. wrote:
> On 8/23/2011 4:00 PM, Greg Ames wrote:
> > On Tue, Aug 23, 2011 at 3:32 PM, William A. Rowe Jr. wrote:
> > I suggest we should be parsing and reassembling the list
> > before we start the bucket logic.
> >
> > I propose we satisfy range requests in the only sensible
> > manner, returning the ranges in sequence,
> >
> > yeah, overlapping ranges should be merged up front. That ought to
> > completely fix the issue.
>
> So the only remaining question; are we free to reorder them into
> sequence?

Good point. I haven't seen anything in the RFC about that. I guess
that there are at least some clients that will be broken by that.

Nevertheless, I have done a first try at a patch. The necessary
modification to only merge and not reorder should be small. I have
done only limited testing, so there are probably some bugs. There are
no tests with multiple ranges in the test-framework, yet.

> Even in the most pedantic case, I believe that the total array
> shouldn't ever exceed 1024, because in those cases a large number
> of the acceptable expected ranges should be in the nnn-nnn,
> format, or 8 characters long, out of our MAX_LINE_LENGTH of some
> 8190. If we argue that asking for single bytes is simply wrong,
> we should probably allocate some 16 ranges and grow the list by a
> power of four, resulting in a max of some 4 allocs and maximum
> memory consumption of less than 64k per request.

Just counting the commas in the header line seems acceptable to me. In
any case, single byte ranges are explicitly mentioned in the RFC as
example, so we probably should not disallow those.

On Aug 23, 2011, at 2:34 PM, William A. Rowe Jr. wrote:

> On 8/23/2011 4:00 PM, Greg Ames wrote:
>>
>> On Tue, Aug 23, 2011 at 3:32 PM, William A. Rowe Jr. wrote:
>>
>> I suggest we should be parsing and reassembling the list before we
>> start the bucket logic.
>>
>> I propose we satisfy range requests in the only sensible manner, returning
>> the ranges in sequence,
>>
>> yeah, overlapping ranges should be merged up front. That ought to completely fix the issue.
>
> So the only remaining question; are we free to reorder them into sequence?

And the spec says ...

When a client requests multiple ranges in one request, the
server SHOULD return them in the order that they appeared in the
request.

My suggestion is to reject any request with overlapping ranges or more
than five ranges with a 416, and to send 200 for any request with 4-5
ranges. There is simply no need to support random access in HTTP.

....Roy

On Wednesday 24 August 2011, Roy T. Fielding wrote:
> My suggestion is to reject any request with overlapping ranges or
> more than five ranges with a 416, and to send 200 for any request
> with 4-5 ranges. There is simply no need to support random access
> in HTTP.

Even with WebDAV?

BTW, I think Adobe reader does range requests to download single pages
from a pdf. It would be interesting to see what kind of requests it
does, but I don't have it installed right now.

> -----Original Message-----
> From: Stefan Fritsch
> Sent: Mittwoch, 24. August 2011 00:28
> To: dev@httpd.apache.org
> Subject: Re: DoS with mod_deflate & range requests
>
> On Tuesday 23 August 2011, William A. Rowe Jr. wrote:
> > On 8/23/2011 4:00 PM, Greg Ames wrote:
> > > On Tue, Aug 23, 2011 at 3:32 PM, William A. Rowe Jr. wrote:
> > > I suggest we should be parsing and reassembling the list
> > > before we start the bucket logic.
> > >
> > > I propose we satisfy range requests in the only sensible
> > > manner, returning the ranges in sequence,
> > >
> > > yeah, overlapping ranges should be merged up front. That ought to
> > > completely fix the issue.
> >
> > So the only remaining question; are we free to reorder them into
> > sequence?
>
> Good point. I haven't seen anything in the RFC about that. I guess
> that there are at least some clients that will be broken by that.
>
> Nevertheless, I have done a first try at a patch. The necessary
> modification to only merge and not reorder should be small. I have
> done only limited testing, so there are probably some bugs. There are
> no tests with multiple ranges in the test-framework, yet.
>
> > Even in the most pedantic case, I believe that the total array
> > shouldn't ever exceed 1024, because in those cases a large number
> > of the acceptable expected ranges should be in the nnn-nnn,
> > format, or 8 characters long, out of our MAX_LINE_LENGTH of some
> > 8190. If we argue that asking for single bytes is simply wrong,
> > we should probably allocate some 16 ranges and grow the list by a
> > power of four, resulting in a max of some 4 allocs and maximum
> > memory consumption of less than 64k per request.
>
> Just counting the commas in the header line seems acceptable
> to me. In
> any case, single byte ranges are explicitly mentioned in the RFC as
> example, so we probably should not disallow those.

Patch looks good, but some comments:

As far as I can see the following range request would not get merged:

Range: bytes=0-0,1-1,2-2

into a 0-2 range as need_sort would remain 0. OTOH

Range: bytes=0-0,0-1,1-2

would get get merged into a 0-2 range.

Using boundary and !boundary in the later if statements to decide whether a request
is multi range or single range is IMHO bad as boundary is set based on the old number
ranges and not based on the number of merged ranges. So multiple ranges in the beginning
might get merged to a single range in the end.

Regards

Rüdiger

On Tue, Aug 23, 2011, Roy T. Fielding wrote:
> And the spec says ...
>
> When a client requests multiple ranges in one request, the
> server SHOULD return them in the order that they appeared in the
> request.
>
> My suggestion is to reject any request with overlapping ranges or more
> than five ranges with a 416, and to send 200 for any request with 4-5
> ranges. There is simply no need to support random access in HTTP.

Deshpande & Zeng in http://dx.doi.org/10.1145/500141.500197 describe a
method for "streaming" JPEG 2000 documents over HTTP, using many more than
5 ranges in a single request.
A client that knows about any server-side limit could make multiple
requests each with a small number of ranges, but discovering that limit
will add latency and take more code.

Tim Bannister

On Aug 23, 2011, at 9:34 PM, Roy T. Fielding wrote:

> On Aug 23, 2011, at 2:34 PM, William A. Rowe Jr. wrote:
>
>> On 8/23/2011 4:00 PM, Greg Ames wrote:
>>>
>>> On Tue, Aug 23, 2011 at 3:32 PM, William A. Rowe Jr. wrote:
>>>
>>> I suggest we should be parsing and reassembling the list before we
>>> start the bucket logic.
>>>
>>> I propose we satisfy range requests in the only sensible manner, returning
>>> the ranges in sequence,
>>>
>>> yeah, overlapping ranges should be merged up front. That ought to completely fix the issue.
>>
>> So the only remaining question; are we free to reorder them into sequence?
>
> And the spec says ...
>
> When a client requests multiple ranges in one request, the
> server SHOULD return them in the order that they appeared in the
> request.
>
> My suggestion is to reject any request with overlapping ranges

+1

> or more
> than five ranges with a 416, and to send 200 for any request with 4-5
> ranges. There is simply no need to support random access in HTTP.

-0

On 24 Aug 2011, at 16:35, Tim Bannister wrote:

> On Tue, Aug 23, 2011, Roy T. Fielding wrote:
>> And the spec says ...
>>
>> When a client requests multiple ranges in one request, the
>> server SHOULD return them in the order that they appeared in the
>> request.
>>
>> My suggestion is to reject any request with overlapping ranges or more
>> than five ranges with a 416, and to send 200 for any request with 4-5
>> ranges. There is simply no need to support random access in HTTP.
>
> Deshpande & Zeng in http://dx.doi.org/10.1145/500141.500197 describe a
> method for "streaming" JPEG 2000 documents over HTTP, using many more than
> 5 ranges in a single request.
> A client that knows about any server-side limit could make multiple
> requests each with a small number of ranges, but discovering that limit
> will add latency and take more code.

Agreed - I've seen many 10's of ranges in a single request for things like clever PDF pagination (or tiny TIFF quicklooks for the pages), clever http fake streaming and clever use of jumping to i-Frames.

I think we just need to sit this out - and accept up to RequestFieldSize limit bytes on that line - and then do a sort & merge overlaps as needed.

And then it is fine.

Dw

On Aug 24, 2011, at 4:05 AM, Plüm, Rüdiger, VF-Group wrote:

>
> Patch looks good, but some comments:
>
> As far as I can see the following range request would not get merged:
>
> Range: bytes=0-0,1-1,2-2
>
> into a 0-2 range as need_sort would remain 0. OTOH
>
> Range: bytes=0-0,0-1,1-2
>
> would get get merged into a 0-2 range.
>
> Using boundary and !boundary in the later if statements to decide whether a request
> is multi range or single range is IMHO bad as boundary is set based on the old number
> ranges and not based on the number of merged ranges. So multiple ranges in the beginning
> might get merged to a single range in the end.

+1…

Suggestion: Let's fold the patch, as-is, into trunk, tune it there
and then backport to 2.x...

> -----Original Message-----
> From: Dirk-Willem van Gulik [mailto:Dirk-Willem.van.Gulik@bbc.co.uk]
> Sent: Mittwoch, 24. August 2011 17:46
> To: dev@httpd.apache.org
> Subject: Re: DoS with mod_deflate & range requests
>
>
> On 24 Aug 2011, at 16:35, Tim Bannister wrote:
>
> > On Tue, Aug 23, 2011, Roy T. Fielding wrote:
> >> And the spec says ...
> >>
> >> When a client requests multiple ranges in one request, the
> >> server SHOULD return them in the order that they appeared in the
> >> request.
> >>
> >> My suggestion is to reject any request with overlapping
> ranges or more
> >> than five ranges with a 416, and to send 200 for any
> request with 4-5
> >> ranges. There is simply no need to support random access in HTTP.
> >
> > Deshpande & Zeng in http://dx.doi.org/10.1145/500141.500197
> describe a
> > method for "streaming" JPEG 2000 documents over HTTP, using
> many more than
> > 5 ranges in a single request.
> > A client that knows about any server-side limit could make multiple
> > requests each with a small number of ranges, but
> discovering that limit
> > will add latency and take more code.
>
> Agreed - I've seen many 10's of ranges in a single request
> for things like clever PDF pagination (or tiny TIFF
> quicklooks for the pages), clever http fake streaming and
> clever use of jumping to i-Frames.
>
> I think we just need to sit this out - and accept up to
> RequestFieldSize limit bytes on that line - and then do a
> sort & merge overlaps as needed.

Hm. If I got it right what Roy says above about the spec sorting and merging is
not an option as we need to stick to the order and number of ranges the client
requested. But we can deny overlapping with a 416.
Or we do a 416 as well if merging would change something.

Regards

Rüdiger

Sorting isn't allowed but I get the impression that merging is OK…
Roy can confirm…

If not, then some sort of runtime limit on the number of allowable
ranges plus a 416 w/ overlapping ranges makes the most sense.

On Aug 24, 2011, at 11:55 AM, Plüm, Rüdiger, VF-Group wrote:
>
> Hm. If I got it right what Roy says above about the spec sorting and merging is
> not an option as we need to stick to the order and number of ranges the client
> requested. But we can deny overlapping with a 416.
> Or we do a 416 as well if merging would change something.
>
> Regards
>
> Rüdiger
>

> -----Original Message-----
> From: Jim Jagielski [mailto:jim@jaguNET.com]
> Sent: Mittwoch, 24. August 2011 17:48
> To: dev@httpd.apache.org
> Subject: Re: DoS with mod_deflate & range requests
>
>
> On Aug 24, 2011, at 4:05 AM, Plüm, Rüdiger, VF-Group wrote:
>
> >
> > Patch looks good, but some comments:
> >
> > As far as I can see the following range request would not
> get merged:
> >
> > Range: bytes=0-0,1-1,2-2
> >
> > into a 0-2 range as need_sort would remain 0. OTOH
> >
> > Range: bytes=0-0,0-1,1-2
> >
> > would get get merged into a 0-2 range.
> >
> > Using boundary and !boundary in the later if statements to
> decide whether a request
> > is multi range or single range is IMHO bad as boundary is
> set based on the old number
> > ranges and not based on the number of merged ranges. So
> multiple ranges in the beginning
> > might get merged to a single range in the end.
>
> +1...
>
> Suggestion: Let's fold the patch, as-is, into trunk, tune it there
> and then backport to 2.x...
>

Based on Roy's comment about the spec I think we cannot optimize this way.
I think we can only detect if something weird goes on (overlapping, merging
would result in smaller number of ranges, excessive number of ranges, whereas
"excessive" needs to be configurable with a sane default) and reply with a 416 then.

Regards

Rüdiger

> -----Original Message-----
> From: Jim Jagielski [mailto:jim@jaguNET.com]
> Sent: Mittwoch, 24. August 2011 18:02
> To: dev@httpd.apache.org
> Subject: Re: DoS with mod_deflate & range requests
>
> Sorting isn't allowed but I get the impression that merging is OK...
> Roy can confirm...

But merging might require sorting...

>
> If not, then some sort of runtime limit on the number of allowable
> ranges plus a 416 w/ overlapping ranges makes the most sense.
>
> On Aug 24, 2011, at 11:55 AM, Plüm, Rüdiger, VF-Group wrote:
> >
> > Hm. If I got it right what Roy says above about the spec
> sorting and merging is
> > not an option as we need to stick to the order and number
> of ranges the client
> > requested. But we can deny overlapping with a 416.
> > Or we do a 416 as well if merging would change something.
> >
> > Regards
> >
> > Rüdiger
> >
>
>

Regards

Rüdiger

On 8/24/2011 10:55 AM, "Plüm, Rüdiger, VF-Group" wrote:
>
> Hm. If I got it right what Roy says above about the spec sorting and merging is
> not an option as we need to stick to the order and number of ranges the client
> requested.

No. Merging -is- recommended.



10.4.17 416 Requested Range Not Satisfiable

A server SHOULD return a response with this status code if a request
included a Range request-header field (section 14.35), and none of
the range-specifier values in this field overlap the current extent
of the selected resource, and the request did not include an If-Range
request-header field. (For byte-ranges, this means that the first-
byte-pos of all of the byte-range-spec values were greater than the
current length of the selected resource.)

Note; the FIRST byte-pos is invalid. It doesn't suggest that 416 can be
used for semantically valid ranges longer than the document length, or
to represent that valid byte ranges overlapped. In fact, if ONE range
can be satisfied, 416 is not appropriate.

So if ONE range can be satisfied, it is to be returned (this is reiterated
in 14.16), which may obviously be out-of-sequence.

I would suggest we simply ignore/extend for all overlapping ranges
rather than rejecting them.

E.g.

0-, 40-50 becomes 0-
0-499, 400-599 becomes 0-599
1000-1075, 200-250, 1051-1100 becomes 1000-1100, 200-250

-Sorting- is to be avoided, although as its a SHOULD, I am happy to break
that recommendation if there is no reasonably efficient solution to the
server side. As Roy suggests, random access on the server side is very
dubious. A client issuing rich requests should assemble them and must
respect the individual Content-Range response headers.

On Aug 24, 2011, at 12:05 PM, Plüm, Rüdiger, VF-Group wrote:

>
>
>> -----Original Message-----
>> From: Jim Jagielski [mailto:jim@jaguNET.com]
>> Sent: Mittwoch, 24. August 2011 18:02
>> To: dev@httpd.apache.org
>> Subject: Re: DoS with mod_deflate & range requests
>>
>> Sorting isn't allowed but I get the impression that merging is OK...
>> Roy can confirm...
>
> But merging might require sorting...
>

then we don't do that merge, imo… In other words, we
progress thru the set of ranges and once a range
is merged as far as it can be (due to the next range
not being merge-able with the previous one), we let
it go...

On Aug 24, 2011, at 12:22 PM, William A. Rowe Jr. wrote:

>
> 0-, 40-50 becomes 0-

> 0-499, 400-599 becomes 0-599

> 1000-1075, 200-250, 1051-1100 becomes 1000-1100, 200-250

This goes against Roy's recommendation to 416 overlaps… But
I do see that an overlap is specifically noted in an example

Until we are *clear* on what we should be doing, spec-wise, I
think it's unwise to make assumptions…

From the above, I would be more comfortable with

0-, 40-50 ---> 0-
0-499, 400-599 ---> 0-599
1000-1075, 1025-1088, 200-250, 1051-1100 --> 1000-1088, 200-250, 1051-1100

that it, merge as we can, but never resort...

On Wednesday 24 August 2011, Jim Jagielski wrote:
> On Aug 24, 2011, at 12:05 PM, Plüm, Rüdiger, VF-Group wrote:
> >> -----Original Message-----
> >> From: Jim Jagielski [mailto:jim@jaguNET.com]
> >> Sent: Mittwoch, 24. August 2011 18:02
> >> To: dev@httpd.apache.org
> >> Subject: Re: DoS with mod_deflate & range requests
> >>
> >> Sorting isn't allowed but I get the impression that merging is
> >> OK... Roy can confirm...
> >
> > But merging might require sorting...
>
> then we don't do that merge, imo… In other words, we
> progress thru the set of ranges and once a range
> is merged as far as it can be (due to the next range
> not being merge-able with the previous one), we let
> it go...

We could also use a two stage approach: Up to some limit (e.g. 50)
ranges, we return them as the client requested them. Over that limit,
we violate the RFC-SHOULD and sort and merge them.

On 24 Aug 2011, at 17:47, Stefan Fritsch wrote:
On Wednesday 24 August 2011, Jim Jagielski wrote:
>> On Aug 24, 2011, at 12:05 PM, Plüm, Rüdiger, VF-Group wrote:
>>>
>>> But merging might require sorting...
>>
>> then we don't do that merge, imo… In other words, we progress thru the set of ranges and once a range is merged as far as it can be (due to the next range not being merge-able with the previous one), we let it go...
>
> We could also use a two stage approach: Up to some limit (e.g. 50) ranges, we return them as the client requested them. Over that limit, we violate the RFC-SHOULD and sort and merge them.

Another option is just to return 200. Servers MAY ignore the Range header. I prefer this because existing clients already handle that case well, and there's no opportunity for a client to exploit this (“malicious” clients that want the whole entity need only request it).

Can anyone see why returning 200 for these complex requests (by ignoring Range / If-Range) is a bad idea?

--
Tim Bannister – isoma@jellybaby.net

On Wed, Aug 24, 2011 at 12:42 PM, Jim Jagielski <jim@jagunet.com> wrote:

>
> On Aug 24, 2011, at 12:22 PM, William A. Rowe Jr. wrote:
>
> >
> > 0-, 40-50 becomes 0-
>
> > 0-499, 400-599 becomes 0-599
>
> > 1000-1075, 200-250, 1051-1100 becomes 1000-1100, 200-250
>
> This goes against Roy's recommendation to 416 overlaps… But
> I do see that an overlap is specifically noted in an example
>

yeah. The very end of section 14.35.1 says an overlap is legal, so I'm
confused.


>
> Until we are *clear* on what we should be doing, spec-wise, I
> think it's unwise to make assumptions…
>

> From the above, I would be more comfortable with
>
> 0-, 40-50 ---> 0-
> 0-499, 400-599 ---> 0-599
> 1000-1075, 1025-1088, 200-250, 1051-1100 --> 1000-1088, 200-250,
> 1051-1100
>
> that it, merge as we can, but never resort...


how about:

1000-2000,100-200,3000-4000,200-300,1999-3001

?

If we don't return a 416 for that due to overlap, I think the merge should
be;

1000-4000,100-300

If we only merge adjacent ascending ranges, then it seems like an attacker
could just craft a header where the ranges jump around and dodge our fix.

The other small point I wanted to make is that both ends of a range could
overlap previously specified ranges.

Greg

On Aug 24, 2011, at 2:43 PM, Tim Bannister wrote:

> On 24 Aug 2011, at 17:47, Stefan Fritsch wrote:
> On Wednesday 24 August 2011, Jim Jagielski wrote:
>>> On Aug 24, 2011, at 12:05 PM, Plüm, Rüdiger, VF-Group wrote:
>>>>
>>>> But merging might require sorting...
>>>
>>> then we don't do that merge, imo… In other words, we progress thru the set of ranges and once a range is merged as far as it can be (due to the next range not being merge-able with the previous one), we let it go...
>>
>> We could also use a two stage approach: Up to some limit (e.g. 50) ranges, we return them as the client requested them. Over that limit, we violate the RFC-SHOULD and sort and merge them.
>
> Another option is just to return 200. Servers MAY ignore the Range header. I prefer this because existing clients already handle that case well, and there's no opportunity for a client to exploit this (“malicious” clients that want the whole entity need only request it).
>
> Can anyone see why returning 200 for these complex requests (by ignoring Range / If-Range) is a bad idea?

In what cases would we ignore it? Dependent only on >=X ranges?
It does seem that 14.5 gives us this as an out...

On Aug 24, 2011, at 3:10 PM, Greg Ames wrote:

>
>
> On Wed, Aug 24, 2011 at 12:42 PM, Jim Jagielski <jim@jagunet.com> wrote:
>
> >From the above, I would be more comfortable with
>
> 0-, 40-50 ---> 0-
> 0-499, 400-599 ---> 0-599
> 1000-1075, 1025-1088, 200-250, 1051-1100 --> 1000-1088, 200-250, 1051-1100
>
> that it, merge as we can, but never resort...
>
> how about:
>
> 1000-2000,100-200,3000-4000,200-300,1999-3001
>
> ?
>
> If we don't return a 416 for that due to overlap, I think the merge should be;
>
> 1000-4000,100-300

That's what Bill thinks as well, but that almost seems like
a "resorting" to be, such that the 100-200 range (2nd requested)
comes *after* the server sends 3000-4000, which is actually the 3rd
range requested.

>
> If we only merge adjacent ascending ranges, then it seems like an attacker could just craft a header where the ranges jump around and dodge our fix.
>

I think no matter what, we should still have some sort of
upper limit on the number of range-sets we accept… after all,
merge doesn't prevent jumping around ;)

On 8/24/2011 11:42 AM, Jim Jagielski wrote:
>
> On Aug 24, 2011, at 12:22 PM, William A. Rowe Jr. wrote:
>
>> 0-, 40-50 becomes 0-
>
>> 0-499, 400-599 becomes 0-599
>
>> 1000-1075, 200-250, 1051-1100 becomes 1000-1100, 200-250
>
> This goes against Roy's recommendation to 416 overlaps… But
> I do see that an overlap is specifically noted in an example

And... 416 is not identified for this specific purpose, we would need
to go with 400 or fall back on the 200 full-content solution.

> Until we are *clear* on what we should be doing, spec-wise, I
> think it's unwise to make assumptions…
>
> From the above, I would be more comfortable with
>
> 0-, 40-50 ---> 0-
> 0-499, 400-599 ---> 0-599
> 1000-1075, 1025-1088, 200-250, 1051-1100 --> 1000-1088, 200-250, 1051-1100
>
> that it, merge as we can, but never resort...

We should adamantly refuse to serve bytes 1051-1088 twice, no matter
which scheme we use.

On Aug 24, 2011, at 3:34 PM, William A. Rowe Jr. wrote:

> On 8/24/2011 11:42 AM, Jim Jagielski wrote:
>>
>> On Aug 24, 2011, at 12:22 PM, William A. Rowe Jr. wrote:
>>
>>> 0-, 40-50 becomes 0-
>>
>>> 0-499, 400-599 becomes 0-599
>>
>>> 1000-1075, 200-250, 1051-1100 becomes 1000-1100, 200-250
>>
>> This goes against Roy's recommendation to 416 overlaps… But
>> I do see that an overlap is specifically noted in an example
>
> And... 416 is not identified for this specific purpose, we would need
> to go with 400 or fall back on the 200 full-content solution.
>
>> Until we are *clear* on what we should be doing, spec-wise, I
>> think it's unwise to make assumptions…
>>
>> From the above, I would be more comfortable with
>>
>> 0-, 40-50 ---> 0-
>> 0-499, 400-599 ---> 0-599
>> 1000-1075, 1025-1088, 200-250, 1051-1100 --> 1000-1088, 200-250, 1051-1100
>>
>> that it, merge as we can, but never resort...
>
> We should adamantly refuse to serve bytes 1051-1088 twice, no matter
> which scheme we use.
>

Why? If allowed by the spec, or, at least, not disallowed, then
what is the rationale? After all, the client is expecting it after
it gets bytes 200->250.

On 24 Aug 2011, at 20:13, Jim Jagielski wrote:

>> Another option is just to return 200. Servers MAY ignore the Range header. I prefer this because existing clients already handle that case well, and there's no opportunity for a client to exploit this (“malicious” clients that want the whole entity need only request it).
>>
>> Can anyone see why returning 200 for these complex requests (by ignoring Range / If-Range) is a bad idea?
>
> In what cases would we ignore it? Dependent only on >=X ranges?

I don't have any strong opinion about exactly when to ignore Range. From an HTTP client PoV I wouldn't want to get 416 from requesting a satisfiable but complex range (maliciously or otherwise).

Ignoring Range on (ranges >= X) is simple to implement and easy to document, so why not do that?

--
Tim Bannister – isoma@jellybaby.net

On Wed, Aug 24, 2011 at 3:19 PM, Jim Jagielski <jim@jagunet.com> wrote:

>
> >
> > If we only merge adjacent ascending ranges, then it seems like an
> attacker could just craft a header where the ranges jump around and dodge
> our fix.
> >
>
> I think no matter what, we should still have some sort of
> upper limit on the number of range-sets we accept… after all,
> merge doesn't prevent jumping around ;)
>
>
The problem I have with the upper limit on the number of range sets is the
use case someone posted for JPEG2000 streaming. That has a lot of range
sets but is completely legit. However, the ranges are in ascending order
and don't overlap. Maybe we could count overlaps and/or non-ascending order
ranges and fall back to 200 + the whole object if it exceeds a limit.

Greg

On 24 Aug 2011, at 21:39, Greg Ames wrote:

> On Wed, Aug 24, 2011 at 3:19 PM, Jim Jagielski <jim@jagunet.com> wrote:
>
> >
> > If we only merge adjacent ascending ranges, then it seems like an attacker could just craft a header where the ranges jump around and dodge our fix.
> >
>
> I think no matter what, we should still have some sort of
> upper limit on the number of range-sets we accept… after all,
> merge doesn't prevent jumping around ;)
>
>
> The problem I have with the upper limit on the number of range sets is the use case someone posted for JPEG2000 streaming. That has a lot of range sets but is completely legit. However, the ranges are in ascending order and don't overlap. Maybe we could count overlaps and/or non-ascending order ranges and fall back to 200 + the whole object if it exceeds a limit.

Right - and the other two use cases in the wild are

- PDF readers - which fetch something at the start in RQ 1 and then the index form the end - and then quick looks images for each page and title pages. I've seen them do a second and 3rd request with many 10's of ranges.

- Some of the streaming video (semi/pro) video editors - which fetch a bunch of i-Frames and do clever skip over stuff. Not in the high tens; but 10-15 ranges common.

- Likewise for very clever MXF professional editing equipment - the largest case (yup - it did crash my server) tried to fetch over 2000 ranges :)

So I think we really should endeavor to allow 50 to a few 100 of them. Or at the very least - make it a config option to cut off below 50 or so.

Dw.

On Aug 24, 2011, at 8:35 AM, Tim Bannister wrote:

> On Tue, Aug 23, 2011, Roy T. Fielding wrote:
>> And the spec says ...
>> When a client requests multiple ranges in one request, the
>> server SHOULD return them in the order that they appeared in the
>> request.
>> My suggestion is to reject any request with overlapping ranges or more than five ranges with a 416, and to send 200 for any request with 4-5 ranges. There is simply no need to support random access in HTTP.
>
> Deshpande & Zeng in http://dx.doi.org/10.1145/500141.500197 describe a method for "streaming" JPEG 2000 documents over HTTP, using many more than 5 ranges in a single request.
> A client that knows about any server-side limit could make multiple requests each with a small number of ranges, but discovering that limit will add latency and take more code.

I have no interest in supporting such a use case over HTTP.
Consider how stupid it is to request ranges like their example

Range: bytes=120-168,175-200,205-300,345-346,400-500,555-666,
667-800,900-1000,2500-2567,2890-3056,5678-9000,
10000-12004,12050-12060,15600-15605,17000-17001,
17005-17010,17050-17060,17800-17905,20000-20005

keeping in mind that between each one of those ranges will be
a multipart boundary of approximately 80 bytes! Hence, any
range request that contains gaps of less than 80 bytes should
be considered a denial of service, or at least an idiot programmer
that deserves to be slapped by Apache.

To be clear, I am more than willing to rewrite the part on
Ranges such that the above is explicitly forbidden in HTTP.
I am not sure what the WG would agree to, but I am quite certain
that part of the reason we have an Apache server is to protect
the Internet from idiotic ideas like the above.

....Roy

On Aug 24, 2011, at 8:55 AM, Plüm, Rüdiger, VF-Group wrote:
> Hm. If I got it right what Roy says above about the spec sorting and merging is
> not an option as we need to stick to the order and number of ranges the client
> requested. But we can deny overlapping with a 416.

We should implement whatever is needed to make the service
secure from this denial of service. If that means changing the
spec, then so be it.

> Or we do a 416 as well if merging would change something.

Or 200 if folks are squeamish about making the developer feel
the pain.

....Roy

On 8/24/2011 3:45 PM, Dirk-WIllem van Gulik wrote:
>
> On 24 Aug 2011, at 21:39, Greg Ames wrote:
>
>> On Wed, Aug 24, 2011 at 3:19 PM, Jim Jagielski <jim@jagunet.com
>> <mailto:jim@jagunet.com>> wrote:
>>
>>
>> >
>> > If we only merge adjacent ascending ranges, then it seems like an attacker could
>> just craft a header where the ranges jump around and dodge our fix.
>> >
>>
>> I think no matter what, we should still have some sort of
>> upper limit on the number of range-sets we accept… after all,
>> merge doesn't prevent jumping around ;)
>>
>>
>> The problem I have with the upper limit on the number of range sets is the use case
>> someone posted for JPEG2000 streaming. That has a lot of range sets but is completely
>> legit. However, the ranges are in ascending order and don't overlap. Maybe we could
>> count overlaps and/or non-ascending order ranges and fall back to 200 + the whole object
>> if it exceeds a limit.
>
> Right - and the other two use cases in the wild are
>
> -PDF readers - which fetch something at the start in RQ 1 and then the index form the end
> - and then quick looks images for each page and title pages. I've seen them do a second
> and 3rd request with many 10's of ranges.
>
> -Some of the streaming video (semi/pro) video editors - which fetch a bunch of i-Frames
> and do clever skip over stuff. Not in the high tens; but 10-15 ranges common.
>
> -Likewise for very clever MXF professional editing equipment - the largest case (yup - it
> did crash my server) tried to fetch over 2000 ranges :)
>
> So I think we really should endeavor to allow 50 to a few 100 of them. Or at the very
> least - make it a config option to cut off below 50 or so.

At least, after 256 ranges or so, fall back to a 200 response in lieu of
a 400/416 response.

On 8/24/2011 3:12 PM, Jim Jagielski wrote:
>
> On Aug 24, 2011, at 3:34 PM, William A. Rowe Jr. wrote:
>
>> On 8/24/2011 11:42 AM, Jim Jagielski wrote:
>>>
>>> On Aug 24, 2011, at 12:22 PM, William A. Rowe Jr. wrote:
>>>
>>>> 0-, 40-50 becomes 0-
>>>
>>>> 0-499, 400-599 becomes 0-599
>>>
>>>> 1000-1075, 200-250, 1051-1100 becomes 1000-1100, 200-250
>>>
>>> This goes against Roy's recommendation to 416 overlaps… But
>>> I do see that an overlap is specifically noted in an example
>>
>> And... 416 is not identified for this specific purpose, we would need
>> to go with 400 or fall back on the 200 full-content solution.
>>
>>> Until we are *clear* on what we should be doing, spec-wise, I
>>> think it's unwise to make assumptions…
>>>
>>> From the above, I would be more comfortable with
>>>
>>> 0-, 40-50 ---> 0-
>>> 0-499, 400-599 ---> 0-599
>>> 1000-1075, 1025-1088, 200-250, 1051-1100 --> 1000-1088, 200-250, 1051-1100
>>>
>>> that it, merge as we can, but never resort...
>>
>> We should adamantly refuse to serve bytes 1051-1088 twice, no matter
>> which scheme we use.
>>
>
> Why? If allowed by the spec, or, at least, not disallowed, then
> what is the rationale? After all, the client is expecting it after
> it gets bytes 200->250.

The client was malformed, if not malicious. The range 0-,0-,0-,0-
is syntactically valid, but the client doesn't deserve four copies.

On Wednesday 24 August 2011, Dirk-WIllem van Gulik wrote:
> > I think no matter what, we should still have some sort of
> > upper limit on the number of range-sets we accept… after all,
> > merge doesn't prevent jumping around ;)
> >
> >
> >
> >
> > The problem I have with the upper limit on the number of range
> > sets is the use case someone posted for JPEG2000
> > streaming. That has a lot of range sets but is completely
> > legit. However, the ranges are in ascending order and don't
> > overlap. Maybe we could count overlaps and/or non-ascending
> > order ranges and fall back to 200 + the whole object if it
> > exceeds a limit.
>
> Right - and the other two use cases in the wild are
>
> - PDF readers - which fetch something at the start in RQ 1
> and then the index form the end - and then quick looks images for
> each page and title pages. I've seen them do a second and 3rd
> request with many 10's of ranges.
>
> - Some of the streaming video (semi/pro) video editors -
> which fetch a bunch of i-Frames and do clever skip over stuff. Not
> in the high tens; but 10-15 ranges common.
>
> - Likewise for very clever MXF professional editing equipment
> - the largest case (yup - it did crash my server) tried to fetch
> over 2000 ranges :)
>
> So I think we really should endeavor to allow 50 to a few 100 of
> them. Or at the very least - make it a config option to cut off
> below 50 or so.

Do you know if those clients send the ranges in order? If they are
sorted, it is easy to check if they are non-overlapping. And in that
case, we could easily allow 1000 ranges.

I'm cool w/ that… treat non-ascending ranges as potential hinky
and count those and only allow a certain number of them…

Still not sure if we should count overlaps as bad or not…
that RFC example troubles me:

14.35.1 Byte Ranges
- Several legal but not canonical specifications of the second 500
bytes (byte offsets 500-999, inclusive):
bytes=500-600,601-999
bytes=500-700,601-999

The 2nd seems to imply that one *MUST* merge adjacent overlaps to get the
correct response (500 bytes not 201+399=600bytes)

With all that in mind, I am still of the opinion that any
adjacent overlaps should be merged…

So how about we parse Range and merge all adjacent overlaps
(or merges (200-249,250-999 would merge into 200-999);
We then count how many non-ascends are in that revised set of
ranges and 200 out if it exceeds some config limit. We can also
provide some overall limit on the number of ranges, or at least
the ability to add one (a default of 0 means unlimited)…

Sound OK?

On Aug 24, 2011, at 4:39 PM, Greg Ames wrote:

> On Wed, Aug 24, 2011 at 3:19 PM, Jim Jagielski <jim@jagunet.com> wrote:
>
> >
> > If we only merge adjacent ascending ranges, then it seems like an attacker could just craft a header where the ranges jump around and dodge our fix.
> >
>
> I think no matter what, we should still have some sort of
> upper limit on the number of range-sets we accept… after all,
> merge doesn't prevent jumping around ;)
>
>
> The problem I have with the upper limit on the number of range sets is the use case someone posted for JPEG2000 streaming. That has a lot of range sets but is completely legit. However, the ranges are in ascending order and don't overlap. Maybe we could count overlaps and/or non-ascending order ranges and fall back to 200 + the whole object if it exceeds a limit.
>
> Greg

On Aug 24, 2011, at 5:00 PM, William A. Rowe Jr. wrote:
>
> At least, after 256 ranges or so, fall back to a 200 response in lieu of
> a 400/416 response.
>


+1 on not sending 416 if we hit some limit and fall back on 200.

On 8/24/2011 3:56 PM, Roy T. Fielding wrote:
> On Aug 24, 2011, at 8:35 AM, Tim Bannister wrote:
>
>> On Tue, Aug 23, 2011, Roy T. Fielding wrote:
>>> And the spec says ...
>>> When a client requests multiple ranges in one request, the
>>> server SHOULD return them in the order that they appeared in the
>>> request.
>>> My suggestion is to reject any request with overlapping ranges or more than five ranges with a 416, and to send 200 for any request with 4-5 ranges. There is simply no need to support random access in HTTP.
>>
>> Deshpande & Zeng in http://dx.doi.org/10.1145/500141.500197 describe a method for "streaming" JPEG 2000 documents over HTTP, using many more than 5 ranges in a single request.
>> A client that knows about any server-side limit could make multiple requests each with a small number of ranges, but discovering that limit will add latency and take more code.
>
> I have no interest in supporting such a use case over HTTP.
> Consider how stupid it is to request ranges like their example
>
> Range: bytes=120-168,175-200,205-300,345-346,400-500,555-666,
> 667-800,900-1000,2500-2567,2890-3056,5678-9000,
> 10000-12004,12050-12060,15600-15605,17000-17001,
> 17005-17010,17050-17060,17800-17905,20000-20005
>
> keeping in mind that between each one of those ranges will be
> a multipart boundary of approximately 80 bytes! Hence, any
> range request that contains gaps of less than 80 bytes should
> be considered a denial of service, or at least an idiot programmer
> that deserves to be slapped by Apache.
>
> To be clear, I am more than willing to rewrite the part on
> Ranges such that the above is explicitly forbidden in HTTP.
> I am not sure what the WG would agree to, but I am quite certain
> that part of the reason we have an Apache server is to protect
> the Internet from idiotic ideas like the above.

Then if we are opening up the spec for sensible revision, particularly
in the gray areas of what was not answered, insisting that the server
is free to respond to the client with any serialized superset of their
requested ranges [.deliberately ignoring the SHOULD in the section you
had previously quoted] is the right answer. In your pedantic case
above, adjacent ranges < 80 bytes apart would be processed as a
single merged range.

A client insisting on ranges must be prepared to follow the rules
provided to all proxies in that section on range handling, given that
the proxy case is already one user agent case, and the requirements
for proxy handling should certainly be applied in the generic case.

The spec does not actually state that ranges are returned 1:1 in
sequence, and I believe we should liberally read this to protect
the server from abuse. Perhaps we have a threshold number of
ranges which trigger the behavior, or any overlapping (apparently
abusive) range requests would trigger the behavior regardless.

On 8/24/2011 4:06 PM, Jim Jagielski wrote:
> I'm cool w/ that… treat non-ascending ranges as potential hinky
> and count those and only allow a certain number of them…
>
> Still not sure if we should count overlaps as bad or not…
> that RFC example troubles me:
>
> 14.35.1 Byte Ranges
> - Several legal but not canonical specifications of the second 500
> bytes (byte offsets 500-999, inclusive):
> bytes=500-600,601-999
> bytes=500-700,601-999
>
> The 2nd seems to imply that one *MUST* merge adjacent overlaps to get the
> correct response (500 bytes not 201+399=600bytes)
>
> With all that in mind, I am still of the opinion that any
> adjacent overlaps should be merged…
>
> So how about we parse Range and merge all adjacent overlaps
> (or merges (200-249,250-999 would merge into 200-999);
> We then count how many non-ascends are in that revised set of
> ranges and 200 out if it exceeds some config limit. We can also
> provide some overall limit on the number of ranges, or at least
> the ability to add one (a default of 0 means unlimited)…
>
> Sound OK?

Yup, sounds good. The only question is non-adjacent overlaps.
Given Roy's pedantic example, I believe we should also start to
dismiss any gap of less than X (80 bytes?) and provide those
bytes as well in the merged range.

Yes, clients may break. They were morons anyways for asking us
to skip a few bytes for them and increase network traffic. Once
the author accommodates the fact that they aren't in control, the
response is semantically accurate.

For that matter, perhaps User-Agent could be used to determine if
we have a backwards-broken client for which we fall into the very
well documented 200 response.

On Wed, Aug 24, 2011 at 5:06 PM, Jim Jagielski <jim@jagunet.com> wrote:

> I'm cool w/ that… treat non-ascending ranges as potential hinky
> and count those and only allow a certain number of them…
>
> Still not sure if we should count overlaps as bad or not…
> that RFC example troubles me:
>
> 14.35.1 Byte Ranges
> - Several legal but not canonical specifications of the second 500
> bytes (byte offsets 500-999, inclusive):
> bytes=500-600,601-999
> bytes=500-700,601-999
>
> The 2nd seems to imply that one *MUST* merge adjacent overlaps to get the
> correct response (500 bytes not 201+399=600bytes)
>
> With all that in mind, I am still of the opinion that any
> adjacent overlaps should be merged…
>

So how about we parse Range and merge all adjacent overlaps
> (or merges (200-249,250-999 would merge into 200-999);
> We then count how many non-ascends are in that revised set of
> ranges and 200 out if it exceeds some config limit.


Sounds good to me. Maybe re-define an overlap to include gaps of less than
80 bytes, per Roy's comments, and merge those too.


> We can also
> provide some overall limit on the number of ranges, or at least
> the ability to add one (a default of 0 means unlimited)…
>

sure, but it feels less urgent than the above.

Greg

On Aug 24, 2011, at 1:56 PM, Roy T. Fielding wrote:
> To be clear, I am more than willing to rewrite the part on
> Ranges such that the above is explicitly forbidden in HTTP.
> I am not sure what the WG would agree to, but I am quite certain
> that part of the reason we have an Apache server is to protect
> the Internet from idiotic ideas like the above.

http://trac.tools.ietf.org/wg/httpbis/trac/ticket/311

....Roy

On 8/24/2011 4:54 PM, Roy T. Fielding wrote:
> On Aug 24, 2011, at 1:56 PM, Roy T. Fielding wrote:
>> To be clear, I am more than willing to rewrite the part on
>> Ranges such that the above is explicitly forbidden in HTTP.
>> I am not sure what the WG would agree to, but I am quite certain
>> that part of the reason we have an Apache server is to protect
>> the Internet from idiotic ideas like the above.
>
> http://trac.tools.ietf.org/wg/httpbis/trac/ticket/311

Excellent, thanks. Just curious, isn't this clarification outside of
the remit of 2616bis?

On Aug 24, 2011, at 4:39 PM, William A. Rowe Jr. wrote:

> On 8/24/2011 4:54 PM, Roy T. Fielding wrote:
>> On Aug 24, 2011, at 1:56 PM, Roy T. Fielding wrote:
>>> To be clear, I am more than willing to rewrite the part on
>>> Ranges such that the above is explicitly forbidden in HTTP.
>>> I am not sure what the WG would agree to, but I am quite certain
>>> that part of the reason we have an Apache server is to protect
>>> the Internet from idiotic ideas like the above.
>>
>> http://trac.tools.ietf.org/wg/httpbis/trac/ticket/311
>
> Excellent, thanks. Just curious, isn't this clarification outside of
> the remit of 2616bis?

Security repairs are never out of scope.

....Roy

On 8/24/2011 6:43 PM, Roy T. Fielding wrote:
> On Aug 24, 2011, at 4:39 PM, William A. Rowe Jr. wrote:
>
>> On 8/24/2011 4:54 PM, Roy T. Fielding wrote:
>>> On Aug 24, 2011, at 1:56 PM, Roy T. Fielding wrote:
>>>> To be clear, I am more than willing to rewrite the part on
>>>> Ranges such that the above is explicitly forbidden in HTTP.
>>>> I am not sure what the WG would agree to, but I am quite certain
>>>> that part of the reason we have an Apache server is to protect
>>>> the Internet from idiotic ideas like the above.
>>>
>>> http://trac.tools.ietf.org/wg/httpbis/trac/ticket/311
>>
>> Excellent, thanks. Just curious, isn't this clarification outside of
>> the remit of 2616bis?
>
> Security repairs are never out of scope.

Ack.

So, I suspect the best we can do today, 4 days later, is to implement Roy's
draft [link] as the POC/reference implementation and work with the rest of
the http server community to ensure it is the right solution.

I suggest we publish this as a patch, /not/ as a release, until we find just
a bit more buy-in from the other implementors.

Bill

On Aug 24, 2011, at 4:56 PM, Roy T. Fielding wrote:

> On Aug 24, 2011, at 8:35 AM, Tim Bannister wrote:
>
>> On Tue, Aug 23, 2011, Roy T. Fielding wrote:
>>> And the spec says ...
>>> When a client requests multiple ranges in one request, the
>>> server SHOULD return them in the order that they appeared in the
>>> request.
>>> My suggestion is to reject any request with overlapping ranges or more than five ranges with a 416, and to send 200 for any request with 4-5 ranges. There is simply no need to support random access in HTTP.
>>
>> Deshpande & Zeng in http://dx.doi.org/10.1145/500141.500197 describe a method for "streaming" JPEG 2000 documents over HTTP, using many more than 5 ranges in a single request.
>> A client that knows about any server-side limit could make multiple requests each with a small number of ranges, but discovering that limit will add latency and take more code.
>
> I have no interest in supporting such a use case over HTTP.
> Consider how stupid it is to request ranges like their example
>
> Range: bytes=120-168,175-200,205-300,345-346,400-500,555-666,
> 667-800,900-1000,2500-2567,2890-3056,5678-9000,
> 10000-12004,12050-12060,15600-15605,17000-17001,
> 17005-17010,17050-17060,17800-17905,20000-20005
>
> keeping in mind that between each one of those ranges will be
> a multipart boundary of approximately 80 bytes! Hence, any
> range request that contains gaps of less than 80 bytes should
> be considered a denial of service, or at least an idiot programmer
> that deserves to be slapped by Apache.
>
> To be clear, I am more than willing to rewrite the part on
> Ranges such that the above is explicitly forbidden in HTTP.
> I am not sure what the WG would agree to, but I am quite certain
> that part of the reason we have an Apache server is to protect
> the Internet from idiotic ideas like the above.
>

OK then… we seem to be coalescing into some consensus here…
basically, if the client sends stuff which is brain-dead stupid,
we simply 2000 and send the whole kit-and-kaboodle.

I'd like to propose that we update the byterange filter to perform
the following:

o coalesce all adjacent ranges, whether overlapping or not.
(eg: 200-250,251-300 & 200-250,220-300 both merge to 200-300)
o We count:
> the number of times a gap between ranges is <80bytes
> the number of times we hit a descendent range
(eg: 200-1000,2000-3000,1200-1500,4000-5000 would count as 1)
> the number of ranges total (post ascending merge)
If any >= some config-time limit, we send a 200

This is a start and was chosen simply for ease of implementation…
We can then expand it to be more functional…

Comments?

On Aug 24, 2011, at 5:54 PM, Roy T. Fielding wrote:

> On Aug 24, 2011, at 1:56 PM, Roy T. Fielding wrote:
>> To be clear, I am more than willing to rewrite the part on
>> Ranges such that the above is explicitly forbidden in HTTP.
>> I am not sure what the WG would agree to, but I am quite certain
>> that part of the reason we have an Apache server is to protect
>> the Internet from idiotic ideas like the above.
>
> http://trac.tools.ietf.org/wg/httpbis/trac/ticket/311
>

This is why I still love httpd...

On Thursday 25 August 2011, Jim Jagielski wrote:
> OK then… we seem to be coalescing into some consensus here…
> basically, if the client sends stuff which is brain-dead stupid,
> we simply 2000 and send the whole kit-and-kaboodle.
>
> I'd like to propose that we update the byterange filter to perform
> the following:
>
> o coalesce all adjacent ranges, whether overlapping or not.
> (eg: 200-250,251-300 & 200-250,220-300 both merge to 200-300)

This may still confuse a broken client. Maybe we could omit that from
the 2.2 patch for now and only commit to 2.3.

> o We count:
> > the number of times a gap between ranges is <80bytes
> > the number of times we hit a descendent range
> (eg: 200-1000,2000-3000,1200-1500,4000-5000 would count as
> 1) > the number of ranges total (post ascending merge)
> If any >= some config-time limit, we send a 200
>
> This is a start and was chosen simply for ease of implementation…
> We can then expand it to be more functional…
>
> Comments?

Please also look at the patch at

http://mail-archives.apache.org/mod_mbox/httpd-
dev/201108.mbox/%3C201108250138.49474.sf@sfritsch.de%3E

which greatly reduces the memory needed for the range requests.
BTW, I won't have time to beat that into shape today. If anyone else
has, please go ahead.

> -----Original Message-----
> From: Stefan Fritsch
> Sent: Donnerstag, 25. August 2011 08:21
> To: dev@httpd.apache.org
> Subject: Re: DoS with mod_deflate & range requests
>
> On Thursday 25 August 2011, Jim Jagielski wrote:
> > OK then... we seem to be coalescing into some consensus here...
> > basically, if the client sends stuff which is brain-dead stupid,
> > we simply 2000 and send the whole kit-and-kaboodle.
> >
> > I'd like to propose that we update the byterange filter to perform
> > the following:
> >
> > o coalesce all adjacent ranges, whether overlapping or not.
> > (eg: 200-250,251-300 & 200-250,220-300 both merge to 200-300)
>
> This may still confuse a broken client. Maybe we could omit that from
> the 2.2 patch for now and only commit to 2.3.

Sounds like a plan. Or make it configurable with a default of off in 2.2.x
and on in 2.3.x

>
> > o We count:
> > > the number of times a gap between ranges is <80bytes
> > > the number of times we hit a descendent range
> > (eg: 200-1000,2000-3000,1200-1500,4000-5000 would count as
> > 1) > the number of ranges total (post ascending merge)
> > If any >= some config-time limit, we send a 200
> >
> > This is a start and was chosen simply for ease of implementation...
> > We can then expand it to be more functional...
> >
> > Comments?


Looks good. Plus we should implement the patch from Stefan below and then we
should be good.

>
> Please also look at the patch at
>
> http://mail-archives.apache.org/mod_mbox/httpd-
> dev/201108.mbox/%3C201108250138.49474.sf@sfritsch.de%3E
>
> which greatly reduces the memory needed for the range requests.
> BTW, I won't have time to beat that into shape today. If anyone else
> has, please go ahead.
>

Regards

Rüdiger

On Aug 25, 2011, at 2:56 AM, Plüm, Rüdiger, VF-Group wrote:

>
>
>> -----Original Message-----
>> From: Stefan Fritsch
>> Sent: Donnerstag, 25. August 2011 08:21
>> To: dev@httpd.apache.org
>> Subject: Re: DoS with mod_deflate & range requests
>>
>> On Thursday 25 August 2011, Jim Jagielski wrote:
>>> OK then... we seem to be coalescing into some consensus here...
>>> basically, if the client sends stuff which is brain-dead stupid,
>>> we simply 2000 and send the whole kit-and-kaboodle.
>>>
>>> I'd like to propose that we update the byterange filter to perform
>>> the following:
>>>
>>> o coalesce all adjacent ranges, whether overlapping or not.
>>> (eg: 200-250,251-300 & 200-250,220-300 both merge to 200-300)
>>
>> This may still confuse a broken client. Maybe we could omit that from
>> the 2.2 patch for now and only commit to 2.3.
>
> Sounds like a plan. Or make it configurable with a default of off in 2.2.x
> and on in 2.3.x
>
>>
>>> o We count:
>>>> the number of times a gap between ranges is <80bytes
>>>> the number of times we hit a descendent range
>>> (eg: 200-1000,2000-3000,1200-1500,4000-5000 would count as
>>> 1) > the number of ranges total (post ascending merge)
>>> If any >= some config-time limit, we send a 200
>>>
>>> This is a start and was chosen simply for ease of implementation...
>>> We can then expand it to be more functional...
>>>
>>> Comments?
>
>
> Looks good. Plus we should implement the patch from Stefan below and then we
> should be good.
>

++1 (see other thread: Fixing Ranges)