Matthew Toseland wrote: > Not sure I understand... You, the attacker, are an internal node. You > only know what is sent to you by your peers... so are you talking about > correlation attacks?
I had a couple of attacks in mind... or sketches of attacks, since I don't fully understand how greedy routing will be used in 0.7. Will it be possible to send packets to a node using its location as a routing address, or will it only be possible to insert and request data by keys, as in 0.5? First attack: recipient proximity Let's say you get a message from an anonymous source saying "I'm at location 180 degrees, here's my public key, can we talk?" You know someone who was recently at location 179 degrees and someone else who was recently at 181, so if the location swapping algorithm is working and the social network has been successfully embedded in one dimension, your anonymous source is probably (a) one of those people or (b) someone both those people know. Alternatively, the anonymous source's location might be close to your own location. Second attack: sender proximity Your location is 180 degrees. You receive a packet for location 1. Greedy forwarding means that the sender must be further away from the destination than you are, so the sender's location must be between 178 and 180. In general, the more distant the destination, the smaller the number of possible senders. The second attack gets easier if you control a small number of nodes scattered around the network (not easy in a friend-to-friend network, but not impossible either). Imagine a recipient who's only communicating with one sender. (How can you know this? Maybe you're the recipient.) If a node you control forwards a packet towards the recipient, you can rule out any senders who are nearer the recipient than your node is. On average, this rules out half the network. As long as the network remains perfectly stable, the sender's packets continue to follow the same path and you don't get any additional information. But whenever a link comes up or goes down there's the possibility of a packet passing through another one of your nodes and giving you another sample. I'd like to quantify this attack - what's the expected size (and entropy) of the sender's anonymity set for a given number of samples? How long does it take to gather samples? I don't have a hope of answering these questions analytically... I can do simulations, but the results will probably depend on the topology of the social network (pretty much a matter of conjecture at this point) and the details of the location swapping algorithm, plus some hand-waving assumptions about node lifetime, available bandwidth, congestion... Cheers, Michael
