# Deniability properties of the X3DH Key Agreement Protocol

Signal's X3DH Key Agreement Protocol specification states in section 4.5.:

Alternatively, it might be tempting to replace the DH-based mutual authentication (i.e. DH1 and DH2) with signatures from the identity keys. However, this reduces deniability, [...]

How exactly does replacing DH1 and DH2 with signatures reduce deniability?

I think, using of signatures means something like STS protocol (https://en.wikipedia.org/wiki/Station-to-Station_protocol). In STS, for the purpose of mutual authentication, each party must send a signature of ephemeral keys. So, in terms used in https://signal.org/docs/specifications/x3dh , Alice should sign EK_a || SPK_b, and Bob should sign the same.

In X3DH, authentication provided by signatures is substituted by the fact that for getting the key (SK) each party should execute DH exchange using his identity key (say, ID_a) and counter-party's ephemeral key (say, SPK_b). So, in fact, signing of SPK_b with private key of ID_a (in STS) is substituted with just running of DH for ID_a and SPK_b (in X3DH).

So, what's the difference for deniability? Very simple: signature is evidence of communication and knowing of ephemeral keys, and hence knowing of SK. While running of DH is not an evidence, because it's even impossible to know wether Bob (or Alice) run DH and get SK or not. If Alice will want to prove to some judge that Bob communicated with her, and Bob knows some SK (and hence - he could create or at least decrypt some cypher-texts provided by Alice to judge), she can't prove it: it's obvious that Alice could simulate DH with any EK_a key she wants. There's no evidence that Bob was running DH with EK_a and even know about existence of such EK_a.

How exactly does replacing DH1 and DH2 with signatures reduce deniability?

\begin{aligned} k &= \text{kdf}(A^{b_e} \| A^{b}_e \| A^{b_e}_e)\\ &= \text{kdf}(B^{a}_e \| B^{a_e} \| B^{a_e}_e) \end{aligned}

Diffie-Hellman can be computed by "either Alice or Bob", however, the question of which computed the shared key is not revealed. If Alice knows Bob's public key, but has not interacted with Bob, she may forge a transcript under Signal's protocol.

\begin{aligned} k &= \text{kdf}(A^{b_e}_e)\\ &= \text{kdf}(B^{a_e}_e)\\ s_A &= \text{sign}_a(A_e)\\ s_B &= \text{sign}_b(B_e) \end{aligned}

Signatures, by definition are not deniable and their mere presence implies some communication occurred. If Alice and Carol exchange private messages and either Carol, or the signal servers, or a MiTM leaks the signed ephemeral $s_A$; then Bob can still forge a transcript. Bob relies on such a leak so he cannot forge a transcript with any user.

Because Bob cannot forge a transcript with just anyone; Alice is going to have a harder time disputing having ever communicated with Bob, although because deniability was only reduced and not broken, she may succeed. This is the only leakage. The transcript remains deniable thanks to Double Ratchet.

$s_B$ is implied by Signal's signed prekey bundles; although it has additional structure so the semi-ephemeral cannot be mistakened as a fresh ephemeral.

On the other hand so long that the average user cannot forge transcripts because the Signal application does not expose such a feature; the deniability can be disputed not only for the liklihood that the handshake occurred, but can "prove" to a degree using forensic analysis that the transcript was not forged.

Worse, many people will blindly accept a screenshot without signatures nor other authenticators or proofs of identity.

Signatures are verifiable by a third party—any party knowing the public key can verify signed messages, but that's not enough to forge them.

If Alice wants to persuade Charlie that Bob wrote a message and Alice has Bob's signature on it, Charlie can verify that signed message using Bob's public key with no threat of violence.

Symmetric authenticators under secrets from DH key agreements are not verifiable by a third party—any party that can verify message authenticators can also forge them.

If Alice wants to persuade Charlie that Bob wrote a message and there's only a symmetric authenticator on the message, not only could Alice have forged the authenticator but in order to enable Charlie to verify the authenticator Alice has to reveal her own secret keys, or under threat of violence cause Bob to reveal his own.

Thus, when Bob has signed a message that may later work against his interests, there's an easy way for Alice to persuade Charlie that Bob wrote it—but when Bob has only provided a symmetric authenticator, Charlie has no way to tell whether Bob actually sent it or whether Alice forged it, giving Bob an easy way to deny it.

• That is not very accurate. after every signature you can demand the signer to give up her secret key. In that way the signature you could have been forged by anyone. – curious Feb 6 '18 at 7:45
• Yes—third-party verifiability is premised on the signer keeping the signing key secret. I don't understand the point you're making here. With signatures, third parties can verify as long as the signing key is secret; with symmetric authenticators, third parties can never verify because the verification procedure requires a secret key, knowledge of which is also sufficient for forgery. Thus there is a reasonable situation in which signatures admit third-party verification while symmetric authenticators never do. In what way is my answer not accurate? – Squeamish Ossifrage Feb 6 '18 at 8:02
• One party of the communication always passes the secret keys to the third parties. So be it signature or MAC the third party can always verify. In the MAC scheme it can be either parties who have sent the message: that provides deniability. The same can be achieved with the signatures if you open your secret key each time you send a signature. A similar approach is followed by OTR protocol. It is also dependant on what you are signing: If the signature does not contain any ID then still it could be anyone holding the key – curious Feb 6 '18 at 8:34
• If Alice wants to persuade Charlie that Bob wrote a message and Alice has Bob's signature on it, Charlie can verify that signature using Bob's public key with no threat of violence. If Alice wants to persuade Charlie that Bob wrote a message and there's only a symmetric authenticator on the message, not only could Alice have forged the authenticator but in order to enable Charlie to verify the authenticator Alice has to reveal her own secret keys, or under threat of violence cause Bob to reveal his own. Still don't understand your objection, or how OTR reveals signature keys. – Squeamish Ossifrage Feb 6 '18 at 17:30
• @curious Also, a signature may identify a user even if you don't deliberately put a user id in it—this was used, for instance, to break the privacy of the PLAID smartcard protocol. I would be curious to understand what your continued objection to this post is, if you would care to elaborate. – Squeamish Ossifrage May 13 '19 at 22:19