On the Feasibility of Secure Traceability in End-to-End Encrypted Messaging

2021-06-02

Update (August 2nd, 2021, 7:00PM CEST): Professor Matthew Green has written an elaborate article that further explores the questions discussed in this post. I recommend reading it.

WhatsApp recently published an article titled “What is traceability and why does WhatsApp opposite it?”, in which it argues that “some governments” (a reference to Facebook’s current lawsuit against the Indian government) “are seeking to force technology companies to find out who sent a particular message on private messaging services. This concept is called ‘traceability.’”

WhatsApp’s article states that “technology and privacy experts have determined that traceability breaks end-to-end encryption”. As an applied cryptographer who’s been closely involved in research on secure messaging for a decade, I was surprised by this statement for two reasons:

  1. I have never seen any necessary, irrevocable link being established between traceability properties and confidentiality properties in secure messaging.
  2. I have never seen any open discussion between experts on the security impact of traceability properties on end-to-end encrypted secure messaging.

Oddly, while WhatsApp’s article claims that there is consensus between “technology and privacy experts” on the topic, every source that WhatsApp’s article quotes happens to be a legal or social non-profit, and not a source of technical expertise: Access Now, Internet Society, Center for Democracy and Technology, etc. — this substantiated a worry in me that WhatsApp was attempting to claim that a technical consensus existed for ideological reasons, whereas no such consensus exists since, to my knowledge, the necessary discussion for its existence hadn’t even had the chance to occur.

Is secure traceability possible in secure messaging? WhatsApp claims that expert consensus indicates otherwise — but not only does such a technical consensus not exist; it is contradicted by systems that WhatsApp’s parent company, Facebook, already employs in practice in end-to-end encrypted systems.

Within a short while of WhatsApp’s article being published, however, some public experts began to agree with its expressed opinions with surprising speed, leading me to wonder if they had the time to investigate the serious theoretical and technical question as to whether a link between traceability and confidentiality/authentication in end-to-end encrypted messaging actually exists:

So, let’s try to answer the following question more seriously: is secure traceability possible in secure messaging?

Facebook Messenger already implements the potential foundations for traceability.

In 2016, Facebook introduced an anti-abuse measure known as message franking. Franking is known to be deployed at least in Facebook Messenger, and is probably also deployed (and certainly deployable in theory) in WhatsApp.

The reality is that “message franking” is secure traceability cloaked in the veneer of abuse reporting. To quote page 11 of Facebook’s whitepaper:

Franking tag Authenticity for messages in a secret conversation is provided by the Franking tag TF. Senders must send the Franking tag along with each encrypted message. To compute TF, the sender first generates a 256-bit random nonce NF. NF is added to the unencrypted message being transmitted. Next, the entire data structure is serialized into a string M, and TF is computed as:

TF = HMAC·SHA256(NF, M)

NF remains within the serialised, encrypted data sent to the recipient. The sender destroys any other copies of NF after transmission. TF is transmitted to Facebook along with each encrypted message.

Franking messages When Facebook receives TF, it uses a Facebook key KF to compute the Reporting tag RF over TF and conversation context (e.g., sender and recipient identifiers, timestamp) as:

RF = HMAC·SHA256(KF, TF || context)

Both TF and RF are sent to the recipient along with the encrypted message. The recipient decrypts the ciphertext, parses the resulting plaintext to obtain NF, and verifies the structure of TF prior to displaying the message. If TF is not verified then the recipient discards the message without displaying it. The recipient stores the message M, NF, TF, RF and context in its local storage.

The above constitutes a full implementation of a form of traceability that Facebook employs to this day. Reporting abusive messages using franking is voluntary, but the calculation of the franking tags TF and RF is not, and happens automatically with each message sent.

Security and Privacy The authenticity properties of the franking mechanism are based on reasonable assumptions about the collision-resistance of the SHA256 hash function and the unforgeability of HMAC·SHA256.

Authenticity In order to “forge” invalid content M0, a user must either (a) produce a forged HMAC tag under Facebook’s key KF, or (b), identify a collision NF0, M0, context0 such that the HMAC of these values is equal to the HMAC of a different valid message M sent through Facebook.

Confidentiality Similarly, under reasonable assumptions about HMAC·SHA256, the resulting tag reveals no information about the message to Facebook or to eavesdroppers.

Above, we see that Facebook itself claims that the above approach allows for reporting abusive messages without compromising confidentiality. WhatsApp’s claims are therefore contradicted by Facebook itself!

The above mechanism can be extended to allow for secure traceability. In the most naïve case, Facebook can immediately allow traceability to the Indian government simply by sharing KF and with minor changes to its messenger application.

In order to then securely trace a potential message, the following procedure can be followed:

  1. The plaintext that is to be traced is submitted along with RF, NF and context. This is precisely the same procedure as Facebook’s existing message franking protocol, with the exception that a guess for the plaintext is submitted — since the Indian government already knows which plaintext it wants to trace, we assume that they already have a good guess for it. Note that since we’re already looking for a message the contents of which we are guessing for a-priori, confidentiality isn’t violated in the same sense that it would be via a lawful intercept program.
  2. In exact accordance with the existing message franking protocol, Facebook recomputes TF and then validates RF using the provided information as well as its internal key KF.
  3. Determining the initial originator of a message is simple: we simply order the franking tags by date, which is already part of the context value as a timestamp.

So, as clearly outlined above, we are simply replacing a “message franking request” with a “traceability request” — the protocol remains the same.

WhatsApp’s claim that consensus exists against secure traceability is misleading.

Is traceability “good” or “bad”? Is it desirable or undesirable? It’s not up to me to answer those questions. But in this case, WhatsApp appears to have used a moral opinion (i.e. that traceability is bad and undesirable) in order to make a claim regarding a technical consensus (i.e. that secure traceability is impossible) that does not actually exist.

Not only does such a technical consensus not exist; it is contradicted by systems that WhatsApp’s parent company, Facebook, already employs in practice in end-to-end encrypted systems.

WhatsApp’s claims that consensus exists against secure traceability simply isn’t true. The question not only remains open, but research in secure messaging indicates the opposite: that forms of secure traceability are likely possible and already feasibly, partially implemented in consumer products.

What is more likely happening here is that WhatsApp is girding itself for what it feels is likely to be an easy fight with a third-world government that it can push around — a likely mistaken way for it to restore some good faith with the privacy community after damning defeats and rejections by the European Union for its invasive privacy practices.