The Ambassador protocol: Multi-device E2EE with Privacy

TL;DR: In this blog we present the ambassador protocol, our new cryptographic solution to enable End-to-End Encryption (E2EE) in the Multi-device setting without compromising user privacy.

We recently discovered a privacy issue with Meta’s WhatsApp, the world’s most popular Instant Messaging (IM) application.

PSA: Anyone can tell if you are using WhatsApp on your computer | TechCrunch

Meta’s WhatsApp suffers from a privacy issue that leaks the victims’ device setup information (mobile device + up to 4 linked devices) to any user, even if blocked and not in contacts. Monitoring this information over time allows potential attackers to gather actionable intelligence about victims and their device changes (device replaced/ added / removed). Additionally, message recipients can associate the message with the specific sender device that sent it.

Hi Meta, WhatsApp with privacy?

We followed up with another blog post, showing some solutions for Instant Messaging service with End-to-End Encryption (E2EE) in the Multi-device setting without compromising user privacy, to refute Meta’s claims that this problem is inherent to E2EE.

Unnecessary Evil: Multi-Device Instant Messaging can be private

Some researchers pointed out such issues are not limited to Meta’s WhatsApp only but probably relevant to all leading IM solutions, including Apple’s iMessage and even the privacy-oriented Signal Messenger

In this blog post we will detail the cryptographic solution that enables End-to-End Encryption (E2EE) in the Multi-device setting without compromising user privacy.

Instant Messaging: The postal service analogy

E2EE is commonly defined as “ a type of messaging that keeps messages private from everyone, including the messaging service. When E2EE is used, a message only appears in decrypted form for the person sending the message and the person receiving the message. The sender is one “end” of the conversation and the recipient is the other “end”; hence the name “end-to-end.” (source: cloudflare)

To better understand E2EE and its threat model we can use the postal service analogy:

Prior to E2EE, senders sent their letter in an envelope, but the envelope was not sealed. As part of its service, the post office opens the envelope and then puts it in another envelope and delivers it to the intended recipient.

This scheme has many advantages:

• Thanks to envelopes, eavesdroppers cannot see the contents of the letters.
• Thanks to the post office buffering, users do not need to meet to converse, but rather do so indirectly. This not only allows asynchronous conversations but also can protect user anonymity. Receivers can disclose only their nicknames to senders, and have the post service resolve from nicknames to true names and addresses. In fact, there is a privacy tradeoff between service and the conversation counterparty: If the conversing parties are directly connected, then the service is not exposed to the contents of the conversation, however the parties may uncover more metadata about each other and be able to break the “rules” of the protocol as the service is not there to enforce them. Generally speaking, it makes sense to assume that the service provider is more trustworthy than some counterparties that might be malicious.
• The post office can scan the contents of envelopes to make sure they do not contain bad content: Bombs, terror group messaging or pedophile photos.
• If letters are intended for multiple addresses (groups or a user with multiple houses) the post office can simply copy the message and send it to all addresses.

However, this scheme has a major drawback: Postal service employees are exposed to the contents of the letters and can leak them. The practical reasons for such leakage can vary: The service may act in negligence and mishandle user data, sell the data to advertisers for financial gain, be hacked by attackers, fail to restrict rogue employee access to private customer data, or even be served with a subpoena by the government.

When you control the mail, you control information.

To address this issue, E2EE was introduced. With E2EE, users send their message in locked boxes within the envelopes. Users provide their locks to the service when they join, but keep the keys themselves. When senders want to send a letter to a recipient they get the relevant padlock from the service and send their letter in a locked box within the envelope. As before, the post office opens the envelope and then puts it in another envelope and delivers it to the intended recipient. However, due to the locked box, the postal service personnel can no longer see the contents of the letter.

While E2EE indeed protects message content from the prying eyes of the service operator, it should be noted that:

