Hop chains: Secure routing and the establishment of distinct identities. (English) Zbl 1157.68011

Bazzi, Rida A.; Choi, Young-Ri; Gouda, Mohamed G.

Theor. Comput. Sci. 410, No. 6-7, 467-480 (2009).

Summary: We present a secure routing protocol that is immune to Sybil attacks and that can tolerate collusion of Byzantine routers. It can tolerate either initial collusion of Byzantine routers or runtime collusion of non-adjacent Byzantine routers, both in the absence of runtime collusion between adjacent routers. For these settings, the calculated distance from a destination to a node is not smaller than the actual shortest distance from the destination to the node. The protocol can also simultaneously tolerate initial collusion of Byzantine routers and runtime collusion of adjacent Byzantine routers but in the absence of runtime collusion between non-adjacent routers. For this setting, it guarantees a bound on the difference between the calculated distance and the actual shortest distance. The bound depends on the number of Byzantine routers on a path. The protocol makes very weak timing assumptions and requires synchronization only between neighbors or second neighbors. We propose to use this protocol for secure localization of routers using hop-count distances, which can be then used as a proof of identity of nodes.

MSC:

68M10	Network design and communication in computer systems
68M12	Network protocols

Keywords:

computer networks; Sybil attack; routing; security; Byzantine

Software:

S-RIP

References:

[2]	Bazzi, R. A.; Konjevod, G., On the establishment of distinct identities in overlay networks, Distributed Computing, 19, 4, 267-287 (2007) · Zbl 1266.68045
[5]	Awerbuch, B.; Holmer, D.; Nita-Rotaru, C.; Rubens, H., An on-demand secure routing protocol resilient to Byzantine failures, (Proceedings of the 3rd ACM Workshop on Wireless Security. Proceedings of the 3rd ACM Workshop on Wireless Security, WiSE’02 (2002), ACM Press), 21-30
[6]	Fonseca, R.; Ratnasamy, S.; Zhao, J.; Ee, C. T.; Culler, D.; Shenker, S.; Stoica, I., Beacon vector routing: Scalable point-to-point routing in wireless sensornets, (Proceedings of the 2nd Conference on Symposium on Networked Systems Design & Implementation. Proceedings of the 2nd Conference on Symposium on Networked Systems Design & Implementation, NSDI’05 (2005), USENIX Association: USENIX Association Berkeley, CA, USA), 329-342
[7]	Mittal, V.; Vigna, G., Sensor-based intrusion detection for intra-domain distance-vector routing, (Proceedings of the 9th ACM conference on Computer and Communications Security. Proceedings of the 9th ACM conference on Computer and Communications Security, CCS’02 (2002), ACM Press), 127-137