unMessage Protocol

This section describes the logic for sending/accepting requests and exchanging messages in Establishing Conversations, as well as the packets used in each of those stages in Packet Formats.

Establishing Conversations

The unMessage protocol is based on the Double Ratchet Algorithm to establish conversations and exchange messages privately and anonymously.

Note

unMessage uses Tor Onion Services to anonymously connect peers as we believe that it is the best transport for this kind of application, but other approaches such as posting the packets to a public mailing list should also work (as long as the packets are anonymously posted).

In the Double Ratchet Algorithm, a secret key must be agreed on to derive all the other keys involved in the conversation. The secret key used by unMessage is generated with the Triple Diffie-Hellman Key Agreement, using one party’s public identity and handshake keys, and another’s private identity and handshake keys.

Each party must have its mode assigned to as either Alice or Bob. The one who starts the initialization is Bob and can send messages right after the secret key is generated. As part of the initialization, Bob must send his public ratchet key to Alice so that she is able to start the Diffie-Hellman ratcheting and also send messages immediately.

unMessage conversations have the following stages:

  1. Request sent
  2. Request accepted
  3. Conversation established

In order to send requests, both parties must launch unMessage to generate their Onion Service and Double Ratchet keypairs. unMessage is a serverless application, so a peer who wishes to receive requests must send/publish their Onion Service address and Double Ratchet public identity key through some other communication channel.

unMessage assigns Bob to the one who sends a request and Alice to the one who receives it.

Important

In the following sections, the shared request key and conversation ID are described as the direct input of hash and encryption functions for simplicity. In fact, these keys are input of a Key Derivation Function (KDF) along with its respective salt, and the output keys of the KDF that are actually used by such functions.

Stage 1: Request sent

A request keypair is generated by Bob’s unMessage to derive a Diffie-Hellman shared request key using the private request key and Alice’s public identity key. The shared request key, is used to encrypt the following information needed by Alice to initialize a conversation with Bob:

  • Bob’s identity address
  • Bob’s identity public key
  • Bob’s handshake public key
  • Bob’s ratchet public key

This set composes the handshake packet, which after encrypted is used to compose the request packet:

  • IV
  • hash(IV + Alice’s public identity key + shared request key)
  • keyed_hash(shared request key, encrypted handshake packet)
  • public request key
  • encrypted handshake packet

The packet is then sent to Alice’s Onion Address and Stage 1 is completed.

Important

The handshake packet should be signed by the Onion Service and Double Ratchet keys so that a peer cannot advertise keys they do not own. This will be implemented in a future version of unMessage.

Stage 2: Request accepted

After receiving the request packet, Alice’s unMessage derives the shared request key using Alice’s private identity key and the public request key. The shared request key is hashed with the IV and the handshake packet to make sure that is indeed an unMessage request packet and the handshake packet can be decrypted. Alice is notified that the request was received from Bob and accepts it to initialize the Double Ratchet conversation.

Bob’s public identity and handshake keys sent in the handshake packet are used to generate the Double Ratchet secret key with Alice’s private identity and handshake keys (the former was generated when unMessage was launched by the first time and the latter when the request was accepted, to be used for this specific conversation). The Double Ratchet conversation is finally initialized using the secret key and Bob’s public ratchet key (also sent in the handshake packet). At this point, Stage 2 is completed and Alice can start sending encrypted messages. However, as Bob does not have Alice’s public handshake key, it is encrypted (using the shared request key) and sent along with the unMessage reply packet:

  • IV
  • hash(IV + Bob’s public identity key + shared request key)
  • keyed_hash(shared request key, encrypted handshake key + encrypted payload)
  • Alice’s encrypted public handshake key
  • encrypted payload

Stage 3: Conversation established

When messages from Alice are received, Bob’s unMessage hashes the shared request key with the IV and Alice’s encrypted public handshake key concatenated with the encrypted payload to make sure that is indeed an unMessage packet from Alice, and her public handshake key can be decrypted. Bob now can also generate the secret key with his private identity and handshake keys, and Alice’s public identity and handshake keys. With his part of the conversation initialized, he can start sending unMessage regular packets:

  • IV
  • hash(IV + Alice’s public identity key + conversation ID)
  • keyed_hash(conversation ID, encrypted payload)
  • encrypted payload

Stage 3 is completed when Alice receives a regular packet from Bob, which means that he was able to initialize the conversation with her public handshake key and there is no need to send reply packets anymore, so her unMessage also starts sending regular packets.

Identifying conversations

All of the identifying information of an unMessage packet is encrypted so that an attacker who intercepts it cannot tell who are the receiver and sender.

