Secure Messaging Apps and Group Protocols, Part 1

Ephemeral stories

In 1976, Diffie and Hellman published the well-known Diffie–Hellman–Merkle protocol [DH76] [Hel02]. It allows, in particular, to exchange a common secret key confidentially over a public channel. In the current state of our protocol, authenticity of the interlocutors and perfect forward secrecy are not yet achieved. One way to achieve that is to use the Station-to-Station protocol [DvOW92]; a simple, but close-to-reality, way to reach perfect forward secrecy is to:

• use the permanent cryptographic material only to sign messages;

• draw a new session key for each session.

Here is how to evolve P0 into a simplified ephemeral Diffie–Hellman–Merkle (DHE) protocol P1. We first consider that A owns the asymmetric key pair (skA, pkA) and B the pair (skB, pkB), where pkA and pkB are the public keys. We assume that A and B have previously authenticated each other's public key.

1. A draws a random ephemeral key pair (eskA, epkA), computes sA to be the signature of epkA by the private key skA and sends epkA and sA to B;

2. B verifies the signature sA with epkA and pkA;

3. B picks a random ephemeral key pair (eskB, epkB), computes sB to be the signature of epkB by the private key skB and sends epkB and sB to A;

4. A verifies the signature sB with epkB and pkB;

5. A computes the session key k using eskA and epkB, B computes the same session key using eskB and epkA.

Note that a Diffie–Hellman–Merkle key-exchange must be done for every message, as shown in this protocol model, and its output: indeed, at this stage, the only way to go from one session key to another is to perform a DHE for every message.

The protocol P1 is synchronous when building the encrypting key. Based on P1, an asynchronous protocol P2 can be proposed, which is close to the one we implemented in the e2ee Mattermost plugin. Let us consider now that A owns two asymmetric key pairs:

• (skA, pkA) to sign;

• (xskA, xpkA) to perform the key exchange.

B is in possession of two similar key pairs, respectively (skB, pkB) and (xskB, xpkB), and all of the public keys are authenticated by the two parties. The process for A to send an encrypted message to B is:

1. draw a random session key MK and an initial vector IV;

2. encrypt (not with an authenticated encryption algorithm) the message to be sent with MK and IV;

3. draw a random ephemeral key pair (keyECDHE, pubECDHE);

4. compute the shared secret DHSS using keyECDHE and xpkB and derive a key KWK from DHSS;

5. encrypt MK with KWK to get encryptedKey;

6. sign the concatenation of IV, pubECDHE, the public key identifier (basically the hash of pkB || xpkB) and the encrypted message.

With such a protocol P2, the communication may be done asynchronously, since the DHE used to derive the session key may be done by both parties at any time. However, the protocol P2 only achieves partial PFS: indeed, if the secret material of B leaks, it is impossible for an attacker to decrypt the message he sent in the past; but if it is the material of A that leaks, the attacker is able to decrypt all the messages she received.

One ratchet

To fully (i.e. on both sides) obtain PFS asynchronously, it is possible to use the Signal protocol [DR]. Let us consider that A and B already agreed on a shared secret s – how s is obtained is described in the next section.

The idea here is to let the session keys evolve from a common root, without reseeding them every time. To evolve from one session key to the next, a KDF is used: applying the KDF on the current key yields the key used to encrypt the next message. The KDF used in Signal is described as a ratchet (or a one-way function): indeed, one of the properties of that KDF is that, given the current session key, it is impossible to compute the previous session key (i.e. the one used to compute the current key). This gives the following chain:

The new protocol P3 is the following:

1. A and B both compute the secret key k0 using a KDF on s;

2. A encrypts the message m0 with the key k0 and sends the encrypted message to B;

3. B decrypts the message using k0;

4. A and B compute the next secret key k1 using a KDF on k0;

5. B encrypts the message m1 with the key k1 and sends the encrypted message to A;

6. ...

Note that in this situation, we have a walkie-talkie like conversation (push-to-talk or press-to-transmit). Since it is not convenient for most use cases, A and B must maintain two (symmetric) ratchet chains, one for each direction of the messages:

• the emission chain of A is synchronized with the reception chain of B;

• the emission chain of B is synchronized with the reception chain of A.

Beware: the name "double ratchet" of the Signal protocol does not refer to these two chains, but to yet another one, which is described below in Post compromise security.

Compared to the previous solution P2, the Signal protocol also needs less bandwidth, but the emission and reception chains need to evolve synchronously, which is another type of problem that we do not discuss here. Except for the agreement on the shared secret s, the protocol P3 is asynchronous. Let us see now how an asynchronous DHE-like part can be added to P3 to make it fully asynchronous.

Keys authentication matters

One of the key notions in the previous protocols P1, P2 and P3 is the authentication of the permanent keys. This setup step is not necessary to communicate, but necessary to communicate confidentially. To authenticate a public key, one way is to verify through an authenticated channel that the fingerprint of (the public key of) a contact that appears on the user's device is the same as the one that appears on the contact's device. The usual way to perform this verification is to scan a QR code encoding the fingerprint of the targeted key.

This generally optional verification is actually mandatory to perform in Olvid.

Double ratchet

Let's recap:

• with one ratchet, the Signal protocol provides PFS by making the keys evolve via a one-way function,

• with a (costly) DHE for each message, we have both PFS and PCS.

The hybrid solution is then to regularly perform a new DHE key exchange, simpler than X3DH, to refresh the ratchet that is used to obtain PFS by injecting some randomness: this step is the second (asymmetric) ratchet, which finally brings us to the double ratchet protocol.

The question is how regularly to perform the second ratchet: performed for every message, we go back to protocols P1/P2. If the period is too long, this could imply a large leak, since, once the attack is performed, all the messages exchanged within that period can be decrypted.

