Lightweight, pollution-attack resistant multicast authentication scheme

ABSTRACT

Authentication is an important security measure for multicast applications, providing receivers with confidence that the packets they receive are valid. Simply signing every multicast packet with a digital signature incurs high overhead; therefore, a scheme such as signature amortization helps reduce this overhead. To tolerate packet loss, erasure codes are employed to enhance signature amortization. However, the use of erasure codes introduces pollution attack, an attack in which the adversary injects packets to disrupt the erasure decoding procedure and consequently denies the authentication service to the receiver. Unfortunately, current solutions to pollution attack are computationally intensive and inefficient. To cope with this problem, we propose a new lightweight, pollution-attack resistant multicast authentication scheme (PARM), which generates evidence that receivers can validate on a fast, per-packet basis. This approach effectively resists pollution attacks and has better performance than previously proposed solutions.

REFERENCES

• 1: Chris Karlof, Naveen Sastry, Yaping Li, Adrian Perrig, and J.D. Tygar, "Distillation Codes and Applications to DoS Resistant Multicast Authentication", In Proceedings of the 11th Annual Network and Distributed System Security Symposium (NDSS'04), February 2004.
• 2: Jung Min Park , Edwin K. P. Chong , Howard Jay Siegel, Efficient multicast stream authentication using erasure codes, ACM Transactions on Information and System Security (TISSEC), v.6 n.2, p.258-285, May 2003 [doi>10.1145/762476.762480]
• 3: Jung Min Park , Edwin K. P. Chong , Howard Jay Siegel, Efficient Multicast Packet Authentication Using Signature Amortization, Proceedings of the 2002 IEEE Symposium on Security and Privacy, p.227, May 12-15, 2002
• 4: Adrian Perrig, The BiBa one-time signature and broadcast authentication protocol, Proceedings of the 8th ACM conference on Computer and Communications Security, November 05-08, 2001, Philadelphia, PA, USA [doi>10.1145/501983.501988]
• 5: Leonid Reyzin , Natan Reyzin, Better than BiBa: Short One-Time Signatures with Fast Signing and Verifying, Proceedings of the 7th Australian Conference on Information Security and Privacy, p.144-153, July 03-05, 2002
• 6: R. Merkle. Protocols for public key cryptosystems. In Proceedings of the IEEE Symposium on Research in Security and Privacy, pages 122--134, Apr. 1980.
• 7: Michael Luby, LT Codes, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.271, November 16-19, 2002
• 8: M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi, and D. A. Spielman. Efficient erasure correcting codes. IEEE Transactions on Information Theory, 47(2):569--584, February 2001.
• 9: Michael O. Rabin, Efficient dispersal of information for security, load balancing, and fault tolerance, Journal of the ACM (JACM), v.36 n.2, p.335-348, April 1989 [doi>10.1145/62044.62050]
• 10: Jung Min Park , Edwin K. P. Chong , Howard Jay Siegel, Efficient Multicast Packet Authentication Using Signature Amortization, Proceedings of the 2002 IEEE Symposium on Security and Privacy, p.227, May 12-15, 2002
• 11: Jung Min Park , Edwin K. P. Chong , Howard Jay Siegel, Efficient multicast stream authentication using erasure codes, ACM Transactions on Information and System Security (TISSEC), v.6 n.2, p.258-285, May 2003 [doi>10.1145/762476.762480]
• 12: I. Reed and G. Solomon. Polynomial codes over certain finite fields. Journal of the Society for Industrial and Applied Mathematics, 8(2):300--304, 1960.
• 13: Hugo Krawczyk, Distributed fingerprints and secure information dispersal, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.207-218, August 15-18, 1993, Ithaca, New York, United States [doi>10.1145/164051.164075]
• 14: R. Merkle. Protocols for public key cryptosystems. In Proceedings of the IEEE Symposium on Research in Security and Privacy, pages 122--134, Apr. 1980.
• 15: P. Golle and N. Modadugu. Authenticating streamed data in the presence of random packet loss. In Proceedings of the Symposium on Network and Distributed Systems Security (NDSS 2001), pages 13--22. Internet Society, Feb. 2001.
• 16: Sara Miner , Jessica Staddon, Graph-Based Authentication of Digital Streams, Proceedings of the 2001 IEEE Symposium on Security and Privacy, p.232, May 14-16, 2001
• 17: A. Pannetrat and R. Molva. Efficient multicast packet authentication. In Proceedings of the Symposium on Network and Distributed System Security Symposium (NDSS 2003). Internet Society, Feb. 2003.
• 18: Adrian Perrig , J. D. Tygar , Dawn Song , Ran Canetti, Efficient Authentication and Signing of Multicast Streams over Lossy Channels, Proceedings of the 2000 IEEE Symposium on Security and Privacy, p.56, May 14-17, 2000
• 19: Dawn Song , J. D. Tygar , David Zuckerman, Expander Graphs for Digital Stream Authentication and Robust Overlay Networks, Proceedings of the 2002 IEEE Symposium on Security and Privacy, p.258, May 12-15, 2002
• 20: Digital Signatures for Flows and Multicasts, Proceedings of the Sixth International Conference on Network Protocols, p.198, October 13-16, 1998
• 21: E. Ayanoglu, I. Chih-Lin, R.D. Gitlin, J.E. Mazo. Diversity Coding for Transparent Self-Healing and Fault-Tolerant Communication Networks. IEEE Transactions on Communications, 41(11), 1993.
• 22: Rosario Gennaro , Pankaj Rohatgi, How to Sign Digital Streams, Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.180-197, August 17-21, 1997

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)
          Subjects: Authentication

Additional Classification:
  E. Data
  E.3 DATA ENCRYPTION
  E.4 CODING AND INFORMATION THEORY

General Terms:
Algorithms, Security

Keywords:
authentication, erasure code, multicast, pollution-attack, signature amortization