Front page | perl.perl5.porters |
Postings from October 2003
Re: Perl 5.8.1, plan C, and algorithmic complexity attacks.
Thread Previous
|
Thread Next
From:
Scott A Crosby
Date:
October 22, 2003 02:44
Subject:
Re: Perl 5.8.1, plan C, and algorithmic complexity attacks.
Message ID:
oydfzhlbo9j.fsf@bert.cs.rice.edu
On Tue, 21 Oct 2003 22:44:48 +0100, Nicholas Clark <nick@ccl4.org> writes:
> On Tue, Oct 21, 2003 at 04:26:27PM -0500, Scott A Crosby wrote:
>
> > AFAIK, you switch from the past predictable hash function to a new
> > randomized one only when you detect that you're under attack. I have a
> > couple of concerns:
> >
> > 1. How do you dectect 'under attack', and is it possible to
> > construct an attack while not triggering the rekey & rehash?
>
I dislike switching algorithms like this proposal because it is too
easy to make a mistake and not accurately detect when you're under
attack. For instance, the proposal below has two mistakes, one that
someone else already noticed, and a different one that I haven't seen
anyone mention.
If you need to do a scheme like this for binary compatibility, I hope
you rip it out in the next major version and just randomize everything.
> Currently the criteria is that if the longest linked list in the hash
> contains >50% of the entries then the rehashing is triggered
This can be avoided by an attack where the attack inputs hash to two
distinct values. That way, each chain is only half as long, but we
avoid the trigger to randomly rekey and rehash. The attack exists with
its effectiveness reduced by only a half.
> (strictly this is at a hash split, when the number of buckets is doubled,
> and it is skipped if the longest linked is < 8, or we're already on
> the alternative hashing function)
This check is also easy to avoid. If you only check 'under attack'
when the number of keys doubles during a rehash, the attacker can
'preload' the hash table with $2^n+3$ keys, perfectly distributed
among all hash values, then send $2^n-3$ attack keys. Since the hash
table won't rehash until $2*2^n$ keys are inserted, it won't notice
its under attack until the $2^n-3$ are all inserted, costing quadratic
time. Thus, the attack still exists; its effectiveness is only reduced
by three quarters.
If you go this way where you change the hash function when you detect
attack, you need to do that check for too long chains on every insert.
> > 2. When you rekey and rehash with a new random key, how do you avoid
> > potentially rehashing endlessly. Is it possible to engage in a new
> > attack by forcing endless rehashings instead of lots of collisions?
>
> There is only one rekeying done. I'm assuming that that works.
Yes, its good. Thanks for explaining.
> I hope this answers your questions.
Yes. Thanks. Please don't forget to CC me, I'm not on the list.
> We almost need a FAQ :-)
:)
> More maths or experimentation on what the "attack" criteria should be is
> welcome.
Well, there's always regexp DoS's. :) PCRE has a way to limit its node
expansiosn before it gives up, as a brake on this sort of attack.
Scott
Thread Previous
|
Thread Next