Zero pre-shared secret key establishment in the presence of jammers

ABSTRACT

We consider the problem of key establishment over a wireless radio channel in the presence of a communication jammer, initially introduced in [13]. The communicating nodes are not assumed to pre-share any secret. The established key can later be used by a conventional spread-spectrum communication system. We introduce new communication concepts called intractable forward-decoding and efficient backward-decoding. Decoding under our mechanism requires at most twice the computation cost of the conventional SS decoding and one packet worth of signal storage. We introduce techniques that apply a key schedule to packet spreading and develop a provably optimal key schedule to minimize the bit-despreading cost. We also use efficient FFT-based algorithms for packet detection. We evaluate our techniques and show that they are efficient both in terms of resiliency against jammers and computation. Finally, our technique has additional features such as the inability to detect packet transmission until the last few bits are being transmitted, and transmissions being destination-specific. To the best of our knowledge, this is the first solution that is optimal in terms of communication energy cost with very little storage and computation overhead.

REFERENCES

• 1: Baruch Awerbuch , Andrea Richa , Christian Scheideler, A jamming-resistant MAC protocol for single-hop wireless networks, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada [doi>10.1145/1400751.1400759]
• 2: E. Bayraktaroglu, C. King, X. Liu, G. Noubir, R. Rajaraman, and B. Thapa. On the performance of ieee 802.11 under jamming. In Infocom, 2008.
• 3: Michael A. Bender , Martin Farach-Colton , Simai He , Bradley C. Kuszmaul , Charles E. Leiserson, Adversarial contention resolution for simple channels, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA [doi>10.1145/1073970.1074023]
• 4: Timothy X Brown , Jesse E. James , Amita Sethi, Jamming and sensing of encrypted wireless ad hoc networks, Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing, May 22-25, 2006, Florence, Italy [doi>10.1145/1132905.1132919]
• 5: A. Chan, X. Liu, G. Noubir, and B. Thapa. Control channel jamming: Resilience and identification of traitors. In IEEE ISIT, 2007.
• 6: Jerry T. Chiang , Yih-Chun Hu, Cross-layer jamming detection and mitigation in wireless broadcast networks, Proceedings of the 13th annual ACM international conference on Mobile computing and networking, September 09-14, 2007, Montréal, Québec, Canada [doi>10.1145/1287853.1287901]
• 7: S. Gilbert, R. Guerraoui, and C. Newport. Of malicious motes and suspicious sensors: On the efficiency of malicious interference in wireless networks. In OPODIS, 2006.
• 8: B. Gupta, S. Gupta, and S. Chang. Performance analysis of elliptic curve cryptography for ssl. In MobiCom, 2002.
• 9: M. Li, I. Koutsopoulos, and R. Poovendran. Optimal jamming attacks and network defense policies in wireless sensor networks. In INFOCOM, 2007.
• 10: Guolong Lin , Guevara Noubir, On link layer denial of service in data wireless LANs: Research Articles, Wireless Communications & Mobile Computing, v.5 n.3, p.273-284, May 2005 [doi>10.1002/wcm.v5:3]
• 11: Kasper Bonne Rasmussen , Srdjan Capkun , Mario Cagalj, SecNav: secure broadcast localization and time synchronization in wireless networks, Proceedings of the 13th annual ACM international conference on Mobile computing and networking, September 09-14, 2007, Montréal, Québec, Canada [doi>10.1145/1287853.1287892]
• 12: Marvin K. Simon , Jim K. Omura , Robert A. Scholtz , Barry K. Levitt, Spread spectrum communications; vols. 1-3, Computer Science Press, Inc., New York, NY, 1985
• 13: Mario Strasser , Christina Pöpper , Srdjan Capkun , Mario Cagalj, Jamming-resistant Key Establishment using Uncoordinated Frequency Hopping, Proceedings of the 2008 IEEE Symposium on Security and Privacy, p.64-78, May 18-21, 2008 [doi>10.1109/SP.2008.9]
• 14: P. Tague, D. Slater, G. Noubir, and R. Poovendran. Linear programming models for jamming attacks on network traffic flows. In WiOpt, 2008.
• 15: http://www.cv.nrao.edu/pdemores/gpu/. Gpu benchmarking.
• 16: W. Xu, K. Ma, W. Trappe, and Y. Zhang. Jamming sensor networks: attack and defense strategies. In IEEE Network, 2006.

INDEX TERMS

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

General Terms:
Algorithms, Design, Security

Keywords:
anti-jamming, spread spectrum, zero pre-shared secret