+ - 0:00:00
Notes for current slide
Notes for next slide

Distributed secure routing in permissionless flat networks

Distributed secure routing in permissionless flat networks

Benedict Lau // Radical Networks 2018

1 / 22

Distributed secure routing in permissionless flat networks

2 / 22

Distributed secure routing in permissionless flat networks

IP address packet

2 / 22

Distributed secure routing in permissionless flat networks

IP address packet

2 / 22

Distributed secure routing in permissionless flat networks

Internet BGP inter-domain routing

https://csperkins.org/research/thesis-phd-strowes.pdf

3 / 22

Distributed secure routing in permissionless flat networks

For a large network to scale, it must be subnetted into smaller, more easily manageable networks, which then must in turn be networked together (to form a network of networks from inter-network connections, i.e. the internet). This requires some level of expertise and planning to do, and tends to favor hierarchies wherein small networks are largely at the mercy of a larger network (e.g. the only connection your LAN has to another network is your connection to an ISP, and “peering” or directly connecting to your neighbor’s LAN is virtually unheard of).

Arceliar, Yggdrasil: The World Tree, https://yggdrasil-network.github.io/2018/07/17/world-tree.html

4 / 22

Distributed secure routing in permissionless flat networks

Distributed secure routing in permissionless flat networks

5 / 22

Distributed secure routing in permissionless flat networks

Distributed every node is capable of compact routing

6 / 22

Distributed secure routing in permissionless flat networks

Distributed every node is capable of compact routing

Secure end-to-end encryption • route around malicious nodes

6 / 22

Distributed secure routing in permissionless flat networks

Distributed every node is capable of compact routing

Secure end-to-end encryption • route around malicious nodes

Permissionless IP address self-assignment • autonomous network

6 / 22

Distributed secure routing in permissionless flat networks

Distributed every node is capable of compact routing

Secure end-to-end encryption • route around malicious nodes

Permissionless IP address self-assignment • autonomous network

Flat random IP addresses • no subnet hierarchy

6 / 22

Distributed secure routing in permissionless flat networks

Compact routing

in comparison to BGP inter-domain routing

7 / 22

Distributed secure routing in permissionless flat networks

Compact routing

in comparison to BGP inter-domain routing

  • Keep small amounts of routing state at each router, rather than piling all that work onto the core network infrastructure
7 / 22

Distributed secure routing in permissionless flat networks

Compact routing

in comparison to BGP inter-domain routing

  • Keep small amounts of routing state at each router, rather than piling all that work onto the core network infrastructure

  • Without the full network view, a node cannot always determine shortest path
    e.g. Dijkstra's algorithm as in OSPF

7 / 22

Distributed secure routing in permissionless flat networks

Compact routing

in comparison to BGP inter-domain routing

  • Keep small amounts of routing state at each router, rather than piling all that work onto the core network infrastructure

  • Without the full network view, a node cannot always determine shortest path
    e.g. Dijkstra's algorithm as in OSPF

  • Have routing table grow sublinearly with number of nodes, while getting close to shortest path routing with upper bound

7 / 22

Distributed secure routing in permissionless flat networks

Compact routing

in comparison to BGP inter-domain routing

  • Keep small amounts of routing state at each router, rather than piling all that work onto the core network infrastructure

  • Without the full network view, a node cannot always determine shortest path
    e.g. Dijkstra's algorithm as in OSPF

  • Have routing table grow sublinearly with number of nodes, while getting close to shortest path routing with upper bound

  • Name-independent schemes that require no pre-processing are suitable for an unmanaged permissionless network

7 / 22

Distributed secure routing in permissionless flat networks

Hyperboria

https://www.fc00.org

cjdns

  • Auto-configure overlay network

  • Secure all network traffic with end-to-end encryption:

    • Curve25519 encryption keys
    • Ed25519 signatures
    • XSalsa20 stream cipher
    • Poly1305 MAC

  • Self-assign IPv6 in fc00::/8 from cryptographic keys

  • Source route with Kademlia-like distributed hash table

8 / 22

Distributed secure routing in permissionless flat networks

Self-assignment of IP addresses

for permissionless network participation

9 / 22

Distributed secure routing in permissionless flat networks

Self-assignment of IP addresses

for permissionless network participation

  • Perform two rounds of SHA-512 on Curve25519 public key then truncate to derive IPv6 address

  • fc00::/8 address space has 2120 addresses

9 / 22

Distributed secure routing in permissionless flat networks

