Help harden HashMap in libstd!

[alexcrichton]

Your comment makes it seem like extend is the culprit, rather than a more general flaw with the open addressing scheme

Ah yes indeed, and very good points that it’s more general!

so a quick fix seems essential. The change is trivial and massively reduces the attack surface.

True yeah, but it won’t hit stable any more rapidly if we were to land it today or a few weeks from now. That, coupled with the fact that this doesn’t seem actively exploited, led the libs team to the conclusion that we can regroup for a bit to determine the best long-term solution here.

The downside of going back to per-map keys is that it brings in quite a bit of randomness machinery back into the standard library. Additionally, it can drastically slow down creating of a large number of hash maps (the motivation for the original PR). Just to mention that it’s not a free revert!

[Veedrac]

The downside of going back to per-map keys is that it brings in quite a bit of randomness machinery back into the standard library. Additionally, it can drastically slow down creating of a large number of hash maps (the motivation for the original PR).

I should have been more clear; I’m just referring to incrementing the keys each hash map. This was the original idea of PR #33318, but that part was removed after some discussion.

[arthurprs]

19±36 no longer seems very controlled.

Well, for a 7M+ hashmap approaching a occupancy of 91% I’d say it is.

[sfackler]

Have @briansmith’s concerns with that approach been addressed?

[arthurprs]

The downside of going back to per-map keys is that it brings in quite a bit of randomness machinery back into the standard library.

That seems unavoidable.

We could go halfway back and update only one of the seeds on each hashmap creation, this reduces the rng overhead in half. The other half can be generated by a simpler rng seeded from the OS as well.

[Veedrac]

@briansmith’s concerns are basically

The hash function isn’t necessarily SipHash.

I’m not sure this matters because this part of the code is explicitly tied to SipHash.

I don’t find “we don’t currently know of a related-key attack on SipHash” very encouraging.

It’s strictly harder than an attack when the keys are already equal.

Further, hash maps don’t care about any hypothetical key attack; the nature of the problem means that the attack has to be both extremely fast, else it’s useless for amplification, and extremely effective, as a HashMap only leaks the bottom few bits of its hashes (and even then imperfectly).

We assume that the attacker can add or remove arbitrary (key, value) entries from any hash table used in the program.

Though it would be useful to defend against this kind of “anything goes” attack, right now we’re vulnerable to attackers with extremely basic capabilities.

More generally, crypto people never generate a secret key by adding a constant value to another secret key.

Block cipher mode of operation |

[briansmith]

It generates the next keystream block by encrypting successive values of a “counter”.

This isn’t the same thing as deriving a key by adding one to the previous key.

[Veedrac]

This isn’t the same thing as deriving a key by adding one to the previous key.

Assuming you’re combining it additively with the IV, it’s a randomly chosen key that’s incremented by one each block you encrypt.

I’ll admit it’s a very different domain with a different security model.

[jethrogb]

Assuming you’re combining it additively with the IV, it’s a randomly chosen key that’s incremented by one each block you encrypt.

No. Counter mode will generate a keystream like this: E(K,IV+0), E(K,IV+1), ..., E(K,IV+n). This is very different from E(K,IV)+0, E(K,IV)+1, ..., E(K,IV)+n. If you were to use the former (which is basically NIST SP 800-90A’s CTR DRBG) to initialize successive HashMaps, that would be totally fine.

[Veedrac]

IV+n corresponds to the seed to SipHash, not E(K,IV+n). (Not that it matters; “what do completely different cryptographic schemes do” is a poor heuristic anyway.)

[dobenour]

@briansmith please check this, but I think that incrementing the seed to SipHash (not the key) would solve the problem, inasmuch as as SipHash is considered to be a strong PRF (pseudorandom function) and that is not affected by any of these attacks. Since SipHash is a PRF, changing even one bit of the input completely changes the output. By “seed”, I mean the common prefix that is used by all hasher invocations.

Also, here is another point to consider: We aren’t encrypting anything. We don’t need to defend against offline attacks by attackers with NSA-level computing power. As long as the attacker requires significantly more computing power to launch the attack than we need to defend against it, we win.

That means that we can use PRFs and PRNGs for hash tables that would be very ill-advised in any other context. I am thinking of 7-round AES-CTR on machines with AES-NI, or 8-round ChaCha20 otherwise.

Additionally, I think we need to look into optimizing the SipHash implementation. It may very well be worthwhile to use hand tuned assembler here, or at least SIMD intrinsics.

Finally, I very much like the idea of adaptive hashing. There are hash functions (universal hash functions) that offer unconditional guarantees regarding the maximum probability of collisions, and which are often very fast, but which lose all strength if the actual hash codes are revealed. This means that those would need to be somehow protected.

[bascule]

@dobenour if you’d really like to improve the performance (which seems to be a perpetual point of concern), I’d suggest taking a look at HighwayHash, which is AVX-2 optimized (with a fallback SSE4.1 implementation) and performs much better than SipHash for larger inputs:

google/highwayhash

[briansmith]

[quote=“dobenour, post:19, topic:4138, full:true”] @briansmith please check this, but I think that incrementing the seed to SipHash (not the key) would solve the problem, inasmuch as as SipHash is considered to be a strong PRF (pseudorandom function) and that is not affected by any of these attacks. Since SipHash is a PRF, changing even one bit of the input completely changes the output. By “seed”, I mean the common prefix that is used by all hasher invocations.[/quote]

Sounds plausible.

It seems strange to me to add this extra complexity to every single hash table, just in case merges another hash table with attacker-controlled contents into it. I’m curious what other implementations do or don’t do to avoid this.

[Ofekmeister]

Aren’t we going to replace SipHash anyway?

Also, why not cuckoo hashing instead of robin hood? edit: links

basic theory web.stanford.edu/class/cs166/lectures/13/Small13.pdf original paper (.pdf) some concurrent work https://da-data.blogspot.nl/2013/03/optimistic-cuckoo-hashing-for.html

[arthurprs]

Also, why not cuckoo hashing instead of robin hood? edit: links

@Ofekmeister one just have to prove the Cuckoo benefits and open the PR.

Personally I think chucko hash will perform worse on average. There’s this excellent paper with a comprehensive-ish analysis https://infosys.cs.uni-saarland.de/publications/p249-richter.pdf but they don’t store the hash on the table and that’s really a shame because doing so really unlocks the best optimizations for RH. I’m working on optimizing the current implementation, for instance https://github.com/rust-lang/rust/pull/36692

[sfackler]

Aren’t we going to replace SipHash anyway?

With what? I’m not aware of any plans to change the default hashing algorithm.

[matthieum]

Performance is a concern, but not at the cost of security (in this particular case).

We have verified the bit distribution and avalanche properties of HighwayHash. A formal security analysis is pending publication, though new cryptanalysis tools may still need to be developed for further analysis.

It might be worth waiting a bit before jumping the gun, here.

And in any case, it would not solve the issue at hand. The collision attacks here come not from a weak hash, but from the ability to observe the distribution of keys in the buckets of two maps using a similar distribution and injecting a cluster from one into the cluster (in a close enough position) of the other.

Changing the hash algorithm does not solve the issue. Seeding it differently might (if it is strong).

[arthurprs]

Performance is a concern, but not at the cost of security (in this particular case).

Assuming that the computer even have (SSE4/AVX2) the crossing point seems to be at 10, so a sizable amount of real word cases would actually be slower.

And std lib actually uses the sip13 variant, so that crossing point would be even larger.

[alexcrichton]

I’ve posted a summary comment with the discussion of the libs team and our thoughts on how to proceed here.

[alexcrichton]

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.