I'm not sure this is practical. Caveats: I have only read the paper while sleepy, and I'm worried that I'm breaching our negativity rules with my attack, but I'll proceed: I propose the following attack on the protocol.
Bisect North and South America with a 'no go zone' for packets -- we can't live with a packet hitting Omaha, for a variety of reasons.
I propose that there exists no safe "alibi" route from SF to NY. Any crooked peer can route into the dreaded Omaha and to a crooked NY peer faster than any safe route can go west through Asia. A crooked peer can forge sequential MACs showing a 'legitimate' looking route easily.
So, I would reformulate the claims to "If a packet is never routed to an attacker that can route through a forbidden zone more quickly than obeying the restrictions, there is a valid alibi routing."
It's hard to come up with a good use case for this protocol, in my mind. Especially because we are most often concerned with packet routing at the destination and source, and for legal reasons, not inspection reasons.
It's largely understood by anyone who might possibly be using alibi routing that packets are often inspected in flight, and there is nothing you can do about it, and that furthermore the concepts of safe or unsafe nations or regions or cities are almost laughable when it comes to even the smallest nation state's avaricious desire for inspection and storage of data flying by.
Indeed, totally not practical.
First, it is a very impressive paper that got into the flagship conference. It presents and solves an intriguing puzzle.
The implied attacker model: you are safe unless your packet traverses an unsafe country. Wrong in my opinion (RFC 7258).
As a scientist I've seen this over-and-over again. No healthy scientific community exists around privacy. SIGCOMM-like venue want novel/crazy ideas. We known onion routing works to a large extend. However, it is a career/tenure killer to work on that. No grants. No citations.
I don't understand why this is true: my crooked peer can route both ways if you have some other way of 'checking' on my routing. Or I can be right next to you and pretend to be in Asia by offering bad GPS coordinates and auto-lagging my response times. No?
So they use "checkpoints" everywhere in the world and use time as a radius of impact. I wonder how precise this is.
> Our proofs of avoidance are built around the idea of using what we call “alibis”: relays that are sufficiently far away from the forbidden region such that traversing both relay and forbidden region would result in a noticeably high delay.
And they implemented a p2p protocol to find these alibis easily. I guess from a starting list of trusted alibis.
> The second contribution we make is the design and implementation of Alibi Routing, a peer-to-peer overlay routing system for finding alibis safely and efficiently
My main concern is how can they predict the minimum speed a packet takes to reach their target? Especially with zones of poor cabling.
In the example on the home page, the traffic from Italy to Norway, avoiding Germany, travels across the ocean, which means it bottlenecked through undersea cables, the most thoroughly tapped network links in the world.
This research is of aesthetic interest, not practical interest.
If Russia wants to tap fibre, anywhere in the world, do we think it's beyond their capabilities? I doubt this capability is even beyond the reach of large corps. Cables have to go underseas (expensive but a known access method) or over land (even easier).
Even if both ends of a link are actively monitoring (can you even tell the distance on a fibre cut?) - an adversary with more than 2 people can just make 3 cuts. It simply doesn't seem practical to think that fibre isn't monitored by any large group that wants to. Seriously, what are we talking about, to run a tap for a year? A million bucks? Probably considerably less.
You can tell the distance of a fibre cut by measuring time it takes for any internal reflections to come back to you. There will be faint reflections when you cut the fiber unless you are extremely lucky and skilled, because of the nature of the material. Think of the edges around a chip in a drinking glass.
Source: my Dad used to work for Agilent in the 90s, who made test equipment for doing exactly this (although that was mainly to find which roadworks had put a backhoe through the fiber I think, but they did undersea stuff too).
Being able to detect a tap is different from doing something about it when the alternatives are living with the tap and shutting down a transoceanic cable until the tap is removed. Actors with nuclear submarines have been tapping lines on the sea floor for fifty years or so.
Bisect North and South America with a 'no go zone' for packets -- we can't live with a packet hitting Omaha, for a variety of reasons.
I propose that there exists no safe "alibi" route from SF to NY. Any crooked peer can route into the dreaded Omaha and to a crooked NY peer faster than any safe route can go west through Asia. A crooked peer can forge sequential MACs showing a 'legitimate' looking route easily.
So, I would reformulate the claims to "If a packet is never routed to an attacker that can route through a forbidden zone more quickly than obeying the restrictions, there is a valid alibi routing."
It's hard to come up with a good use case for this protocol, in my mind. Especially because we are most often concerned with packet routing at the destination and source, and for legal reasons, not inspection reasons.
It's largely understood by anyone who might possibly be using alibi routing that packets are often inspected in flight, and there is nothing you can do about it, and that furthermore the concepts of safe or unsafe nations or regions or cities are almost laughable when it comes to even the smallest nation state's avaricious desire for inspection and storage of data flying by.