Ideas

Towards a simple secure messaging protocol with forward secrecy

by | Published

Here is a possible approach to a very simple secure messaging protocol. The simplicity is intended to make the protocol robust and easy to analyse. The well-known Signal protocol and others use a famous “double ratchet” and public key cryptography. This protocol uses a single ratchet and symmetric cryptography.

Motivations for simplicity

A 48-page cryptography paper with five authors analysing ratcheting protocols like Signal from a provable security point of view includes in the introduction “Our intent is to formalize and understand the simplest form of ratcheting that captures the essence of the goal, which is single, one-sided ratcheting. This (as we will see) is already complex enough. Extended forms of ratcheting are left as future work.” [1]

The Signal protocol allows missing and out-of-order messages. Regardless of whether this creates additional difficulties in security analysis, no motivation is provided for it, and higher level protocols are normally expected to guarantee the opposite. For example, on the internet, and unreliable and possibly out-of-order packet delivery is provided by IP and the higher level TCP running on top of it guarantees bytes arrive in order.

The simple protocol proposed here will guarantee that messages are not dropped and that they arrive in order. One advantage will be that the parties can agree on a transcript of the conversation. In fact it will be possible for example to derive a transcript hash which they could later compare to check for a MITM attack.

Forward secrecy

A currently passive attacker who is spying on and storing the encrypted traffic now might later obtain the keys to decrypt it. So-called forward secrecy is realised by destroying those keys to prevent this. They can be destroyed at the transmitting side as soon as the traffic has been encrypted, and at the receiving side as soon as the traffic has been decrypted.

The ratchet

The general idea of the ratchet was to derive the next key from the current key by applying a one-way function that is hard to reverse, something essentially like a cryptographic hash. This process would mean that an attacker obtaining a key cannot derive from it any key used earlier.

Here the proposal is to also mix in true randomness from the machine's hardware at each ratchet step. In fact if cryptographic-quality random numbers are available, it is not clear that the one-way function is even necessary, but it is in this design as an insurance against RNG failure or low quality random numbers. One advantage of the additional randomness is that an attacker with an incomplete traffic record is unable to ratchet over the gap.

The randomness to be mixed in defines what will be called here a ratchet proposal. For the ratchet to the next key one party uses its true random number generator to generate a ratchet proposal. It sends this proposal to the other party under the current key and then ratchets its own key. When a party decrypts a ratchet proposal it immediately ratchets the key and destroys the old key it has just used for decryption.

Ratcheting in this description always means also erasing the key held immediately before.

The proposed protocol

It works between two parties only, who have already a pre-shared symmetric key. Sharing this initial key is outside the scope of this protocol.

A fundamental simplification compared to other protocols is that messages are always sent in a “ping-pong” fashion, meaning each party can send a message only after receiving a message from the other. The key is updated after every single message. Figure 1 shows operation of the protocol when no packets are lost or corrupted.

 Alice        Alice's PC          Bob's PC             Bob
   |             |                    |                 |
   |-----M1----->|                    |                 |
   |     R2 := Random()               |                 |
   |     C1 := Encrypt(K1, R2|M1)     |                 |
   |     K2 := Ratchet(K1, R2)        |                 |
   |             |------C1----------->|                 |
   |             |            R2|M1 := Decrypt(K1, C1)  |
   |             |                    |-------M1------->|
   |             |            K2 := Ratchet(K1, R2)     |
   |             |                    |                 |
   |             |                    |<------M2--------|
   |             |            R3 := Random()            |
   |             |            C2 := Encrypt(K2, R3|M2)  |
   |             |            K3 := Ratchet(K2, R3)     |
   |             |<------C2-----------|                 |
   |     R3|M2 := Decrypt(K2, C2)     |                 |
   |<----M2------|                    |                 |
   |     K3 := Ratchet(K2, R3)        |                 |
   |             |                    |                 |
   |             |                    |                 |
   |-----M3----->|                    |                 |
   |     R4 := Random()               |                 |
   |     C3 := Encrypt(K3, R4|M3)     |                 |
   |     K4 := Ratchet(K3, R4)        |                 |
   |             |------C3----------->|                 |
   |             |                    |                 |
