Author haypo
Recipients Arach, Arfrever, Huzaifa.Sidhpurwala, Mark.Shannon, PaulMcMillan, Zhiping.Deng, alex, barry, benjamin.peterson, christian.heimes, dmalcolm, fx5, georg.brandl, grahamd, gvanrossum, gz, haypo, jcea, lemburg, mark.dickinson, merwok, neologix, pitrou, skrah, terry.reedy, tim.peters, v+python, zbysz
Date 2012-01-16.12:45:15
SpamBayes Score 0.000333819
Marked as misclassified No
Message-id <CAMpsgwYM=Wi1fnfh3opoiUsZzLoMna2Z35kbudk2rtdCF3x-Lw@mail.gmail.com>
In-reply-to <1326449848.75.0.36679779906.issue13703@psf.upfronthosting.co.za>
Content
The vulnerability is known since 2003 (Usenix 2003): read "Denial of
Service via Algorithmic Complexity Attacks" by Scott A. Crosby and Dan
S. Wallach.
http://www.cs.rice.edu/~scrosby/hash/CrosbyWallach_UsenixSec2003.pdf

This paper compares Perl 5.8 hash function, MD5, UHASH (UMAC
universal), CW (Carter-Wegman) and XOR12. Read more about UMAC:
http://en.wikipedia.org/wiki/UMAC
"A UMAC has provable cryptographic strength and is usually a lot less
computationally intensive than other MACs."

oCERT advisory #2011-003: multiple implementations denial-of-service
via hash algorithm collision
http://www.ocert.org/advisories/ocert-2011-003.html

nRuns advisory:
http://www.nruns.com/_downloads/advisory28122011.pdf

CRuby 1.8.7 fix (use a randomized hash function):
http://svn.ruby-lang.org/cgi-bin/viewvc.cgi/branches/ruby_1_8_7/string.c?r1=34151&r2=34150&pathrev=34151
http://svn.ruby-lang.org/cgi-bin/viewvc.cgi?view=revision&revision=34151

JRuby uses Murmurhash and a hash (random) "seed" since JRuby 1.6.5.1:
https://github.com/jruby/jruby/commit/c1c9f95ed29cb93806fbc90e9eaabb9c406581e5
https://github.com/jruby/jruby/commit/2fc3a13c4af99be7f25f7dfb6ae3459505bb7c61
http://jruby.org/2011/12/27/jruby-1-6-5-1
JRUBY-6324: random seed for srand is not initialized properly:
https://github.com/jruby/jruby/commit/f7041c2636f46e398e3994fba2045e14a890fc14

Murmurhash:
https://sites.google.com/site/murmurhash/
pyhash implements Murmurhash:
http://code.google.com/p/pyfasthash/
History
Date User Action Args
2012-01-16 12:45:17hayposetrecipients: + haypo, lemburg, gvanrossum, tim.peters, barry, georg.brandl, terry.reedy, jcea, mark.dickinson, pitrou, christian.heimes, benjamin.peterson, merwok, grahamd, Arfrever, v+python, alex, zbysz, skrah, dmalcolm, gz, neologix, Arach, Mark.Shannon, Zhiping.Deng, Huzaifa.Sidhpurwala, PaulMcMillan, fx5
2012-01-16 12:45:16haypolinkissue13703 messages
2012-01-16 12:45:16haypocreate