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.
|
