Top

Distributed Computing

Published in:

24-08-2016

Who are you? Secure identities in single hop ad hoc networks

Authors: Seth Gilbert, Calvin Newport, Chaodong Zheng

Published in: Distributed Computing | Issue 2/2017

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

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 can effectively thwart sybil attacks in single hop multi-channel wireless ad hoc networks using radio resource testing strategies. We present and analyze new anti-sybil algorithms for establishing trusted identities, specifically, 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 provide 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 network size estimation.

previous article Reliable broadcast with respect to topology knowledge

next article The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

O(t) sybil identities is clearly asymptotically optimal as the malicious nodes could behave honestly.

The consensus protocol maintains its safety properties with high probability, but not with probability one.

Currently, most existing radio transceivers implement half-duplex communication. However, researchers have been studying how to build full-duplex wireless transceivers (see, e.g., [7, 23]).

Here we assume that each device owned by the adversary can access one channel per time slot. Two points commonly deployed to support this model are: (1) for coordination protocols the slot length can be quite short (as we are not trying to send high-throughput traffic), and therefore, the channel switching time for the adversary does not allow it to switch to multiple channels within a given slot; and (2) the ability to participate on multiple channels can be captured in t; that is, if there are 2 malicious devices, but each is able to usefully switch between 3 channels per slot, we can model this conservatively by assuming \(t=6\). On the other hand, however, it is plausible that the adversary can listen for part of a time slot, before deciding whether to broadcast or jam, or do nothing. In this paper, for simplicity, we do not allow such behavior; nevertheless, it has no material effect on the algorithms presented, as they can in fact tolerate this stronger type of adversary.

Alchieri, E.A., Bessani, A., da Silva Fraga, J., Greve, F.: Byzantine consensus with unknown participants. In: Baker, T.P., Bui, A., Tixeuil, S. (eds.) Principles of Distributed Systems, Volume 5401 of Lecture Notes in Computer Science, pp. 22–40. Springer, Berlin (2008)

Aspnes, J., Jackson, C., Krishnamurthy, A.: Exposing computationally-challenged byzantine impostors. Technical report, Yale University Department of Computer Science (2005)

Attiya, H., Welch, J.: Distributed Computing: Fundamentals, Simulations, and Advanced Topics. Wiley, London (2004)CrossRefMATH

Awerbuch, B., Richa, A., Scheideler, C.: A jamming-resistant mac protocol for single-hop wireless networks. In: Proceedings of the 27th ACM Symposium on Principles of distributed computing, pp. 45–54. ACM (2008)

Bluetooth Consortium: Bluetooth Specification Version 2, 1 (July 2007)

Chockler, G., Demirbas, M., Gilbert, S., Lynch, N., Newport, C., Nolte, T.: Consensus and collision detectors in radio networks. Distrib. Comput. 21(1), 55–84 (2008)CrossRefMATH

Choi, J.I., Jain, M., Srinivasan, K., Levis, P., Katti, S.: Achieving single channel, full duplex wireless communication. In: Proceedings of the Sixteenth Annual International Conference on Mobile Computing and Networking, MobiCom ’10, pp. 1–12. ACM (2010)

Delporte-Gallet, C., Fauconnier, H., Guerraoui, R., Kermarrec, A.-M., Ruppert, E., Tran-The, H.: Byzantine agreement with homonyms. In: Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, pp. 21–30. ACM, New York (2011)

Delporte-Gallet, C., Fauconnier, H., Tielmann, A.: Fault-tolerant consensus in unknown and anonymous networks. In: 29th IEEE International Conference on Distributed Computing Systems, pp. 368–375 (2009)

10.

Demirbas, M., Song, Y.: An rssi-based scheme for sybil attack detection in wireless sensor networks. In: Proceedings of the 2006 International Symposium on on World of Wireless, Mobile and Multimedia Networks, pp. 564–570. IEEE Computer Society, Washington, DC (2006)

11.

Dolev, S., Gilbert, S., Guerraoui, R., Newport, C.: Secure communication over radio channels. In: Proceedings of the 27th ACM Symposium on Principles of Distributed Computing, PODC ’08, pp. 105–114. ACM (2008)

12.

Dolev, S., Gilbert, S., Khabbazian, M., Newport, C.: Leveraging channel diversity to gain efficiency and robustness for wireless broadcast. In: Peleg, D. (ed.) Distributed Computing. Lecture Notes in Computer Science, vol. 6950, pp. 252–267. Springer, Berlin (2011)

13.

Douceur, J.R.: The sybil attack. In: Druschel, P., Kaashoek, F., Rowstron, A. (eds.) Peer-to-Peer Systems. Lecture Notes in Computer Science, vol. 2429, pp. 251–260. Springer, Berlin (2002)

14.

Dubhash, D.P., Panconesi, A.: Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, Cambridge (2009)CrossRef

15.

Dwork, C., Naor, M.: Pricing via processing or combatting junk mail. In: Brickell, E.F. (ed.) Advances in Cryptology 92. Lecture Notes in Computer Science, vol. 740, pp. 139–147. Springer, Berlin (1993)

16.

Fusco, E., Pelc, A.: Communication complexity of consensus in anonymous message passing systems. In: Fernandez, A., Lipari, G., Roy, M. (eds.) Principles of Distributed Systems, volume 7109 of Lecture Notes in Computer Science, pp. 191–206. Springer, Berlin (2011)

17.

Gilbert, S., Guerraoui, R., Kowalski, D., Newport, C.: Interference-resilient information exchange. In: IEEE INFOCOM 2009, pp. 2249–2257 (2009)

18.

Gilbert, S.L., Zheng, C.: Sybilcast: Broadcast on the open airwaves. In: Proceedings of the 25th Annual ACM Symposium on Parallelism in Algorithms and Architectures, pp. 130–139, ACM, New York (2013)

