Default hashmap implementation can cause processes to block

[derekstraka]

When the /dev/urandom pool has not yet been initialized, the use of the default HashMap can cause a process to block. The behavior is problematic when a program is started by an initscript and is not intended to run in the background. The process will block until the urandom pool is initialized which on some embedded systems may be several minutes.

A concrete example of the issue in docopt/docopt.rs#178, but the issue can also occur in other places like regex.

[derekstraka]

Should the crates use a non-default hasher or should the default implementation not block when the random pool isn't initialized?

[cardoe]

/cc @BurntSushi

[BurntSushi]

cc @rust-lang/libs

[alexcrichton]

Interesting! One possible thing we could do is make the default hashing algorithm configurable, but that also seems pretty unfortunate in terms of how it may be implemented.

Another possibility would be to build on a strategy like #31356 except also provide a function to manually seed a thread. That way in cases like this a thread could be manually seeded and all future hash maps on that thread would use the same seed.

Exposing seeding though would be exposing the internals of using siphash, so that may not be that great either...

[cardoe]

So I believe the the reason that Rust uses SipHash is to avoid the denial of service attack against many hash table implementations since SipHash was designed to be resistant against it given a good seed. However that's really for unbounded data. My understanding is that if the data set is bounded a "weaker" hasher is not dangerous to a DoS. Obviously a second opinion is very welcome here.

In that case it would then make sense to allow different crates to chose their hashing algorithm if they know their data set is bounded. Obviously that adds some complexity by exposing options that people could get wrong in a bad way but the default should be SipHash, not sure if that's enough to be safe.

[bluss]

like @derekstraka points out, getrandom can tell you when it would block, so libstd could detect that and fall back to a different seed but it will inevitably be a weaker random key for the hash function then.

[cardoe]

Right. That would have to get exposed via the rand crate which currently has no mechanism to do so. OsRng just wires up to the best implementation available.

[BurntSushi]

What should we do in the mean time? Does it make sense to start moving away from the default sip hasher in crates like regex? (i.e., preferring either fnv or BTreeMap?)

[bluss]

@cardoe the relevant code is actually in this source tree, see libstd/sys/unix/rand.rs

[jcreekmore]

So, I would suggest migrating to something like FNV for crates that really don't need the DoS resiliency that SipHash provides (such as the regex crate). Extending SipHash (and ultimately rand) to allow using a weaker seed value would still require migrating the other crates to using this extended SipHash mode so you have additional changes for very little benefit.

The biggest issue is how to communicate when you should use one hasher versus another inside of a crate. On the one hand, it is great that HashMap is proactive and providing a hasher that protects against hash-flooding denial of service attacks by default, but it is unfortunate that, by default, all users of HashMap are paying a performance penalty when many (most?) of them do not need that protection.

[cardoe]

So I'll say that I checked systemd which is obviously used at early boot and their hash implementation uses SipHash and they also use getrandom() to seed it like Rust does. But they call getrandom() with the non-block flag set which avoids the problem.

[bluss]

@Cardo you left out what they do if the getrandom call errors, that's the solution part 😉

systemd's code is here

So this was news to me, that on a system where getrandom may block since there is not yet enough "entropy", a read to urandom will still succeed and not block. I don't think we can produce a better fallback / weak randomness than simply using the same methodology. (Lwn on getrandom / urandom)

I think that HashMap::new() using a randomly keyed hash function, HashMaps being ubiquitous, and Rust wanting to be as portable as possible, all this supports randomly keyed hash functions to be a best-effort approach. We can't require all crates that use HashMaps to change to use FNV. Besides, more uses of fnv is just a net reduction in denial of service protection.

(We wouldn't do it in a best-effort approach if there was an explicit API named “create a HashMap with a strongly random hash function”. Our API is called HashMap::new()).

[cardoe]

Right my point is they seed their hasher in a best effort case by getting the best possible data they can get in a non-blocking fashion by using a fallback. I didn't expand on how they did it.

I don't think @jcreekmore advocated changing all crates to FNV. He's advocating giving crates the option to change to FNV if they know their dataset is bounded and therefore they know they aren't vulnerable and can use a faster hasher function since FNV is faster than SipHash even in the random data is available immediately case.

Maybe leave HashMap::new() but add HashMap::new_with_hasher(h: Hasher)

[bluss]

Using fnv with HashMap is a stable feature since Rust 1.7 (link)

[BurntSushi]

Yeah, I feel like I could be convinced to go tweak this to get past the bad behavior for now, but I feel like "don't use the default std::collections::HashMap if you don't want your program to block for some unspecified amount of time" is not a particularly nice thing. I think that means I'm sympathetic to @bluss's idea, but that also feels like a pretty big change that warrants more visibility.

[alexcrichton]

Oh wow, thanks for the tip @cardoe, and the code @bluss. Sounds like we should just implement that strategy in the standard library for now? I agree that we shouldn't stop recommending HashMap as a result of this, we need to figure out a solution!

@jcreekmore it's definitely true that some crates don't need this DoS protection, but one of the arguments for doing it by default is that a surprising number of crates might. For example you may write a crate that's not considering consuming user input, but them it may be pulled into someone else's application where they do so.

@BurntSushi I agree for now if you want to immediately work around this I'd just recommend using the FNV hashing for hash maps (or even btrees). Hopefully we can solve this in the standard library, however, so it's only a temporary solution.