• Even with E2EE, users must place some trust in the service provider, as the storing and forwarding messages, even encrypted, exposes metadata. Whether it’s conversationrelated (counterparties, number of messages, length of messages, timing) or operational (online status, devices used, IP addresses which may have geo-location information).
• The newly added E2EE lock creates a new identifier for the user. When users lose their key, they must issue a new lock for the service. Aware attackers might leverage this information to deduce something changed on the user side.
• To make sure the E2EE lock is indeed of the intended user and not maliciously replaced by the service or a “Monster-in-the-Middle” (MITM) attacker, the sender must verify the lock’s genuinity with the receiver using another independent channel. This requirement not only hinders the user experience but also jeopardizes the privacy of the users as they need to connect via additional service with additional identifiers.

But even with E2EE, users were still concerned: What happens if attackers break into their homes? Surely the system cannot prevent attackers from unlocking boxes and reading letters while they are still there and can use the keys, but we want to make sure that this privacy breach is limited to the exact period of the breach. Namely:

• Perfect Forward Secrecy (PFS): Attackers cannot open locked boxes that were locked before they broke into their victims’ homes.
• Post Compromise Security (PCS): Attackers cannot open locked boxes that were locked after they left their victims’ homes.

To achieve these properties, keys must be updated for every message, such that in case of compromise, the compromised keys are only useful for that message only. To do so, the two parties within the conversation are sending information to update the next locks and keys within their conversation.

It should be noted that while the first scenario of the pre-E2EE postal service privacy leak might be relevant at a large scale, for example to read the conversation of many users for serving ads or for mass surveillance, the case of post E2EE breaking into victims’ homes does not scale well and mostly relevant to a small portion of the population consisting of highly targeted individuals. Since the contents of the messages themselves cannot be protected during the time of the attackers breaking in, the scenario for which PCS and PFS are relevant is only when attackers break into the victims’ homes along with compromise of the service to get some of the victims’ locked message boxes. Having such two successful independent attacks is a much less likely scenario than each of these attacks on their own.

Signal protocol: From postal service analogy to real world crypto

WhatsApp is using the Signal protocol to implement E2EE’s “postal service locked boxes” with public key cryptography. Users create their private and public key pair on their device when they join the IM service, and provide their public keys (possibly along with additional auxiliary data) to the IM service, which maintains the directory of the user’s public keys. When parties wish to converse, the IM server provides them with their counterparty’s public keys. It should be noted, as discussed above, that the newly added E2EE public key creates a new identifier for the user. When users lose their device, they must issue a new pair of keys for the service. Aware attackers might leverage this information to infer changes on the user side and leverage them to facilitate attacks.

Leveraging both parties’ public keys, the parties can securely create a shared secret using the X3DH protocol, an extended version of the Diffie-Hellman protocol. This shared secret is then used to derive keys to encrypt the messages between the parties. While this in of itself might be sufficient to fulfill E2EE’s promise, in order to fulfill the advanced properties of E2EE, namely the aforementioned Perfect Forward Secrecy (PFS) and Post Compromise Security (PCS), more is needed.

• Perfect Forward Secrecy (PFS): Attackers cannot read messages that were encrypted before they took over the victims’ app.
• Post Compromise Security (PCS): Attackers cannot read messages that were encrypted that were encrypted after they were removed from the victims’ app.

As discussed above, to limit breached key exposure and achieve PCS and PFS, a new key for each message needs to be created. To do so the Signal protocol introduced the “Double Ratchet” algorithm. As its name suggests, the solution consists of two “ratchets” preventing attackers compromising a key to “move it forward” to read future encrypted messages, or “backwards” to read past encrypted messages :

• The Symmetric ratchet: Ensures PFS, as it uses a one-way Key Derivation Function (KDF) to prevent attackers from calculating past keys from current keys.

The Symmetric ratchet (source: signal.org )

• The Asymmetric ratchet: This ratchet (sometimes called the “Diffie-Hellman/DH ratchet”) ensures PCS as it utilizes the entropy coming from the uncompromised other party to generate new keys.

The Asymmetric ratchet (source: signal.org)

Combining the symmetric and asymmetric ratchets together gives the Double Ratchet:

• When a message is sent or received, a symmetric-key ratchet step is applied to the sending or receiving chain to derive the message key.
• When a new ratchet public key is updated via a received message, a DH ratchet step is performed prior to the symmetric-key ratchet to replace the chain keys.

Extending E2EE to the Multi Device setting: Simple solutions

