[liberationtech] CJDNS hype

[Caleb James DeLisle]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hi Michael,

I'm trying to keep liberationtech in the loop here, if you
want to talk privately just let me know.

On 08/01/2013 09:34 AM, Michael Rogers wrote:
> Hi Caleb,
> 
> Thanks a lot for the answers! Responses are inline below...
> 
> On 25/07/13 21:58, Caleb James DeLisle wrote:
>>> Can a node on the switching path between the pinger and the pingee respond to a ping on the pingee's behalf?
> 
>> Never ever. That's critical to the model that when you are told about a node that you don't trust that it's real until you're sure that you've talked to it.
> 
> If nodes along the switching path can't respond on behalf of the pinged node, I guess there must be some kind of authentication between the pinger and the pingee, right?
> 
> So I'm imagining the following scenario:
> 
> * Alice has a direct connection to her friend Bob * Bob tells Alice he has a direct connection to his friend Carol * Bob gives Alice some information with which to authenticate a ping response from Carol (such as Carol's public key) * Alice sends a ping to Carol via Bob, and receives a valid response
> 
> 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.

> 
>> There are no specific defenses against sybil attacks but I don't think any are needed given the fact that it's inherently different from a traditional overlay network.
> 
> I'm sorry but I disagree. The specific attacks will certainly be different from those in, say, Gnutella or the BitTorrent DHT, but some form of the Sybil attack still applies.


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.


> 
> The reason I raised Sybil attacks and Byzantine faults in my first email is that they're problems that appear again and again in distributed systems, each time in a slightly different form.
> 
>>> Obviously this is just a toy example, but it shows that in the general case a Sybil attack doesn't necessarily produce long labels.
> 
> 
>> That's a valid point. We tried to avoid trapping bad behavior and dropping a node because in my opinion it is too brittle and is more likely to introduce a vulnerability.
> 
> 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.


> 
>> Rather than trust early and detect known bad behavior, cjdns is slow to trust. If you tell me about a new node I will generally not use it until the node I'm currently using fails. This hurts performance but helps stability once the network is functional.
> 
> I like that approach, but it has two limitations. First, it slows down attacks but doesn't prevent them - an attacker can behave well until she's integrated into the network, then start to misbehave, at which point we're back to detecting and dropping bad nodes. And remember that without a Sybil defense, the attacker can have an endless series of identities in the pipeline, so that at any given time some identities are 'paying their dues' while others have finished paying their dues and
> started to misbehave.
> 
> Second, it requires some way of measuring whether the node you're currently using has failed. Right now, as far as I can tell, a node isn't considered to have failed as long as it responds promptly to pings. It doesn't actually have to forward data. So the current definition of 'failed' isn't useful for detecting misbehaviour, only accidental faults.


Correct on both counts, I think if DoS attacks are expensive and
attract lots of attention, I've basically won. If the person is
drawing attention they risk being dropped by their peers and losing
their sybil edges.

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.

Of course a virus which attacks a large subset of the nodes and makes
them all misbehave is something I have no answer for.

> 
>> Since cjdns populates it's table by periodically querying randomly generated ip addresses, nodes share their best paths causing a sort of "wisdom of the crowd" effect and making it difficult for a sybil attack to gain traction.
> 
> Have you heard of the eclipse attack? It's similar to the Sybil attack, in that it tries to fill the victim's view of the network with identities that are controlled by the attacker. But unlike the Sybil attack, it doesn't necessarily require the attacker to control a lot of identities - the attacker only needs to bias the discovery process so that attacker-controlled identities are disproportionately likely to be discovered. Then, as nodes share information about their views of the
> network, the bias accumulates and the views gradually fill with attacker-controlled identities.
> 
> As with the Sybil attack, I'd urge you to think about how an attacker might customise the eclipse attack for use in cjdns.


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.

Thanks,
Caleb


> 
> Cheers, Michael
> 
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.12 (GNU/Linux)

iQIcBAEBAgAGBQJR+oq3AAoJECYAmptlsgnWR7IP/0yHyVrJbhDgj8aawYtON9H9
vaYNyXLfxs4wkysgWYI4+Wq7aHeHYzewYnjEc+TRAhwGXbMGB2VSsG3IObK6C+if
rV8oJXIkaicJmMxhFf+c/X5OIZ1ePYMay9MHL0mPhKccgLwbVRv4XhQtOe34cV3X
4PvHj9Lve+n3k/N9Mg74vYQURz7HBkjpyG1ed1wW4P+E2a/RkydTeKf4HAgvXS8q
WTLiCM/hVVS8H0rPtxuxUdyiC9QNpxAeoScMkltEj/UB2fLV7xa5QzfVKQ2OnAEE
cmKnGvO8U5upcWTIY+koblP4kAUerIOxMEj13+vZpAYjI7j+0/+0z7cydOiwhzR3
lMzlsu1g+PG6ptKOaXYEoWphb3F+PWLf0+1E6uyaL4M98rdSUYOn/eBGeSPCDpY4
7oZAwcBl55xrjTqIMlHuviktH3HT/xt69Y/uZja58Teh0EbS5Z8r0Z6rMj5gaCH0
auG6sQG/L7XIuI5GA1HtViR/5fX5OS9VEmPyJi7/X5HfRzDPMwCS6m2DkbWHftfC
FaO/9UlBjQHN9EG+8rN1bTzVrHXTwbCx5P+46YirPmI6ojngzcx5b4sOf+e27rqH
Miosd+pKVvEuZ+JFUPzCsBTMDpC/72B0scKS5WL9f6X8VXlVRTmZx7wpXmOkU5hu
JMFYvqFUi2SyG1yHxkkX
=QvzS
-----END PGP SIGNATURE-----