[messaging] KCI in X3DH

[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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20180118/26d534e4/attachment.html>