Towards securing interdomain routing on the Internet

The Internet consists of multiple autonomous systems (ASes), each consisting of networks of devices that are prone to malfunction, misconfiguration, or attack by malicious parties, and each controlled by profit-seeking businesses with different economic goals. Despite these complex relationships, the interdomain routing system (that allows ASes to communicate over the global Internet) currently operates under the assumption that all nodes in the network can trust each other. The thesis contributes to the body of works that seeks to remedy this, by considering network protocols that operate correctly even in the presence of adversarial or selfish behavior.;We take a principled approach to analyze the types of security guarantees that are possible within the engineering and economic constraints of the Internet's interdomain routing system. We focus exclusively on protocols that can be used to improve availability in the Internet, i.e., to increase the likelihood that packets arrive uncorrupted at their correct destination, and analyze two broad themes: (1) Which part of the system should be secured? (2) What is the right tradeoff between security and efficiency? To address these questions, we consider securing the following two parts of the system: the routing protocols, used to set up paths through the Internet, and the data-plane mechanisms, used to forward packets along the paths set up by the routing protocols. (1) We start with a game-theoretic analysis that shows that even the strongest known secure routing protocol is not sufficient to prevent selfish ASes from lying about the paths that data packets take through the network. We then find sufficient conditions that ensure that ASes will not lie. Unfortunately, these conditions are highly unrealistic, and so we conclude that ASes may have an incentive to lie about paths, and thus potentially forward their customer's traffic via paths that drop or corrupt packets. (2) We next consider secure data-plane mechanisms. We use novel cryptographic and data-streaming approaches to design lightweight protocols that detect packet loss and corruption on a path through the network, even when some nodes on the path are adversarial. Our protocols allow a sender and receiver to securely monitor billions of packets using only a few hundred bytes of storage and a pair of comparably sized control packets. (3) Finally, we take the security guarantees above even further, by considering protocols that also localize an adversarial node that drops or corrupts packets. We use cryptographic proof techniques to design new protocols and argue that any secure localization protocol requires the participation of every node on the path. This requirement is considered severe in the setting of interdomain routing, where each node is owned by independent economic entity, with little incentive to participate in the localization protocol. Our results have implications on the design of high-performance network architectures that can withstand selfish and adversarial behavior.