2 Comments

  1. Kerry Thompson on 18 February 2016 at 3:45 pm

    Interesting talk Russ, and plenty to think about.
    I take it when you refer to SPF then you’re thinking Shortest Path First (aka Dijkstra’s algorithm). I think it would technically work if each AS advertised it’s connections – then a distant router could build an AS-link state database and form a topology map of the network and provably verify all paths. However, I don’t think this would scale and the solution would rely on _all_ Internet routers performing path validation.

    I was thinking maybe a better would be for the source AS to detect and then poison known bad paths (like poison reverse, maybe call it poison forward). Let’s say an organisation with an important AS build a server which connects to Internet looking glass points and pulls global BGP tables periodically from different points around the Internet. From this data, the software should be able to figure out which paths are bad for it’s own AS and prefixes, and then isolate which AS is advertising bad paths – for example AS65666 may advertise a bad path to your AS65001.

    If AS65001’s BGP could now advertise a bad path notice “AS65001 not valid via AS65666”, DPKI-signed by AS65001, then it would be much easier for distant routers to take note and remove bad paths from their tables.

    This might just be scalable if we assume that the vast majority of paths are good and only a tiny minority are bad. However there’s some corner-cases where it wouldn’t work – for example if you find thousands of AS’s are advertising bad paths.

    However, I don’t think path-poisoning is a function in BGP today – but I’m no BGP expert by any means.

    Lots to think about here.



    • Russ on 19 February 2016 at 7:26 am

      The concept we’re talking about can be used as roughly a DAG — similar to SPF, but — the simplest explanation is you move everything from the TENT to the PATH, rather than only the shortest path, so you end up with a list of all paths in the network. This wouldn’t be at the router level, but at the AS level, so the entire DAG would be around 32k entries if every AS participated. 32k is pretty easy in terms of building a DAG using something like Dijkstra.

      The poison idea is interesting — the problem is it would be too slow in most cases (most hijacks only last a few minutes, much less the time for the route to be noticed and poisoned), it would likely block legitimate traffic in some cases (the hijacker doesn’t just hijack the address space, but also the AS number as the origin in some cases), and it’s reputation dependent (how many legitimate emails are caught in email blacklists every day I wonder?). Path poisoning also opens a new attack surface — sadly. 🙁 That’s why there’s no “negative route” in routing protocols, it’s just one big fat target waiting to be exploited.

      Thanks for the comments — I’m working on a long series for the LinkedIn engineering blog that should publish at some point that’s going to mimic the talk, but deeper in some areas, and less deep in others.

      🙂

      Russ