[messaging] KCI in X3DH

[Ximin Luo]

Thanks for the explanation Katriel! That all makes sense to me.

X

Katriel Cohn-Gordon:
> Hi all,
> 
> I'm one of the authors of the Signal and ART papers. We have pushed a
> small update to the paper to help clarify its wording. If you spot any
> other places where we can improve things, please do let us know :)
> I think in general there is a lot of subtlety here because different
> threat models consider compromises of different sets of keys. Define
> X3DH(Alice, Bob) = 1 || 2 || 3 where 1 = DH(Alice's ephemeral, Bob's medium-
> term), 2 = DH(Alice's static, Bob's medium-term), 3 = DH(Alice's
> ephemeral, Bob's static), and 4 = DH(Alice's static, Bob's static).
> 
> 
> *KCI *For the KCI attack described by Kobeissi et al [
> https://doi.org/10.1109/EuroSP.2017.38] you only need to compromise one
> key (Bob's medium term signed prekey). If I know that key, I can
> impersonate anybody to Bob by making up a fake ephemeral key for Alice.
> Then I can compute 1 because I know Alice's ephemeral, 2 because I know
> Bob's medium-term, and 3 because I know Alice's ephemeral. I can't
> compute 4.
> If you think it is impossible to compromise Bob's medium-term key
> without also compromising his identity key, then including the static-
> static does not help you. Otherwise, it does, since it requires the
> adversary to compromise both Bob’s medium-term key and his long-term
> private key.
> *Bad RNG* Suppose that I know Alice's ephemeral and Bob's medium-term
> keys. I can compute any session key: I know 1 because I know Alice's
> ephemeral, 2 because I know Bob's medium-term, and 3 because I know
> Alice's ephemeral. I can't compute 4.
> If you think it is impossible to compromise Bob's medium-term key and
> Alice's ephemeral keys without also compromising at least one of their
> long-term keys, then including the static-static does not help you.
> Otherwise, it does, since it requires the adversary to compromise at
> least one static key in order to compute the static-static DH share.
> 
> 
> In both cases, the resistance of the protocol to some attacks is
> increased at the cost of a fourth exponentiation, which can however be
> cached over multiple sessions. (My view is that the cost is worth it for
> the additional benefits and that there are realistic contexts in which
> this sort of compromise can occur. Three examples: storing identity keys
> in an iPhone secure enclave, a Debian-style update which breaks the
> system RNG, or finding the state of an ISO DRBG and predicting future
> values. But reasonable people can disagree here.)
> *UKS* Unknown key share attacks are subtle, and come in multiple
> flavours. We are planning to write a separate document to clarify
> them. That is really an orthogonal argument to what we mean to say in
> the paper, so we've removed their mention from the ART paper for now.
> Stay tuned!
> I hope that helps shed some light here.
> 
> Katriel
> 


-- 
GPG: ed25519/56034877E1F87C35
GPG: rsa4096/1318EFAC5FBBDBCE
https://github.com/infinity0/pubkeys.git