Everything around the message

Communications law in the United States and many other countries draws a line between content and metadata, and protects the first far more than the second. A law enforcement officer can request telephone calling records "with merely a subpoena — essentially a formal letter from the investigating agency." The assumption underneath that line is that the outside of the envelope is not very revealing. In 2016, Jonathan Mayer, Patrick Mutchler and John C. Mitchell tested the assumption instead of arguing about it. They crowdsourced logs from 823 participants, covering 251,788 calls and 1,234,231 text messages, and reported that telephone metadata "is densely interconnected, can trivially be reidentified, enables automated location and relationship inferences, and can be used to determine highly sensitive traits."

Nothing in that study needed a single word of any conversation. End-to-end encryption is orthogonal to it.

What a relay sees

Any messenger that delivers asynchronously has a server, and that server needs to know where to put a message. At minimum it learns the recipient. In practice it learns much more: the sender, the timestamp, the size, the source address, and the pattern — a conversation is a burst of small envelopes alternating between two identities, and that shape is legible even when every byte inside is opaque.

Sealed sender, and its limits

Signal's answer, previewed in October 2018, is sealed sender: take the "from" address off the outside of the package. Two mechanisms make it workable. Clients "periodically retrieve a short-lived sender certificate from the service attesting to their identity," containing the phone number, public identity key and an expiry, so a recipient can verify a sender the server never saw. And to stop the anonymous channel becoming a spam channel, clients "derive a 96-bit delivery token from their profile key and register it with the service"; the service requires proof of knowledge of that token before it will carry a sealed-sender message to that user.

What it does not remove is stated in the same post, by Signal, without spin: "additional resistance to traffic correlation via timing attacks and IP addresses are areas of ongoing development." The recipient is still visible. The timing is still visible. Your address still reaches the server.

And there is a sharper limit. In 2021, Ian Martiny, Gabriel Kaptchuk, Adam Aviv, Dan Roche and Eric Wustrow showed at NDSS that sealed sender's "one-sided anonymity is broken when two parties send multiple messages back and forth; that is, the promise of sealed sender does not compose over a conversation of messages." Their statistical disclosure attack is made "particularly effective by delivery receipts that inform the sender that a message has been successfully delivered, which are enabled by default on Signal," and they conclude that Signal "could link sealed sender users in as few as 5 messages." Worse, it operates at the application layer, so it works against users behind Tor or a VPN who would otherwise be safe from network-level tracing.

Sealed sender is a real improvement and it is not anonymity. Both statements are true, and only one of them makes a good headline.

Not sending the question at all

The other half of the problem is lookup rather than delivery: to build a contact list you tell a server who you know. Signal has been explicit about the difficulty since 2017, when it described running contact discovery inside an Intel SGX secure enclave with remote attestation, so that a client can check "the code running on our servers was the code they wanted to be running on our servers." That is a real design, and its trade-off is equally real: you are trusting a CPU vendor's attestation rather than a mathematical argument.

Private information retrieval is the alternative that needs no such trust. The client encrypts its query, the server computes over the ciphertext without ever seeing the keyword, and returns an encrypted answer only the client can open. This has left the whiteboard: Apple has described using homomorphic encryption together with PIR and private nearest-neighbour search in production. The costs are honest ones — more bandwidth and far more server computation than a plain lookup — and PIR answers questions about a database. It does not deliver a message to a person, so it addresses discovery, not the envelope.

What minimisation actually buys is best measured by what a subpoena returns. Signal's published position is that "the only information we can produce in response to a request like this is the date and time a user registered with Signal and the last date of a user's connectivity to the Signal service."

What OSHI's relay sees

Ours is worse than that, and this is the part of the article that is not about anyone else. OSHI's relay envelope carries from, to, a message type, an optional groupId, a client timestamp and a server-assigned sequence number, beside the opaque header and ciphertext. There is no sealed sender. The relay can therefore see who talks to whom and when, which is precisely the material the 2016 study was about.

One consequence is worth spelling out because it is not obvious from the field list. For a group message the client fans out one envelope per member, each carrying the same groupId. A relay that simply logs what it routes can reconstruct group membership from the repetition, without decrypting anything.

This is an open finding, not a solved problem, and we are not going to describe it as a design choice. Sealed sender is a substantial piece of work — a certificate authority for senders, a delivery-token scheme, an abuse story that no longer has a sender to rate-limit — and the NDSS result says that even after all of it the property does not survive a conversation without further defences. We would rather publish the gap than a diagram of a padlock.