-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Hi Caleb,
On 03/08/13 01:33, Caleb James DeLisle wrote: > 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. Excellent point! The adversary I have in mind looks something like this: * Can create adversarial nodes * Can persuade a limited proportion of users to make direct connections to adversarial nodes * Can co-ordinate the behaviour of all adversarial nodes * Can create low-latency, high-bandwidth connections between adversarial nodes * Can't monitor or tamper with direct connections between non-adversarial nodes * Can't break standard crypto primitives * Aims to degrade the performance of cjdns for some or all users >> 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. How would you find a set of known evil nodes? >> 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. Could you elaborate on the differences? The systems I mentioned are designed for use in P2P networks where the edges are based on real-world social relationships and there's no central authority. Isn't that similar to the cjdns setting? > 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. Let's consider what happens as the network grows. On average, each node is pointed to by t routing table entries, where t is the size of a node's routing table. As the network grows, the t entries pointing to a given node will be spread more thinly across the network, unless we increase t in direct proportion to the number of nodes. Increasing t like that won't scale indefinitely, but for the sake of argument let's assume it will scale well enough for whatever size cjdns grows to. So wherever we start from, there's some nearby node that knows a switching path to the destination. However, the length of that switching path will increase (on average) as the network grows. Even if we had a magic oracle that told us the shortest path to any destination, that path would still be longer on average in a large network than a small network. Therefore if some proportion of the nodes are adversarial, the probability of hitting an adversarial node on the way from a randomly chosen source to a randomly chosen destination will increase as the network grows. >> 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. Unfortunately it's not that simple. You're assuming that from the point of view of a given node, all the Sybils are behind a single edge (an attack edge, in SybilGuard terminology). But a given Sybil may be reachable via multiple attack edges. That's why SybilGuard and its descendents are so complex: before sampling the network to look for clusters, they have to ensure that there's only a single way for samples to reach each node. Cheers, Michael -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.10 (GNU/Linux) iQEcBAEBAgAGBQJR/+ApAAoJEBEET9GfxSfMa8kH/iK0/TIHXiHSAZoDReJJmljD kPVxkMTa/ejYdRWdDZ2VV6wiTGS7OuMJ4gYk6e8k6mqc3PmcdS8gDRC0ZQBOve44 Oy6b4XtozOJBWB+5K1M4DRMQefoAxttrQD6v6C8ov1eyPqIIPcnPAYRUYufDdphK VmGYFmbGNTvb2If7YfN1xVgbTX1Kyq+5oKAyFtJflMiBRZtFHgSRvVNoTIIfD2Sj K2h0LriJTSvd4SW0/gxtSs20+ZxkjsitgAlaWNWwyvyJDWygYeIzU0KSDFegwnNd 3UtCOF1/WF784RoXwiHwVxAPp4AZ+yfRQ5hwuTRhiUYxCjfEPYRV9E1ckFskyIE= =dVi8 -----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