[Python-Dev] Algoritmic Complexity Attack on Python

[Tim Peters]

[Phillip J. Eby]
> ...
> or at least warning the developers of alternatives to CGI (e.g. Zope,
> Quixote, SkunkWeb, CherryPy, etc.) that alternate hashes might be a good
> idea.

Don't know about SkunkWeb or CherryPy etc, but Zope and Quixote apps can use
ZODB's BTrees for mappings.  Insertion and lookup in a BTree have worst-case
log-time behavior, and no "bad" sets of keys exist for them.  The Buckets
forming the leaves of BTrees are vulnerable, though:  provoking
quadratic-time behavior in a Bucket only requires inserting keys in
reverse-sorted order, and sometimes apps use Buckets directly when they
should be using BTrees.

Using a data structure appropriate for the job at hand is usually a good
idea <wink>.