19.

Golebiewski, Z., Klonowski, M., Koza, M., Kutylowski, M.: Towards fair leader election in wireless networks. In: Ruiz, P., Garcia-Luna-Aceves, J. (eds.) Ad-Hoc. Mobile and Wireless Networks, volume 5793 of Lecture Notes in Computer Science, pp. 166–179. Springer, Berlin (2009)

20.

Goodwins., R.: Next-generation wireless networks: from gigabit WiFi to white space. http://www.zdnet.com/article/next-generation-wireless-networks-from-gigabit-wi-fi-to-white-space (2013)

21.

Hoffman, K., Zage, D., Nita-Rotaru, C.: A survey of attack and defense techniques for reputation systems. ACM Comput. Surv. 42(1), 1:1–1:31 (2009)CrossRef

22.

IEEE: IEEE standard for information technology–local and metropolitan area networks–specific requirements–part 11: wireless lan medium access control (MAC) and physical layer (PHY) specifications amendment 5: Enhancements for higher throughput. IEEE Std 802.11n-2009 (Amendment to IEEE Std 802.11-2007 as amended by IEEE Std 802.11k-2008, IEEE Std 802.11r-2008, IEEE Std 802.11y-2008, and IEEE Std 802.11w-2009), pp. 1–565 (2009)

23.

Jain, M., Choi, J.I., Kim, T., Bharadia, D., Seth, S., Srinivasan, K., Levis, P., Katti, S., Sinha, P.: Practical, real-time, full duplex wireless. In: Proceedings of the 17th Annual International Conference on Mobile Computing and Networking, MobiCom ’11, pp. 301–312. ACM (2011)

24.

Klonowski, M., Koza, M.: Countermeasures against sybil attacks in wsn based on proofs-of-work. In: Proceedings of the 6th ACM Conference on Security and Privacy in Wireless and Mobile Networks, pp. 179–184. ACM, New York (2013)

25.

Klonowski, M., Koza, M., Kutyowski, M.: Repelling sybil-type attacks in wireless ad hoc systems. In: Steinfeld, R., Hawkes, P. (eds.) Information Security and Privacy. Lecture Notes in Computer Science, vol. 6168, pp. 391–402. Springer, Berlin (2010)

26.

Luby, M.G.: Pseudorandomness and Cryptographic Applications. Princeton University Press, Princeton (1996)MATH

27.

Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, Cambridge (2005)CrossRefMATH

28.

Mónica, D., Leitão, J., Rodrigues, L., Ribeiro, C.: On the use of radio resource tests in wireless ad-hoc networks. In: Proceedings of the 3rd Workshop on Recent Advances on Intrusion-Tolerant Systems, pp. F21–F26 (2009)

29.

Mónica, D., Leitão, J., Rodrigues, L., Ribeiro, C.: Observable non-sybil quorums construction in one-hop wireless ad hoc networks. In: 2010 IEEE/IFIP International Conference on Dependable Systems and Networks, pp. 31–40 (2010)

30.

Navda, V., Bohra, A., Ganguly, S., Rubenstein, D.: Using channel hopping to increase 802.11 resilience to jamming attacks. In: 26th IEEE International Conference on Computer Communications, pp. 2526–2530 (2007)

31.

Newsome, J., Shi, E., Song, D., Perrig, A.: The sybil attack in sensor networks: analysis and defenses. In: Proceedings of the 3rd International Symposium on Information Processing in Sensor Networks, pp. 259–268. ACM, New York (2004)

32.

Piro, C., Shields, C., Levine, B.: Detecting the sybil attack in mobile ad hoc networks. In: Securecomm and Workshops, pp. 1–11 (2006)

33.

Richa, A., Scheideler, C., Schmid, S., Zhang, J.: A jamming-resistant mac protocol for multi-hop wireless networks. In: Proceedings of the 24th International Conference on Distributed Computing, pp. 179–193. Springer (2010)

34.

Richa, A., Scheideler, C., Schmid, S., Zhang, J.: Competitive and fair medium access despite reactive jamming. In: 31st International Conference on Distributed Computing Systems, pp. 507–516 (2011)

35.

Srikanth, T., Toueg, S.: Simulating authenticated broadcasts to derive simple fault-tolerant algorithms. Distrib. Comput. 2(2), 80–94 (1987)CrossRef

36.

Strasser, M., Pöpper, C., Capkun, S., Cagalj, M.: Jamming-resistant key establishment using uncoordinated frequency hopping. In: Proceedings of the IEEE Symposium on Security and Privacy, pp. 64–78 (2008)

37.

The WhiteSpace Alliance. http://www.whitespacealliance.org/InTheNews.html (2015)

38.

Yu, H., Gibbons, P., Kaminsky, M., Xiao, F.: Sybillimit: A near-optimal social network defense against sybil attacks. In: 2008 IEEE Symposium on Security and Privacy, pp. 3–17 (2008)

39.

Yu, H., Kaminsky, M., Gibbons, P., Flaxman, A.: Sybilguard: defending against sybil attacks via social networks. IEEE/ACM Trans. Netw. 16(3), 576–589 (2008)CrossRef

40.

Zheng, C.: Securing multi-channel wireless networks against malicious behavior. PhD thesis (2015)

Title: Who are you? Secure identities in single hop ad hoc networks
Authors: Seth Gilbert
Calvin Newport
Chaodong Zheng
Publication date: 24-08-2016
Publisher: Springer Berlin Heidelberg
Published in: Distributed Computing / Issue 2/2017
Print ISSN: 0178-2770
Electronic ISSN: 1432-0452
DOI: https://doi.org/10.1007/s00446-016-0280-0

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner