denial of service of too many headers in response

Created attachment 59
randomized hashmaps to prevent DOS attacks

hashmap are not randomized, so that it is possible to forge fake headers that will always go into the same bucket.
try 'curl http://78.230.4.96/hashes.asis' via tinyproxy and without it to convince you (~8 MB of headers). I'll remove this url as soon as bug is accepted...

attached patch should solve this. it's certainly perfectible, though (autoconf for time() and rand() are missing...).

even with this patch, it takes ages. maybe headers should be sanitized before hiting the buckets...

Created attachment 60
limit number of headers to prevent DoS attacks

gpernot reports:

Bug 110 - algorithmic complexity denial of service

randomized hashmaps to prevent DOS attacks

hashmap are not randomized, so that it is possible to forge fake headers that
will always go into the same bucket.
try 'curl http://78.230.4.96/hashes.asis' via tinyproxy and without it to
convince you (~8 MB of headers). I'll remove this url as soon as bug is
accepted...

attached patch should solve this. it's certainly perfectible, though
(autoconf for time() and rand() are missing...).

even with this patch, it takes ages. maybe headers should be sanitized before
hiting the buckets...

Created attachment 60 [details]
limit number of headers to prevent DoS attacks

External references:
https://banu.com/bugzilla/show_bug.cgi?id=110#c2
https://bugs.launchpad.net/ubuntu/+source/tinyproxy/+bug/1036985

Created tinyproxy tracking bugs for this issue

Affects: fedora-all [bug 849369]

Created tinyproxy tracking bugs for this issue

Affects: epel-all [bug 849370]

Created attachment 605402
CVE-2012-3505-tinyproxy-limit-headers.patch

Created attachment 605403
CVE-2012-3505-tinyproxy-randomized-hashmaps.patch

Hi.

Thanks for the report and the patch!
And sorry for the long delay.

I have made minor modifications to the patches.
(will attach next).

I have to admit though, that I did not quite understand the problem though.
The seeding of the hash seems reasonabe in any case, but for, the loading of your hashes page takes approximately the same time
- without a proxy
- with unpatched tinyproxy
- with patched tinyproxy.

Maybe it is simply too late here and I am doing something wrong,
but could you please explain some more what you are experiencing
with and without the patches?

Thanks - Michael

Created attachment 62
updated version of the hash seeding patch

slightly polished version of the seeding patch.

Created attachment 63
updated version of the header limiting patch

To be quite clear: I see the danger of hash collisions and also understand the risk of higher CPU consumption when the hashes collide since behind a hash, we have a linear list in the bucket.

But since the "hashofheaders" is currently only built of 32 buckets,
(i.e. a 5 bit hash), with a big number of headers, we will have many
many collisions anyway. So I dont't quite see the point. What am I thinking wrong?

Maybe we should use a tree implementation, e.g. an rbtree.
That would give us really quick searching.

Cheers - Michael

(In reply to comment #6)
> Maybe we should use a tree implementation, e.g. an rbtree.
> That would give us really quick searching.

Pickup an rbtree implementation from the tofu repo:
https://banu.com/cgit/tofu/tree/tofu/

It's standalone and would need some minor editing to remove the tofu prefixes from symbols. Deletion from this tree is not possible though (as it's unnecessary in tofu). If we want deletion, I'll give you another local implementation.

Created attachment 65
Using maps from libHX

Supports deletion, etc.

This needs more testing because I am not sufficiently familiar with tinyproxy to get this crash-free.

Believe it or not:
Fixes pushed to upstream and will be released soon with Tinyproxy 1.8.4.

Upstream release including fix available at

https://github.com/tinyproxy/tinyproxy/releases/tag/1.8.4

(Note: upstream hosting is currently changing.)