Border Gateway Protocol (BGP) is the backbone of routing infrastructure in the Internet. In its current form, it is an insecure protocol with potential for propagation of bogus routing information. There have been several high-profiles Internet outages linked to BGP in recent times. Several BGP security proposals have been presented in the literature; however, none has been adopted so far and, as a result, securing BGP remains an unsolved problem to this day. Among existing BGP security proposals, Secure BGP (S-BGP) is considered most comprehensive. However, it presents significant challenges in terms of number of signature verifications and deployment considerations. For it to provide comprehensive security guarantees, it requires that all Autonomous Systems (ASes) in the Internet to adopt the scheme and participate in signature additions and verifications in BGP messages. Among others, these challenges have prevented S-BGP from being deployed today. In this thesis, we present two novel lightweight security protocols, called Credible BGP (C-BGP) and Hybrid Cryptosystem BGP (HC-BGP), which rely on security mechanisms in S-BGP but are designed to address signature verification overhead and deployment challenges associated with S-BGP. We develop original and detailed analytical and simulation models to study performance of our proposals and demonstrate that the proposed schemes promise significant savings in terms of computational overhead and security performance in presence of malicious ASes in the network. We also study the impact of IP prefix hijacking on control plane as well as data plane. Specifically, we analyze the impact of bogus routing information on Inter-Domain Packet Filters and propose novel and simple extensions to existing BGP route selection algorithm to combat bogus routing information.

Border Gateway Protocol (BGP) is the backbone of routing infrastructure in the Internet. In its current form, it is an insecure protocol with potential for propagation of bogus routing information. There have been several high-profiles Internet outages linked to BGP in recent times. Several BGP security proposals have been presented in the literature; however, none has been adopted so far and, as a result, securing BGP remains an unsolved problem to this day. Among existing BGP security proposals, Secure BGP (S-BGP) is considered most comprehensive. However, it presents significant challenges in terms of number of signature verifications and deployment considerations. For it to provide comprehensive security guarantees, it requires that all Autonomous Systems (ASes) in the Internet to adopt the scheme and participate in signature additions and verifications in BGP messages. Among others, these challenges have prevented S-BGP from being deployed today. In this thesis, we present two novel lightweight security protocols, called Credible BGP (C-BGP) and Hybrid Cryptosystem BGP (HC-BGP), which rely on security mechanisms in S-BGP but are designed to address signature verification overhead and deployment challenges associated with S-BGP. We develop original and detailed analytical and simulation models to study performance of our proposals and demonstrate that the proposed schemes promise significant savings in terms of computational overhead and security performance in presence of malicious ASes in the network. We also study the impact of IP prefix hijacking on control plane as well as data plane. Specifically, we analyze the impact of bogus routing information on Inter-Domain Packet Filters and propose novel and simple extensions to existing BGP route selection algorithm to combat bogus routing information.

Border Gateway Protocol (BGP) is the backbone of routing infrastructure in the Internet. In its current form, it is an insecure protocol with potential for propagation of bogus routing information. There have been several high-profiles Internet outages linked to BGP in recent times. Several BGP security proposals have been presented in the literature; however, none has been adopted so far and, as a result, securing BGP remains an unsolved problem to this day. Among existing BGP security proposals, Secure BGP (S-BGP) is considered most comprehensive. However, it presents significant challenges in terms of number of signature verifications and deployment considerations. For it to provide comprehensive security guarantees, it requires that all Autonomous Systems (ASes) in the Internet to adopt the scheme and participate in signature additions and verifications in BGP messages. Among others, these challenges have prevented S-BGP from being deployed today. In this thesis, we present two novel lightweight security protocols, called Credible BGP (C-BGP) and Hybrid Cryptosystem BGP (HC-BGP), which rely on security mechanisms in S-BGP but are designed to address signature verification overhead and deployment challenges associated with S-BGP. We develop original and detailed analytical and simulation models to study performance of our proposals and demonstrate that the proposed schemes promise significant savings in terms of computational overhead and security performance in presence of malicious ASes in the network. We also study the impact of IP prefix hijacking on control plane as well as data plane. Specifically, we analyze the impact of bogus routing information on Inter-Domain Packet Filters and propose novel and simple extensions to existing BGP route selection algorithm to combat bogus routing information.

