To what extent is anonymity through a Chaum mix compromised by using trusted mixes in the cascade?

Question

As I understand it, a fundamental of Chaum's mix-net is that, absent an external adversary who can analyse traffic on links within the network, no mix can link the source and destination of any message unless it collaborates with every other mix participating in the cascade through which that message passes.

Most of the mix-net projects about which I have read (both those that have been implemented and those that remain theoretical) mitigate such a "collaboration attack" by introducing randomness into path selection: thus an adversary must collaborate with a significant proportion of all mixes throughout the network in order to achieve a high probability that those in any given cascade will all be collaborators. Various techniques have been suggested to further frustrate an adversary who attempts to so bias the network, such as viewing all mixes on a single subnet as potential collaborators.

If one is certain (at least, as much as one can ever be) that some particular mixes are honest (i.e. not collaborating with an adversary), it would at first glance appear desirable to ensure that at least one such honest mix is included in every cascade used for one's messages so as to significantly reduce (if not completely eliminate) the threat of such "collaboration attacks".

However, forcing all one's messages to pass through a subset of the network that is defined by one's trust relationships leaks information about those relationships. Over time, an adversary might be able to use such information to link together all one's messages or even identify oneself.

My question is: how can one measure this trade-off? Is there existing research that already has considered it (I have not been able to find any yet)?

Where senders are themselves also acting as mixes in the presence of sufficient inbound cover traffic, does the inclusion of known honest mixes in downstream cascades for their own messages actually provide any additional anonymity given that those messages could arguably have been forwarded for another party?

Answer 1

I haven't seen a paper that addresses your (first) question specifically. One extreme example of a mix node that you trust is yourself, if you are participating in the network as well as using it. One paper that talks about the trade-offs of using yourself as a node in a mix network is: On the Economics of Anonymity. It sort of addresses your second question.

While Tor is not exactly a mix network, I believe it carefully chooses entry nodes based on individuals the network maintainers trust. In this case, all users have the same "trust network" and so it avoids the problem you are proposing to study. The drawback is you personally must trust the same nodes.

As to your specific question, I haven't seen a paper that specifically addresses what you want but I also do not follow the area closely. Most papers on Mix Networks are catalogued here: http://freehaven.net/anonbib/ and so you could thumb through the titles for something that might be related.

Finally, I'm not sure you'll find the adversary has much power unless if they can observe large portions of the network, in which case there are more effective attacks (especially in Tor-like anonymity networks which don't actually mix or obfuscate packet timing).

Answer 2

It is hard to answer without knowing your exact adversary model. For example, does the adversary know all of the mixes you trust? What is the adversary able to see (only what is coming into your trusted mixes and what goes out)? How much of the network besides the trusted mixes does the adversary control?

Looking at the worst case (you have only one trusted mix, and you are the only person in the entire network who uses that mix, and the adversary controls all other nodes in the cascade), it would seem that anonymity would be completely broken.

In a slightly better case, say the trusted mix is highly used by others. It now seems that the system remains secure. The attacker could follow your packets up until the trusted mix is used, but after that, the attacker should have no idea which packets are yours.