Study of a Secure Probabilistic Routing Algorithm for Ad Hoc NetworksBackgroundCurrent StateIdeaRouting Protocol - Basic OperationForwarding - at sourceForwarding – on intermediate node, niReception –at destination dAcknowledgment – at intermediate node niAcknowledgment – at source, sLink Weight Updates at source, sLink Weight Updates at source, sRouting Protocol - Basic OperationPerformance AssessmentConclusion and Future WorkStudy of a Secure Probabilistic Routing Algorithm for Ad Hoc NetworksStefan VelicaECE 646Cryptography and Computer-Network SecurityFall 20031Background• Mobile Ad Hoc Networks (MANET’s) – Wireless broadcast– Cooperative nature– Ease of access for adversaries• Secure Routing Problem 2Current StateClassical Routing Protocols3AODV, DSRSimple Attacks• Advertise false routes• Modify existent routes• Routing packets in a loopSecurity-aware Routing ProtocolsARAN, AriadneSophisticated Attacks• Denial-of-Service• Single Byzantine Adversaries• Colluding Byzantine AdversariesOur Target ProtocolIdea4Behavior of antsRouting Protocol - Basic Operations - Sourced - Destinations d data• generate source route• append it to packet• start ack timer• send packeti – Intermediate Node• forward packet• start timer waiting for ack• receive packet• reply with ack• append/create ack• verify ack• update “routing table”5Forwarding - at source1. Generate source route1221),),(,(,,,2snsnsnsnKKKKMACMACEnsEdatas ⋅⋅⋅dnnnsL→→→→→−121L“Onion” Encryptionflip a coin>< datads ,,sddnnnsL→→→→→−121L2. Encrypt source route3. Start ack timer4. Send packet to n16Forwarding – on intermediate node, niiinn →−1isnisnisnisnKKKiiKMACMACEnnEdatas ),),(,,(,,1111++⋅⋅⋅+−3. Start timer waiting for ack4. Send packet to next node 1. Authenticate packet 2. Decrypt path list )),(,,11 ++⋅⋅⋅isnisnKKMACEdatas7Reception –at destination drnL→−1sdsdKLKMACdnEdatas ),,(,,1−1. Authenticate payload2. Decrypt path list3. Send ack to ssdKMACdidsack ,,,,rnL←−18Acknowledgment – at intermediate node niif ( & “timer not expired” )1+←iinn“onion encrypt”:isnisnisnisnKKKiKiMACMACEnidsackEnidsack ),),(,,,,(,,,,111++⋅⋅⋅+elseif ( “no ack” & “timer expired” )prepare:isnKiMACnidsack ,,,,iinn ←−19Acknowledgment – at source, s1ns←11),(,,,,1snsnKKMACEnidsack ⋅⋅⋅if ( & “timer not expired” )1ns←foreach niverify MAC“onion decrypt” next ackif ( “ack forged” || “timer expired at one node” )penalize subsequent links10Link Weight Updates at source, sAccumulated acks-link (3, 4):s 1 2 3 4 dPositive ack’s:s 3 4 6 7 dpa=2Negative ack:s 5 3 4 dna=110, <<←+ββnapanab“Loss” of link:wbw⋅←~New Weight:11Link Weight Updates at source, s),( EVG=s1d0s3s2s41=∑ewWeight Pushing{}Eewe∈:~1=∑ew{}Eewe∈:4302 112Routing Protocol - Basic Operations - source d - destinationi – intermediate nodes d data• generate source route• append it to packet• start ack timer• send packet• forward packet• start timer waiting for ack• receive packet• reply with ack• append/create ack• verify ack• link weight update13Performance Assessment• Advantages– Reduced traffic overhead– Robustness to various attacks•Drawbacks– Algorithmic complexity – Slow convergence14Conclusion and Future Work• Original approach based on:– Ant behavior– Onion encryption• Addresses stronger adversarial models:– DoS attacks– Adaptive single/colluding Byzantine attacks• Can the algorithm be improved?– Computational complexity – Convergence
View Full Document