Chapter 11. Secret Broadcasts

11.1. Table Talk

Chris:	I heard that Bobby got fired?
Leslie:	Fired?
Pat:	I heard he was let go because of a drop in sales.
Chris:	Yes, the sales he's supposed to be making.
Leslie:	But everyone's sales are down.
Pat:	He said he was having a good quarter.
Chris:	Good? His sales are down even more.
Leslie:	Down more than what?
Pat:	Maybe they're just down relative to last year, which was a good year for everyone.
Chris:	I think they're down relative to everyone else'.
Leslie:	Maybe it was something else. I heard he was drinking too much.
Pat:	I heard because he couldn't take his boss's stupidity.
Chris:	Actually, his boss is brilliant. Bobby's the problem.
Leslie:	This doesn't add up.
Pat:	Well, it does add up. Maybe the truth is somewhere in between everything we've said. You just need to add it together.

11.2. Secret Senders

How can you broadcast a message so everyone can read it but no one can know where it is coming from? Radio broadcasts can easily be located with simple directional antenna. Anonymous remailers (see Chapter 10) can cut off the path back to its source, but they can often be compromised or traced. Practically any message on the Net can be traced because packets always flow from one place to another. This is generally completely impractical, but it is still possible.

None of these methods offers unconditional security, but there is one class of algorithms created by David Chaum that will make it impossible for anyone to detect the source of a message. He titled the system the “dining cryptographers” which is a reference to a famous problem in computer system design known as the “dining philosophers.” In the Dining Philosophers problem, n philosophers sit around the table with n chopsticks set up so there is one chopstick between each pair. To eat, a philosopher must grab both chopsticks. If there is no agreement and no schedule, then no one will eat at all.

Chaum phrased the problem as a question of principle. Three cryptographers are eating dinner and is from the National Security Agency. The waiter arrives and tells them that one person at the table has already arranged for the check to be paid, but he wouldn't say who left the cash. The cryptographers struggle with the problem because neither of the two nongovernment employees want to accept even an anonymous gratuity from the NSA. But, because they respect the need for anonymity, they arrange to solve the problem with a coin-tossing algorithm. When it is done, no one will know who paid the check, but they'll know if the payer is from the NSA.

This framing story is a bit strained, but it serves the purpose. In the abstract, one member will send a 1-bit message to the rest of the table. Everyone will be able to get the same message, but no one will be able to identify which person at the table sent it. There are many other situations that seem to lend themselves to the same problem. For instance, a father might return home to find the rear window smashed. He suspects that it was one of the three kids, but it could have been a burglar. He realizes that none will admit to doing it. Before calling the police and reporting a robbery, he uses the same dining cryptographer protocol so one of the kids can admit to breaking the window without volunteering for punishment.^[1]

¹ This may be progressive parenting, but I do not recommend that you try this at home. Don't let your children learn to lie this well.

Random protocols for sharing a communication channel are used by the Ethernet developed at Xerox PARC.

If a 1-bit message can be sent this way, then there is no reason why long messages cannot come through the same channel. One problem is that no one knows when someone else is about to speak, since no one knows who is talking. The best solution is to never interrupt someone else. When a free slot of time appears, participants should wait a random amount of time before beginning. When they start broadcasting something, they should watch for corrupted messages caused by someone beginning at the same time. If that occurs, they should wait a random amount of time before beginning again.

The system can also be easily extended to create a way for two people to communicate without anyone being able to trace the message. If no one can pinpoint the originator of a message with the Dining Cryptographers protocol, then no one can know who is actually receiving the message. If the sender encrypts the communication with a key that is shared between two members at the table, then only the intended recipient will be able to decode it. The rest at the table will see noise. No one will be able to watch the routing of information to and fro.

The system for the dining cryptographers is easy to understand. In Chaum's initial example, there are three cryptographers. Each one flips a coin and lets the person on his right see the coin. Now, each cryptographer can see two coins, determine whether they're the same or different, and announce this to the rest of the table. If one of the three is trying to send a message—in this case that the NSA paid for dinner—then they swap their answer between same and different. A 1-bit message of “yes” or “on” or “the NSA paid” is being transmitted if the number of “different” responses is odd. If the count is even, then there is no message being sent.

There are only three coins, but they are all being matched with their neighbors so it sounds complex. It may be best to work through the problem with an example. Here's a table of several different outcomes of the coin flips. Each column shows the result of one diner's coin flip and how it matches that of the person on their right. An “H” stands for heads and a “T” stands for tails. Diner #1 is to the right of Diner #2, so Diner #1 compares the coins from columns #1 and #2 and reports whether they match or not in that subcolumn. Diner #2 is to the right of Diner #3 and Diner #3 is to the right of Diner #1.