As discussed above, in the pre E2EE era, the multi-device support requirements were trivial to solve. Since the IM server had access to the contents of the message, senders could just send their message once to the server, totally unaware of the receiver’s device setup and the IM server would handle its distribution to all of the receiver’s devices and sender’s other devices (so that their history would be up to date). However once E2EE is applied, the IM server cannot read the contents of the message and thus can no longer distribute them to all of the devices.

IM providers needed to address E2EE in the multi-device setting while still maintaining PCS and PFS requirements. Extending PFS and PCS definitions for the multi-device setting is quite natural:

• Perfect Forward Secrecy (PFS): Attackers cannot read messages that were encrypted before they took over the victim’s app on one device.
• Post Compromise Security (PCS): Attackers cannot read messages that were encrypted that were locked after they took over the victim’s app on one device and were removed from it.

There are two simple solutions to do so:

1. The “Leader” based solution: One of the user’s devices serves as the leader and the E2EE conversation happens between the parties leaders, in the same manner as if both users had a single device. The leaders then distribute the messages to their other devices, using E2EE between Leader and Devices. In the WhatsApp mobile based IM case, it would be natural to appoint the mobile device which was associated with the phone number that created the account as “leader” ( or “primary device” in WhatsApp lingo). This solution was applied by WhatsApp until mid-2021. However, the solution suffers from an obvious centralization drawback: When the leader device is offline, none of the other devices can communicate.
2. The Multiplication solution: In this solution, all user device public keys become public, compared to a single public key per user in the single device setting. The sender’s sending device creates an E2EE channel with each of the receiver devices, as if they were different users and uses these channels to send E2EE messages in the same manner of the single device setting. The sender device also creates such channels with all other sender’s devices and uses them to securely E2EE update other senders devices with the sent messages. This Multiplication solution is WhatsApp’s current solution for the multi-device setting. WhatsApp’s white-paper states: “In order for WhatsApp users to communicate with each other securely and privately, the sender client establishes a pairwise encrypted session with each of the recipient’s devices. Additionally, the sender client establishes a pairwise encrypted session with all other devices associated with the sender account. Once these pairwise encrypted sessions have been established, clients do not need to rebuild new sessions with these devices unless the session state is lost, which can be caused by an event such as an app reinstall or device change. WhatsApp uses this “client-fanout” approach for transmitting messages to multiple devices, where the WhatsApp client transmits a single message N number of times to N number of different devices. Each message is individually encrypted using the established pairwise encryption session with each device.”

It should be noted that WhatsApp still uses the leader concept for managing the life cycle of additional devices (or “companion device” in WhatsApp lingo). i.e. adding and removing other devices is done via the “leader” device.

While this Multiplication solution solves its predecessor’s centralization problem, it also multiplies the E2EE privacy issue. The multiplication solution exposes all of the user’s device setups and allows aware attackers to leverage this information to infer changes in the user’s devices and use it to facilitate their attacks. For example, attackers can learn without interacting with their targets, that they added a device to their setup and thus represent an opportunity to attack it, as discussed in our previous blog posts. Additionally, the receiver knows which of the sender devices’ sent to it and can infer on the sender’s real-world information, such as the physical location of the user (e.g. “my spouse is near their desktop right now”).

Besides device information leakage issues, the Multiplication solution potentially allows attackers to pinpoint their attack to a specific device. Since the sender creates independent channels with the receiver devices, it can send a malicious message to a single receiver’s device to exploit a vulnerability specific to it, e.g. mobile vs. desktop exploit, with no impact and thus detection opportunities for defenders on other devices.

The threat of device hostile takeover is very much within the IM’s E2EE threat model, as shown by the existence of the PFS and PCS requirements. Since device takeover is within the threat model, the privacy of users’ devices exposed by the Multiplication solution which allows attackers to gather information for such takeover should be addressed too.

The ambassador: Extending E2EE to the Multi-Device setting with privacy

We present the ambassador protocol: A way to modify WhatsApp’s solution to support E2EE, including its advanced features of PFS and PCS, in the multi-device setting while maintaining privacy for user device setup .

