So, what is a private messenger? Many would just say that a messaging app is private if the messages it conveys are encrypted. But in reality, messaging privacy is a lot more complex than that. At the Chaos Communication Congress, Roland Schilling and Frieder Steinmetz gave a talk in which they explained in simple words what a private messenger is and what attributes a messaging app must have to be considered private.
The six pillars of private conversation
To understand the idea of private messaging, Schilling and Steinmetz suggest that we imagine trying to have a private conversation at a party. What do we do to make that conversation private? We probably find a secluded room, where no one but the person we wanted to talk to could hear us.
That’s the first thing about private conversations: Whether they are happening face to face or online, they have to be confidential. No other person but you and your communication partner should be able to hear what you’re talking about.
The second thing is authenticity — you have to know that the person you are talking to is actually the person you intend to talk to. In real life, you recognize the person’s face, but with online messaging, that’s more complicated.
If the conversation is really important — and private conversations usually are — you want to be sure your conversation partner hears every word you say, and vice versa. More than that, you want to be sure that the person hears exactly what you say. In other words, for private online messaging, you need to know that some third party hasn’t corrupted your messages. And that’s the concept of integrity, which is also critical for private messaging.
Let’s now imagine that a third party entered the room and listened to a part of your conversation. In a real-life conversation, this third party would know only the part of the conversation they were actually listening to, not what you were talking about before they came or after they left. However, the Internet never forgets, and online communication is not as simple as offline. That brings us to two more important concepts behind private messaging: forward secrecy and future secrecy.
Forward secrecy doesn’t allow the third party to know anything you’ve discussed with your communication partner before they entered the room, and future secrecy doesn’t allow the third party to know what you talked about after they left the room.
Let’s say the subject you were discussing was really delicate. In this case, if someone accused you of saying something on the subject, you might want to deny it. If the conversation was private, the only people who can quote it are you and your communication partner, so it’s your word (“I didn’t say that!”) against theirs (“You said that!”). In such a case, no one can prove anything, and that brings us to the important concept of deniability.
Implementing privacy in messengers
So, those are the six features that have to be implemented in a messaging app before we can call it private. They are quite easy to achieve when we are talking about a real-life, face-to-face private conversation, but when it comes to messaging services there’s always a third party — the service itself. How are the six pillars implemented with this third party in mind?
Confidentiality is maintained through the use of encryption. There are different types of encryption, symmetric and asymmetric, namely public key cryptography. Private messengers (in this case, Schilling and Steinmetz reviewed Threema as an example) use both, creating a shared key from one person’s public key and the other person’s private key. Or the first person’s private key and the second person’s public key — the math behind the encryption works the same either way.
Therefore, the key is identical for both people and unique to the two of them (no other pair gets the same key). The app generates the key independently and maintains confidentiality by not transferring it — both people have it right after they decide to talk to each other.
This method is also used to ensure integrity — an outside party adding something to the already-encrypted text would render it unreadable. In that case, your conversation partner would either receive what you sent them or an error message (because the messenger couldn’t decrypt the ciphertext).
For even greater confidentiality, you might want to hide the fact that you and your conversation partner spoke to each other at all. Another layer of encryption takes care of that. The message you send gets encrypted using your and your conversation partner’s shared key — it’s like wrapping the message in an envelope, with an address on it. And then you encrypt it once again — stick it into another envelope and send it to the messenger’s server address. In this case, you use the key generated on the basis of your key and the server’s key.
So, this envelope-within-an-envelope is delivered to the messenger server. If a potential attacker tries to look at it, they’ll know that you sent it, but not its final destination. The messenger server unwraps the outer envelope, sees the destination address (not the message itself), wraps the package in yet another envelope, and sends it to the recipient. At this point, a potential attacker can see only an envelope from the messenger server to the recipient, but not where it originated.
With a whole lot of envelopes flying in all directions, it’s hard to track which person received your message. Hard, but not impossible: If someone were to weigh all of the envelopes, they could find two envelopes of the exact same weight and associate you with your conversation partner. To ensure that can’t happen, the system adds a random weight to every envelope, so the envelope you sent and the envelope your partner received never weigh the same.
It’s harder to maintain authenticity. Some messaging apps use e-mail addresses or phone numbers as user IDs — that’s the way the user proves he is who he claims he is. But phone numbers and e-mail addresses are confidential data that you might not want to share with the app. Some — like Threema — encourage users to use a different ID and exchange QR codes to prove their identity.
Deniability in this case is achieved by sending every message to both participants of the dialogue. The key is the same for both persons, so either could’ve sent the message. Therefore, even if somebody manages to intercept and decrypt the incoming message, they can’t be sure who sent it.
That takes care of confidentiality, authenticity, integrity, and deniability. What about forward and future secrecy? If a person’s private key and public key are always the same, then if the shared key is compromised, the attacker can decrypt both previous messages and future conversations.
To limit that, keys have to be periodically reissued by the server. If the key is reissued, say, once a month, an attacker would be able to read the conversation history for this month only and lose the ability to monitor the conversation once a new key is issued (in practice, reissuing happens much more frequently).
Thus ends our very brief introduction to the concept of private messaging. It’s actually a lot more complicated, because modern messaging apps have to handle media files, group chats, and sometimes even video calls.
If you are interested learning more, we suggest that you watch this video below from 33C3. In it, Schilling and Steinmetz explain not only the basic ideas, but also talk about how they’ve reverse-engineered Threema and found out how it implements key privacy principles. We enjoyed the video and hope you will too.