[messaging] X3DH: why put OTPKs on the server?

[Ron Garret]

OK, that all makes sense.  Let me try putting this a different way.

Suppose we change the presentation of X3DH as one protocol with two special cases (OTPK available or not) into two protocols as you suggest: X3DH and X4DH=X3DH+OTPK.  Does X4DH really need to specify how Alice gets an OTPK from Bob?  Would it not suffice to suggest a server as one possible implementation without actually specifying that as part of the protocol?

(FWIW, I think splitting up the presentation into two protocols in this way makes a lot of sense.  It’s conceptually simpler, and also makes it clearer that the unavailability of an OTPK is not just a minor detail, it actually gives you different security properties: X4DH gives you forward secrecy, X3DH does not.)

Hm, the more I think about this, the more storing OTPKs on a server makes me queasy.  To do this safely you have to assume that the contents of the server cannot be read by an adversary (otherwise they can copy the OTPKs, which destroys forward secrecy).  You also have to trust the server to securely delete an OTPK once it has been distributed.  If your server has those properties then you can safely store cleartext on it, which no one in their right mind would do.  Why then should we trust a server to store OTPKs?

Could it be that secure off-line OTPK distribution is an unsolved problem?

On Feb 4, 2017, at 9:42 AM, Nadim Kobeissi <nadim at nadim.computer> wrote:

> Dear Ron,
> 
> In the old days, before smartphones were a thing, encrypted chat sessions were largely established between two parties that were both online at the same time. This would allow Bob issue an OTPK to Alice on demand as you say.
> 
> However, X3DH’s designers created that protocol specifically because they needed to be able to initiate secure chat sessions in a manner that replicated the user experience of SMS. If, for example:
> 
> 1. Bob turns off his phone.
> 2. Alice sends an initial SMS to Bob.
> 3. Alice turns off her phone.
> 4. Bob turns on his phone.
> 
> …Bob would still receive the SMS at step 4. At the time when X3DH was created, the existing mainstream encrypted chat protocol, OTR, did not allow for this SMS user experience to be replicated because it necessitated that both parties have their devices online at the same time.
> 
> Therefore, the essential inaccuracy in your description is that you believe that X3DH is a protocol meant "establish a session key for a real-time communications session.” It is more accurate that X3DH was designed in order to allow for communications sessions to be established both synchronously (“in real-time”) and asynchronously (if one of the parties is offline at the time of requested session establishment.)
> 
> Regarding the possibility of draining OTPK and this causing a DOS attack, this has historically been dealt with in the following ways:
> 
> 1. TextSecure V2 (an old version of what is now known as “X3DH” and “Signal Protocol”) used to have something called a “last-resort OTPK” which would be re-used indefinitely until Bob came back online and updated his OTPK bundle.
> 2. More recent specifications make OTPKs optional. If no OTPK is available, the Diffie-Hellman handshake is accomplished exclusively between Bob’s signed pre-key, Alice’s session ephemeral key, Alice’s long-term identity key, and Bob’s long-term identity key. If a OTPK is available, X3DH more or less becomes “X4DH” due to an extra handshake between Bob’s OTPK and Alice’s session ephemeral key.
> 
> Nadim
> 
>> On Feb 4, 2017, at 6:25 PM, Ron Garret <ron at flownet.com> wrote:
>> 
>> The X3DH protocol calls for Bob to publish a set of one-time pre-keys (OTPKs) to the server.  What is the purpose of this?  Why not just have Bob issue an OTPK directly to Alice on demand as the first step in the protocol?
>> 
>> The only possible answer I can think of is that Bob might not be on-line to fulfill the request.  But the whole point of X3DH (as I understand it) is to establish a session key for a real-time communications session, so if Bob is not on line the whole protocol is moot.
>> 
>> AFAICT, having OTPKs on the server introduces additional complexity (the protocol now has two cases depending on whether an OTPK is available) and additional attacks (a DOS attack where an adversary drains the OTPK pool) requiring mitigations (like rate limiting, i.e. more complexity) for no apparent advantage.  Have I missed something?
>> 
>> rg
>> 
>> _______________________________________________
>> Messaging mailing list
>> Messaging at moderncrypto.org
>> https://moderncrypto.org/mailman/listinfo/messaging
>