Horrible, Semi-Anonymous, Secure Communication

Posted 2015-09-03 | Billy Overton

Recently I’ve been thinking about how to make a secure chat program that also hides who is talking to who. I really don’t have a need for it, but it has been a fun thought exercise. The main problem I’ve been having is figuring out how to make an efficient scheme that accomplishes it.

To handle the secure side of things, using a public key system seemed to make sense. It allows confirmation of who you’re talking to by comparing the public key fingerprint they provide to one you confirm in person, while also making it easy to transmit block level encryption keys securely for messaging. However it does have the drawback that now it’s obvious who is talking to who. If Alice uses Bob’s public key to send him a message… it’s obvious that Alice is talking to Bob. At the very least it reveals that Bob is receiving messages.

To get around this, I came up with a horribly inefficient “public wall” system that hides most of the knowledge about who is talking to who, while still allowing confirmation of who you’re talking to. It’s horribly inefficient however because of the number of messages that end up on a system with too many users.

Here is an example of a conversation with four online users $U:\{A,B,C,D\}$ and a shared wall $W$ . In this case user $A$ wants to talk with user $C$ without letting the other users know.

$\begin{eqnarray} A &\rightarrow& W:\{\mbox{I want to talk}\} \\ B &\rightarrow& A:\{\{R_1\}_{K_B}\}_{K_A} \\ C &\rightarrow& A:\{\{R_2\}_{K_C}\}_{K_A}\\ D &\rightarrow& A:\{\{R_3\}_{K_D}\}_{K_A} \\ A &\rightarrow& W:R_2,\{\{R_4,\mbox{Hello}\}_{K_A}\}_{K_C} \\ C &\rightarrow& W:R_4,\{\{R_5,\mbox{Greetings}\}_{K_C}\}_{K_A} \end{eqnarray}$

User $A$ starts by stating publicly it wants to talk to somebody. All other users respond to this request by sending an encrypted and signed randomly chosen identifier $R_x$ . The suffix in this case doesn’t show a sequence, just that the identifier is unique from the others. Once the identifier from the intended recipient is received $A$ sends their message publicly. The message is comprised of the unencrypted random identifier, and then a signed and encrypted message containing a new identifier and the actual message. The recipient knows the message is for them because of the identifier, and can decrypt and respond using the identifier it received.

Problems

There are quite a few attacks against the system. It’s vulnerable to collusion. If enough of the users talk to each, it’s possible to discover who is sending messages to who. In the example above, if $B$ and $D$ both talk and agree they are not speaking with A, then any messages seen becomes known to be between $A$ and $C$ . Ideally this should require collusion by $|U|-2$ users in order to become absolutely certain.

There are probably other issues related to replay attacks. Using multiple keys to send the same message, etc. I haven’t quite thought through all the of issues yet. It’s more of a general idea than something concrete at this point.