This solution can be seen as a combination of both of WhatsApp’s aforementioned solutions. Similarly to the leader based solution, all of the user devices are represented externally as a single ambassador device and thus eliminate the device setup exposure issue. To solve the Leader based solution centralization issue, we suggest decentralizing the ambassador by distributing its cryptographic state (i.e. all relevant cryptographic material) to all of the users’ devices. To securely distribute that state between all of the user devices, we leverage WhatsApp’s current Multiplication solution. Unlike when it is applied to distribute messages to the other party, when it is limited to the user’s own device group the multiplication solution does not impact user privacy as the user is already privy to the state of its own devices. For brevity, we name it “device multicast channel”.

To create such a decentralized leader, we introduce the new single ambassador key pair (each device still has its own device key pair as before). This ambassador key pair life cycle is managed by the primary device, as it already handles the companion device lifecycle:

• The leader generates the ambassador key pair upon registration.
• The leader updates the IM server with the ambassador key public key.
• The key pair, including the secret key, is securely distributed to all other devices via the device multicast channel.
• Whenever the device setup changes (device added or removed) the leader repeats this process: A new ambassador key pair is issued by the leader, updated to the IM server and distributed to all other devices.

The “Ambassador” is not tied to a specific device, but he is always there (source: brainyquote)

Specically, when Alice wants to talk to Bob:

• One of Alice’s devices (the one the user currently uses) gets Bob’s ambassador key public information from IM server, creates a shared secret and can start sending data messages immediately (property of X3DH).
• When Alice sends a message from any device:
• This message is identically duplicated by the server and distributed to each of Bob’s devices.
• Alice’s device distributes the message to each of Alice’s other devices, via the device multicast channel, along with additional crypto information as needed. Specifically:
• As Alice’s sending device updates its asymmetric ratchet DH pair for each sent message, it also distributes its DH private key to all of Alice’s other devices.
• On the first message, all of the relevant states created by Alice’s sending device (e.g. shared secret, private key of the initial DH pair) is distributed to all of Alice’s other devices.

As a result, all of Alice’s and Bob’s devices are able to follow all of the double ratchet steps, updated with all other device’s messages and able to decrypt them and maintain “the same voice” when they want to join into the conversation and send their message.

It is easy to verify that this ambassador protocol maintains E2EE confidentiality, including the advanced PFS and PCS features:

• Perfect Forward Secrecy (PFS): When attackers compromise a device, They cannot decrypt past communications as past keys are protected with the symmetric ratchet KDF.
• Post Compromise Security (PCS): Once the attackers are removed from a device that was taken over, or the user removes this companion device, the attackers do not get new DH private key updates and cannot follow the asymmetric ratchet.

It is easy to verify that this ambassador protocol solves the aforementioned privacy and security issues that the current multiplication solutions suffers from:

• The IM server does not reveal device setup information to the sender, as they are all represented by a single ambassador key.
• The receiver cannot know which of the sender devices sent the message to it, as they all “speak with the ambassador’s voice”.
• Since the sender’s messages are broadcasted to receiver devices via the IM server, it prevents that attacker from pinpointing their maliciously crafted message to a single device.

It should be noted that changes to device setup still can be detected by attackers, as they are reflected in changes to the ambassador key, however, since they are aggregated, the attacker cannot tell the nature of this change (devices added or removed) which can be considered as a privacy improvement even compared to the single device E2EE privacy in which the key directly reveals changes to the device.

While this ambassador protocol is inspired by the “Multi-Device for Signal” 2019 paper that suggests a unified distributed state entity, it presents multiple advancements in implementing the device multicast channel by leveraging WhatsApp’s existing Multiplication solution that was not created in 2019.

Additionally, due to its generic nature, we believe that the Ambassador protocol is not limited to the Signal protocol only, but relevant for any IM E2EE protocol.

Parting thoughts

The field of IM E2EE and especially user privacy with it gets a lot of attention and innovation, as many vendors have recently extended their IM E2EE offering to allow username-based private communications

Keep your phone number private with Signal usernames

or Post Quantum Crypto support

Blog - iMessage with PQ3: The new state of the art in quantum-secure messaging at scale - Apple…

Therefore, it is time to address also the privacy issues that E2EE in the multi-device setting has introduced. As we have shown, there are a number of feasible solutions.