Secure communication over radio channels

ABSTRACT

We study the problem of secure communication in a multi-channel, single-hop radio network with a malicious adversary that can cause collisions and spoof messages. We assume no pre-shared secrets or trusted-third-party infrastructure. The main contribution of this paper is f-AME: a randomized (f)ast-(A)uthenticated (M)essage (E)xchange protocol that enables nodes to exchange messages in a reliable and authenticated manner. It runs in O(|E|t² log n) time and has optimal resilience to disruption, where E is the set of pairs of nodes that need to swap messages, n is the total number of nodes, C the number of channels, and t < C the number of channels on which the adversary can participate in each round. We show how to use f-AME to establish a shared secret group key, which can be used to implement a secure, reliable and authenticated long-lived communication service. The resulting service requires O(nt³ log n) rounds for the setup phase, and O(t log n) rounds for an arbitrary pair to communicate. By contrast, existing solutions rely on pre-shared secrets, trusted third-party infrastructure, and/or the assumption that all interference is non-malicious.

REFERENCES

• 1: Noga Alon , Amotz Bar-Noy , Nathan Linial , David Peleg, A lower bound for radio broadcast, Journal of Computer and System Sciences, v.43 n.2, p.290-298, Oct. 1991 [doi>10.1016/0022-0000(91)90015-W]
• 2: Reuven Bar-Yehuda , Oded Goldreich , Alon Itai, On the time-complexity of broadcast in multi-hop radio networks: an exponential gap between determinism and randomization, Journal of Computer and System Sciences, v.45 n.1, p.104-126, Aug. 1992 [doi>10.1016/0022-0000(92)90042-H]
• 3: Reuven Bar-Yehuda , Amos Israeli , Alon Itai, Multiple communication im multihop radio networks, SIAM Journal on Computing, v.22 n.4, p.875-887, Aug. 1993 [doi>10.1137/0222055]
• 4: Vartika Bhandari , Nitin H. Vaidya, On reliable broadcast in a radio network, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073841]
• 5: Bluetooth Consortium. Bluetooth Specification Version 2.1, July 2007.
• 6: M. Cagalj, S. Capkun, and J-P. Hubaux. Key agreement in peer-to-peer wireless networks. Proceedings of the IEEE (Special Issue on Cryptography and Security), 94(2), February 2006.
• 7: Bogdan S. Chlebus , Leszek Gąsieniec , Andrzej Lingas , Aris T. Pagourtzis, Oblivious gossiping in ad-hoc radio networks, Proceedings of the 5th international workshop on Discrete algorithms and methods for mobile computing and communications, p.44-51, July 2001, Rome, Italy [doi>10.1145/381448.381454]
• 8: Bogdan S. Chlebus , Dariusz R. Kowalski, Robust gossiping with an application to consensus, Journal of Computer and System Sciences, v.72 n.8, p.1262-1281, December, 2006 [doi>10.1016/j.jcss.2006.08.001]
• 9: Andrea E. F. Clementi , Angelo Monti , Riccardo Silvestri, Optimal F-Reliable Protocols for the Do-All Problem on Single-Hop Wireless Networks, Proceedings of the 13th International Symposium on Algorithms and Computation, p.320-331, November 21-23, 2002
• 10: Andrea E. F. Clementi , Angelo Monti , Riccardo Silvestri, Round Robin is optimal for fault-tolerant broadcasting on wireless networks, Journal of Parallel and Distributed Computing, v.64 n.1, p.89-96, January 2004 [doi>10.1016/j.jpdc.2003.09.002]
• 11: Artur Czumaj , Wojciech Rytter, Broadcasting Algorithms in Radio Networks with Unknown Topology, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.492, October 11-14, 2003
• 12: W. Diffe and M. Hellman. New directions in cyptography. Transactions on Information Theory, November 1976.
• 13: S. Dolev, S. Gilbert, R. Guerraoui, and C. Newport. Gossiping in a multi-channel radio network: An oblivious approach to coping with malicious interference. In the Proceedings of the International Symposium on Distributed Computing, September 2007.
• 14: S. Gilbert, R. Guerraoui, and C. Newport. Of malicious motes and suspicious sensors: On the efficiency of malicious interference in wireless networks. In the Proceedings of the International Conference on Principles of Distributed Systems, December 2006.
• 15: János Komlós , Albert G. Greenberg, Correction to "An asymptotically nonadaptive algorithm for conflict resolution i, IEEE Transactions on Information Theory, v.31 n.6, p.841-841, Nov. 1985
• 16: Chiu-Yuen Koo, Broadcast in radio networks tolerating byzantine adversarial behavior, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011807]
• 17: Chiu-Yuen Koo , Vartika Bhandari , Jonathan Katz , Nitin H. Vaidya, Reliable broadcast in radio networks: the bounded collision case, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146420]
• 18: Dariusz R. Kowalski , Andrzej Pelc, Time of Deterministic Broadcasting in Radio Networks with Local Knowledge, SIAM Journal on Computing, v.33 n.4, p.870-891, 2004 [doi>10.1137/S0097539702419339]
• 19: Evangelos Kranakis , Danny Krizanc , Andrzej Pelc, Fault-tolerant broadcasting in radio networks, Journal of Algorithms, v.39 n.1, p.47-67, April 2001 [doi>10.1006/jagm.2000.1147]
• 20: Eyal Kushilevitz , Yishay Mansour, An Ω(D log(N/D)) lower bound for broadcast in radio networks, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.65-74, August 15-18, 1993, Ithaca, New York, United States [doi>10.1145/164051.164059]
• 21: Andrzej Pelc , David Peleg, Feasibility and complexity of broadcasting with random transmission failures, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073879]
• 22: Frank Stajano , Ross J. Anderson, The Resurrecting Duckling: Security Issues for Ad-hoc Wireless Networks, Proceedings of the 7th International Workshop on Security Protocols, p.172-194, April 19-21, 1999
• 23: Dan E Willard, Log-logarithmic selection resolution protocols in a multiple access channel, SIAM Journal on Computing, v.15 n.2, p.468-477, May 1986 [doi>10.1137/0215032]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

General Terms:
Algorithms, Security

Keywords:
malicious (byzantine) interference, randomized algorithms, wireless radio networks