User: Password:
Subscribe / Log in / New account

only a vulnerability in djbx33a?

only a vulnerability in djbx33a?

Posted Jan 16, 2012 12:28 UTC (Mon) by wingo (guest, #26929)
Parent article: Denial of service via hash collisions

What is the feasibility of this attack on other standard hash functions, I wonder?

Guile for example (on its master branch) uses Bob Jenkin's lookup3:

(Log in to post comments)

only a vulnerability in djbx33a?

Posted Jan 17, 2012 2:46 UTC (Tue) by wahern (subscriber, #37304) [Link]

Broken for static initialization vectors, at least:

only a vulnerability in djbx33a?

Posted Apr 14, 2014 22:04 UTC (Mon) by rurban (guest, #96594) [Link]

Every single hash table which uses unsorted linear linked lists is attackable by this, because the attack goes against the unsorted list, and the hash function can not help much. I wonder why everybody wants to improve X when Y is the problem, not X.
The random seeding also does not help much, as the seed can be attacked also (e.g. "REMOTE ALGORITHMIC COMPLEXITY ATTACKS AGAINST RANDOMIZED HASH TABLES", N Bar-Yosef, A Wool - 2009 - Springer). And if you've got a seed you get the collisions pretty easily with the right tools. You don't even need to use the \0 trick to which perl (<5.18) were and most other languages still are susceptible.

See where I added some stats and analysis for the avg. and worst cases, and how to fix this problem.

Keeping sorted bucket collisions or perfect hashes are the easiest fixes. It depends on the usage scenario and hash table sizes. Google uses perfect hashes, languages and smaller usages (i.e. the linux kernel, caches) should typically use sorted bucket collisions. They also improve cache lookup performance as with open addressing. Robin-hood hashing also looks good theoretically, but I haven't tested it yet against such attacks.

Detecting hash flooding as done by DJB's DNS server or limiting MAX_POST_SIZE as done with PHP is also fine.

Copyright © 2017, Eklektix, Inc.
Comments and public postings are copyrighted by their creators.
Linux is a registered trademark of Linus Torvalds