Self-assignment of IP addresses

for permissionless network participation

  • Perform two rounds of SHA-512 on Curve25519 public key then truncate to derive IPv6 address

  • fc00::/8 address space has 2120 addresses


Birthday problem

1 in 1,329,227,995,784,915,872,903,807,060,280,344,576 chance of generating the same IPv6. Feeling Lucky?

https://github.com/cjdelisle/cjdns/blob/master/doc/notes/arc-workings.md

9 / 22

Distributed secure routing in permissionless flat networks

Distributed every node is capable of compact routing

Secure end-to-end encryption • route around malicious nodes

Permissionless IP address self-assignment • autonomous network

Flat random IP addresses • no subnet hierarchy

10 / 22

Distributed secure routing in permissionless flat networks

The Kademlia DHT

Laying out IP addresses

  • Node 0011 has physical peers to some neighbourhoods

  • Node 0011 learns paths to every neighbourhood

  • Each node keeps a routing table at each XOR distance

  • Each node knows its neighbourhood well relative to distant ones

https://pdos.csail.mit.edu/~petar/papers/maymounkov-kademlia-lncs.pdf

11 / 22

Distributed secure routing in permissionless flat networks

Searching the DHT


https://pdos.csail.mit.edu/~petar/papers/maymounkov-kademlia-lncs.pdf

Node 0011 searches 1110:

  • 0011 knows path to 101 and makes first query to learn 1101

  • 0011 makes successive queries 1 to 4 to reach 1110

  • 0011 calculates XOR distance:

    0011
    1110
    ----
    1101 XOR distance

  • 0011 adds newly learnt path to its routing table at 1--- bucket

12 / 22

Distributed secure routing in permissionless flat networks

Distributed every node is capable of compact routing

Secure end-to-end encryption • route around malicious nodes

Permissionless IP address self-assignment • autonomous network

Flat random IP addresses • no subnet hierarchy

13 / 22

Distributed secure routing in permissionless flat networks

Rick 1101 wants to send a packet to 1110

14 / 22

Distributed secure routing in permissionless flat networks

Source routing

Rick assembles the set of directors and sends to his peer Morty
0000000000000000000000000 0001 101011 011010 100101101 10111 0100011
unused space
15 / 22

Distributed secure routing in permissionless flat networks

Source routing

Rick assembles the set of directors and sends to his peer Morty
0000000000000000000000000 0001 101011 011010 100101101 10111 0100011
unused space

Morty pops the director and sends it down the network interface
1000000 0000000000000000000000000 0001 101011 011010 100101101 10111
unused space
15 / 22

Distributed secure routing in permissionless flat networks

Source routing

Rick assembles the set of directors and sends to his peer Morty
0000000000000000000000000 0001 101011 011010 100101101 10111 0100011
unused space

Morty pops the director and sends it down the network interface
1000000 0000000000000000000000000 0001 101011 011010 100101101 10111
unused space

The reaches Morty's peer, Summer, and she sees the director

15 / 22

Distributed secure routing in permissionless flat networks

Distributed every node is capable of compact routing

Secure end-to-end encryption • route around malicious nodes

Permissionless IP address self-assignment • autonomous network

Flat random IP addresses • no subnet hierarchy

16 / 22

Distributed secure routing in permissionless flat networks

Hyperboria

with more than 1000 nodes mostly tunneled over Internet links

17 / 22

Distributed secure routing in permissionless flat networks

Hyperboria

with more than 1000 nodes mostly tunneled over Internet links

DHT source routing limitations

  • XOR address space distance and DHT does not resemble physical network topology

  • Nodes lack local visibility to link quality typical of wireless links

  • 64-bit packet header cannot fit all the directors for long paths with many hops

17 / 22

Distributed secure routing in permissionless flat networks

Hyperboria

with more than 1000 nodes mostly tunneled over Internet links

DHT source routing limitations

  • XOR address space distance and DHT does not resemble physical network topology

  • Nodes lack local visibility to link quality typical of wireless links

  • 64-bit packet header cannot fit all the directors for long paths with many hops

Supernodes

  • Supernodes have full network view and offer path discovery service to subnodes

  • Traffic is still source routed and distributed throughout the mesh

17 / 22

Distributed secure routing in permissionless flat networks

Yggdrasil Network

Yggdrasil

