ABSTRACT:

The basic foundations of the Internet are surprisingly vulnerable to simple attacks that could be mounted by rogue hackers or result from simple misconfiguration. One area that remains particularly exposed to attacks is routing: packets usually traverse many intermediate routers on their way from a source to their destination. Since these routers may belong to different (some possibly malicious) organizations, how do we guarantee that our packets arrive as intended at their destination and are not dropped or tampered with by some intermediate router?

In this talk I will outline a formal security framework for this problem and focus on two results that show how the level of security one requires drastically changes the amount of resources necessary to achieve security.

Our first result is a protocol that distinguishes between extremely bad performance (say > 1% of traffic is dropped or modified) and tolerable performance (say < 0.05% of traffic is dropped or modified) in the presence of malicious adversaries. The protocol adds only a O(log T) size additional message per T data packets transmitted, and requires only the participation of the source and destination routers, with no active participation by intermediate routers. Our techniques are based on the sketching scheme of Charikar-Chen-Farach-Colton '02, but we are able to prove better performance guarantees by our use of cryptographic hash functions. These improved performance bounds may be of independent interest.

Our second result shows that in order to know whether each individual packet was transmitted correctly, and if not where exactly it was dropped or modified, the cooperation of all the intermediate routers is necessary. Our result is a black-box separation in the style of Impagliazzo-Rudich '89, and uses as a building block a learning algorithm of Naor-Rothblum '06. Practically speaking, this result means such strong security may be hard to achieve in real life, since intermediate routers may not have any incentive to participate in such a protocol.

This is joint work with Boaz Barak, Sharon Goldberg, Jennifer Rexford, and Eran Tromer.