Due to the absence of appropriate security mechanisms, even the latest version of Board Gateway Protocol (BGP) is still highly vulnerable to malicious routing hijacking. The original problem is that BGP allows router to accept any BGP update message without any extra validation process. Resource Public Key Infrastructure (RPKI) issues a series of digital signature certificates to provide binding relationship between the IP prefix in the route advertisement and the Autonomous System (AS) number on the propagation path to protect BGP routing. However, RPKI is a centralized architecture in which Certification Authority (CA) can launch power abuses attacks, such as unilaterally certificate revocation or publication repository tampering. In this thesis, we propose a blockchain-based BGP security infrastructure, named BGPcredit. The BGPcredit system synchronizes RPKI certificates by consensus process. It can maintain identical RPKI certificates repository across the whole system through blockchain, providing necessary security protection for BGP routing. In order to provide such features, we customize a proper consensus algorithm for BGPcredit which a reasonable credence management mechanism, credit computing function, block forger election process, Verifiable Random Function (VRF) are introduced. Also, the blockchain is customized to meet the system requirements. Moreover, BGPcredit advocates to make fully use of the trust of certification authorities to build a partially decentralized system. Some trusted nodes with higher authority are set to enhance the system’s security and robustness. Finally, I implement the BGPcredit prototype and conduct some validation experiments to test its performance. / På grund av avsaknaden av lämpliga säkerhetsmekanismer är även den senaste versionen av BGP fortfarande mycket sårbar för skadlig routerkappning. Det ursprungliga problemet är att BGP tillåter routern att acceptera alla BGP uppdateringsmeddelande utan någon extra valideringsprocess. RPKI utfärdar en serie digitala signaturcertifikat för att ge bindande relation mellan IP-adressprefixet i ruttannonsen och AS-numret på spridningsvägen för att skydda BGP-routningssäkerheten. Men RPKI är för centraliserad och CA kan starta strömmissbruk, till exempel ensidigt återkallande av certifikat och skadlig modifiering av publikationsregistret. I detta projekt föreslår vi en blockkedjebaserad BGP-säkerhetsinfrastruktur, kallad BGPcredit. Detta system synkroniserar RPKI-certifikat genom konsensusprocessen och kan upprätthålla identiska RPKI-certifikat arkiv över hela systemet genom blockchain, vilket ger nödvändigt säkerhetsskydd för BGP-routing. För att tillhandahålla sådana funktioner skräddarsyr vi en lämplig konsensusalgoritm baserad på nodkredit för BGPcredit som inkluderar en rimlig kredithanteringsmekanism, kreditberäkningsfunktion, blockförfalskningsprocess, VRF, etc. Dessutom har vissa anpassade ändringar i blockchain gjorts för att uppfylla systemkraven. Dessutom förespråkar BGPcredit att fullt ut utnyttja certifieringsmyndigheternas förtroende för att bygga upp ett delvis decentraliserat system. Vissa tillförlitliga noder med högre auktoritet är inställda för att förbättra systemets säkerhet och robusthet. Slutligen implementerar vi BGPcredit prototypen och genomför några valideringsexperiment. Resultaten visar att BGPcredit kan fungera bra och är kompatibel med BGP routing nätverk.

