23
$\begingroup$

Assume that there is a big and powerful country with an information-greedy secret service which has backdoors to all internet nodes throughout the world which permit him to observe all exchanged data and all computations done inside the nodes.

Is it still possible under these conditions to ensure by mathematical means that this secret service cannot find out who communicates with whom, if one designs internet protocols in a suitable way?

My feeling is that the answer is likely "yes", but I am not working in cryptography. -- Probably a cryptographer can tell more.

Clarification (added after the first two answers): A good answer to this question could either consist of a description of a method together with substantial heuristic arguments in support of its suitability for the given purpose, or it could give substantial heuristic arguments that there is no such method. Mere handwaving arguments in favor of a positive or a negative answer do not answer the question.

On the other hand, the question is only meant to ask whether there are mathematical methods which in practice serve the purpose, just like in practice RSA can be used as a public key cryptosystem. It is not asking for a proof or disproof (of what precisely??), since this would not make sense.

Added after the first 5 answers (excluding deleted one(s)): The answers given so far mostly take the question as a soft question, which it is not. So far, Goldstern's answer comes closest to answering the question in that it proposes a concrete method -- but as it stands, it is still quite a way to go to get to anything practical.

Let me also emphasize that any transmission of data is "communication", including transmissions of publicly available webpages, downloads etc.. So firstly everybody has a lot of communication partners, and secondly efficiency is a very important concern.

$\endgroup$
13
  • 9
    $\begingroup$ Who would think such a horrible prospect could happen? Oh my, fortunately the real world is a much better place… $\endgroup$ Oct 29, 2013 at 11:36
  • 6
    $\begingroup$ It doesn't happen very often that mathematics and the actual (political) reality are intertwined that much. $\endgroup$
    – Wolfgang
    Oct 29, 2013 at 11:43
  • 26
    $\begingroup$ Dear MO users: please let's try not to veer off-topic. While the question might be irresistibly inviting to making coded references to the NSA controversy, I enjoin everyone to try to address the question in strict mathematical terms -- else this might have to be deleted. $\endgroup$
    – Todd Trimble
    Oct 29, 2013 at 13:08
  • 2
    $\begingroup$ Use the Postal Service. Gerhard "Check On Locked Box Problems" Paseman, 2013.10.29 $\endgroup$ Oct 29, 2013 at 18:12
  • 2
    $\begingroup$ @GerhardPaseman: Sender's and recipient's addresses can (and are often in practice) be scanned, and the mailbox where the sender has put the letter is known as well. $\endgroup$
    – Stefan Kohl
    Oct 29, 2013 at 18:19

5 Answers 5

17
$\begingroup$

Let us assume that everybody uses the same asymmetric encryption system (such as PGP), with keys that are so large that Big Brother cannot crack them.

