This prevents making an infinite set of keys that collide, yes, but does not fix the problem completely. It only increases the request size required to perform the attack. But even with 8 character UTF-8 keys, you could generate 2^64 unique keys with the same length.
Note: IANAC (I am not a cryptographer.) But if I was looking for guarantees for worst-case performance, I'd (pretty much) never use a HashMap. If nothing else, because of the array resizing.
I wonder why none[1] of the major dynamic languages offer the option of running with the built-in associative-data structures implemented using a Red-Black Tree. Seems like an obvious thing to do.
There are interface issues, of course. In particular, for a new type to be usable as a key, it would need to provide an ordering rather than a hash function.
But if only built-in types are used as keys, then there might be no reason to change the interface at all. Just re-run the same program with a different option and you've traded some average-case performance for a guarantee on worst-case performance. And the Red-Black Tree is already written (somewhere out there ...). So why not?
[1] To my knowledge.
It's not a command-line option, but Perl lets you "tie" a hash to a different backing implementation, and there are some tree-based ones:
use Tree::RB;
tie my %hash, 'Tree::RB';They address all of the problems of this sort by just designing a hash function that is good enough that collisions are difficult to find, I think even with the secret key.
Basically, if the attacker can view enough of an 'ordered' list of hashtable entries, they can calculate the seed and then generate appropriate keys to hit the worst case.
Yes. And it is documented as such. Any dependency on repeatable iteration order is a bug.