Diner #1		Diner #2		Diner #3
Coin	Match	Coin	Match	Coin	Match	Message
H	Y	H	Y	H	Y	none
T	N	H	Y	H	N	none
T	Y	H	Y	H	N	yes
T	N	H	N	H	N	yes
T	N	H	N	T	Y	none
T	Y	H	N	T	Y	yes

In the first case, there are three matches and zero differences. Zero is even so no message is sent. But “no message” could be considered the equivalent of 0 or “off”. In the second case, there are two differences, which is even so no message is sent. In the third case, a message is sent. That is, a “1” or an “on” goes through. The same is true for the fourth and sixth cases.

The examples don't need to be limited to three people. Any number is possible and the system will still work out the same. Each coin flipped is added into the final count twice, once for the owner and once for the neighbor. So the total number of differences will only be odd if one person is changing the answer.

What happens if two people begin to send at once? The protocol fails because the two changes will cancel each other out. The total number of differences will end up even again. If three people try to send at once, then there will be success because there will be an odd number of changes. A user can easily detect if the protocol is failing. You try to broadcast a bit, but the final answer computed by everyone is the absence of a bit. If each person trying to broadcast stops and waits a random number of turns before beginning again, then the odds are that they won't collide again.

Is this system unconditionally secure? Imagine you're one of the people at the table. Everyone is flipping coins and it is clear that there is some message emerging. If you're not sending it, then can you determine who is? Let's say that your coin comes up heads. Here's a table with some possible outcomes:

You		Diner #2		Diner #3
Coin	Match	Coin	Match	Coin	Match
H	Y	H	N	?	Y
H	Y	H	N	H	Y
H	Y	H	N	T	Y
H	Y	H	Y	?	N
H	Y	H	Y	T	N
H	Y	H	Y	H	N
H	N	T	Y	?	Y
H	N	T	Y	H	Y
H	N	T	Y	T	Y
H	N	T	N	?	N
H	N	T	N	T	N
H	N	T	N	H	N

We were never that concerned about Slothrop qua Slothrop. —Thomas Pynchon in Gravity's Rainbow

There are four possible scenarios reported here. In each case, your coin shows heads. You get to look at the coin of Diner #2 to your right. There are an odd number of differences appearing in each case so someone is sending a message. Can you tell who it is?

The first entry for each scenario in the table has a question mark for the flip of the third diner's coin. You don't know what that coin is. In the first scenario, if that hidden coin is heads then Diner #2 is lying and sending a message. If that hidden coin is tails, then Diner #3 is lying and sending the message. The message sender for each line is shown in italics.

As long as you don't know the third coin, you can't determine which of the other two table members is sending the message. If this coin flip is perfectly fair, then you'll never know. The same holds true for anyone outside the system who is eavesdropping. If they don't see the coins themselves, then they can't determine who is sending the message.

There are ways for several members of a dining cryptographers network to destroy the communications. If several people conspire, they can compare notes about adjacent coins and identify senders. If the members of the table announce their information in turn, the members at the end of the list can easily change the message by changing their answer. The last guy to speak, for instance, can always determine what the answer will be. This is why it is a good idea to force people to reveal their answers at the same time.

The Dining Cryptographers system offers everyone the chance to broadcast messages to a group without revealing anyone's identity. It's like sophisticated anonymous remailers that can't be compromised by simply tracing the path of the messages. Unfortunately, there is no easy way to use system available on the Internet. Perhaps this will become more common if the need emerges.

11.3. Creating a DC Net

The Dining Cryptographers (DC) solution is easy to describe because many of the difficulties of implementing the solution on a computer network are left out of the picture. At a table, everyone can reveal their choices simultaneously. It is easy for participants to flip coins and reveal their choices to their neighbors using menus to shield the results. Both of these solutions are not trivial to resolve for a practical implementation.

The first problem is flipping a coin over a computer network. Obviously, one person can flip a coin and lie about it. The simplest solution is to use a one-way hash function like MD5 or Sneferu.

Manuel Blum described how to flip coins over a network in [Blu82]. This is a good way to build up a one-time pad or a key.

The phone book is a good, practical one-way function but it is not too secure. It is easy to convert a name into a telephone number, but it is hard to use the average phone book to convert that number back into a name. The function is not secure because there are other ways around the problem. You could, for instance, simply dial the number and ask the identity of the person who answers. Or you could gain access to a reverse phone directory or phone CD-ROM that offered the chance to look up a listing by the number, not the name.

The solution to using a one-way function to flip a coin over a distance is simple:

1. You choose x, a random number and send me h(x) where h is a one-way hash function that is easy to compute but practically impossible to invert.
2. I can't figure out x from the h(x) that you sent me. So I just guess whether x is odd or even. This guess is sent back to you.
3. If I guess correctly about whether x is odd or even, then the coin flip will be tails. If I'm wrong, then it is heads. You determine whether it is heads or tails and send x back to me.
4. I compute h(x) to check that you're not lying. You can only cheat if it is easy for you to find two numbers, x, which is odd, and y, which is even, so that h(x) = h(y). No one knows how to do this for good one-way hash functions.

