One of the issues with X3DH is that it requires a server that keeps track of which one-time keys have been used already.
This is problematic for a decentralized system because there’s no single server than can keep track which keys have been used - it’s also an open question as to who should be able to remove the one-time key from the list of keys to use - resulting in vulnerabilities like one-time key draining 4.7.
Once the system runs outs of one-time keys, it is expected that the parties continue anyway, but with diminished security, assuming that the keys will be quickly replaced by for example a ratcheting protocol. One can therefore view the one-time key as nice security bonus to be had when the parties are interested in the increased security it brings.
Here’s an initial brain dump of an idea that could potentially solve the need for a central authority keeping track of which one-time keys have been used:
Like in the X3DH spec, Alice wants to speak to Bob, and Bob has access to some storage that he can update. Unlike X3DH, the storage is dumb - the only needed and permissible updates are those made by Bob.
- Bob uploads a bundle - like in X3DH, it will contain an Identity Key and a Signed Prekey. In addition to this, it will also contain N “one-time” prekeys.
- When Alice wants to speak to Bob, she will download the pre-key bundle and use a random one-time key from the bundle, and record the key that was used so as to ensure that any retries don’t use the same one-time key. If all keys have been used already, Alice sends the request without one-time key.
- Bob receives the message, and goes on to use the “one-time” key, first checking if it has already been used by Alice already.
- Periodically, just like in X3DH, Bob will refresh the bundle.
The improvement over ordinary X3DH is that we retain the use of a unique one-time key without requiring an active server. This means that in the future, Bob could store the pre-key bundle on something like Swarm, and update the “latest” bundle to use in a secure way using something like ENS, or possibly using Mutable Resource Updates as a cheaper option.
Some open questions with this scheme:
- What’s the effect of two different people using the same one-time key? The public key of the initiator is mixed into the generated shared secret so effectively, the shared secret won’t be the same, but what are guarantees regarding forward secrecy of the first message?
- Alice now needs to keep track of which keys have been used. Is this a problem?
- If we blindly choose a random key without keeping track of what’s been used, it’s still an improvement - there’s only a 1/(N-M) chance that a key will be reused, assuming M keys already used - Bob can then use M as a hint to update the bundle. Is it worth the complexity to try to store these values and reject reuses from the same participant?
- Other issues?