denial of service of too many headers in response

[Guillaume Pernot]

can DoS tinyproxy with too many headers in response.

see https://banu.com/bugzilla/show_bug.cgi?id=110#c2

ProblemType: Bug
DistroRelease: Ubuntu 12.04
Package: tinyproxy (not installed)
ProcVersionSignature: Ubuntu 3.2.0-29.46-generic 3.2.24
Uname: Linux 3.2.0-29-generic x86_64
NonfreeKernelModules: openafs nvidia
ApportVersion: 2.0.1-0ubuntu12
Architecture: amd64
Date: Wed Aug 15 09:28:26 2012
ProcEnviron:
 TERM=xterm
 PATH=(custom, no user)
 LANG=fr_FR.UTF-8
 SHELL=/bin/bash
SourcePackage: tinyproxy
UpgradeStatus: No upgrade log present (probably fresh install)

[Guillaume Pernot (gpernot)]

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...).

[Guillaume Pernot (gpernot)]

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

[Guillaume Pernot (gpernot)]

Created attachment 60
limit number of headers to prevent DoS attacks

[Jamie Strandboge (jdstrand)]

Thanks for taking the time to report this bug and helping to make Ubuntu better. Since the package referred to in this bug is in universe or multiverse, it is community maintained. If you are able, I suggest coordinating with upstream and posting a debdiff for this issue. When a debdiff is available, members of the security team will review it and publish the package. See the following link for more information: https://wiki.ubuntu.com/SecurityTeam/UpdateProcedures

[Jamie Strandboge (jdstrand)]

I have requested a CVE for this on oss-security: http://www.openwall.com/lists/oss-security/2012/08/17/3

[Ubuntu Foundations Team Bug Bot (crichton)]

The attachment "limit number of headers to prevent DoS attacks" of this bug report has been identified as being a patch. The ubuntu-reviewers team has been subscribed to the bug report so that they can review the patch. In the event that this is in fact not a patch you can resolve this situation by removing the tag 'patch' from the bug report and editing the attachment so that it is not flagged as a patch. Additionally, if you are member of the ubuntu-reviewers team please also unsubscribe the team from this bug report.

[This is an automated message performed by a Launchpad user owned by Brian Murray. Please contact him regarding any issues with the action taken in this bug report.]

[Kurt (kurt-redhat-bugs)]

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

[Kurt (kurt-redhat-bugs)]

Created tinyproxy tracking bugs for this issue

Affects: fedora-all [bug 849369]

[Kurt (kurt-redhat-bugs)]

Created tinyproxy tracking bugs for this issue

Affects: epel-all [bug 849370]

[Kurt (kurt-redhat-bugs)]

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

[Kurt (kurt-redhat-bugs)]

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

[Logan Rosen (logan)]

I have filed a sync request from Debian in Bug 1059887.

[Jeremy Bícha (jbicha)]

This bug was fixed in the package tinyproxy - 1.8.3-3

---------------
tinyproxy (1.8.3-3) unstable; urgency=high

  * Add patches for CVE-2012-3505 (closes: #685281):
    - CVE-2012-3505-tinyproxy-limit-headers.patch: Limit the number of
      headers to prevent DoS attacks.
    - CVE-2012-3505-tinyproxy-randomized-hashmaps.patch: Randomize hashmaps
      in order to avoid fake headers getting included in the same bucket,
      allowing for DoS attacks.
    Bug reported and patches contributed by gpernot.

 -- Jordi Mallach <email address hidden> Mon, 24 Sep 2012 21:05:41 +0200

[Michael Adam (obnox)]

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

[Michael Adam (obnox)]

Created attachment 62
updated version of the hash seeding patch

slightly polished version of the seeding patch.

[Michael Adam (obnox)]

Created attachment 63
updated version of the header limiting patch

[Michael Adam (obnox)]

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

[Mukund Sivaraman (muks)]

(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.

[Jan Engelhardt (jengelh)]

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.

[Michael (michael-redhat-bugs)]

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

[Michael Adam (obnox)]

Fix pushed to upstream and will be released very soon in tinyproxy 1.8.4.

[Michael (michael-redhat-bugs)]

Upstream release including fix available at

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

(Note: upstream hosting is currently changing.)

[Steve Beattie (sbeattie)]

This was fixed in precise in:

tinyproxy (1.8.3-1ubuntu0.1) precise-security; urgency=low

  * SECURITY UPDATE: Fix for denial of service vulnerability where remote
    attackers send crafted request headers. (LP: #1154502)
    - debian/patches/001-CVE-2012-3505.patch: Limit the number of headers to
      prevent DoS attacks. Randomize hashmaps in order to avoid fake headers
      getting included in the same bucket, allowing for DoS attacks.
    - CVE-2012-3505
 -- Christian Kuersteiner <email address hidden> Wed, 13 Mar 2013 16:42:14 +0700

Closing the precise task.