When a packet is received, unMessage assumes it is a regular packet and attempts to use all of the peer’s conversation IDs to derive the IV hash. If the hash matches the packet’s IV hash, unMessage identifies the sender and is able to decrypt the payload (after verifying its integrity). If the IV hash does not match, unMessage assumes the packet is a request packet and derives a shared request key using the public request key from the packet and the peer’s public identity key. unMessage attempts to use the shared request key and the IV to derive a hash that matches the packet’s IV hash. If it matches, unMessage checks the integrity of the rest of the packet and processes the request as described in Stage 2.

When unMessage fails to identify or check the integrity of packets, they are ignored.

Note

The IV hash also uses the receiver’s public identity key as part of the hash so that, for example, Alice can tell the difference between messages she sent to Bob and messages she received from Bob.

The IV hash is another implementation of an hSub.

Packet Formats

unMessage’s conversations have three stages, each using a different packet format:

  • Request: contains Bob’s name, address and keys (identity, handshake and ratchet)
  • Reply: contains Alice’s key (handshake) and optionally an encrypted element
  • Regular: contains an encrypted element

Note

Elements are the plaintext of the information exchanged in unMessage’s conversations, which are wrapped by Double Ratchet’s encryption and added to reply/regular packets for transmission. (e.g., presence notifications, text messages, authentication buffers)

The following sections summarize what each packet is used for, their exact contents and their size in bytes.

(In the following diagrams, data surrounded by === is encrypted)

Request Packet

To notify Alice that Bob wishes to establish a conversation with her, he must send all the information she needs to complete this process. The information is sent in a request packet:

+------------------------------------------------+
| Request packet (240 + address)                 |
+------------------------------------------------+
| IV (8)                                         |
| IV Hash (32)                                   |
| Keyed hash (32)                                |
| Public request key (32)                        |
|                                                |
| +--------------------------------------------+ |
| | Encrypted handshake packet (136 + address) | |
| +--------------------------------------------+ |
| | Nonce (24)                                 | |
| | MAC (16)                                   | |
| | +========================================+ | |
| | | Identity address                       | | |
| | | Public identity key (32)               | | |
| | | Public handshake key (32)              | | |
| | | Public ratchet key (32)                | | |
| | +========================================+ | |
| +--------------------------------------------+ |
+------------------------------------------------+

The request key is used to derive a shared request key with Alice’s identity key in order to encrypt Bob‘s information so that only the ones in possession of the private request or identity keys are able to read who sent the request.

Reply Packet

Once Alice accepts the request, she is able to send encrypted elements to Bob, who sent all information required by her to initialize a conversation. However, as Bob needs her handshake key, she adds it before the payload of the message, in case an element should also be included. This information is sent in a reply packet:

+------------------------------------------------+
| Reply packet (192 + 72 + payload)              |
+------------------------------------------------+
| IV (8)                                         |
| IV Hash (32)                                   |
| Keyed hash (32)                                |
|                                                |
| +--------------------------------------------+ |
| | Encrypted public handshake key (72)        | |
| +--------------------------------------------+ |
| | Nonce (24)                                 | |
| | MAC (16)                                   | |
| | +========================================+ | |
| | | Public handshake key (32)              | | |
| | +========================================+ | |
| +--------------------------------------------+ |
|                                                |
| +--------------------------------------------+ |
| | Encrypted payload (120 + payload)          | |
| +--------------------------------------------+ |
| | +----------------------------------------+ | |
| | | Double Ratchet header (80)             | | |
| | +----------------------------------------+ | |
| | | Nonce (24)                             | | |
| | | MAC (16)                               | | |
| | | +====================================+ | | |
| | | | Ns (3)                             | | | |
| | | | PNs (3)                            | | | |
| | | | DHRs (32)                          | | | |
| | | +====================================+ | | |
| | | Padding (2)                            | | |
| | +----------------------------------------+ | |
| |                                            | |
| | +----------------------------------------+ | |
| | | Double Ratchet payload (40 + payload)  | | |
| | +----------------------------------------+ | |
| | | Nonce (24)                             | | |
| | | MAC (16)                               | | |
| | | +====================================+ | | |
| | | | Payload                            | | | |
| | | +====================================+ | | |
| | +----------------------------------------+ | |
| +--------------------------------------------+ |
+------------------------------------------------+

In order to send multiple messages to Bob (which might be delivered out of order), Alice must continue to send her handshake key until Bob replies (signaling that he was able to establish a conversation as well). To prevent reply packets from being linked by leaking the handshake key, it is encrypted using the shared request key used in the encryption of the request packet sent by Bob.

Regular Packet

Once both peers have initialized their sides of the conversation, there is no need for Alice to send the handshake key anymore. The only content subsequent exchanges transmit are their payloads. This information is sent in a regular packet:

