Make HashMap use a per-process or per-thread seed instead of a per-instance seed

[Gankra]

Currently every call to HashMap::new makes a new RandomState that makes two new calls to the thread_rng to create its seed. This is, to my knowledge cryptographic overkill, as there is no clear distinction between a single HashMap with a seed and many HashMaps with the same seed, as long as that seed is not hardcoded (and therefore able to be attacked offline).

There is no argument to be had on minimizing the risk of a single compromise, as the SipHash security model is designed to make it impossible to compromise a single map. If our users disagree with this, we may consider exposing a constructor for RandomState that explicitly reseeds it.

This can be implemented via Once or through a Thread Local Static. Whichever is more efficient.

CC @alexcrichton

[Gankra]

Willing to mentor

[apasel422]

@gankro I'd be willing to take a look at this.

[Gankra]

Awesome! Go for it!

[alexcrichton]

Note that this is done today for ease of implementation, if a global seed
is painful to add I wouldn't bother
On Thu, Jul 23, 2015 at 12:22 PM Alexis Beingessner <
notifications@github.com> wrote:

Awesome! Go for it!

—
Reply to this email directly or view it on GitHub
#27243 (comment).

[frankmcsherry]

Just a quick comment. There are definitely other reasons to value a seeded HashMap other than DoS attacks, if that is interesting. The most common one I deal with is when I partition work among worker threads, possibly using a hash function, and then hope that when they arrive they will not have rotted out some bits of their hashes and make HashMap perf all wonky. The "per-thread" version might not suffer from this much, but you could easily imagine other ways to shoot yourself in the foot if you re-use seeded hashes too often.

I need cluster-wide consistency, so I actually seed all my own stuff and personally rot out the bits, but ... Just thought I'd mention it!

[Gankra]

@frankmcsherry could you elaborate on this idea of bits rotting out?

[frankmcsherry]

Sure, sorry. It may be tricky to make a version using only HashMap, so perhaps the answer is ... "bah!" :)

Let's say you have a bunch of workers thinking they'd like to count the words in all the strings they have. So, they distribute the words among themselves using their favorite hash function. Once the words next arrive at each worker, each puts their words in a HashMap to count them up. If the hash function they used to distribute the strings is related to the one in the HashMap (e.g. the same) the low order bits will be fixed, and bad perf can happen.

So, you may say: "hey well, you don't get to use HashMap's hash function to do the distribution", and I totally don't plan on trying that, but if anything bad happens because of how the keys are laid out (say I pre-aggregate all my word counts, and ship them, using HashMap.drain()) you can get accidentally crummy performance.

Random stuff like this happens, and you beat your head against the wall trying to understand what went wrong, and then you learn about number theory and that you and the HashMap implementor chose the same prime number somewhere, and ...

So, probably don't sweat it. :)

[Gankra]

Ah, neat! Thanks!