Figure 1. The protocol working with no missing packets and no attack. The labels C1, K2 etc are intended to identify a value that comes out of the process shown. For example C2 is a ciphertext encrypted under key K2, which contains message M2 and random string R3. R3 and K2 are inputs to the ratchet function to derive K3.

Messages can never be lost or arrive out of order because a party never sends a different message until it has seen an acknowledgement of the last message it sent. Ciphertexts are idempotent, meaning after a ciphertext has once been received, further receipts of an identical ciphertext have no effect on the cryptographic protocol state of the receiving party. Apparent packet loss is handled by the sender resending an identical ciphertext, even though the sender will no longer have the key to it. Conceptually this looks like a retransmission at a lower layer of a protocol stack even though the cryptographic layer is aware of it. Figure 2 shows the protocol operating with a dropped packet.

 Alice        Alice's PC          Bob's PC             Bob
   .             .                    .                 .
   .             .                    .                 .
   |             |<------C2-----------|                 |
   |     R3|M2 := Decrypt(K2, C2)     |                 |
   |<----M2------|                    |                 |
   |     K3 := Ratchet(K2, R3)        |                 |
   |             |                    |                 |
   |-----M3----->|                    |                 |
   |     R4 := Random()               |                 |
   |     C3 := Encrypt(K3, R4|M3)     |                 |
   |     K4 := Ratchet(K3, R4)        |                 |
   |             |------C3---->//     |                 |
   |             |                    |                 |
   |             |                    |<--Retry-please--|
   |             |<------C2-----------|                 |
   |             |------C3----------->|                 |
Figure 2. The protocol operating with packet loss. Here the first transmission of ciphertext C3 fails. At some point Bob decides the reply has taken too long and resends ciphertext C2. Alice no longer has key K2 and cannot authenticate or decrypt C2 but recognises the duplicate because she has kept a copy of the last valid ciphertext she received. She sends a duplicate ciphertext C3 from the copy she kept of the last ciphertext she sent, for which she also no longer has the key. The duplicates leak some information about what is happening, which is a potential drawback of this protocol.

