May 21 2018

Playing battleships over BGP

BGP is the glue of the internet. For a protocol that was produced on two napkins in 1989 it is both amazing and horrifying that it runs almost all of the ISP to ISP interactions and is now a very fundemental part of the internet.

BGP normally gets a bad rep, mainly because of its default trusting nature of peers, and the hard task of verifying a routes legitimacy. This is why we hear about BGP hijackings of varying severity from the whole of youtube to a section of all AWS Route 53 requests.

However to understand this, you also have to understand how the topology of the internet works. In this case, we start with a lonely router:

A router isn’t much use if it cannot route anything, so we connect it to another router on a physical layer (this can be anything from copper ethernet, to undersea fibre, to 802.11 “wifi” links)

After that, the two connected routers (in our case, the red and blue router) need to know what they can route for each other. After all the point of routers is to route traffic from one destination to another.

As mentioned above, the globally accepted way to do this between ISPs is to setup BGP on both sides, and let the sides “announce” to each other what they can route:

However it’s not much use if they can only talk to each other, and what if red and blue are not directly connected? The more routers we connect to, and those other routers connect to, we form a topology of routing information. This is possible because BGP shares routing information with its other peers it’s connected to:

How routers share information between each other is dependent on the configuration policy, and that is normally dictated by the real world relationship two routers have in common. Different setups exist for customers, traffic exchange agreements, or upstream providers.

Because of this, routers should have sets of instructions programmed into them to filter out things they are not expecting to give or to take from another peer. However from time to time someone with malicious intentions obtains access to a router that is connected to a router that does not have these filters. Fixing this programatically is incredibly hard because it would require every ISP to change how their routers work, and previous attempts to fix this have proven to not be widely adopted.

BGP also has a way to encode information with a route called communities. Defined in RFC1997 (sadly written in 1996, so. close.) a community can be attached to a route announcement, and consists of a 32bit number. That in practice is split into two 16 bit numbers (one for a ASN and one for a signal related to/for that ASN):

These are used to signal extra information about the route, for example where a provider picked up a route:

This is useful in terms of filtering. For example if you have many providers and you want to try and ensure traffic stays local to your country, you can use these communities to give a better preference to those routes.

This had me thinking though. What else could we signal? And how far do communities go?

After some testing, it appears that every tier 1 network strips communities except former Level 3 who carry communties from origin router to customer router. This also means that a router could send information to other routers without ever actually talking directly to each other.

Battleships

Knowing that I could do “indirect communication” over BGP now, I wanted to somehow use this to conduct some non conventional communication. I picked Battleships as a medium to test this in, since the communication required to play a battleship game is tiny (X and Y coordinates and if the last shot was a hit or a miss)

Two communities were produced that would allow me run a game of battleships over BGP

This fits a entire game setup into two 16 bit numbers, allowing the game move to be reliably communicated with two communities.

Since battleships is a 2 player game, I recruited AS203729 to play with me. Since they had BGP sessions in New York while I had my own BGP connections setup in London.

While planning out the game, we foresaw we could trigger BGP Route Flap Damping while playing the game due to the frequency we would both be updating our routes. Since we were both supporting real production traffic through the prefixes we were using to play the game, we agreed to a 30 second cooldown timer on every move we made, since triggering route flap damping would cause prefixes to be blackholed, and thus cause an outage for either of us.

As we were running other traffic through these routers, we had to keep our normal routing demon online rather than a custom BGP demon. To work around this the battleship game binary live generated and reloaded BIRD configuration and used the demons control socket to poll for route changes.

With that all setup, on May 16th 2018 myself AS206924 and AS203729 played what is likely the first board game ever conducted purely over BGP.

The game went smoothly, apart from a 45 minute period where no moves were exchanged due to causing the previously mentioned route flap damping to activate. This happened on my side and caused Level 3 to have a less optimal route for my traffic in the 45 minute period. To mitigate this from happening again later on the game, we decided to move to a 90 second cooldown period on every move.

Despite this, the final blow to my friend AS203729 was dealt on the 68th move. Making me the first winner of a board game conducted done over a public internet routing protocol.

Was this a logical thing to do? Probably not. Was this a fun to do? Hell yes.

I’ve open sourced the code that we both ran, though I really would not suggest repeating this experiment.

https://github.com/benjojo/bgp-battleships

And if you enjoyed this, you will be glad to know that I am going to be at Recurse Center in NY for the next 5 weeks! Meaning you can follow my Twitter or RSS to keep up with the other silly (or sometimes sensible) things I will do!

Until next time!