-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
On 08/02/2013 04:48 PM, Michael Rogers wrote: > Thanks yet again for the answers, Caleb! Responses inline. > > On 02/08/13 19:03, Caleb James DeLisle wrote: >>> That's a big if. Do you currently have a way to detect Sybil edges? > > >> Sure, I'd just run `cjdcmd traceroute` and look for the nodes whose names I >> don't recognize. Sure it doesn't scale but since attacks are localized, it >> doesn't have to. I waste 10 minutes and the attacker wastes their entry >> point into the network. Getting let in isn't automatic so getting thrown out >> doesn't need to be either. > > Are you saying that your defense against the Sybil attack is to manually > blacklist anyone you don't recognise? And every other user is supposed to do > the same? > > What happens if someone you recognise is automatically generating names you > don't recognise? Whack-a-mole... We could spend a long time discussing locally effective attacks on social networks and not be any closer to agreement. Instead I think it's worth asking who your attacker is... I find that when people don't stop to ask who the attacker is, what he wants and what resources he can apply on the attack, they end up with a default assumption that the attacker is everywhere and has infinite resources..... If you can give me a clear picture of the person who would use this attack, what they want from the attack and what resources they can bring to bear on the problem, I might be able to speak more to the issue. > >> If you really wanted to automate the process, you could use heuristics. > > What heuristics do you have in mind? Given a set of known evil nodes, find the longest common route prefix(es) which contain all of the evil nodes. The last node along each common prefix is probably an edge. > > People have put years of research effort into designing automatic Sybil > defenses. The solutions they've come up with (SybilGuard, SybilLimit, > Gatekeeper, SybilInfer) are complex and heavyweight, and they depend on > assumptions about the structure of the social network - in other words > they're not off-the-shelf solutions that you could just drop into cjdns later > if the need arises. They operate under different constraints. > >>> It seems like you're assuming that by minimising the physical distance >>> covered by each hop, you can reach the destination without ever travelling >>> physically far from the source. But in the general case that can't be true, >>> because the destination may not be physically close to the source. > > >> No, by minimizing the physical distance covered by each hop, you can reach >> *someone* who knows the full path to the destination without traveling >> physically far from the source. > > This assumption doesn't scale. As the network grows, the probability that any > given node has a full path to the destination falls. > > If you're already near the destination then sure, you can expect to find a > node with a full path to the destination. But in a large network, you don't > necessarily start near the destination, and you can't necessarily get near > the destination without passing near the attacker. Everybody knows paths to those who are the numerically closest to themselves no matter the physical distance. Since addresses are spread randomly throughout the network, it means that anyone given node is directly reachable from a few nodes in each physical locality of the network. > > On the other hand, in a small network, you're already near the destination, > but you're also already near the attacker. > > I understand your argument that routing table entries pointing to the > attacker will tend to be localised around the attacker. But the same applies > to routing table entries pointing to the destination. There's a subtle distinction, routes propagate throughout the network but unless they are physically close, they are not used unless they are an exact match. In other words: I route to the physically closest node who makes forward progress in address space *unless* I have a node whose address matches the target, in which case I route to him. > >> The table is populated with physically close and numerically close nodes, if >> the destination is physically close you'll probably know the full path >> already. If not then the physically closest node who is numerically closer >> to the target than you has a better chance because they're still physically >> close to you (and thus the target) and they're numerically closer to the >> target. > > Sorry, I don't understand what you mean by "physically close to you (and thus > the target)". One doesn't imply the other. I was responding to this: "even if the source and destination are physically close together, there's no guarantee that there's a path between them..." Where the premise is that there's a node which is physically close to you but you're unaware of them. > >>> The difference is significant: if I walk without ever stepping far from my >>> previous step, I can still end up far from where I started. > > >> I think you're confusing "reaching the destination" with "reaching someone >> who knows the way". There's only one destination but a significant portion >> of nodes know how to get there. > > As the network grows, the proportion of nodes who know how to get to the > destination falls. That's correct, to scale the routing tables have to grow or the packet has to take more hops before finding someone who knows the whole route. > >>> Could you explain how favouring physical diversity of nodes would mitigate >>> eclipse attacks and Sybil attacks? > > >> Since sybil nodes are clustered in physical space, this would limit the >> physical scope of the tablespace exhaustion attack detailed above. > > Bear in mind that the attacker can create arbitrarily large Sybil regions of > "physical" space. (We should probably avoid calling it physical space - maybe > social space would be a better name, because it's defined by social > relationships, not by geographical location.) > > If the attacker creates a Sybil region of social space that's larger than the > non-Sybil region, and you try to ensure that your routing table contains a > diverse sampling of the whole social space, then your routing table will tend > to contain more Sybils than non-Sybils. The number of nodes and the way they're organized doesn't help. They're all behind a common label prefix (the path to the sybil edge) and that label prefix would cause them to be seen as a cluster. > > So it seems to me that favouring physical (social) diversity might be a worse > strategy than favouring physical (social) locality, in terms of Sybil > resistance. You need physical diversity for numerical locality so you know the full routes to nodes whose addresses are close to your own. This rule would not change the behavior of the node when not under pressure. > >> Also multiple simultaneous sybil attacks could be carried out using >> compromised but otherwise valid cjdns nodes. > >> I'd like to implement a payment system to limit the first attack, the second >> is an open question... How do you approach an attack where a large number of >> honest people suddenly become colluding adversaries? > > I wouldn't worry about it - right now the network is vulnerable to Sybil and > black hole attacks that don't require compromising innocent nodes. The difference is that if you compromise innocent nodes then the attack actually works. If you want to help with simulating your attack I'd love the help. Thanks, Caleb > > Cheers, Michael > -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.12 (GNU/Linux) iQIcBAEBAgAGBQJR/E/CAAoJECYAmptlsgnWqpMP/A0dGea1osrnSz9B8zjnHXY2 g1204iZOeai49E6gFdunX2ZSKz0GUFkmYtgmVUMyAPudrP+mfUlkvXdaSsmfu3lw RGKiQbMxBCf0dCYTOyw7RGJY8gNG42UYKCpgNMdjs8sau+jG4b3TrPbGdjNRNb0J JHgWOzNeLhHcmA1B+i8bfdL1icq2bVjLw+FR6osAUWxF9AB1us8iHMSrihHOlzkL M27TQgY/o+gJlBJJEVUlgL+n6Wtm06V7q9s75Y1ek46Uc+lIkGsVrDTc+TDczmnQ ybZ4aVPr/3AB8IN4erujrDPctbbYX/4HfNeXTPpn9CtN6Fs1SfbCXHBDdQKlgoAq r4kX91KjPTLw6tx67mUCayQ5tA7roucmb77rFu6XEy93rE9fZKoagY3BknqJlJNI AE6Uo/dP7ClX9vzpcA0rK/M2/ubLHDZOz/pDN+QS0lleN2LnH0Bn/0OpYu4EuIQj eyo78ZXpc+iSDPFK8ncP/T774SuLD6hgYc2AQREdhlEZlMh82vxfri2HBfaaCK7y VjONIRagNsny/wVVhxwMXJzp/bD1vApR+ZhdR2ePbCFvxDNQ+Iq9l9RymewqdZYb nKqxUoCalcwNVzZcPqgQYnsFTbqSuNZ19vz/Fmtv0oUaX5d2+jlAe3bZYh/U+MRJ bamUstdd09e/K3yJs3aE =aN5L -----END PGP SIGNATURE----- -- Liberationtech list is public and archives are searchable on Google. Too many emails? Unsubscribe, change to digest, or change password by emailing moderator at compa...@stanford.edu or changing your settings at https://mailman.stanford.edu/mailman/listinfo/liberationtech