René added the comment:
Christian Heimes: It has always been trivial to artificially generate
collisions for fast hashes designed for hash tables, like MurmurHash. I
wouldn't call Murmurhash3 "busted" because of that, as this was never a design
goal. It is a known propriety of this type of hash: you do that basically
running them backwards. You can't even call that cryptanalysis.
Of course, you need the seed to search those collisions, but from this thread
it seems very difficult, if not impossible, not to leak the random seed to the
attacker.
I see the various collision counting alternatives proposed as the less
intrusive and definitive solution for this problem. It also has the benefit
that it can work for any type of key. Some pseudo code:
hash as always, with a fast hash.
if reprobes > initial_threshold:
if the table has only one key type AND it has a robust comparison method:
store the collisions in a O(log n) worst case structure (tree).
elif the object has a secondary slow secure hash:
try searching/inserting the key again with the new secure hash.
It works like a double hashing reprobing hash table.
elif collisions > max_threshold:
raise Exception("Under attack or the object is using a crappy hash,
with no fallback.")
The first option, the O(log n) structure, can be ignored as unnecessary
complication (even though there is already a path implementing that), but I
suspect it may be faster than a secure hash. If not, then there is really no
point in this option, except if the secure hash proves to be not so secure.
----------
nosy: +ReneSac
_______________________________________
Python tracker <rep...@bugs.python.org>
<http://bugs.python.org/issue14621>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe:
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