the mythical world tree of Norse cosmology

  • Auto-configure a self-addressing encrypted network similar to cjdns

  • Route traffic via paths resembling physical topology

  • Allow all nodes to make the same assumptions about the network topology without keeping a full view

  • Guarantee a path to every node, which although unbound in theory, is usually close to the shortest path

https://en.wikipedia.org/wiki/Yggdrasil#/media/File:The_Ash_Yggdrasil_by_Friedrich_Wilhelm_Heine.jpg

18 / 22

Distributed secure routing in permissionless flat networks

Routing in Yggdrasil

  • Switch layer creates a globally agreed spanning tree
19 / 22

Distributed secure routing in permissionless flat networks

Routing in Yggdrasil

  • Switch layer creates a globally agreed spanning tree

  • A DHT is used to look up the coordinates for a given IP address

19 / 22

Distributed secure routing in permissionless flat networks

Routing in Yggdrasil

  • Switch layer creates a globally agreed spanning tree

  • A DHT is used to look up the coordinates for a given IP address

  • edges are always direct peers, selected based on peering stability

19 / 22

Distributed secure routing in permissionless flat networks

Routing in Yggdrasil

  • Switch layer creates a globally agreed spanning tree

  • A DHT is used to look up the coordinates for a given IP address

  • edges are always direct peers, selected based on peering stability

  • coordinates are shared with peers and cryptographically verifiable from root

19 / 22

Distributed secure routing in permissionless flat networks

Routing in Yggdrasil

  • Switch layer creates a globally agreed spanning tree

  • A DHT is used to look up the coordinates for a given IP address

  • edges are always direct peers, selected based on peering stability

  • coordinates are shared with peers and cryptographically verifiable from root

  • Switch layer uses coordinate system for greedy embedded routing

19 / 22

Distributed secure routing in permissionless flat networks

Routing in Yggdrasil

  • Switch layer creates a globally agreed spanning tree

  • A DHT is used to look up the coordinates for a given IP address

  • edges are always direct peers, selected based on peering stability

  • coordinates are shared with peers and cryptographically verifiable from root

  • Switch layer uses coordinate system for greedy embedded routing

  • Each node keeps a partial view of where locally stored state information scale at O(p*log(n)) for p peers in a network with n nodes

19 / 22

Distributed secure routing in permissionless flat networks

Routing in Yggdrasil

  • Switch layer creates a globally agreed spanning tree

  • A DHT is used to look up the coordinates for a given IP address

  • edges are always direct peers, selected based on peering stability

  • coordinates are shared with peers and cryptographically verifiable from root

  • Switch layer uses coordinate system for greedy embedded routing

  • Each node keeps a partial view of where locally stored state information scale at O(p*log(n)) for p peers in a network with n nodes

  • Routing traffic by walking represents a worst-case path with guaranteed reachablity, since greedy routing often take shortcuts not shown on

19 / 22

Distributed secure routing in permissionless flat networks

Yggdrasil global spanning tree

view from node 3efd [ 3 ]

20 / 22

Distributed secure routing in permissionless flat networks

Yggdrasil global spanning tree

view from node 3efd [ 3 ]

to d40c [ 3 5 2 ]

20 / 22

Distributed secure routing in permissionless flat networks

Yggdrasil global spanning tree

view from node 3efd [ 3 ]

to d40c [ 3 5 2 ]

  • Tree path: [ 3 ] [ 3 5 ] [ 3 5 2 ]
20 / 22

Distributed secure routing in permissionless flat networks

Yggdrasil global spanning tree

view from node 3efd [ 3 ]

to d40c [ 3 5 2 ]

  • Tree path: [ 3 ] [ 3 5 ] [ 3 5 2 ]
  • Greedy path: [ 3 ] [ 3 5 2 ]
20 / 22

Distributed secure routing in permissionless flat networks

cjdns Yggdrasil

21 / 22

Distributed secure routing in permissionless flat networks


#tomesh:tomesh.net freenode/#tomesh

#cjdns:matrix.org efnet/#cjdns
#yggdrasil:matrix.org freenode/#yggdrasil

22 / 22

Distributed secure routing in permissionless flat networks

2 / 22
Paused

Help

Keyboard shortcuts

↑, ←, Pg Up, k Go to previous slide
↓, →, Pg Dn, Space, j Go to next slide
Home Go to first slide
End Go to last slide
Number + Return Go to specific slide
b / m / f Toggle blackout / mirrored / fullscreen mode
c Clone slideshow
p Toggle presenter mode
t Restart the presentation timer
?, h Toggle this help
Esc Back to slideshow