Sybil attacks occur when malicious users create multiple fake identities to gain an advantage over honest users. Wireless ad hoc networks are particularly vulnerable to these attacks because the participants are not known in advance, and they use an open and shared communication medium. In this paper, we develop algorithms that thwart sybil attacks in multi-channel wireless ad hoc networks using radio resource testing strate- gies. In particular, we describe and analyze new anti-sybil algorithms that guarantee, with high probability, that each honest device accepts a set of trusted and unforgeable identities that include all other honest devices and a bounded number of fake (sybil) identities. The proposed algorithms pro- vide trade-offs between time complexity and sybil bounds. We also note that these algorithms solve, as subroutines, two problems of independent interest in this anonymous wireless setting: Byzantine consensus and net- work size estimation.
['Seth Gilbert', 'Calvin C. Newport', 'Chaodong Zheng']
Who Are You? Secure Identities in Ad Hoc Networks