A coding-theoretic approach for efficient message verification over insecure channels

ABSTRACT

We address the problem of allowing authorized users, who have yet to establish a secret key, to securely and efficiently exchange key establishment messages over an insecure channel in the presence of jamming and message insertion attacks. This problem was first introduced by Strasser, Pöpper, Čapkun, and Čagalj in their recent work, leaving joint consideration of security and efficiency as an open problem. In this paper, we present three approaches based on coding theory which reduce the overall time required to verify the packets and reconstruct the original message in the presence of jamming and malicious insertion. We first present the Hashcluster scheme which reduces the total overhead included in the short packets. We next present the Merkleleaf scheme which uses erasure coding to reduce the average number of packet receptions required to reconstruct the message. We then present the Witnesscode scheme which uses one-way accumulators to individually verify packets and reduce redundancy. We demonstrate through analysis and simulation that our candidate protocols can significantly decrease the amount of time required for key establishment in comparison to existing approaches without degrading the guaranteed level of security.

REFERENCES

• 1: Ross J. Anderson, Security Engineering: A Guide to Building Dependable Distributed Systems, John Wiley & Sons, Inc., New York, NY, 2001
• 2: N. Baric and B. Pfitzmann. Collision-free accumulators and fail-stop signature schemes without trees. Advances in Cryptology -- EUROCRYPT '97, pages 480--494, 1997.
• 3: Josh Benaloh , Michael de Mare, One-way accumulators: a decentralized alternative to digital signatures, Workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.274-285, January 1994, Lofthus, Norway
• 4: L. Buttyán, L. Czap, and I. Vajda. Securing coding based distributed storage in wireless sensor networks. In IEEE Workshop on Wireless and Sensor Network Security (WSNS), Atlanta, GA, USA, Sept. 2008.
• 5: John W. Byers , Michael Luby , Michael Mitzenmacher , Ashutosh Rege, A digital fountain approach to reliable distribution of bulk data, ACM SIGCOMM Computer Communication Review, v.28 n.4, p.56-67, Oct. 1998
• 6: R. Durrett. Essentials of Stochastic Processes. Springer-Verlag, Inc., 1999.
• 7: P. Golle and N. Modadugu. Authenticating streamed data in the presence of random packet loss. In Proc. of the Symposium on Network and Distributed Systems Security (NDSS 2001), pages 13--22, Feb. 2001.
• 8: V. Gupta, S. Krishnamurthy, and M. Faloutsos. Denial of service attacks at the mac layer in wireless ad hoc networks. Military Communications Conference (MILCOM 2002), 2:1118--1123, 2002.
• 9: M. Hirt and K. Sako. Efficient receipt-free voting based on homomorphic encryption. Advances in Cryptology -- EUROCRYPT 2000, pages 539--556, 2000.
• 10: C. Karlof, N. Sastry, Y. Li, A. Perrig, and J. D. Tygar. Distillation codes and applications to dos resistant multicast authenication. In The 11th Annual Network and Distributed System Security Symposium (NDSS 2004), San Diego, CA, USA, Feb. 2004.
• 11: J. Liang, R. Kumar, Y. Xi, and K. W. Ross. Pollution in p2p file sharing systems. Proc. IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2005), 2, 2005.
• 12: 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]
• 13: W.-T. Lin and K.-B. Yu. Adaptive beamforming for wideband jamming cancellation. IEEE National Radar Conference, pages 82--87, 1997.
• 14: M. Luby. LT codes. In Proc. of the 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS '02), pages 150--159, May 1997.
• 15: P. Maymounkov. Online codes. NYU, Tech. Rep. 2002--833, Nov. 2002.
• 16: R. Merkle. Protocols for public key cryptosystems. In Proc. 1980 IEEE Symposium on Security and Privacy, pages 150--159, Apr. 1980.
• 17: L. Nguyen. Accumulators from bilinear pairings and applications. Topics in Cryptography -- CT--RSA 2005, pages 275--292, 2005.
• 18: R. A. Poisel. Modern Communication Jamming Principles and Techniques. Artech House, 2004.
• 19: C. Popper, M. Strasser, and S. Capkun. Jamming-resistant broadcast communication without shared keys. Technical Report 609, ETH Zurich, Sept. 2008.
• 20: Theodore Rappaport, Wireless Communications: Principles and Practice, Prentice Hall PTR, Upper Saddle River, NJ, 2001
• 21: Ron Roth, Introduction to Coding Theory, Cambridge University Press, New York, NY, 2006
• 22: Amin Shokrollahi, Raptor codes, IEEE/ACM Transactions on Networking (TON), v.14 n.SI, p.2551-2567, June 2006 [doi>10.1109/TIT.2006.874390]
• 23: 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]
• 24: Digital Signatures for Flows and Multicasts, Proceedings of the Sixth International Conference on Network Protocols, p.198, October 13-16, 1998
• 25: Anthony D. Wood , John A. Stankovic, Denial of Service in Sensor Networks, Computer, v.35 n.10, p.54-62, October 2002 [doi>10.1109/MC.2002.1039518]
• 26: W. Xu, K. Ma, W. Trappe, and Y. Zhang. Jamming sensor networks: Attack and defense strategies. IEEE Network, 20(3):41--47, May/June 2006.
• 27: Wenyuan Xu , Wade Trappe , Yanyong Zhang , Timothy Wood, The feasibility of launching and detecting jamming attacks in wireless networks, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA [doi>10.1145/1062689.1062697]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)

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

General Terms:
Algorithms, Performance, Reliability, Security

Keywords:
insecure channels, insertion attacks, jamming, message verification