RFC: Make it possible to ensure that keys are _never_ reused.

[nmathewson]

Hello!

In our project, we'd like to use slotmap for cases where we need to make sure, for security reasons, that keys will never be reused over the lifetime of a slotmap.

But in the current slotmap design, once a given slot has been reused ~2^31 times, its version counter wraps around to zero again, and the same keys are handed out as were handed out the first time. This is problematic for us, since it can result in the same key being given out (at different times) to two different objects if an attacker can cause the same slot to get reused over and over.

I see two possible solutions here. Both of these would work for us, and I'd be happy (with a little guidance) to work on an implementation for either one, but I'd like a little feedback first on whether they'd be acceptable.

Solution 1: 64-bit version counters?

If we had the option to use a 64-bit version counter, we'd be satisfied that the counter wouldn't overflow.

One downside here is the complexity: Making this change would require parameterizing all existing slotmap types on a counter type, keeping the u32-bit counter as a default. The keydata type would need to be an associated type or something, so that its ffi-keys could be u128.

I think it would be possible to do this without breaking backward compatibility or adding excess complexity, but I'm not sure.

Another downside here is the cost tradeoff: every user would need to decide whether the possibility of key reuse was acceptable, and whether they wanted to accept the cost in space and time for 64-bit counters.

(As an aside, one might ask: can't 64-bit counters also overflow? Yes, but not on a timescale that makes it practical for an attacker to try this, given our performance requirements. Even if the adversary can cause a reuse in 1ns, it would take them 584 years to overflow a u64. Other users might have different requirements.)

Solution 2: Saturating version counters and unusable slots?

Right now, the version field wraps when it hits u32::MAX. We could instead have the counter "stick" at u32::MAX, and mark its slot as unusable. That is to say, after any slot was reused out ~2^31 times, it could never be used again.

This approach would require no API changes, and it would prevent key-reuse for every user without size overhead.

The first downside is: we would have to add an extra test on the remove-object path. We could probably get the performance impact to be very small, but it wouldn't be zero.

The second downside is: having the possibility of unusable slots would it possible for a slotmap's storage to grow over time without bound, even if the number of objects at any time remains small. I think this possibility is acceptable, since in order to trigger a small leak of this type, an attacker would need to force a pretty huge number of reuses.

---

So, what do you think? Would one of these approaches be worth writing a patch for?