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 other (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 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
This work will appear at EUROCRYPT 2008 and SIGMETRICS 2008 and is joint with Boaz Barak,
Sharon Goldberg, Jennifer Rexford, and Eran Tromer.