The protocol for both parties is identical, but they have to decide in advance who is going to send the first message. There would be a problem if both sent a first message (before receiving each other's) because then they would ratchet the key differently.

All packets transmitted are encrypted and authenticated with a MAC tag. The MAC can be generated either by a combined authenticated-encryption mode (AEAD) or by separate encryption and MAC. The term “key” will be used here in both cases but in the case of separate MAC and encryption, “key” in more detail means a shared secret from which a MAC key and a separate encryption key will be derived by some standard KDF (key derivation function).

There must be a negligible chance of (anyone) generating a ciphertext with a valid MAC tag without knowing this key, so the tag must be at least 128 bits. When Alice receives a packet with a valid MAC under her current key she knows that Bob has received the last packet she sent and performed its proposed key ratchet, as will be explained.

Each key is used for only one ciphertext and is then immediately ratcheted. Just after Bob has sent a ciphertext, the only key he he holds is unrelated to any ciphertext that has ever yet been sent by either party. Just after receiving this ciphertext, the only key Alice holds is the same as the one Bob is holding, and so unrelated to any ciphertext ever yet sent. This is forward secrecy.

The ciphertext contains not only the user plaintext as payload but also fields needed for the ratcheting protocol. Only one kind of packet is ever sent. It always contains the following.

The state machine of each party

This section is intended to exhaustively describe what each party in the protocol must do in all possible conditions.

The state kept by each party consists of only

The possible events that the state machine responds to are the following:

On receiving a ciphertext

Check the received MAC using the current key. If the MAC is valid then:

If the MAC is invalid but there is a copy of the last ciphertext received then compare the ciphertext byte by byte with this copy. If it is identical then:

Otherwise if the MAC is invalid then drop the packet, possibly informing the user.

On a request to send a message

A new ciphertext may be sent only when it is this party's turn to speak.

If the current state includes a copy of a last unanswered ciphertext sent, then there is a reply pending and it is not this party's turn to speak. This could be indicated to a user wanting to send a message. What is allowed is repeating the previous sent message, (which applications might use to indicate that the sender would like a reply and the chance to send something more) and this can be done at any time without changing state. The copy of the last ciphertext sent is used to send it again.

Otherwise, if there is no copy of an unanswered ciphertext, then it is this party's turn to speak, and a new message can be sent, as follows.

Cryptographic modes

Ideally we would like the encrypted packet to be indistinguishable from random bytes to anyone not knowing the key. However most cryptographic modes require a nonce or an IV used by the encrypting party which the decrypting party must somehow (“magically” [1]) know. This protocol, which never uses the same key twice, could use a fixed nonce which it never sends. But using a nonce has the potential to cause security problems with the first packet, as explained below. An alternative is to use a mode with a random IV rather than a nonce.

Limitations

Resending identical ciphertexts leaks the information that the message is identical and that it is part of the same communication session.

Replay attacks are possible though they cannot compromise secrecy. The protocol state machine replies to a replay of the last packet received by repeating its previous reply. This might be used by an attacker to confirm whether a party was listening at a certain endpoint. If a resending of the same packet is used as a way of requesting a reply, then an attacker replaying the last packet would be an annoyance.

Bob and Alice have to decide in advance who is going to send the first packet and stick to this decision. If they both send (as they each suppose) a first packet, then they will both ratchet the key, each using their own randomness. Not only will they then no longer hold any secret in common, but there will be a worse problem. If the protocol is implemented with a nonce-based cryptographic mode, then they will each have sent a different packet with the same nonce under the same key.

Further work

The protocol could be modified in several ways. Firstly, rather than being symmetrical it could have one party sending only acknowledgements and one party transmitting messages. Then two instances of the protocol could be run independently and in opposite directions. The benefit of acknowledgements only is that they would be immediate. The benefit of a duplicate protocol is that once it is proven secure and implementations are secure then using it twice needs no further analysis.

For the use-case where Bob and Alice meet to share a strong secret, various problems, including who is to send the first message, might be solved along the following lines. They share a secret, but this is not directly used as a key. Instead they also agree on names or nick names for each other. Then each puts the shared secret through a KDF with the nicknames they have agreed on as some kind of additional data. Alice uses the KDF with the additional information string “Alice” and the result is her sending key, and she uses the KDF with the string “Bob” and that is her receiving key. The danger of them both sending under the same key is gone. If two protocols are to be run, one in each direction, then these can be the first keys.

Another variation would be that Bob's computer acknowledges receiving a message from Alice immediately and ratchets the key and then some time later Bob sends a message (possibly under the same key). When Alice receives the acknowledgement, she knows that she is waiting for Bob rather than for her packet to be delivered. This might mean that the one acknowledgement and one message would be sent under the same key, or at least if there is an extra ratchet it is without additional randomness. But the acknowledgements would not contain any information on the message contents. In fact, it is not clear that the acknowledgement should have any content. It just needs a MAC to ensure it is authentic.

Terminology

AEAD
Authenticated encryption with associated data
IV
Initialisation vector
KDF
Key derivation function
MITM
Man in the middle
RNG
Random number generator

References

[1]

Ratcheted Encryption and Key Exchange: The Security of Messaging Mihir Bellare, Asha Camper Singh, Joseph Jaeger, Maya Nyayapati, Igors Stepanovs, June 2017

In 2024 at https://eprint.iacr.org/2016/1028.pdf was a PDF with SHA256 hash 036ec1b58454841c1e9c4dd718d78a12722a518c00eb36909f6676d84e0eeb41.

[2]

Nonces are Noticed: AEAD Revisited Mihir Bellare, Ruth Ng, Björn Tackmann, November 2019

In 2026 somewhere on the web was a PDF file with SHA256 hash fe382d8fcdad42efde84801643a9d2f25dac6aa21def481ecbdfe5ca0f9788f6.

Related articles