The protocol can be made stronger if I provide the first n bits of x. A precomputed set of x and y can't be used.

This is the algorithm that the two neighbors can use to flip their coins without sitting next to each other at the dinner table. If you find yourself arguing with a friend over which movie to attend, you can use this algorithm with a phone book for the one-way function. Then the flip will be fair.

The second tool must allow for everyone to reveal at the same time whether their coin flips agree or disagree. Chaum's paper suggests allowing people to broadcast their answers simultaneously but on different frequencies. This requires more sophisticated electronics than computer networks currently have. A better solution is to require people to commit to their answers through a bit commitment protocol.

The solution is pretty simple. First, the entire group agrees on a stock phrase or a collection of bits. This should be determined as late as possible to prevent someone from trying to use computation in advance to game the system. Call this random set of bits B. To announce their answers, the n participants at the table:

1. Choose n random keys, {k¹, …, kⁿ}, in secret.
2. Individually take their answers, put B in front of the answer, and encrypt the string with their secret key. This is f^ki(Baⁱ), where f is the encryption function, kⁱ is the key, and aⁱ is the answer to be broadcast.
3. Broadcast their encrypted messages to everyone in the group. It doesn't matter what order this happens.
4. When everyone has received the messages of everyone else, everyone begins sending their keys, kⁱ, out to the group.
5. Everyone decrypts all of the packets, checks to make sure that B is at the beginning of each packet, and finally sums the answers to reveal the message.

These bit commitment protocols make it nearly impossible for someone to cheat. If there were no B stuck at the beginning of the answers that were encrypted, a sophisticated user might be able to find two different keys that reveal different answers. If he wanted to tell the group that he was reporting a match, then he might show one key. If he wanted to reveal the other, then he could send out another key. This might be possible if the encrypted packet was only one bit long. But it would be near impossible if each encrypted packet began with the same bitstring, B. Finding such a pair of keys would be highly unlikely, which is why the bitstring B should be chosen as late as practical.

The combination of these two functions makes it easy to implement a DC network using asynchronous communications. There is no need for people to announce their answers in synchrony. Nor is there any reason for people to be adjacent to each other when they flip the coin.

11.3.1. Cheating DC Nets

There are a wide variety of ways for people to subvert the DC networks, but there are adequate defenses to many of the approaches. If people conspire to work together and reveal their information about bits to others around the table, then there is nothing that can be done to stop tracing. In these situations, anonymous remailers can be more secure because they're as secure as their strongest link.

Another major problem might be jamming. Someone on the network could just broadcast extra messages from time to time and thus disrupt the message of someone who is legitimately broadcasting. If, for instance, a message is emerging from the network, a malicious member of the group could start broadcasting at the same time and destroy the rest of the transmission. Unfortunately, the nature of DC networks means that the identity of this person is hidden.

If social problems become important, then it is possible to reveal who is disrupting the network by getting everyone on the network to reveal their coin flips. When this is done, it is possible to determine who is broadcasting. Presumably, there would be rules against broadcasting when another person is using the DC network so it would be possible to unwind the chain far enough to reveal who that person might be.

This can be facilitated if everyone sends out a digital signature of the block of coin flips. Each person in the network has access to two keys— theirs and their neighbor's. The best solution is to have someone sign the coin flips of their neighbor. When the process is unwound, this prevents them from lying about their coin flips to protect themselves. Forcing everyone to sign their neighbor's coin flips prevents people from lying about their own coin flips and changing the signature.

This tracing can be useful if only one person uses the DC network for a purpose that offends a majority of the participants—perhaps to send an illegal threat. If one person is trying to jam the communications of another, however, then it reveals both senders. The only way to determine which one is legitimate is to produce some rules for when members can start broadcasting. The first one would be the legitimate sender. The one who began broadcasting afterward would be the jammer.

11.4. Summary

Dining Cryptographers networks offer a good opportunity to provide unconditional security against traffic analysis. No one can detect the broadcaster if the nodes of the network keep their coin flips private. Nor can anyone determine the recipient if the messages are encrypted.

The major limitation to DC nets is the high cost of information traffic. Every member of the network must flip coins with their neighbor and then broadcast this information to the group. This can be done in blocks, but it is still a significant cost. n people mean that network bandwidth increases by a factor of 2n.

• The Disguise DC nets offer an ideal way to obscure the source of a transmission. If this transmission is encrypted, then only the intended recipient should be able to read it.
• How Secure Is It? The system is secure if all of the information about the coin flips is kept secret. Otherwise, the group can track down the sender by revealing all of this information.

Further Reading

• Philippe Golle and Ari Juels updated the algorithm making it easier to identify the cheating players without requiring extra rounds. The data for checking the calculations is bundled with each broadcast making it noninteractive. [GJ04]