bugtraq - Re: Algorimic Complexity Attacks

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20030607181144.2D0.0@Bobanek.nowhere.cz>
Date: Sat, 7 Jun 2003 19:01:06 +0200 (MET DST)
From: "Pavel Kankovsky" <peak@...o.troja.mff.cuni.cz>
To: bugtraq@...urityfocus.com
Subject: Re: Algorimic Complexity Attacks

On Sat, 31 May 2003, Solar Designer wrote:

> This is precisely one of the attacks which have been considered,
> avoided(*), and documented in my Phrack #53 article entitled "Designing
> and Attacking Port Scan Detection Tools" - "Data Structures and
> Algorithm Choice" back in 1998.

Of course, this kind of solution (throwing the data causing excessive
collisions away) is unacceptable for many applications.

> Changing the secret once in a while reduces this attack and may well
> make it impractical with many particular applications.  Note that one
> doesn't have to use any additional true randomness (and possibly
> exhaust the randomness pool) for each new secret to be used with the
> keyed hash.  If the secret itself is not leaked in the attack (and it
> shouldn't be), something as simple as secret++ could suffice.
> However, this does have its difficulty: maintaining existing entries.

First, let us observe the attacker needs no less than O(h) inserts (where
h is the size of the hash table) to find a collision of an unknown hash
function with a non-negligible probability of success.

This means the attack will be thwarted if the secret hash function (e.g.
a universal hash function using a secret parameter) is changed every
O(h) inserts.

Second, it is possible to avoid the need to rebuild the hash table from
the scratch and add O(N)-time complexity penalty (where N is the total
number of entries in the table) every time the hash function has to be
changed. The trick is to keep two hash tables Ho (old) and Hn (new),
holding No and Nn entries, with two corresponding hash functions Fo and
Fn, and counter C whose initial value is 0. When a new entry to be
inserted, we put it into Nn, take min(No, roundup((No+Nn)/h)) entries
from Ho and move them into Hn (using Fn, of course), and as the last
step we increment C, and when C > h, we switch Hn and (empty!) Ho (in
O(1)-time, e.g. by switching pointers), replace Fo with Fn, generate a new
secret function Fn, and reset C to 0. Fetches and deletes are distributed
over Ho and Hn in an obvious way.

--Pavel Kankovsky aka Peak  [ Boycott Microsoft--http://www.vcnet.com/bms ]
"Resistance is futile. Open your source code and prepare for assimilation."