Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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.
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.
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.
Correct me if I'm wrong.
When we understand deniability, we should also understand what non-deniability is. To achieve non-deniability, each message needs to contain the digital signature of the sender private key. After receiving the message, the receiver can use the public key of the sender to verify the message content. If the authentication is passed, the message is non-deniability. Although the X3DH protocol representation and the corresponding libsignal-protocol-javascript in the signal sdk show the Mac part of the message content, the digital signature of the message content is not seen. Adding a Mac to the message content only supports proof of message integrity and is not sufficient to support that the message came from the sender.
So this is my point to understand the deniability of x3dh this way.
