Plaintext DH keys in the message header in the Double Ratchet Algorithm

Question

I've been reading details about the Double Ratchet algorithm, and I wanted some clarification regarding the aspect of the DH public keys going out in the plain in the header of every message. Quoting from the specifications of the Double Ratchet:

Every message from either party begins with a header which contains the sender's current ratchet public key. When a new ratchet public key is received from the remote party, a DH ratchet step is performed which replaces the local party's current ratchet key pair with a new key pair

Doesn't that effectively allow an adversary to trace back the message to you and effectively prevent deniability? For example, lets say some messages get delayed from A to B, and meanwhile B is advertising the same public key over and over again, won't you be able to somehow know that it is B communicating with A. Probably, another way to put the same question is, is there a way for some adversary to know who B is, given that they can see their public key in the header (in that interval of time when B has not received a new DH public key from A)? Or alternatively, at least link that communication to a distinct user.

Thanks!

Answer 1

The Header does not contain any information that would proof that it was created by Alice. Alice's public-key is publicly available. X3DH and Double Ratchet are believed to be offline Deniable because the whole communication could have been simulated by one person.

This is because Diffie-Hellman secrets may be calculated in two different ways: $DH(DHK^s_A,DHK^p_B) = DH(DHK^s_B,DHK^p_A)$.

The generated shared secret at x3dh may be calculated by Bob and by Alice. Hence, Bob could just generate a shared secret by choosing a random ephemeral key, then make up a message, encrypt it using double ratchet and afterwards pretend that he had received it by Alice.

If a judge is actually able to track the message traffic between Alice and Bob (including a possibility to see it actually was sent by Alice), it might be a case of a online Deniability failure (which Signal doesn't claim to have). But even that would less be a failure of the signal algorithm and more of the communication protocol. If otherwise, a judge only receives a list with all the messages that have been "sent" (including the unencrypted headers), it can't prove that those messages were written by Alice, because Bob could just have simulated those.

A property that would lead to a possible proof is the use of signatures: If Signal Protocol would use some kind of cryptographic signatures within the sent messages it couldn't claim offline deniability, because signing a message with Alice's private key may only be done by Alice. This could not be simulated by Bob, hence it would prove that the message is sent by Alice. But this is not the case. The only signature Signal use is the when signing the signed prekey, which is then uploaded and made publicly available. By this, it can be proven that Bob uploaded the signed prekey to the server, but not that he had contact with anyone.

Here you can read about the deniability of Signal in more detail.

Answer 2

I don't know if by the word "deniability" you mean something else, but I don't think the Double Ratchet protocol or any of its building blocks provide any kind of deniability security properties like deniability of message exchange, at least it isn't mentioned somewhere. But, plausible deniability for example may be achieved by somehow having the DH Ratche making steps at random intervals independent of the existence of messages to be transferred, of course appropriate padding will need to be orchestrated for it to work. The above is somehow depicted in the figures of the specification, like the following where the number of exchanged messages looks independent to when the next DH Ratchet step is made.

A few other notes, the Double Ratcher header message can be encrypted using the Header Key (HK) which is derived from the Root KDF Chain which is initialized with the Root Key which is provided by Key Agreement protocol (in the case of Signal this is the 3XDH [2]). For more information see p.22 of the protocol description [3] you mentioned.

Now answering your exact question :

Another way to put the same question is, is there a way for some adversary to know who B is, given that they can see their public key in the header (in that interval of time when B has not received a new DH public key from A)?

The public key that is used to initialize the DH ratchet is a fresh one and for the initialization or immediate step of the DH ratchet a fresh key is/should be generated. So from my understanding, a passive adversary that is tapping the wire, even in the case of the plain text header, cannot learn any useful information from any header, since of course DH is secure against passive adversaries.

As mentioned in the protocol description :

Message headers contain ratchet public keys and (PN, N ) values. In some cases it may be desirable to encrypt the headers so that an eavesdropper can’t tell which messages belong to which sessions, or the ordering of messages within a session.

I think they are considering a passive adversary in this case. But in my opinion, encrypting the header should be offering more than this, e.g. it should offer some kind of security and integrity properties against active adversaries. But, expect much of the security load to be shifted to the Key Agreement protocol that seeds the Double Ratchet.

This paper [4] should probably be a really good read discussing all the above, focusing more on the Signal protocol. It is a long read and heavy on notation.