The BGP (Border Gateway Protocol) is responsible for establishing routing at the core of the Internet, yet it was not designed with security in mind. The Internet routing protocol is currently not secure — but its security can be enhanced. Initially conceived as a small community of trusted peers, the Internet has grown over time into a robust network of complex processes and securing these has become a priority. Thanks to the research community, the RPKI (Resource Public Key Infrastructure) protocol was designed to provide a layer of security to routing — by securing the origin, i.e., attesting that the source of the routing announcements is authorized to do so. As RPKI route validation has been recently widely adopted by multiple large carrier networks, many research projects have sought to measure the adoption of RPKI. This work aims to measure the adoption and the effects of RPKI route validation and filtering through the use of active experiments. A peering session was first established with one of the largest Tier-1 ISP: Arelion (formerly known as Telia Carrier) to announce and propagate a prefix with RPKI Valid, Invalid, and Unknown records. Then, the visibility of the prefix (in the control plane) and reachability of the prefix (in the data plane) was measured using visibility feeds from public BGP Route Collectors and reachability feeds from RIPE Atlas probes. The obtained results confirmed that some, but not all previously believed major networks, drop RPKI Invalid prefixes, affecting the destination network’s visibility. For networks that could still reach the destination, the data plane probes demonstrated that parameters such as the RTT and the hop count were not generally affected. A small increase in the destination network visibility was observed when comparing RPKI Valid with Unknown routes. All RPKI Valid Invalid and Unknown effects and their behavior are deeply analyzed. Data sets have been made publicly available for other researchers to analyze the data, and ensure the future of a more secure Internet. / BGP (Border Gateway Protocol) används för att sprida routinginformation mellan routrar i de tusentals nätverk som tillsammans bildar Internet, men det utformades inte med säkerhet i åtanke. Protokollet är i grunden inte säkert - men det kan bli det. Det som ursprungligen var en liten grupp sammanlänkade universitetsnätverk växte med tiden till att bli Internet, ett robust globalt nätverk med komplexa processer för utbyte av routinginformation. I ett modernt samhälle där vi kommit till att förlita oss på dess existens och funktion så har det blivit en prioritet att säkra dessa. Tack vare initiativ tagna i forsknings- och utvecklingsgruppen IETF (Internet Engineering Taskforce) utformades RPKI (Resource Public Key Infrastructure) för att tillhandahålla ett säkerhetslager för routing – genom att säkra ursprunget till routinginformation. Eftersom RPKI-validering nyligen har anammats av flera stora operatörsnätverk, har många forskningsprojekt försökt mäta användningen av RPKI. Detta arbete syftar till att mäta användningen och effekterna av RPKI-validering och filtrering genom användning av aktiva experiment. En BGP peering-session etablerades först med en av de större Tier-1 ISP: Arelion (tidigare känd som Telia Carrier) för att originera och sprida ett IP prefix med RPKI Valid, Invalid och Unknown poster. Sedan mättes prefixets synlighet (i kontrollplanet) och prefixets nåbarhet (i dataplanet) med hjälp av synlighetsflöden från offentliga BGP Route Collectors och nåbarhetsflöden från RIPE Atlas-prober. De erhållna resultaten bekräftade att vissa, men inte alla, stora nätverk blockerar RPKI Invalid prefix, vilket påverkar dess synlighet och nåbarhet. För nätverk som fortfarande kunde nå destinationen visade dataplanssonderna att parametrar som RTT och hoppantal inte påverkades generellt. En liten ökning av destinationsnätverkets synlighet observerades vid jämförelse av RPKI Valid med Unknown rötter. Alla RPKI Valid Invalid och Unknown effekter och deras beteende analyseras djupt. Datauppsättningar har gjorts offentligt tillgängliga för andra forskare för att analysera data och säkerställa framtiden för ett säkrare Internet.

While distributed databases offer great promise their decentralized nature poses a number of security and privacy issues. In what ways can parties misbehave? If a database is truly distributed can a malicious actor hide their misdeeds by presenting conflicting views of the database? Can we overcome such deceit and either prevent it by eliminating trust assumptions or detect such perfidy and hold the malicious party to account? We study these questions across two distributed databases: RPKI (Resource Public Key Infrastructure), which is used to authenticate the allocation and announcement of IP prefixes; and Bitcoin, a cryptocurrency that utilizes a permissionless database called a blockchain to track the transfer and ownership of bitcoins. The first part of this dissertation focuses on RPKI and the potential of RPKI authorities to misbehave. We consider the methods, motivations, and impact of this misbehavior and how an RPKI authority can present inconsistent views to hide this misbehavior. After studying the problem we propose solutions to detect and identify such misbehavior. Now we turn our attention to Bitcoin. We look at ways an attacker can manipulate Bitcoin's Peer-to-Peer network to cause members of the network to have inconsistent views of Bitcoin's blockchain and subvert Bitcoin's core security guarantees. We then propose countermeasures to harden Bitcoin against such attacks. The final part of this dissertation discusses the problem of privacy in Bitcoin. Many of the protocols developed to address Bitcoin's privacy limitations introduce trusted parties. We instead design privacy enhancing protocols that use an untrusted intermediary to mix \aka anonymize, bitcoin transactions via blind signatures. To do this we must invent a novel blind signature fair-exchange protocol that runs on Bitcoin's blockchain. This dissertation favors a dirty slate design process. We work to layer protections on existing protocols and when we must make changes to the underlying protocol we carefully weigh compatibility and deployment considerations. This philosophy has resulted in some of the research described in this dissertation influencing the design of deployed protocols. In the case of Bitcoin our research is currently used to harden a network controlling approximately a trillion dollars.