Guile for example (on its master branch) uses Bob Jenkin's lookup3:
only a vulnerability in djbx33a?
Posted Jan 17, 2012 2:46 UTC (Tue) by wahern (subscriber, #37304)
Posted Apr 14, 2014 22:04 UTC (Mon) by rurban (guest, #96594)
See https://github.com/rurban/perl-hash-stats 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