[ZCM] [ZC] 605/ 3 Resolve "potential DoS in ZTUtils' Tree code"

[Collector: Zope Bugs, Features, and Patches ...]

Issue #605 Update (Resolve) "potential DoS in ZTUtils' Tree code"
 ** Security Related ** (Public)
 Status Resolved, Zope/bug medium
To followup, visit:
  http://collector.zope.org/Zope/605

==============================================================
= Resolve - Entry #3 by mj on Oct 4, 2002 11:02 am

 Status: Accepted => Resolved

Fix checked into 2.5 and 2.6 branches, and the trunk.
________________________________________
= Accept_confidential - Entry #2 by mj on Oct 4, 2002 10:28 am

 Status: Pending => Accepted

 Supporters added: mj

Okay, I'll put in a hard limit for the string length.

As the ZTUtils trees are always dynamic, and we cannot expect people to go and tell it the number of nodes the tree may have, we can only limit the length of the string to decode.

We'll set the limit to 8K for now. A fully expanded tree with an average depth of 10 will still allow some 340 expansion ids in the string, which would make a pretty big tree. This kind of state encoding could only be passed in through a POST anyway. If you need to encode the state of a larger tree, you'll have to resort to using a SESSION, where encoding the expansion state wouldn't even be needed.
________________________________________
= Request - Entry #1 by Anonymous User on Oct 3, 2002 6:38 pm

Keeping with the theme of my last tree-related DoS attack, we now try to exploit the ZTUtils code.  (Truth be known I found this one first, but its not quite as bad as its much easier to fix.)

ZTUtils/Tree.py encodes expansions in ':' delimited sequences.  The decoding process is relatively in-expensive involving only a dictionary and a list, and a few references, but by handing really long expansion encodings to the decoder you can nickel & dime your machine to death.  For example consider the "encoding" as offered with:

$ w3m -cookie "tree-state="`perl -e 'print "A:"x50000;'`"A" http://example.com/page/with/zt-tree

Luckily this bug is largely mitigated by a few external factors.  1) most web servers limit the header length on incoming requests (apache uses 4k by default IIRC)
2) zlib compression isn't supported in zlib so you can't send a zip bomb.

Unfortunately ZServer isn't in the category of "most" web servers. (thats my next bug, *sigh*)  So people using ZServer on a bare wire to the net, and the ZTUtils tree code are quite vulnerable to attack.

The workaround I developed for the ExpansionTree Product was to enforce limits on the expasion encoding content, specifically on the number of what I term "expansion ids".  An expansion id is an element of an expansion encoding which may either be a node id or a depth encoding of the following node.  I count() the number of ':' characters in the expansion encoding and raise an exception if they are over a user supplied limit.  Reasonable limits for static trees are easy to calculate using the worst-case scenario tree consisting solely of a root node and N children. (I define worst-case as a tree with the most possible depth expansion ids per node ids.) The equation is simply 2N-2 (and I tend to let a slop of 1 roll around in my conditional so people who expand a tree out all the way can actually close it again, but I digress).
Dynamic trees aren't quite as easy, you basically have to just define an upper growth limit that you know won't swamp your machine with the calculations.  Anyway attack strings over the limit will be caught this way before the costly data structures are built in the decoding process, effectively eliminating the attack vector.

Limits are poorly documented in my ExpansionTree product because I wanted to give ZC a chance to fix the the ZTUtils code before I explained why they existed in  my code in depth.  Anyone who thinks about web security on a regular basis though is gonna be able to figure it out should they read my docs (which lets face it, is unlikely).

Anyhow, thats my workaround, if you have other ideas I'd be happy to know about them.
==============================================================