If Alice wants to send a message to Bob, she encrypts it with Bob's public key and broadcasts it to everybody. All of Alice's friends will use their own private keys to decrypt the message, but only Bob will succeed. Big brother has no way of knowing who was able to read the message. (Unless Big Brother can look over Bob's shoulder, in which case nothing will work.)

Of course this system is a bit expensive, but only by some more or less constant factor. If everybody has 1000 friends, and sends a message per day to each of them, then I have to decode 1 million messages per day, only 1000 of which are for me.

EDIT: Now that the questions explicitly asks for a "practical" solution, here is a (slight?) improvement(?). Alice's messages will be pairs (x,y), where x looks like a large random number and y is the actual encrypted message. Whenever Alice writes to Bob, she could add a P.S. "My next message to you will be labeled with $\langle$_large random number here_$\rangle$. But please continue downloading all my messages, lest Big Brother could gain information about my conversation partners."

$\endgroup$
9
  • 4
    $\begingroup$ This scheme could also provide some sender privacy by broadcasting messages encrypted for a (securely) randomly generated key at random intervals so that Big Brother doesn't know when you actually intend to send a message. $\endgroup$ Oct 29, 2013 at 23:53
  • 1
    $\begingroup$ Thank you! -- I think of the 5 answers given so far, this is the best. $\endgroup$
    – Stefan Kohl
    Oct 29, 2013 at 23:57
  • 2
    $\begingroup$ If the system is not applied widely but only by some people, the government can be interested in knowing the group of “common friends” listed as receivers by many senders in this broadcasting scheme. It’d give a clue that they form a group which is very much interested in protecting their privacy. This could signal that they are potentially bad guys. (see Henry Cohn's meta-questions) $\endgroup$
    – Waldemar
    Oct 30, 2013 at 0:28
  • 1
    $\begingroup$ I think that for a sender privacy broadcasting dummy messages is necessary. Without a sender privacy, it can be much easier to infer e.g. who is the boss in the group sending orders down through the hierarchy. It makes the system more expensive: if e.g. I want to send just one true message to someone I have to broadcast $n$ messages with $n-1$ being dummy ones. Moreover, if I don’t want to send any true message I should also broadcast $n$ messages in order to protect sender privacy of the others in the group. $\endgroup$
    – Waldemar
    Oct 30, 2013 at 0:28
  • 2
    $\begingroup$ If you have a small group of friends, you can certainly use this approach to maintain privacy within that group, but scaling is a problem if you want to keep the secret service from knowing who your friends are. (If you expand the group to the size of the internet, then you'll end up downloading encrypted versions of every e-mail in the world to find yours. You'd need an NSA-scale server to handle that.) $\endgroup$
    – Henry Cohn
    Oct 30, 2013 at 14:45
15
$\begingroup$

Let's assume that the secret service can view all transmitted messages and how they are routed, but has no access to anyone's private computer, since otherwise privacy clearly cannot be guaranteed.

There's still no way to mathematically guarantee privacy in any realistic way. One big problem is traffic analysis: the secret service can try to correlate when you send messages with when other people receive messages (this correlation needs to take place over time; an individual message is certainly not enough by itself, and this can only detect patterns of frequent communication, but that is already a problem). This doesn't even require extensive access to the internals of the network, but just the ability to monitor when users send or receive anything. Encryption will disguise the messages themselves, but not who is communicating.

Perhaps the most obvious way to try to foil traffic analysis is by introducing random delays into the system. If the delays are long enough, then it can make traffic analysis much harder, but delays cause severe problems of their own. (Real-time chat becomes impossible, and even e-mail becomes less useful as the delays grow.) And even with delays, making traffic analysis harder and less useful is not the same as making it impossible.

The only guaranteed way to defeat traffic analysis is to communicate all the time. If there's ever a period in which you do not send any messages, then the secret service will know that any messages received during that time either were sent before you stopped communicating or weren't from you. That's already a small information leak. Of course it might not matter in practice, but this is important if we want a mathematical guarantee. It is difficult to model what someone might guess in practice from small leaks, especially when combined with side information, so at a rigorous level all bets are off once information starts to leak.

So this means that if a group of people want to defeat traffic analysis rigorously, then they must all be communicating nonstop, using dummy messages if they don't have anything real to say. This is not generally considered realistic, and I don't know of any large-scale implementation.

Of course nonstop communication is not enough by itself: you also need a system for routing messages indirectly. If nonstop communication isn't an obstacle, then you can guarantee privacy using mix networks, in which a sequence of trusted servers anonymize and randomly permute messages. If all the servers are compromised, then the system becomes insecure, but otherwise it's OK.

In practice, people see constant communication as too costly for whatever benefit it offers. However, mix networks are a good idea nevertheless. The most widespread implementation is Tor. Tor does not provide mathematically guaranteed privacy, and it can be vulnerable to traffic analysis. However, it still provides far more anonymity than the internet does by default.

Of course then there are all sorts of meta-questions. For example, Tor is not very common among internet users. Does it actually attract attention and signal that Tor users are interesting targets for more careful investigation? I've got no idea.

Mathematics certainly plays an important role in addressing privacy concerns, and there's more it could contribute than it currently does. However, the practical constraints are significant, and privacy issues ultimately transcend any specific mathematical model. Sadly, there's no realistic scenario in which internet users could say "Do what you like, because mathematics guarantees our privacy."

$\endgroup$
17
  • 1
    $\begingroup$ I think at any given time there are so many internet users sending or receiving something that it seems hardly possible to tell much alone from who communicates when. Occasional dummy information which goes to nobody or comes from nobody may be used in addition. Maybe I'm mistaken, but so far what you say does not convince me. I'm sorry to say it in that way -- but what you write is not a mathematical analysis of the problem, but just an essay. $\endgroup$
    – Stefan Kohl
    Oct 29, 2013 at 14:29
  • 7
    $\begingroup$ @StefanKohl: You're certainly right that a single instance is almost useless, because the internet is large enough that it could fit any number of possibilities. However, patterns emerge over time: if someone observes that 10% of the time Alice sends a message, Bob quickly receives one, then they can be confident that Alice communicates frequently with Bob and they can make pretty accurate guesses about which messages were to him. Most people don't send so many messages, so this sort of timing-based traffic analysis is completely feasible if you have the timing data. I'll edit to clarify. $\endgroup$
    – Henry Cohn
    Oct 29, 2013 at 14:48
  • 2
    $\begingroup$ I'm not sure whether you're looking for an argument that timing-based traffic analysis is a genuine concern, or that it's difficult to defend against. If you want a system in which traffic analysis is provably impossible, then you must disguise when you are transmitting and receiving. If you assume this can be monitored, then the only way to fully disguise it is to communicate constantly. This doesn't rule out the possibility of making a system that defeats traffic analysis in practice, but it says you won't be able to eliminate all possible information leaks. $\endgroup$
    – Henry Cohn
    Oct 29, 2013 at 15:16
  • 2
    $\begingroup$ So I'd summarize it as follows. In the standard model, where you want to prove that no information can possibly leak, you can solve the problem but only unrealistically. You might be able to solve the problem in practice, but without proofs. You might be able to prove that there are no leaks of a particular sort you find worrisome, but then you give up the universal applicability of the standard model. $\endgroup$
    – Henry Cohn
    Oct 29, 2013 at 15:24
  • 3
    $\begingroup$ A more realistic model might have one "safe" central computer that is constantly sending out bits to all others, and in fact is the only source of outwards info. Then the other computers can send in bits into the safe computer whenever they want and it will redirect the information to the appropriate destination. Because computers only receive information (mostly useless) from the central computer, there is no way to track who is communicating to whom. $\endgroup$ Oct 29, 2013 at 16:57
4
$\begingroup$

Unconditional sender privacy is a well-known problem; D. Chaum - "The dining cryptographers problem" could be a reasonable starting point.

Having decided on existance, the question remains what price (in terms of communication complexity) could be considered acceptable to name it efficient enough (that is, practical).

"Dining" communication scheme had a impact and was extended in a number of ways, including an option for lost messages: M. Waidner, B. Pfitzmann - The dining cryptographers in the disco: Unconditional sender and recipient untraceability with computationally secure serviceability.

For a practical (depending on a computationally hard problem) solution, "remailer" was designed long ago for email. Papers of Lance Cotrell and Ulf Moeller there could be of interest. This was mentioned by Henry Cohn as "mix network" already.

$\endgroup$
3
$\begingroup$

Think of the handwritten letters for a moment. Suppose Alice wants to secretly communicate with Bob, so she writes the message in a secret language that only Alice and Bob know, puts it in an envelope, and ... writes Bob's address in plain letters on the top of the envelope before mailing it. Big Brother may not be able to read the message, but surely can read the address on the envelope: if Alice would try to encrypt Bob's address she would completely confuse the Post Office and the letter won't get delivered.

It's pretty much the same thing with Internet communications. Cryptography obscures the message, but not the destination: otherwise the routers won't be able to deliver the message. This leads to the negative answer under the assumption that Big Brother watches all the nodes.

However, Big Brother does not have access to all the nodes: quite a few of them are overseas. Therefore Alice can try to secretly communicate with Bob by bouncing her messages off offshore nodes.

Back to our handwritten letter analogy. Alice can put her letter addressed to Bob into another envelope addressed to her Russian friend Ivan and write Ivan's address on the exterior envelope. Ivan receives the letter, takes it out of the exterior envelope, and hands it letter to his friend Alexander. Alexander then forwards Bob the original letter. Assuming that Big Brother has no ears in Moscow and that Internet traffic is heavy enough between Moscow and whichever country Big Brother is watching over, it would be virtually impossible for Big Brother to detect Alice-Bob communications. There are too many letters coming back-and-forth between the countries to guess that the letter Bob receives from Alexander is the same one that Alice sent to Ivan.

This is pretty much how hackers try to conceal their identities, in my layman understanding. This is not always successful though: Big Brother may have ears in Moscow as well...

$\endgroup$
9
  • 3
    $\begingroup$ Shouldn't your Muscovites be called Cyril and Dimitry? $\endgroup$ Oct 29, 2013 at 20:04
  • $\begingroup$ Your model with addressed single data packages travelling through the network from a sender to a recipient is just the most obvious possibility, and what is actually used in the internet. -- Other protocols are conceivable -- though, if feasible, admittedly conceptually more difficult. $\endgroup$
    – Stefan Kohl
    Oct 29, 2013 at 21:29
  • $\begingroup$ Imagine e.g. a protocol where, when A sends a message to B, A encodes the message and merges (think of a mathematical process, not just kind of concatenation!) it with a big pool of other data with other sources and destinations, in such a way that some mathematical process ensures that the nodes transport it to B without knowing that they are doing so, and in such way that the way the message takes cannot be traced within all the lots of other data it is merged into. I don't know whether this is feasible or not -- but problems like this are what I think a good answer should address. $\endgroup$
    – Stefan Kohl
    Oct 29, 2013 at 21:53
  • $\begingroup$ @StefanKohl: the nodes need to know that they are transmitting something to B. They may not be aware of the primary origin of the message, only the immediate origin needs to be known. As described in my answer, the primary origin could be hidden by bouncing off offshore nodes; as you described in the comment the primary origin can be hidden in the pool of other messages. As long as there is an intermediate node - either overseas or in your big pool server - you can mask true origin A. Until, that is, Big Brother makes a deal with Moscow or issues a warrant for you big pool server. $\endgroup$
    – Michael
    Oct 29, 2013 at 22:06
  • $\begingroup$ Why do the nodes need to know that they are transmitting something to B? -- I think it is at least conceivable that this information is encoded by A into the data in some way such that, although the nodes cannot decipher the destination address or track the data within all the other data in the network, some mathematical process ensures that the data is shipped to B. I don't know whether this is feasible, but simply claiming that it is not is not a good answer. $\endgroup$
    – Stefan Kohl
    Oct 29, 2013 at 22:13
3
$\begingroup$

If Alice encrypts a a lot of messages with Bob's RSA public key, after a while they can be identified as being directed to Bob, since the encrypted value is a number from the multiplicative group $\mathbb Z/N\mathbb Z$ where $N$ is Bob's RSA modulus. By collecting enough of these ciphertexts, Big Brother can notice that they max out around $N$. That is enough to distinguish them from messages addressed to Charlie, who has a different modulus.

There is an old rectangularization trick to get around this (I'm not sure who invented it). Remember that Alice's message to Bob is $C=x^e\mod N$ where $e$ is a public encryption exponent. So Alice simply generates a large random number $R$ (say in the range $1\dots 2^{100}$) and sends $C+RN$ instead of just $C$. This is pretty close to uniformly random in the range of the maximum R. Bob simply mods out by $N$ to get rid of the random addition, before decrypting.

This scheme actually does leak a little bit of information, according to an old paper by Quisqater that I don't remember the title of. But IIRC it is pretty good for practical usage if the number of messages is reasonable.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.