Deniability and Prekey Security in X3DH Key Agreement Protocol

Question

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).

Answer 1

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).