➜

This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Author vstinner
Recipients Arach, Arfrever, Huzaifa.Sidhpurwala, Mark.Shannon, PaulMcMillan, Zhiping.Deng, alex, barry, benjamin.peterson, christian.heimes, dmalcolm, eric.araujo, fx5, georg.brandl, grahamd, gvanrossum, gz, jcea, lemburg, mark.dickinson, neologix, pitrou, skrah, terry.reedy, tim.peters, v+python, vstinner, zbysz
Date 2012-01-16.12:45:15
SpamBayes Score 0.00033381933
Marked as misclassified No
Message-id <CAMpsgwYM=Wi1fnfh3opoiUsZzLoMna2Z35kbudk2rtdCF3x-Lw@mail.gmail.com>
In-reply-to <[email protected]>
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:17vstinnersetrecipients: + vstinner, lemburg, gvanrossum, tim.peters, barry, georg.brandl, terry.reedy, jcea, mark.dickinson, pitrou, christian.heimes, benjamin.peterson, eric.araujo, grahamd, Arfrever, v+python, alex, zbysz, skrah, dmalcolm, gz, neologix, Arach, Mark.Shannon, Zhiping.Deng, Huzaifa.Sidhpurwala, PaulMcMillan, fx5
2012-01-16 12:45:16vstinnerlinkissue13703 messages
2012-01-16 12:45:16vstinnercreate