Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 381Highly Secure and Highly Secure and Efficient RoutingEfficient RoutingIoannis Avramopulos, Hisashi Kobayashi Randolph Wang Ioannis Avramopulos, Hisashi Kobayashi Randolph Wang Arvind KrishamurthyArvind Krishamurthy Dept. of EE Dept. of CS Dept. of EE Dept. of CS Dept. of CS Dept. of CS Princeton University Princeton University Yale University Yale UniversityPresentation: Huan He2 ContentsContentsThe routing protocolThe routing protocolHow the protocol How the protocol defend adversarydefend adversarySummarySummary3 Network FailuresNetwork FailuresSimpleSimple one where some network component( one one where some network component( one or more nodes) simply become inoperativeor more nodes) simply become inoperativeByzantineByzantine In Byzantine failure, a component becomes In Byzantine failure, a component becomes faulty and yet continues to faulty and yet continues to operate( incorrectly)operate( incorrectly)4 The Routing Protocol The Routing Protocol This routing protocol is a This routing protocol is a routing protocol with routing protocol with Byzantine robustnessByzantine robustness and and detectiondetection5 The Routing protocolThe Routing protocolBasic IdeaBasic IdeaSpecific mechanismsSpecific mechanisms•AuthenticationAuthentication•Route SelectionRoute Selection•Reserved Buffers, Timeouts, Reserved Buffers, Timeouts, and Sequence Numbersand Sequence Numbers6 Some definitionSome definitionWhat is a What is a faulty nodefaulty node?? --Does not follow the protocol --Does not follow the protocol --Can be impersonated by another --Can be impersonated by another nodenodeWhat is a What is a faulty linkfaulty link?? --Drops packet--Drops packet --Is incident to a faulty node--Is incident to a faulty nodeIf a link is detected to be faulty, If a link is detected to be faulty, one or more of following is true:one or more of following is true: --The upstream router is faulty--The upstream router is faulty --The link is faulty--The link is faulty --the downstream router is faulty--the downstream router is faulty7 The Routing protocolThe Routing protocolBasic IdeaBasic IdeaSpecific mechanismsSpecific mechanisms•AuthenticationAuthentication•Route SelectionRoute Selection•Reserved Buffers, Timeouts, Reserved Buffers, Timeouts, and Sequence Numbersand Sequence Numbers8 Basic Idea—Basic Idea—Packet Forwarding with Fault Packet Forwarding with Fault DetectionDetectionSource RoutingSource RoutingDestination acknowledgementsDestination acknowledgementsTimeouts( to receive ACK or FA Timeouts( to receive ACK or FA from destination)from destination)Fault Announcements( FA)Fault Announcements( FA)9 Basic Idea—Basic Idea—A Simple ExampleA Simple ExampleSD3M2461××Route(S,1,4,5,D)5Route(S,3,M,6,D)Route(S,2,M,6,D)××10 Basic Idea—Basic Idea—MoreMoreWe also need more following mechanisms We also need more following mechanisms to provide Byzatine robustnessto provide Byzatine robustness•Data and control packet authenticationData and control packet authentication•A-priori reserved buffersA-priori reserved buffers•Monotonically increasing non-wrapping Monotonically increasing non-wrapping sequence numberssequence numbers•Round-robin scheduling of packet Round-robin scheduling of packet transmissiontransmission•Calculation of appropriate time out valuesCalculation of appropriate time out values11 Basic IdeaBasic IdeaNone of the individual None of the individual mechanisms of the basic protocol mechanisms of the basic protocol described in here is novel, it is described in here is novel, it is the the combinationcombination of them that of them that delivers the desired robustness delivers the desired robustness and efficiencyand efficiency12 The Routing protocolThe Routing protocolBasic IdeaBasic IdeaSpecific mechanismsSpecific mechanisms•AuthenticationAuthentication•Reserved Buffers, Timeouts, Reserved Buffers, Timeouts, and Sequence Numbersand Sequence Numbers•Route SelectionRoute Selection13 AuthenticationAuthenticationAuthentication of Authentication of Data PacketsData Packets:: --Safeguards against modification --Safeguards against modification --Ensures that allocated resources( namely, --Ensures that allocated resources( namely, reserved buffers)reserved buffers) Authentication of Authentication of Control packetsControl packets:: --Prevents malicious nodes from forging ACKs and --Prevents malicious nodes from forging ACKs and FAs on behalf of non- faulty nodesFAs on behalf of non- faulty nodesPerformance of Authentication Performance of Authentication mechanism is crucial:mechanism is crucial: As authentication must be performed for each As authentication must be performed for each packet at each node and the speed of packet at each node and the speed of authentication may bound the effective link authentication may bound the effective link bandwidth.bandwidth.14 AuthenticationAuthenticationDigital signatureDigital signature --Most straightforward authentication --Most straightforward authentication mechanismmechanism --Poor performance--Poor performance15 AuthenticationAuthenticationThe The multicast authenticationmulticast authentication construction of Canetti construction of Canetti MACMACdd=f(Key=f(Keysdsd) ) MAC( Message Authentication MAC( Message Authentication code)code)Limitatione:Limitatione: Vulnerable to an adversary that Vulnerable to an adversary that tampers with only a subset of tampers with only a subset of the authentication tags( when the authentication tags( when used to secure data packet used to secure data packet forwarding)forwarding)16 AuthenticationAuthenticationTeslaTesla --A --A broadcast authenticationbroadcast authentication protocol protocol that relies on loose clock that relies on loose clock synchronization and delayed key synchronization and delayed key disclosuredisclosure --limitations:--limitations: 1.Delayed authentication is vulnerable 1.Delayed authentication is vulnerable to a DoS attackto a DoS