Author lemburg
Recipients Arfrever, Giovanni.Bajo, PaulMcMillan, ReneSac, Vlado.Boza, alex, arigo, benjamin.peterson, camara, christian.heimes, cvrebert, dmalcolm, gregory.p.smith, haypo, koniiiik, lemburg, mark.dickinson, sbermeister, serhiy.storchaka, Łukasz.Rekucki
Date 2012-11-30.20:34:36
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <50B91853.8050206@egenix.com>
In-reply-to <1354305992.63.0.159104942898.issue14621@psf.upfronthosting.co.za>
Content
On 30.11.2012 21:06, Serhiy Storchaka wrote:
> 
> Serhiy Storchaka added the comment:
> 
> René, a balanced tree requires rebalancing on every (or almost every) item for some special (sorted) data sequences.

Sure, but that's still O(N*log N) for an attack scenario, not O(N^2).

I think the main point here is that using hash tables or dictionaries
for these things without any size limit is simply a wrong development
approach.

Developers need to be made aware of the problem and given data
structures that they can use more safely to store the data and
instead of trying to hide away the problem using some crypto
approach, it's better to offer methods that allow developers to
gain control over the problem (e.g. via an exception) rather than
hoping for few hash collisions.

If a developer has to build a lookup table from untrusted data,
she should be able to say:

try:
    mapping = insert_untrusted_data(source)
except UnderAttackError:
    return 'no thank you'

instead of:

# Hmm, let's hope this doesn't bomb...
mapping = insert_untrusted_data(source)

At the moment, the best thing you can do is insert the data
in chunks and measure the time it takes for each chunk. If it
takes too long, you raise the UnderAttackError.

If we make the collision counting limit a per-dictionary adjustable
limit with some global default limit, the above could be written
as:

try:
    mapping = {}
    mapping.max_collisions = 100
    mapping.update(source)
except CollisionLimitError:
    return 'no thank you'

Aside: It's better to know you worst case and program for it, rather
than to ignore the problem and hope an attacker won't find your secret
key. In the above case, if you know what the worst-case timing is for
a 100-item dictionary, you can safely deal with it, possibly adjusting
the limit to more suitable value for your application.

-- 
Marc-Andre Lemburg
eGenix.com

Professional Python Services directly from the Source  (#1, Nov 30 2012)
>>> Python Projects, Consulting and Support ...   http://www.egenix.com/
>>> mxODBC.Zope/Plone.Database.Adapter ...       http://zope.egenix.com/
>>> mxODBC, mxDateTime, mxTextTools ...        http://python.egenix.com/
________________________________________________________________________
2012-11-28: Released eGenix mx Base 3.2.5 ...     http://egenix.com/go36
2013-01-22: Python Meeting Duesseldorf ...                 53 days to go

::: Try our new mxODBC.Connect Python Database Interface for free ! ::::

   eGenix.com Software, Skills and Services GmbH  Pastor-Loeh-Str.48
    D-40764 Langenfeld, Germany. CEO Dipl.-Math. Marc-Andre Lemburg
           Registered at Amtsgericht Duesseldorf: HRB 46611
               http://www.egenix.com/company/contact/
History
Date User Action Args
2012-11-30 20:34:37lemburgsetrecipients: + lemburg, arigo, gregory.p.smith, mark.dickinson, haypo, christian.heimes, benjamin.peterson, Arfrever, alex, cvrebert, dmalcolm, Giovanni.Bajo, PaulMcMillan, serhiy.storchaka, Vlado.Boza, koniiiik, sbermeister, camara, Łukasz.Rekucki, ReneSac
2012-11-30 20:34:37lemburglinkissue14621 messages
2012-11-30 20:34:36lemburgcreate