Efficient and Secure Source Authentication with Packet Passports

Efficient and Secure Source Authentication with Packet Passports Xin Liu (UC Irvine) Xiaowei Yang (UC Irvine) David Wetherall (Univ. of Washington) Thomas Anderson (Univ. of Washington)

Outline Motivation Design High-Level Idea Challenges and Solutions Feasibility Analysis Related Work Summary

Denial-of-Service (DoS) Flooding Attack Victim This type of attack is prevailing Yahoo was knocked down in Feb 2000 Online extortion

General Approaches to Combat DoS Flooding Attacks Preventive Prevent DoS attacks from happening Capability System [Anderson03, Yarr04, Yang05] Ticket System [Patel97] Reactive Eliminate DoS attacks after they cause damage Filtering Our next step is to compare the two and pick the winner

Filtering is Difficult Filtering! Filtering! Filtering By default, all traffic is allowed to pass Victim requests to install filters to remove attack traffic Challenges Installing filters close to the attack sources Describing attack traffic in filter description Any field of a packet can be forged, including source IP address

Authentic Source Identifier can Help SrcID X Filter: SrcID X Filter: SrcID Y SrcID Y Advantages Showing where a packet comes from Serving as a traffic descriptor in filters Source IP address is not verifiable Cannot be trusted unless spoofing is totally eliminated Routers may be compromised

Outline Motivation Design High-Level Idea Challenges and Solutions Feasibility Analysis Related Work Summary

Our Solution: Packet Passport System IP Packet IP Header Passport Payload Goal of a passport: providing an authentic source identifier that routers can verify independently at packet forwarding time

Requirements A passport must be: Unforgeable Efficient to generate and verify Digital signature: computationally expensive The packet passport system must: Bootstrap with minimum out-of-band communication Be robust against DoS attacks

High Level Idea MAC: Message Authentication Code K(X,Y): Symmetric key shared between two nodes X and Y K(A,R) K(A,B) K(A,R) K(R,B) R A IP Packet A Source Identifier K(A,B) K(R,B) R MACR B MACB Passport B IP Packet A R MACR B MACB Passport IP Packet A R MACR B MACB Passport MACR MACK(A,R)(A, R, B, SrcIP, DstIP, )

Challenges Scalability Too many keys Path in passport too long How to establish secret keys Bootstrapping key distribution messages can not contain passports Key distribution messages may be dropped due to DoS attacks Packets with valid passports may be replayed to launch DoS attacks

Two-Level Hierarchy for Scalability AS1 AS2 AS3 K(AS1,AS2) K(AS1,AS3) K(AS1,AS2) K(AS2,AS3) K(AS1,AS3) K(AS2,AS3) R1 R2 R3 R5 R6 R4 A Passport Intra-domain Identifier B Passport AS2 AS1 Intra-domain MAC2 Identifier AS3 MAC3

Limitation of Two-Level Hierarchy Only the source domain can verify intra- domain identifiers Filters may not be effective when source domain forges arbitrary intra-domain identifiers Counter-measure: blocking the source domain

Implementation of Intra-domain Identifier is Flexible Each domain can implement intra-domain identifier in its own way Source IP address (if source spoofing is prevented inside a domain) Message authentication code

Key Distribution via BGP AS1 10.1.0.0/16 Prefix Announcement 2 eBGP rAS1 10.1.0.0/16 d AS1 Prefix Announcement 1 Diffie-Hellman Key Exchange rASi 10.2.0.0/16 d ASi g mod p rAS2 rAS1 K ( AS1 , AS 2 ) d AS1 mod p d AS2 mod p eBGP d AS 2 rAS 2 AS2 10.2.0.0/16

Benefits of Key Distribution via BGP Allowing key distribution to bootstrap eBGP session between adjacent domains can be authenticated without passports [RFC3682] Robust against DoS flooding attack BGP is a closed system: BGP traffic can get higher priority Supporting incremental deployment d ASi can be carried in optional and transitive path attribute

Securing Key Distribution d AS is signed with ASi’s private key i ASi’s public key is distributed like d ASi ASi’s public key is bound to ASi using the same mechanism that binds a prefix to a domain Reusing the PKI that secures routing: public key certification by CAs

Preventing Replay Attack Too much traffic from A! Block him! A Compromised Router B Problem: attack traffic cannot be cut off Why replay attack prevention is difficult? Timestamp: time synchronization between domains Sequence number: synchronization inside a domain Our Solution Bloom Filter Fast Re-keying

Bloom Filter to Detect Duplication Bloom Filter AS1,100 ID 100 AS1 ID 100 AS2 ID 100 ID 100 AS3 AS4 ID 100 Limitation: a bloom filter cannot remember a passport for a long time 16Mb SRAM can “remember” 2.5Gbps traffic for 5 seconds with a false positive rate of 5.7 10-6

Fast Re-keying Km(AS1,AS2) HASHm(K(AS1,AS2)) K(AS1,AS2) Hash chain K1(AS1,AS2) AS4 K200(AS1,AS2) KeyIdx 100 K1000 (AS1,AS2) AS1 KeyIdx 100 KeyIdx 200 AS2 200 KeyIdx 200 AS3

Passport Verification Process Receive a packet Forward the packet No KeyIdx too large? Yes No MAC valid? No Yes Duplicate? Yes Discard/demote the packet

Supporting Incremental Deployment Key distribution messages are wrapped in optional and transitive path attributes in prefix announcements Passport can be implemented as a shim layer AS path in a passport only includes those that have deployed packet passport system

Incentives for Early Adoption Passport Enabled AS1 AS3 Passport Enabled AS2 No domains can spoof AS1’s source identifier at AS2 AS2 can filter DoS attack traffic from AS1 AS1 can locate attack sources within itself

Other Applications Fair resource allocation Restricting/eliminating reflector attacks Deterring future attacks

Feasibility Analysis Practical with today’s hardware technology Passport generation and validation: with UMAC, a commodity PC can generate 975K passports and verify 3.9M passports per second Key distribution: computation, communication and storage cost almost negligible Bloom filter: 16Mb SRAM can “remember” 2.5Gbps traffic for 5 seconds with a false positive rate of 5.7 10-6

Related Work Our key advantage: stronger authentication Source address validation: Ingress/egress filtering, reverse path filtering, SAVE [Li02] Source address not verifiable Path as the identifier: Path Identifier [Yaar03], Active Internet Traffic Filtering [Argyraki05] First portion of the path spoofable Authenticated Marking Scheme [Song01] Not verifiable at packet forwarding time Spoofing Prevention Method [Bremler-Barr05] Secret in plain text; secret distribution problematic TVA [Yang05], Ticket System [Patel97], Visa Protocol [Estrin89] Request channel vulnerable

Summary A packet passport efficiently and securely authenticates the source of a packet. The system is incrementally deployable with incentives for early adoption. The system is practical with today’s hardware technology. Future Work Improvement to replay attack prevention Design and implementation of an automatic filtering system

Packet Passport Format