Deniability and Prekey Security in X3DH Key Agreement Protocol

Can someone please explain the below paragraphs from The X3DH Key Agreement Protocol?

1st paragraph: What is deniability and how does it work here?

Deniability

X3DH doesn't give either Alice or Bob a publishable cryptographic proof of the contents of their communication or the fact that they communicated.

Like in the OTR protocol [6], in some cases a third party that has compromised legitimate private keys from Alice or Bob could be provided a communication transcript that appears to be between Alice and Bob and that can only have been created by some other party that also has access to legitimate private keys from Alice or Bob (i.e. Alice or Bob themselves, or someone else who has compromised their private keys).

If either party is collaborating with a third party during protocol execution, they will be able to provide proof of their communication to such a third party. This limitation on "online" deniability appears to be intrinsic to the asynchronous setting.

2nd paragraph: How would this passive attack work?

Compromise of prekey private keys may enable attacks that extend into the future, such as passive calculation of SK values, and impersonation of arbitrary other parties to the compromised party ("key-compromise impersonation"). These attacks are possible until the compromised party replaces his compromised prekeys on the server (in the case of passive attack); or deletes his compromised signed prekey's private key (in the case of key-compromise impersonation).

Deniability

Let's say that Eve notices that Alice and Bob are having a secure communication. Later on, Eve shows up to Alice's home and demands that Alice turn over all of her private keys so that Eve can expose their conversation. Alice and Bob want to ensure that their previous communications remain private.

If Alice encrypted a message $m_1$ into ciphertext $c = E(m_1,r)$, where $r$ is some random input (perhaps a shared secret), then Alice may want to deny she sent $m_1$ and instead claim that she encrypted another message $m_2$ such that $c = E(m_2,r')$, where $r'$ is some other random input. If $E$ has this property, it's called deniable. Unless Eve has telepathic superpowers, she can't trust Alice at all, since she could've turned over $m_2$ and $r'$ instead of $m_1$ and $r$. In fact, this protects Alice's data from even herself in the future! (How could Eve trust anything Alice decrypted?)

(Of course, if Alice for some reason has to hand over $m_1$ and $r$, there is no hope. I took the example from this paper.)

X3DH doesn't allow Alice and Bob to prove that they had a particular conversation; their messages are deniable. But: if Eve forces Alice and Bob to hand over private keys, Eve can generate conversations that appear to have come from Alice and Bob.

Compromise of Prekeys

Recall the formulas used to derive the secret key from the prekeys:

DH1 = DH(IK_A, SPK_B)
DH2 = DH(EK_A, IK_B)
DH3 = DH(EK_A, SPK_B)
SK = KDF(DH1 || DH2 || DH3)


If I have access to the prekeys, I can try to calculate DH1,DH2, and DH3 (although I think this is hard without the ephemeral and identity keys) and carry out key-compromise impersonation attacks; see this informal overview. Basically, I can compute the shared secret if I have a secret key SK and impersonate someone in a conversation. This is why the protocol suggests periodically uploading prekeys to the server, since these attacks are invalidated (the secret key depends on the prekey).

• thanks galvatron. I have some doubts . I understood deniability, but how is it applicable in X3DH? Like if Eve gets the private keys he can generate conversations, so how is this deniable? He shouldn't either be able to get the private keys or he shouldn't be able to decrypt the message with the given keys(the keys may not be correct or something)? Can you also explain a little bit of last part of Deniability para? – tarun14110 May 28 '17 at 4:25
• In compromise of prekeys part, is it assumed that adversary also have access to ephemeral and identity keys? If yes, why only passive attack works here? And it only works if we don't have one-time prekeys, right ? – tarun14110 May 28 '17 at 4:42
• Basically the MAC keys for Alice and Bob are derived from their shared DH secret. So they can prove to each other that they communicate, but for example, Alice can't convince Eve that Bob wrote a message since, for all Eve knows, Alice herself could have written it. So the best Eve can do is accept Alice at her word, unlike PGP/GPG, which each message would be signed by Alice (non-repudiation). – user47922 May 28 '17 at 6:04
• I think the last part of the first paragraph is saying that if Eve and Alice were collaborating, then Eve now has a proof that Bob sent a message to Alice. – user47922 May 28 '17 at 6:08
• No, I don't think they assume possession of identity or ephemeral keys. – user47922 May 28 '17 at 6:13