Exposure of HashMap iteration order allows for O(n²) blowup.

[Veedrac]

Exposing HashMap's iteration order can cause O(n²) blowup even in innocent-looking code without the presence of an attacker. In the presence of an attacker, access to the order of a dictionary allows HashDoS-like attacks with only two requests in common scenarios.

Without an attacker

Consider a user with two possibly-disjoint hash maps

let first_map: HashMap<u64, _> = (0..900000).map(|i| (i, ())).collect();
let second_map: HashMap<u64, _> = (900000..1800000).map(|i| (i, ())).collect();

The user wants to merge the hash maps, and does so naïvely,

let mut merged = first_map;
merged.extend(second_map);

Time for merge when second_map is shuffled: 0.4s

Time for merge when second_map is not shuffled: 40.s (x100 amplification)

This effect is noticeably more pronounced when merging with a round robin strategy.

With an attacker

The threat model here is simple. The attacker is able to send JSON to the server. The server parses the JSON into a HashMap and through whatever means - an error message including the formatted map or explicit listing of the contents of the map - may reveal the order of the map.

The attack on this model requires two requests. The first sends some large JSON to the server

let first_request: HashMap<u64, _> = (0..900000).map(|i| (i, ())).collect();

and recieves an ordering

let returned_data: Vec<_> = first_request.into_iter().collect();

The attacker then sends the first and third quarter of this list in a new JSON object.

let second_request: HashMap<u64, _> =
 returned_data[..225000].iter()
     .chain(&returned_data[450000..675000])
     .cloned().collect();

Total time without second request: 0.1s

Total time with second request: 200s (x2000 amplification)

---

Solutions, near-solutions and non-solutions

These solutions should not be considered to be ordered, necessarily disjoint, nor an exhaustive list of options.

Fall back to BTreeMap

It should be clear that we cannot treat hash maps as a solved problem just because we use SipHash. In fact, SipHash is entirely insufficient to solve the problem. My first suggestion is thus to stop trying to make the hasher secure, and instead fall back to BTreeMap when nonlinear behaviour is detected.

This guarantees a minimum level of performance regardless of the capabilities of the attacker, and allows usage of a faster hashing algorithm by default. Hash maps should get faster by default as a result. This does not prevent having to consider the issue, since the fallback is costly and must be rare, but this is an easier problem than entirely securing the hash map.

Use a hash map without problematic blowup, or less affected by it

Java solves this problem by using a hash map with chaining and converting large buckets to tree maps. This mitigates the impact of degradation, but does not seem to allow using contiguous hash maps by default.

As far as I am aware, the blowup cannot be resolved by moving to another common form of open addressing, although quadratic probing would be significantly less affected by some of these attacks. Chaining alone also defeats the attacks given here, but still requires a secure hash and fails with attackers with more capabilities.

Use different seeds for each hash map

Pull requests #31356 (closed) and #33318 (merged) first proposed incrementing the thread local seed for each hash map. This was later removed when no threat model was seen, but would prevent both attacks listed here.

This still allows attacks when hash maps are reused.

Randomize iteration order

I am not sure how one would randomize iteration order efficiently. However, it should solve the problem unless hashes are exposed through other means.

Ignore the problem

Given that Rust went so far as to use SipHash, quadratic blowup on code as simple as fst.extend(snd) seems too extreme to ignore.

[sfackler]

It seems to me like we should basically just revert #33318 for now and use different seeds per map. Ideally we could find a strategy that avoids key reuse but also doesn't regress hashmap creation performance too much, but as @briansmith noted in #33318 there are risks to using multiple correlated keys as well.

[sfackler]

cc @rust-lang/libs

[briansmith]

The threat model here is simple. The attacker is able to send JSON to the server. The server parses the JSON into a HashMap and through whatever means - an error message including the formatted map or explicit listing of the contents of the map - may reveal the order of the map.

Perhpas we can resolve this by just saying this is outside the threat model. And/or, the Debug implementation for a HashMap isn't performance-sensitive in most applications, and so it could be redone to always output the values in sorted order by key--i.e. it could make a copy of itself into a BTreeMap and then Debug::fmt the BTreeMap. This seems reasonable since either the HashMap is small or it is probably too gigantic to reasonably expect to format in the first place. (Note that HashMap doesn't implement Display, not should it.)

[sfackler]

We'd also have to mandate a sort in JSON serialization, which seems somewhat unreasonable.

The fact that simply merging two maps can run into sadness makes it seem to me like we have to do something about this.

[Veedrac]

You can't always sort a hashmap because the keys aren't required to be Ord. This doesn't matter for the BTreeMap fallback because you can sort by hash code (note: this means it's required to use a cryptographic hash), but sorting by hash is exactly the opposite of what you want to do when you don't have that fallback.

[sfackler]

A shuffle would do fine though I think.

[eternaleye]

@briansmith: Debug is just a trivial example of how the information might leak, though, not the actual issue.

Another example would be if a web service validates the JSON it's given key-by-key, by iterating over (key, value) pairs and delegating to a validation function.

• If it returns the first error it encounters, the attacker can learn the order.
• If it errors early, even without a descriptive message, the attacker can learn the order.
• If it collects the errors and returns them without shuffling (or sorting), the attacker can learn the order.

It's a footgun.

[Veedrac]

We could also use Python's technique to preserve insertion order. It introduces a little more indirection, but the cost doesn't seem to be excessive.

This also makes hash map order deterministic, which is a nice usability bonus. Note that tombstones aren't required for determinism, but are required to preserve insertion order through deletions. Either way prevents the attacks given.

[arthurprs]

Revisiting #33318 sounds like the reasonable way out.

[arielb1]

HashMap creation needs to be fast in the common case. I think we need a HashMap that defaults to FNV but rehashes with a random SIP key when it gets too much collisions.

[eternaleye]

TBH, I'm also curious how alternate approaches (a BTreeMap whose nodes are stored in an overallocated Vec, for similar allocation amortization as HashMap; a trie or crit-bit tree keyed on hashes with the same allocation style, etc) would perform.

Both would likely avoid the pathological merging behavior, and the amortized allocations may bring them closer to HashMap.

[arielb1]

So the problem here is not hard collisions, but rather soft collisions?

[bluss]

@Veedrac It has some wins too, since the data that needs to be swapped by bucket stealing while inserting is smaller, and iteration is much faster since it's on a mostly compact space. But the indirection costs in lookup may not be acceptable at all. (I made a prototype that demonstrates exactly these differences with a +6% hit to lookup.)

Maybe if one moves the hash field to be next to the index, or even special case smaller than 2**32 maps so that they keep 32-bit hashes and 32-bit indices next to each other?