In the documentation of the double ratchet [DR], the proposition is to make a DHE every time a speaker is interrupted and wants to talk again. In a walkie-talkie communication, it ensures the same security as a DHE for every message, i.e. protocol P1.

Note that recent work by Blazy et al. [BFJLOR22] does propose to edit Signal and perform a new DHE at each step, thus sending an ephemeral public key in the additional data of every message – and signing that public key to ensure that it did come from the sender and was not injected by an attacker in order to derail the conversation (this signature makes their protocol lose the deniability property, see below). To handle lost or out-of-order messages, the sender has to add every past public key to the messages' additional data until they are acknowledged. As usual, there is a choice to be made between efficiency (and thus usability) and security.

Deniability

A messaging protocol is said to be deniable if, given a transcript, a user can deny having participated in the conversation, no matter whether the conversation is real or not. In particular, a protocol is deniable if any user A can simulate a conversation transcript with any other user B that is indistinguishable from a legit conversation: this is doable if the protocol is such that at no point does B provide any value or information that A does not know or cannot obtain. In Signal, we reach deniability because once A receives a public key bundle from the server, she can compute any and all following key material herself: the only thing B would normally do is provide randomness for the asymmetric ratchet, but there is no way to distinguish random values generated by A from random values generated by B: she can thus play both roles.

In short, instead of achieving deniability by being able to prove that B did not participate, we achieve it by not being able to prove that B did participate in the conversation.

Note that deniability is desirable to ensure that users cannot be denounced, or tricked into producing incriminating messages.

There is sometimes a misunderstanding as to how deniability may be mixed with authenticity of the messages. We can summarize the two properties as follows:

• authenticity: A wants to be sure that she is talking with B.

• deniability: A wants to prove to everybody that she talked to B.

We can ensure both properties at the same time: authenticity must be proved inside the conversation, between the protagonists themselves, while deniability must be proved outside the conversation, to non-participants. Signal, for example, achieves both deniability and authenticity.

Encryption at rest

If end-to-end encryption refers to encryption on the move, it is also important to know what happens to messages once they are received, both client-side, and server-side.

Same encryption

One obvious option is to store them encrypted as is, i.e. A receives c=Enc(m) from B, decrypts it to read it, and the app will locally store c, fetching it and re-decrypting it as needed. However, that means that A must keep whatever key is used to decrypt c, thus losing Forward Secrecy: at any given time, the application's state would contain keys to decrypt the entire backlog.

Re-encrypt

Another solution is to re-encrypt the messages with another key, and store them either server-side or client-side, using the secure storage of the device: e.g. this is what Wickr does, as detailed in the Encrypted Local Storage section of their whitepaper [WPW]. In this case, the PFS may not be broken if the secure storage is really secure.

Server-side

We find the same options when storing the messages on the server, either using a new key or storing the messages as they are. This is the choice done for the mattermost plugin, which stores on the server both the encrypted messages for A and for B, no matter who is the sender, as opposed to what is described for P2 (which is only partly PFS). Therefore, even if the mattermost plugin provides end-to-end encryption, it does not provide PFS or PCS.

Post-quantum security

As seen previously, we can divide the complete Signal protocol in different steps:

1. the initial session key exchange (X3DH);

2. the (symmetric) ratchet steps to provide PFS;

3. the (asymmetric) ratchet step to provide PCS;

4. the (symmetric) ratchet steps to provide PFS;

5. the (asymmetric) ratchet step to provide PCS;

6. ...

In the previous enumeration, the even (symmetric) steps are already quantum-safe; doubling the size of the key is often sufficient to be quantum-safe if the key size is small (from a quantum-safe standard).

However, the odd (asymmetric) steps, relying on (some sort of) Diffie–Hellman–Merkle protocols, are not quantum-safe. The most important one is the first step of the protocol: indeed, achieving PCS is done by classical DHE, which is not a particularity of the Signal protocol and is thus studied independently. This is, however, not a simple problem to solve, but the X3DH one is more important to discuss here.

Building an X3DH-like post-quantum protocol is not that easy. It is needed to reach all the security goals of X3DH, which are not fully formalized and established. In addition, the diversity of propositions for quantum-safe key-establishment algorithms is wide: at least

• 4 finalists for Post-Quantum Cryptography Standardization: 3 lattice-based and 1 code-based systems;

• 5 alternate candidates: 1 isogeny-based, 2 lattice-based and 1 code-based systems;

• CSIDH, which is an isogeny-based system.

We refer to our blog post about post-quantum cryptography for more details about the development of the post-quantum cryptography and the challenges implied.

Some articles, like [BFGJS19], [HKKP21], [BFGJS21] and [DG21] address the problem of having an X3DH-like post-quantum secure system. Compared to the classical X3DH, all of these schemes cannot completely mimic what X3DH provides (see Page 3 of [DG21] for a comparison). All require additional data to be exchanged (proofs of knowledge, ciphertexts prior to the classical encrypted messages, etc.) or different security assumptions: this shows that plugging new key exchange mechanisms to replace the Diffie–Hellman–Merkle one is not that easy and needs to be done carefully!

These Signal-like protocols are not only a theoretical problem. If solving the protocol issue is yet a big deal, having an efficient implementation of a (reduced) version of these protocols is another issue! Indeed, post-quantum cryptography for key exchange mechanisms is known to require more bandwidth to share the data and often more computational power than the classical ECDH.

The efficiency challenge is highlighted for group conversation, both in classical cryptography and in post-quantum cryptography. In the second part of the blogpost, we will detail how to achieve group conversation in multiple models, trying to always reduce the bandwidth without sacrificing the security and the user-friendliness.