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]

Date: Sun, 8 Jun 2003 18:17:38 +0200 (MET DST)
From: "Pavel Kankovsky" <peak@...o.troja.mff.cuni.cz>
To: Nicholas Weaver <nweaver@...berkeley.edu>
Subject: Re: Algorimic Complexity Attacks

On Sat, 7 Jun 2003, Nicholas Weaver wrote:

> > 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.
> 
> Actually, thanks to the Birthday paradox, it is O(sqrt(h)) when
> collisions start to appear.

Ugh. *bang* *bang* *bang* (This was my head hitting my desk.)
Of course, you are right.

Fortunately, the attacker needs much more than a single collision to carry
out the kind of attack being discussed. He needs to find a set of keys S
such that: 1. F(x) = F(y) for each x, y in S (where F is the hash
function), 2. |S| is large enough, say \Omega(log h) (*).

As far as I remember one needs to try out something like \Omega(h)
randomly chosen keys to find such a set with a non-negligible probability
(**). And any attacker's choice of keys can be considered random when the
hash function is (pseudo)random from the attacker's POV.

(*) Asymptotically equal or greater than C log h for some positive
constant C.

(**) Having a constant (i.e. not dependent on h) positive lower bound.

> Likewise, another solution is to simply use a GOOD cryptographic
> function for your hash.  If, for an attacker to create h(y) == h(x),
> requires the attacker to discover the key used in the hash function or
> otherwise break the hash function, simply make sure that the key is
> well created and use a strong cypher as the basis of the hash
> function.

We need a function having a (relatively) small set of results in order to
build a hash table. We can also assume the information about collisions
leaks out via a timing channel. Ergo, a persistent attacker can find
enough collisions by trial and error.

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