Here is the summary of the traffic analysis paper: @inproceedings{ raymond-traffic, author = "Jean-Fran\c{c}ois Raymond", title = "Traffic Analysis: Protocols, Attacks, Design Issues and Open Problems", booktitle = "Designing Privacy Enhancing Technologies: Proceedings of International Workshop on Design Issues in Anonymity and Unobservability", editor = "H. Federrath", year = 2001, volume = 2009, series = "LNCS", pages = "10--29", publisher = "Springer-Verlag", url = "citeseer.nj.nec.com/454354.html" } This paper looks at methods of defeating traffic analysis, in which an adversary is able to match a message's sender with the receiver. They do this by ensuring network unobservability, where communication patterns such as number of messages sent, when messages are sent, and who messages are sent from and to, cannot be observed, so that traffic analysis cannot work. The first solution described is Dining-cryptographer networks (dc-nets), in which a sender broadcasts an encrypted message that only the intended recipient can decrypt. The way that the encrypted message is transmitted is that the sender sends the message and all other nodes also broadcast some information. The (encrypted) message can be obtained by a node by adding all the broadcasted messages received. It seems that this method of transmitting messages is used to hide the fact that a certain node has sent a message, although this was not explicitly stated in the paper. They note that this scheme has significant drawbacks. The broadcast channel must be able to deal with adversaries which actively remove or add messages from communication channels. Channel jamming, in which "many participants" try to send messages at the same time, will result in a received message that is the sum of all the messages sent, which is meaningless. It seems that even if just two messages are sent at the same time, they cannot be received properly. This problem is even worse if an adversary controls one of the nodes and sends channel jamming messages while a legitimate message is being sent, such that they become the only ones who can receive the legitimate message. Broadcasting of messages by every node each time a message is sent by one nodes is inefficient, and not robust to packet loss. This is impractical for large networks. The number of shared secret keys between every pair of nodes could be too large to be practical. The second method is to use mix nodes, processors which take as input a certain number of messages, which it modifies and reorders such that it becomes nearly impossible to correlate a message that comes into the mix node with a message that comes out of the mix node. A message is encrypted as k1(k2(...kd(message))), where (k1,... kd) are the keys corresponding to mix nodes (i1,...id). Each mix node waits until it has received a certain number of messages and then decrypts one layer from the encrypted messages, randomly reorders the messages and sends them to the next mix node. The sequence of mix nodes that a message goes through is called a route. Route selection can be done through a cascade with a fixed sequence of mix nodes, random order (forming a mix-net), or other methods. Waiting for a certain number of messages to be received before sending them out is called "flushing", and there are different options in implementing this. The drawbacks to using mix nodes is that although there are methods to make them robust to a certain number of misbehaving mix nodes, they are not practical since they require a large number of mix nodes, a bulletin board, and a public key crypto-system. The authors mention a paper by Rackoff and Simon which provides a theoretic framework for proving that traffic analysis will be unsuccessful for a specific type of mix network, assuming constrained user behavior. However, the setting analyzed in that paper may not be practical for implementation in the real world. Next, the attacks against the mix node scheme, independent of specific implementation details, are examined. 1) Brute force attacks. Looking at this type of attack is useful in determining how to use dummy traffic to hide communication patterns. The number of dummy messages should be tuned such that there is a good security to cost ratio. This attack simply follows every possible path a message could have taken. It was not clear to me whether an attacker would be able to tell if a certain path they followed was the correct one. If the attacker is able to tell whether an incoming and an outgoing packet carry the same message, they can follow each possible path until they find the correct outgoing packet and stop. Thus the worst case that the authors describe in which the attacker only needs to follow 1 path to match a sender with a recipient is possible. However, from the description of mix nodes it seemed to me the mix node is supposed to modify the messages such that it is not possible to tell whether an incoming message matches an outgoing message. In this case even if the attacker follows the correct path on the first try, they would not know that it was the correct path. The solution given for minimizing the worst case situation is for each mix node to "spray" packets, containing either real messages or dummy messages, to t' nodes. The last nodes have to send messages to the outside after every t'' messages. This makes the worst case number of paths in the mix net t' instead of 1, and the number of possible recipients for a message becomes t'.t'' instead of 1. 2) Node flushing attacks, also known as Spam, Flooding, n-1 attack. If an attacker knows that nodes wait until they have t messages before sending them to the next node, the attacker can send t-1 messages such that they can identify their own messages going in and out, and hence correlate the one incoming message that didn't come from the attacker with the corresponding outgoing message. Dummy traffic can help, however, if dummy traffic is used only in specific instances such as in (1), an attacker can choose his messages so that dummy traffic is not used. 3) Timing attacks. If an attacker knows that different routes take different amounts of time, they can tell which route a message took. Even if one of the communicating parties uses "constant link padding" such that the flow of messages between the participant and the first node is constant, this attack still works. To prevent this type of attack, mix nodes could wait for random amounts of time before flushing messages. If the message's latency is smaller than the minimum latency for a certain route, we know that the message could not have taken that route. Hence the minimum time for each route needs to be the same, though this could make routing too slow to be practical. 4) Contextual attacks are the most dangerous attacks, and are difficult to model, since they depend on the behavior of users in the real world. Communication pattern attacks in which patterns such as only one person "talking" at a time over a long enough period of time, can indicate who is talking to whom. In packet counting attacks, the attacker makes use of how some types of communications are easy to distinguish from others. For instance, some users may tend to send out more messages than others. A partial solution is to only allow users to send standard numbers of messages, but this is impractical. Packet counting and communication pattern attacks can be combined to give a "message frequency" attack. These 3 attacks mentioned so far are referred to as traffic shaping attacks and are usually dealt with by imposing rigid structure on user communications, but this may not be practical on large networks. Protocols achieving "network unobservability" are immune to such attacks. Another contextual attack is the intersection attack, where an attacker who knows which users are active at any given time can infer who is communicating with whom. 5) Denial of service attacks. An adversary could make some mix nodes inoperational, such that messages will be forced to take different routes than they would normally. 6) Active attacks exploiting user reactions. An attacker could intercept a message M before it reaches the mix net, and send it to a set of possible recipients. The party expecting this message will be likely to behave differently than parties not expecting it. 7) "Sting" attack. One of the parties of the communication could betray the other party's privacy. The example given is that government agencies may set up fake "bomb making instruction web sites", in order to see who accesses it. 8) "Send n' seek" attack. The sender (party initiating the connection) attempts to uncover the recipient's identity, instead of the other way around in the "Sting" attack. 9) Attacks based on the message's distinguishing features. This attack makes use of differences in an unencrypted message that are unique to an individual to link a message with one or many individuals. 10) Message delaying. An attacker can withhold messages until he can obtain enough resources or until the network becomes easier to monitor. 11) Message tagging. An adversary who has control over the first and last node in a message route can tag messages at the first node such that they can be identified if they reach the last node. One solution is to make tagging difficult. A variant of this attack can be used by an external adversary if messages don't have a rigid structure, which has similarities with subliminal channels. This forms the basis for other variants: shadow messages, message delaying, broadcast. 12) Partial or probabilistic attacks. Most of the attacks discussed so far can be carried out partially, such that an attacker can get probabilistic information. If these attacks are carried out a large number of times, they could be very effective. These attacks have not been addressed so far. The authors note that when assuming static adversaries, it makes sense to calculate the probability that certain resources are controlled. However, this assumption is not helpful for making design decisions. The mix network design issues discussed are whether to use anonymity or pseudonymity, the impact of different packet sizes on performance, how to use dummy messages in such a way that they are most effective, how to choose routes, deciding how to implement node flushing, and implementing query servers such that privacy is maintained while still allowing users to retrieve information they may need. Future research directions include making protocols robust to the attacks described above and detecting when an attack can be used. A list of relevant problems is posed, including attacks in which the attacker only needs to find an arbitrary sender-recipient matching, determining how much information an attacker needs to get to be get a convincing sender-recipient matching, formalizing the capabilities and effectiveness of different types of adversaries, incorporating privacy protecting mechanisms within existing protocols, and being able to tell how much security mix-networks provide in different situations.