+------------------------------------------------+
| Regular packet (192 + payload)                 |
+------------------------------------------------+
| IV (8)                                         |
| IV Hash (32)                                   |
| Keyed hash (32)                                |
|                                                |
| +--------------------------------------------+ |
| | Encrypted payload (120 + payload)          | |
| +--------------------------------------------+ |
| | +----------------------------------------+ | |
| | | Double Ratchet header (80)             | | |
| | +----------------------------------------+ | |
| | | Nonce (24)                             | | |
| | | MAC (16)                               | | |
| | | +====================================+ | | |
| | | | Ns (3)                             | | | |
| | | | PNs (3)                            | | | |
| | | | DHRs (32)                          | | | |
| | | +====================================+ | | |
| | | Padding (2)                            | | |
| | +----------------------------------------+ | |
| |                                            | |
| | +----------------------------------------+ | |
| | | Double Ratchet payload (40 + payload)  | | |
| | +----------------------------------------+ | |
| | | Nonce (24)                             | | |
| | | MAC (16)                               | | |
| | | +====================================+ | | |
| | | | Payload                            | | | |
| | | +====================================+ | | |
| | +----------------------------------------+ | |
| +--------------------------------------------+ |
+------------------------------------------------+

Important

Despite the fact that each packet’s contents look like random information, in the current version of unMessage all of them have a different size. In the future, all packets should be padded to a fixed size in order to achieve indistinguishability.

Threat Model

unMessage is characterized by the packets it creates and processes, and the transport used to transmit such packets between its peers. Tor Onion Services is the current supported solution used to connect peers, but as unMessage employs an application protocol that manages its own packets, it would be possible to allow the use of other transports as long as such packets are transmitted from one peer to another, anonymously.

It is expected that the transport connecting the peers conceals their real identity, location and path of transmissions from each other as well as from an external adversary observing the network that is not as powerful as a Global Passive Adversary. From this perspective, unMessage is susceptible to the same security vulnerabilities as the transport in use.

Although unMessage expects that information to be anonymously exchanged between the peers, it does not require anything beyond that because by default its packet format provides:

  • Integrity
  • Authenticity
  • Confidentiality
  • Anonymity

As conversations are established between peers with Double Ratchet sessions, they also benefit from the properties of:

  • Forward secrecy
  • Future secrecy
  • Deniability

Adversary Capabilities

From the application’s perspective, taking into account the local server availability, packet creation and packet processing, we assume the following capabilities from an adversary:

  1. An adversary is unable to break the cryptographic primitives used by unMessage.
  2. An adversary is able to observe, intercept, replay and modify all packets exchanged by the peers.
  3. An adversary is able to send requests and malformed packets to a peer whose unMessage address and public identity key has been acknowledged by them.
  4. An adversary is unable to perform an attack by making multiple connections or sending multiple requests to a peer whose unMessage address has been acknowledged by them, making that peer unavailable to others.
  5. An adversary is unable to send malformed/malicious elements to a peer who accepted their request and therefore has established a conversation with.
  6. An adversary is unable to compromise a peer’s private identity key to impersonate them in current and future conversations.
  7. An adversary is unable to compromise a peer’s private identity key to decrypt any of the requests they received/accepted.

Possible Attacks

Some limitations to the adversary’s capabilities had to be imposed due to the current implementation of unMessage, which does not yet prevent some of the attacks mentioned in Adversary Capabilities:

  • unMessage maps an Onion Service to a local server that accepts connections and receives netstrings to be parsed as unMessage packets. This behavior allows an adversary who has knowledge of a peer’s Onion Service address to perform the attack mentioned in item 4, by either making the Onion Service inaccessible in the network or overloading the unMessage instance.
  • Although unMessage validates the format of the packets it expects to receive and an adversary cannot make any modifications due to the integrity checks, once a packet is decrypted after being validated by passing such checks, there is not yet a mechanism validating the conversation elements (i.e., the plaintext of reply/regular packets) and the attack mentioned in item 5 is possible to be performed.
  • The attack mentioned in item 6 can be mitigated as unMessage provides an authentication feature. As long as the users have securely agreed on a secret that is not known by the adversary, the party who the impersonator is communicating with can use it to initiate the authentication process and detect the attack. Even though any user can initiate the authentication at any time after a conversation is established, it is up to them to properly handle the secret and regularly authenticate themselves - or at least do so under any suspicion. Even if users take such actions, unMessage is only able to detect instead of prevent it.
  • All the peer information required to send/receive conversation requests is encrypted with a shared secret derived from a Diffie-Hellman key exchange using Bob’s request key and Alice’s identity key. The request key is ephemeral and is disposed once the conversation is established, but the identity key is not. For that reason, the attack mentioned in item 7 is possible to be performed but not prevented by unMessage.