Given the recent debates about secure and encrypted communication, it might be interesting to understand why most mobile messenger apps do not exactly allow anonymous communication and what possibilities exist to enable it.

How digital communication works

So, for most of the existing messaging protocols, there is one important goal: get a message from A to B. This is true for all messaging apps you might know, but also for telephone services.
Furthermore, there are apps that encrypt the messages, like Signal, WhatsApp or Telegram. This is to ensure confidentiality, such that an attacker cannot read what you were sending.

Unfortunately, this is not enough for most cases. Imagine a really clever attacker named Mallory, who is not able to decrypt any messages, but he can record when you are sending messages and who you are communicating with. So, Mallory has a log of encrypted calls you made in a day, which looks like this:

07:33 am, A called C, encrypted call, number of C belongs to an oncologist, call length: 6 minutes
09:01 am, A called B, encrypted call, call length: 4.5 minutes
10:12 am, A called C, encrypted call, number of C belongs to a doctor (oncologist), call length: 12 minutes
10:25 am, A called B, encrypted call, call length: 24 minutes
06:11 pm, A called B, encrypted call, call length: 9.6 minutes

Mallory might not know what was said, but he might assume a lot of things. From the frequency of calls between A and B, he could assume that B must be a family member or close friend of A.
Also, calls to doctors might not be that frequent, which is why you can assume that A either has a medical condition or that A was doing an appointment for a checkup.
It is also very probable that A has to work between 11 am and 6 pm, since there is always a gap in the communications of A during the week.

So, even though the calls were confidential, you can get a lot of information, simply by looking at what is called metadata.
This data is usually not protected, since it is often necessary or helpful to know when two users are communicating.

But what if you want to hide this data, because you care about your privacy and you do not want others to assume things about you? Here is where anonymity comes into play.

Doing anonymous communication

I will be looking at a network concept by David Chaum, called DC-nets, which enable to send data to a group of people without exposing the sender. There is a cool example, the Dining cryptographers problem, which shows a practical problem which a DC-net tries to solve. You can read the Wikipedia article for a deeper insight into the problem.

First of all, we have 3 users, A, B and C, which want to talk together about politics. But, since they have very different views on the political situation, they want to avoid to be held responsible for any opinion they express. So, they decide to communicate anonymously.

Before they can communicate, every user has to agree on a shared encryption key with each of the other 2 users. So A shares a secret key with B, and another secret key with C, while B does the same with A and C and so on.

Let us assume that A wants to send a message. So A adds her message to B and C’s shared keys. After that, she sends the result to B and C.

A’s message: 00110101
Secret key with B: 00101011
Secret key with C: 00110110
Sum: 00101000

Now, B and C both receive the message and do the same as A, but use an empty message, which they add with their shared keys. Again, the results are sent to the other users.

B’s message: 00000000 and B’s Sum: 01000100
C’s message: 00000000 and C’s Sum: 01011001

Now, every user has sent a message and received 2 messages, so there are 3 messages AM, BM and CM, which were sent in the network. In order to recover the original message, you need to build the sum of these messages AM + BM + CM.

AM: 00101000
BM: 01000100
CM: 01011001
OM: 00110101

The result is the original message of Alice, but it is impossible to know who sent it.

This is a very cool way to send and receive anonymous messages, but it also has a few drawbacks:

– The users have to know each other and exchange secret keys prior to communicating.
– You need to have a new random key for every new message (in every round).
– In any moment, only one user can send a message at the time, or you get collisions. You can detect collisions and there are some ideas how to solve them.

DC-nets provide perfect anonymity for the sender, which means that an attacker can not learn anything about the sender by observing the communication. This also occurs if the attacker is part of the network (as long as there is at least two uncompromised participants.