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. 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...@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.
RE: DoS with mod_deflate range requests
-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...@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
Re: DoS with mod_deflate range requests
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)
Re: DoS with mod_deflate range requests
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.
RE: DoS with mod_deflate range requests
-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
Re: DoS with mod_deflate range requests
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
Re: DoS with mod_deflate range requests
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
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. And then it is fine. Dw
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...
RE: DoS with mod_deflate range requests
-Original Message- From: Dirk-Willem van Gulik [mailto:dirk-willem.van.gu...@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
Re: DoS with mod_deflate range requests
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
RE: DoS with mod_deflate range requests
-Original Message- From: Jim Jagielski [mailto:j...@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
RE: DoS with mod_deflate range requests
-Original Message- From: Jim Jagielski [mailto:j...@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
Re: DoS with mod_deflate range requests
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.
Re: DoS with mod_deflate range requests
On Aug 24, 2011, at 12:05 PM, Plüm, Rüdiger, VF-Group wrote: -Original Message- From: Jim Jagielski [mailto:j...@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...
Re: DoS with mod_deflate range requests
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...
Re: DoS with mod_deflate range requests
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:j...@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.
Re: DoS with mod_deflate range requests
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 – is...@jellybaby.net
Re: DoS with mod_deflate range requests
On Wed, Aug 24, 2011 at 12:42 PM, Jim Jagielski j...@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
Re: DoS with mod_deflate range requests
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...
Re: DoS with mod_deflate range requests
On Aug 24, 2011, at 3:10 PM, Greg Ames wrote: On Wed, Aug 24, 2011 at 12:42 PM, Jim Jagielski j...@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 ;)
Re: DoS with mod_deflate range requests
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.
Re: DoS with mod_deflate range requests
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.
Re: DoS with mod_deflate range requests
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 – is...@jellybaby.net
Re: DoS with mod_deflate range requests
On Wed, Aug 24, 2011 at 3:19 PM, Jim Jagielski j...@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
Re: DoS with mod_deflate range requests
On 24 Aug 2011, at 21:39, Greg Ames wrote: On Wed, Aug 24, 2011 at 3:19 PM, Jim Jagielski j...@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.
Re: DoS with mod_deflate range requests
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, 1-12004,12050-12060,15600-15605,17000-17001, 17005-17010,17050-17060,17800-17905,2-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
Re: DoS with mod_deflate range requests
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
Re: DoS with mod_deflate range requests
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 j...@jagunet.com mailto:j...@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.
Re: DoS with mod_deflate range requests
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.
Re: DoS with mod_deflate range requests
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.
Re: DoS with mod_deflate range requests
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 j...@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
Re: DoS with mod_deflate range requests
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.
Re: DoS with mod_deflate range requests
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, 1-12004,12050-12060,15600-15605,17000-17001, 17005-17010,17050-17060,17800-17905,2-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.
Re: DoS with mod_deflate range requests
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.
Re: DoS with mod_deflate range requests
On Wed, Aug 24, 2011 at 5:06 PM, Jim Jagielski j...@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
Re: DoS with mod_deflate range requests
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
Re: DoS with mod_deflate range requests
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?
Re: DoS with mod_deflate range requests
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
Re: DoS with mod_deflate range requests
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
Re: DoS with mod_deflate range requests
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, 1-12004,12050-12060,15600-15605,17000-17001, 17005-17010,17050-17060,17800-17905,2-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?
Re: DoS with mod_deflate range requests
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...
RE: DoS with mod_deflate range requests
-Original Message- From: Stefan Fritsch [mailto:s...@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
Re: DoS with mod_deflate range requests
2011/8/23 Stefan Fritsch s...@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: 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 ?
Re: DoS with mod_deflate range requests
On Tue, Aug 23, 2011 at 02:15:16PM +0200, Lazy wrote: 2011/8/23 Stefan Fritsch s...@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: 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
Re: DoS with mod_deflate range requests
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?
Re: DoS with mod_deflate 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).
Re: DoS with mod_deflate range requests
please tell me how to unsubscribe from this mailing list On Tue, Aug 23, 2011 at 9:49 PM, Stefan Fritsch s...@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
Re: DoS with mod_deflate range requests
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.
Re: DoS with mod_deflate range requests
On Tue, Aug 23, 2011 at 3:32 PM, William A. Rowe Jr. wr...@rowe-clan.netwrote: 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
Re: DoS with mod_deflate range requests
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.
Re: DoS with mod_deflate range requests
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-h...@httpd.apache.org list-unsubscribe: mailto:dev-unsubscr...@httpd.apache.org List-Post: mailto:dev@httpd.apache.org List-Id: dev.httpd.apache.org signature.asc Description: OpenPGP digital signature
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.
diff --git a/modules/http/byterange_filter.c b/modules/http/byterange_filter.c
index 13bf0a1..6a40420 100644
--- a/modules/http/byterange_filter.c
+++ b/modules/http/byterange_filter.c
@@ -61,6 +61,11 @@
APLOG_USE_MODULE(http);
+/* returns
+ * 0 if range invalid or whole file
+ * +1 for valid range spec
+ * -1 for start end
+ */
static int parse_byterange(char *range, apr_off_t clength,
apr_off_t *start, apr_off_t *end)
{
@@ -114,13 +119,6 @@ static int parse_byterange(char *range, apr_off_t clength,
static int ap_set_byterange(request_rec *r);
-typedef struct byterange_ctx {
-apr_bucket_brigade *bb;
-int num_ranges;
-char *boundary;
-char *bound_head;
-} byterange_ctx;
-
/*
* Here we try to be compatible with clients that want multipart/x-byteranges
* instead of multipart/byteranges (also see above), as per HTTP/1.1. We
@@ -136,26 +134,43 @@ static int use_range_x(request_rec *r)
ap_strstr_c(ua, MSIE 3)));
}
+struct range_spec {
+apr_off_t start, end;
+};
+
+static int sort_fn(const void *a_, const void *b_)
+{
+const struct range_spec *a = a_, *b = b_;
+if (a-start b-start)
+return -1;
+else if (a-start == b-start)
+return 0;
+else
+return 1;
+}
+
#define BYTERANGE_FMT % APR_OFF_T_FMT -% APR_OFF_T_FMT /% APR_OFF_T_FMT
#define PARTITION_ERR_FMT apr_brigade_partition() failed \
[% APR_OFF_T_FMT ,% APR_OFF_T_FMT ]
+#define MAX(o1, o2) ((o1 o2) ? o1 : o2)
AP_CORE_DECLARE_NONSTD(apr_status_t) ap_byterange_filter(ap_filter_t *f,
apr_bucket_brigade *bb)
{
-#define MIN_LENGTH(len1, len2) ((len1 len2) ? len2 : len1)
request_rec *r = f-r;
conn_rec *c = r-connection;
-byterange_ctx *ctx;
apr_bucket *e;
apr_bucket_brigade *bsend;
-apr_off_t range_start;
-apr_off_t range_end;
+apr_off_t max = 0;
char *current;
apr_off_t clength = 0;
apr_status_t rv;
-int found = 0;
+int found = 0, i = 0;
+int need_sort = 0;
int num_ranges;
+char *boundary = NULL;
+char *bound_head = NULL;
+struct range_spec *ranges;
/* Iterate through the brigade until reaching EOS or a bucket with
* unknown length. */
@@ -183,64 +198,78 @@ AP_CORE_DECLARE_NONSTD(apr_status_t) ap_byterange_filter(ap_filter_t *f,
return ap_pass_brigade(f-next, bb);
}
-ctx = apr_pcalloc(r-pool, sizeof(*ctx));
-ctx-num_ranges = num_ranges;
-/* create a brigade in case we never call ap_save_brigade() */
-ctx-bb = apr_brigade_create(r-pool, c-bucket_alloc);
-
-if (ctx-num_ranges 1) {
+if (num_ranges 1) {
/* Is ap_make_content_type required here? */
const char *orig_ct = ap_make_content_type(r, r-content_type);
-ctx-boundary = apr_psprintf(r-pool, % APR_UINT64_T_HEX_FMT %lx,
- (apr_uint64_t)r-request_time, (long) getpid());
+boundary = apr_psprintf(r-pool, % APR_UINT64_T_HEX_FMT %lx,
+(apr_uint64_t)r-request_time, (long) getpid());
ap_set_content_type(r, apr_pstrcat(r-pool, multipart,
use_range_x(r) ? /x- : /,
Re: DoS with mod_deflate range requests
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
