<p>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: <a href="http://freehaven.net/doc/fc03/econymics.pdf" rel="nofollow">On the Economics of Anonymity</a>. It sort of addresses your second question.</p>

<p>While Tor is not exactly a mix network, I believe it carefully <a href="https://blog.torproject.org/blog/research-problem-better-guard-rotation-parameters" rel="nofollow">chooses entry nodes</a> 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. </p>

<p>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: <a href="http://freehaven.net/anonbib/" rel="nofollow">http://freehaven.net/anonbib/</a> and so you could thumb through the titles for something that might be related.</p>

<p>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).</p>

CC BY-SA 3.0
2012-06-28T10:36:11.323Z
Assume the adversary can observe large portions of the network, but assume a high-latency network as originally proposed by Chaum rather than the lower-latencies achieved by Tor.  Your link to "On the Economics of Anonymity" is useful (thank you) -- I am still reading through it -- but I fear it doesn't really answer the question around the extent to which one can be compromised by one's trust relationships, which is really what I was after.
eggyal
CC BY-SA 3.0
2012-06-28T14:07:39.860Z
In a proper mixnet, if you pass your messages through a node that turns out to be trustworthy, the message will always be anonymous within the set of messages mixed by that node (assuming the other senders don't voluntarily reveal which messages are their's -- or are from the adversary -- which is a different attack vector). So you can never fully link together messages (assuming the messages themselves are not linkable -- again a different attack vector). As the message propagates to mixes that mix in different messages, the adversary could stop the anonymity set from growing but that's it.
PulpSpy
CC BY-SA 3.0
2012-06-28T14:56:45.563Z
But if an adversary is able to witness that all of Alice's messages are relayed through Bob's mix (perhaps because the adversary colludes with every mix between Alice and Bob), then he will be able to determine that Alice trusts Bob even though he can't determine what happened to the message thereafter.  Surely that is a new attack vector which has not been discussed in any of the literature you've cited?
eggyal
CC BY-SA 3.0
2012-06-28T20:25:17.790Z
I see. Agreed it is not in the papers I've cited or ever seen.
PulpSpy
CC BY-SA 3.0
2012-06-25T17:14:04.190Z
2012-06-25T17:14:04.190Z
PulpSpy
<p>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?</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2012-06-25T16:59:40.563Z
2012-06-25T16:59:40.563Z
mikeazo
<p>As I understand it, a fundamental of <a href="http://freehaven.net/anonbib/cache/chaum-mix.pdf" rel="nofollow">Chaum's mix-net</a> 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.</p>

<p>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.</p>

<p>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 <em>appear</em> desirable to ensure that <em>at least one</em> 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".</p>

<p>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.</p>

<p>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)?</p>

<p>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?</p>

CC BY-SA 3.0
2012-06-25T21:29:28.357Z
Seems reasonable to me (I'm a TCS mod)
Suresh Venkat
<cr.crypto-security><privacy>
To what extent is anonymity through a Chaum mix compromised by using trusted mixes in the cascade?
eggyal
# To what extent is anonymity through a Chaum mix compromised by using trusted mixes in the cascade?

(Asked by: username_0 on 2012-06-22)

As I understand it, a fundamental of [Chaum's mix-net](http://freehaven.net/anonbib/cache/chaum-mix.pdf) 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?

**Tags:** cr.crypto-security, privacy

> **Comments:**
> **username_1**: Seems reasonable to me (I'm a TCS mod)  

---

## 2 answers

### Answer by username_2 on 2012-06-25. Score: 3

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](http://freehaven.net/doc/fc03/econymics.pdf). It sort of addresses your second question.

While Tor is not exactly a mix network, I believe it carefully [chooses entry nodes](https://blog.torproject.org/blog/research-problem-better-guard-rotation-parameters) 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).

> **Comments:**
> **username_0**: Assume the adversary can observe large portions of the network, but assume a high-latency network as originally proposed by Chaum rather than the lower-latencies achieved by Tor.  Your link to "On the Economics of Anonymity" is useful (thank you) -- I am still reading through it -- but I fear it doesn't really answer the question around the extent to which one can be compromised by one's trust relationships, which is really what I was after.  
> **username_2**: In a proper mixnet, if you pass your messages through a node that turns out to be trustworthy, the message will always be anonymous within the set of messages mixed by that node (assuming the other senders don't voluntarily reveal which messages are their's -- or are from the adversary -- which is a different attack vector). So you can never fully link together messages (assuming the messages themselves are not linkable -- again a different attack vector). As the message propagates to mixes that mix in different messages, the adversary could stop the anonymity set from growing but that's it.  
> **username_0**: But if an adversary is able to witness that all of Alice's messages are relayed through Bob's mix (perhaps because the adversary colludes with every mix between Alice and Bob), then he will be able to determine that Alice trusts Bob even though he can't determine what happened to the message thereafter.  Surely that is a new attack vector which has not been discussed in any of the literature you've cited?  
> **username_2**: I see. Agreed it is not in the papers I've cited or ever seen.  

---

### Answer by username_3 on 2012-06-25. Score: 0

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.


---

