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?
We had a brief discussion about this in Basel, basically the idea outlined is preventing key re-use of a single peer, so he/she will not re-use the same one-time key (at this point they would not be called one-time keys anymore), but he might be using a key that has been used by a different peer.
This methods provides certainly some benefits:
3 “long-term” private keys needs to be compromised on one side (still 2 on the other side, and not taking into consideration compromising of the SK)
As you mentioned less sessions will rely on the same 3 identity keys, so no “one-time-per-user” key in the bundle is more valuable to an attacker.
on a side note at this stage there is no difference between a “pre-key” and a “one-time” key, and I feel having a difference will only make “pre-key” a better target (when someone used up all the pre-keys it picks another one at random).
The method described though leaves out the main advantages of having one-time keys and probably the reason why they are in the protocol in the first place: as soon as a one time key has been used, that private key can be thrown away, reducing the possibility of a compromise (if you use a pre-signed key that is not the case, while the other side can throw away its ephemeral key).
If we allow re-use of one-time keys from different peers than we will need to keep that key lingering around.
To overcome this we had something similar in mind, basically one-time key are going to be user-specific, so initially x3dh will be using a non-user specific bundle ( and I think the suggestion you made to use multiple keys is a good one here), but as soon as an x3dh exchange is performed, the other party is seeded with a set of one-time keys (in this case they will be really one-time keys), that are specific to that user. Optionally the next message can perform another x3dh with a one-time key and that key can be discarded.
The bundle can be periodically refreshed during message exchanges.
To answer your questions:
As mentioned above, if we allow key re-use we need to keep the key lingering around after it has been used, and also compromise of that key ( + identity + signed-pre-key), will compromise potentially multiple sessions, not just one.
In terms of forward secrecy guarantees, it will still be there as it’s there even when using a pre-shared key (as a side note, here you mentioned the public key of the initiator, but really is the public ephemeral key that provides pfs, the identity key provide authentication, so even on re-use of the same key from the same user you’d get different shared keys).
If we do make a difference between key that can be re-used and key that cannot be re-used you could add something like:
If a “one-time-key” has been compromised (+identity +signed-pre-key), only a single session of any given user is compromised", which I don’t feel is a strong guarantee.
That is not a problem
I personally don’t think preventing re-use from the same participant is worth, as mentioned above I would just have n pre-signed keys, which I feel provide most of the benefits with the lowest cost in terms of complexity.
Also I am assuming here that we allow users to communicate with initial non-pfs messages, otherwise we can have stronger guarantees by simply sending a x3dh bundle with one-time keys that are specific to the user with the contact request/whatever initiation mechanism we choose to implement.
the “pre-key” is signed - the signature takes up space presumably?
good point!
what’s the advantage of doing a full x3dh exchange in this case, over a DH ratchet step?
As mentioned elsewhere, this sounds like a really bad idea - nearly impossible to communicate to the user or reason about in a sane way - though arguably, that’s what they’re doing in an exhaused-one-time-key scenario in X3DH.
the “pre-key” is signed - the signature takes up space presumably?
At that point the bundle is immutable, so you would sign the bundle itself rather than each individual key likely (all keys at once basically), so effectively the size would be the same.
what’s the advantage of doing a full x3dh exchange in this case, over a DH ratchet step?
DH is certainly an option, x3dh has some advantages I think though: we allow re-keying at any point with a single message, we have an already established algorithm for authentication, it’s more flexible in case we want to allow asynchrnous communication (and we don’t have to support 2 different types of key exchange).
As mentioned elsewhere, this sounds like a really bad idea
The only reason I mention this is because the method proposed is only useful if we allow initial non-pfs, otherwise it would not add any benefit.
Whether to disable non-pfs messages (currently enabled, so we would be taking away a feature from the user), is still an open question, and ought to be discussed in a broader context as it impacts product, UX, etc.
My 2p is that if we manage to publish the bundle through ens as well (in addition to qr codes, contact codes, public chats), then we are probably covered in most of the cases and disabling non-pfs messages would not be a problem, so that would be the best case scenario. Essentially we are coupling contact discovery with bundle propagation (you share your bundle instead of your public key). Swarm etc can be taken into consideration when ready.
though arguably, that’s what they’re doing in an exhaused-one-time-key scenario in X3DH.
X3DH does provide PFS even if all the one-time keys are exhausted and the shared key is used.