-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
On 08/01/2013 08:04 PM, Michael Rogers wrote: > Hi Caleb, > > On 01/08/13 17:20, Caleb James DeLisle wrote: >>> At this point, Alice knows that Carol is "real" in the sense that someone >>> owns Carol's private key and uses it to respond to pings. But Alice has no >>> way to determine whether Bob and Carol are actually the same person. In >>> other words, Alice can't tell whether Carol is a Sybil. > >> Correct. > > So if Alice can't tell whether Carol's a Sybil, presumably Alice can't avoid > sharing information about Sybils when sharing routing table entries. > > So people who trust Alice to be honest and diligent can't trust her to give > them non-Sybil routing table entries. Indeed, if sybil nodes are physically close to Alice then they will get favorable locations in her table and thus be shared and forwarded to. As Alice shares with Bob and Bob shares with Charlie, the path becomes longer and less favorable and the chance of that sybil node being shared again decreases thus localizing the attack in physical space. I had said that the majority of the nodes being honest keeps the table clean, I misspoke. Most nodes being non-attackers improves the table but this is obvious. If Alice hands me a far off sybil node with a long route, I will rarely (if ever) route to it anyway so assuming Alice is any less than an attacker, her conformance is not important. > >> To rephrase, given the architecture, I don't know of any attack which would >> be effective enough to warrant specific defenses. Of course changing IP >> addresses to send SMTP spam or evade IRC bans could be considered a sybil >> attack. > > I was thinking of more subtle attacks, such as dropping (some or all) data > packets while responding correctly to pings. Sybil identities would serve two > purposes in such an attack: filling as many routing table slots as possible > with attacker-controlled identities, and evading fault detection by replacing > any identities detected as faulty. > >>> Yes, I agree that detecting and dropping faulty nodes is pointless as long >>> as there's no limit on the creation of identities. > > >> This is not true. If I want to ban you, I won't express the ban as your key >> where you can just make another, I'll express it as your peer's key and the >> interface index which is used to get from him to you. > >> This way you can ban sybil edges if you can identify them. > > 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. > > Returning to the example above: Alice's friend Bob tells her about his friend > Carol. Alice can't tell whether Carol's a Sybil. So if Alice detects > (somehow) that Carol is misbehaving, should she (a) ban Carol, (b) ban the > edge from Bob to Carol, (c) ban Bob, or (d) ban the edge from Alice to Bob? > > If it turns out that Carol is a Sybil created by Bob then (a) and (b) are a > waste of time - Bob can just create a new Sybil. If it turns out that Carol > wasn't created by Bob then (c) and (d) are collateral damage: the attacker > has caused a genuine node or edge to be banned. > > Alice doesn't know whether Carol was created by Bob, so whatever action she > takes is useless at best and harmful at worst. If you really wanted to automate the process, you could use heuristics. > >> The non-forwarding node attack does concern me since it's hard to identify >> but again it is a physically local attack. The cjdns implementation >> conservatively forwards to the physically nearest node which makes any >> forward progress in address space and since the routing table is heavily >> duplicated, I'm likely to get to the destination long before I reach a >> non-forwarding node. > > Sorry, I don't understand how forwarding to the physically nearest node at > each hop will help to avoid faulty nodes. > > 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. > > Furthermore, the source and destination are at random points in the address > space, and every hop must make progress in the address space. So even if the > source and destination are physically close together, there's no guarantee > that there's a path between them where every hop makes progress in the > address space while remaining physically close to the source. 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. > > What's more, the routing algorithm doesn't even try to find such a path - it > tries to find a path where every hop makes progress in the address space > while remaining physically close to the *previous hop*. > > 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. > > So I'm not convinced that the routing algorithm avoids passing through nodes > that are physically distant from the source. > >> After looking over the first couple pages of Eclipse Attacks on Overlay >> Networks: Threats and Defenses I can see a tablespace exhaustion attack >> based on answering every DHT query with a fake node which is numerically >> very close to the target. Unless they're physically close to the victim they >> won't normally be routed to but they will take up space in a size limited >> table which would reduce the duplication of the routing table causing >> packets to be routed further and making localized sybil >> attacks have a wider reach. > >> This attack, as with many others, depends on the implementation of cjdns. >> Because there are hard rules preventing loops, we could adopt a new table >> population algorithm which favors physical diversity of nodes, mitigating >> this and other sybil type attacks without breaking the cjdns protocol. > > 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. A more realistic attack is to send a flood of packets to non-existent destination addresses in order to consume CPU resources from each node who forwards them. 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? Thanks, Caleb > > Cheers, Michael > -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.12 (GNU/Linux) iQIcBAEBAgAGBQJR+/SDAAoJECYAmptlsgnWY8wQALB8BPsIh/EdIG95O21I/9EZ Px66cZOj2C9m6pVugHLH+rljzq63EV58xiwboiecOvdnLmFeU8eHJyEtej9pxZia XImxvGK5RY112Z7hZLlfQQdE6UWxPrlKSI7iT9Ido0L2+QNftjTxs6UgYelXL8jr ExP/ze20Ftf6OHrf15s7+0qdoboA/+q9g3VBzXVLKmJyV228YA9i8Z9ExFoMTPTh kfndzj5lMdh3K+oYpqIIJOTEBW3v2G44kdjPsDkvfU0BbOtwrb3R7j5jUltr7vgA Pki02RjGBZTDaz/HZ2MiIgKfvXEWmRCJzaKtEMXWHNYeugRLyYcTxAUU2gNqHKkL zfE5n57jF4z85Dgpp0XgqgNjQ7OGlKLZVgRrKSvQonkduDTBUjItUm6lY0Wi7XXV 93tYCtG8JstRKYvcCh76z8rxbEal9XDk/O0byUGOymHBI2x4po9FkEm3GAvTHDw2 S/xTfUmNjeqhHdAgrl0Wr3zmQGBati1LZwcko69hXIEiRLqqOjyICYQbcn9CznjU JLr5fhupNqS2HnSowtAvPD0XpOlpYCLlOK8NMKY+nsUu2op2YRbLB5qaVcIPrqh6 F0n8Xd1LlHUDmJA1KvC51I+iwbQ8I2Bf90MdsOK8+cfmIrsj5D+7a3GtT6w1mopz P1XedfLxRO+fimCjdt3U =bYS5 -----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
