Researchers create P2P Alibi Routing to avoid censorship and government surveillance

A team of University of Maryland Institute for Advanced Computer Studies (UMIACS) researchers developed “provable avoidance routing” that they call Alibi Routing; it’s an overlay routing protocol that provides Internet users with a method to avoid sending their data through countries known for their censorship. Users specify where they want their packets NOT to go and Alibi Routing can provide “concrete proof” that users’ data did not pass through “undesired geographic regions.”

The researchers unveiled Alibi Routing at the 2015 Association for Computing Machinery Special Interest Group on Data Communication (ACM SIGCOMM) conference. The research paper (pdf) “introduces a primitive, provable avoidance routing that, when given a destination and region to avoid, provides ‘proof’ after the fact that a packet and its response did not traverse the forbidden region. We rely on the insight that a packet could provide an ‘alibi’—a place and time where it was—to prove that it must have avoided the forbidden region in transit from source to destination.”

“With recent events, such as censorship of Internet traffic, suspicious ‘boomerang routing’ where data leaves a region only to come back again, and monitoring of users’ data, we became increasingly interested in this notion of empowering users to have more control over what happens with their data,” said UMIACS Assistant Research Scientist Dave Levin.

If you are not concerned with censorship, then it might do you well to recall that the U.S. government exploits loopholes in Executive Order 12333, deliberately manipulating Americans’ network traffic so that it is routed through a device located abroad, which allows the NSA to “unconstitutionally” collect and store Americans’ communications.

Peers and neighbors

University of Maryland Institute for Advanced Computer Studies

“A user specifies two things: who they want to communicate with (the destination), and arbitrary ‘forbidden’ geographic regions they wish to avoid while doing so.”

UMIACS

According to a video of the slides, “Alibi Routing is a peer-to-peer protocol for finding potential alibis.” After users choose forbidden regions and target regions where alibis might be, then “Alibi Routing recursively searches for peers within the target regions.”

Every P2P Alibi user has a set of “neighbor” peers and “every peer in the system maintains a constant-sized set of neighbors;” the team used 32 peers with diverse latency in its implementation. In theory, a person would contact a peer they know and ping her.

To “establish a neighbor,” the peers “exchange their GPS coordinates—precise locations would be a violation of the users’ privacy,” so city or even country-level GPS coordinates are used. “The peers establish a shared symmetric key, which they use to compute and verify MACs on the packets they forward for one another. This same process applies when establishing a connection between a source node and an alibi peer.”

“Alibi Routing assumes that nodes outside the forbidden region are trustworthy in reporting their geographic locations and in vouching for neighbors that are too nearby to be in the forbidden region,” the paper states. “It leverages this assumption to direct relay discovery queries toward a target region in which alibis might reside.”

Alibi Routing has an 85% to 95% success rate

The University of Maryland research team simulated a 20,000-user network, defining China, Iran, PR Korea, Syria, and Saudi Arabia as “enemies of the Internet” and India, Japan and USA as having the most Internet users. Alibi Routing “successfully found an alibi more than 85% of the time. With a small safety parameter, the success rate rose to 95%. The results suggest that users can typically avoid the part of the world they wish to route around.”

Failures occurred if “the target region is too small or non-existent.” Proximity could also result in failure when the “source or destination are very close to the forbidden region.”

Routes through alibis incur little increase in latency…sometimes even lower latencies. Another big plus is that Alibi Routing “is immediately deployable and does not require knowledge of—or modifications to—the Internet’s routing hardware or policies.” In other words, the system works at a user – not ISP – level. “Provable avoidance is possible safely and efficiently.”

Security analysis of Alibi Routing

Alibi Routing “derives its security and proofs of avoidance from a ‘clock and a map’: local measurements of round-trip times and a rough knowledge of one’s own (and one’s attacker’s) GPS coordinates.”

UMIACS

The team analyzed the security of Alibi Routing; attacks on safety don’t work since “one cannot trick a trusted peer into thinking that an unsafe peer is safe.” The Alibi Routing protocol “is not susceptible to packet manipulation by nodes within a forbidden region;” packets from an attacker within a forbidden region are ignored altogether.

Attacks on progress, however, are a different story. The researchers wrote, “An adversary could launch an eclipse attack by attempting to populate a victim’s neighbor set with all attackers. Note that such an attack would require an attacker to be very close to the victim.”

Potential “non-attacks” such as “laundering attack traffic,” meaning using the “overlay routing system for reflecting attack traffic” and “sending copies of data to attackers” could be solved by combining Alibi Routing with a more traditional system. The team used Tor in their examples.

Alibi Routing…coming by the end of 2015 for testing

Although you can download the code and data for the Alibi Routing prototype now to run the same experiments described in the paper, the researchers intend to release Alibi Routing, perhaps as a browser extension, by the end of 2015. The more people who use it “in different geographical locations, the more useful it will be.”

However, it’s not bulletproof, “as it is impossible for users to avoid the countries they are in—the very problem traditional censorship-resistant systems address.” Alibi Routing is meant to complement such systems, not to replace them.

I highly recommend watching the video of slides for Alibi Routing (pdf).