Luke, On 12/29/11 12:35 PM, Luke Meyer wrote: >> From: Mark Thomas >>> While both POST-size-limiting and parameter-count-limiting are >>> both reasonable mitigating procedures, would the use of a >>> randomized-hash be something worth doing? >> >> I don't know. My instinct is that it wouldn't but I could be wrong. > > Referring to > https://cryptanalysis.eu/blog/2011/12/28/effective-dos-attacks-against-web-application-plattforms-hashdos/ > - seems like it is at least worth considering. It leaves the hashing > algorithm at O(1) in the normal case and makes it pretty difficult > (depending on size of salt-space) to pick keys that will collide.
Well, the idea is that each server (or even each request) has a completely random salt that can't be predicted so picking colliding keys would very rarely work. Of course, getting a perfect match one time is all it takes to tie-up a thread for a very long time. >> Before changing anything, we'd need to look hard at performance >> figures and take any additional maintenance overhead into >> consideration. >> >> Performance was the reason I didn't just switch to TreeMap. > > Makes sense. How about using a factory-style method in, say, the Context interface that is implemented by StandardContext to just return a new HashMap. An alternative implementation could return a new TreeMap instead. > Worth noting that TreeMap makes all storage O(log n), so the normal > case takes a hit in order to mitigate the worst case (i.e. malicious > case). When n is small, though, O(n) ~= O(log n). I'd be interested to see the relative performance of each of these implementations. A straightforward test can be performed to test raw speed, but the memory-versus-protection issue is really a subjective one. I would venture a guess that most webapps aren't accepting tens of thousands or even thousands of parameters per request. Perhaps some special requests would allow that kind of thing to occur (e.g. some big batch or very complicated data submission) and can be handled either differently or using a less-than-optimal algorithmic complexity. -chris
signature.asc
Description: OpenPGP digital signature
