The fable of the bees: incentivizing robust revocation decision making in ad hoc networks

ABSTRACT

In this paper we present a new key-revocation scheme for ad hoc network environments with the following characteristics:

• Distributed: Our scheme does not require a permanently available central authority.

• Active: Our scheme incentivizes rational (selfish but honest) nodes to revoke malicious nodes.

• Robust: Our scheme is resilient against large numbers of colluding malicious nodes (30% of the network for a detection error rate of 15%).

• Detection error tolerant: Revocation decisions fundamentally rely on intrusion detection systems (IDS). Our scheme is active for any meaningful IDS (IDS error rate 0.5) and robust for an IDS error rate of up to 29%.

Several schemes in the literature have two of the above four characteristics (characteristic four is typically not explored). This work is the first to possess all four, making our revocation scheme well-suited for environments such as ad hoc networks, which are very dynamic, have significant bandwidth-constraints, and where many nodes must operate under the continual threat of compromise.

References

1. G. Arboit, C. Crépeau, C.R. Davis, and M. Maheswaran. A Localized Certificate Revocation Scheme for Mobile Ad Hoc Networks. Ad Hoc Networks, 6(1):17--31, 2008.
2. H. Brandt, C. Hauert, and K. Sigmund. Punishment And Reputation In Spatial Public Goods Games. In Proceedings of the Journal of Biological Science, 270(1519):1099--1104, 2003.
3. H. Chan, V.D. Gligor, A. Perrig, and G. Muralidharan. On the Distribution and Revocation of Cryptographic Keys in Sensor Networks. IEEE Transactions on Dependable and Secure Computing, 2(3):233--247, 2005.
4. H. Chan, A. Perrig, and D. Song. Random Key Predistribution Schemes for Sensor Networks. In Proceedings of the 2003 IEEE Symposium on Security and Privacy (S&P 2003), pages 197--213. IEEE Computer Society, May 2003.
5. J. Clulow and T. Moore. Suicide for the Common Good: A New Strategy for Credential Revocation in Self-organizing Systems. ACM SIGOPS Operating Systems Reviews, 40(3):18--21, 2006.
6. R. Dutta and S. Mukhopadhyay. Designing Scalable Self-healing Key Distribution Schemes with Revocation Capability. In Parallel and Distributed Processing and Applications, volume 4742 of LNCS, pages 419--430. Springer, 2007.
7. L. Eschenauer and V.D. Gligor. A Key-Management Scheme for Distributed Sensor Networks. In Proceedings of the 9th ACM conference on Computer and communications security (CCS 2002), pages 41--47. ACM Press, November 2002.
8. A. Geoffrey, J. Philip, and J. Reny. Advanced Microeconomic Theory. Addison Wesley, second edition, 2000.
9. K. Hoeper and G. Gong. Bootstrapping Security in Mobile Ad Hoc Networks Using Identity-Based Schemes with Key Revocation. Technical Report CACR 2006-04, Centre for Applied Cryptographic Research (CACR) at the University of Waterloo, Canada, 2006.
10. Y-C. Hu, A. Perrig, and D.B. Johnson. Packet Leashes: A Defense against Wormhole Attacks in Wireless Networks. In Proceedings of IEEE Infocomm 2003, pages 1976--1986, 2003.
11. ISO/IEC 11770-1:1996. Information technology - security techniques - key management - part 1: Framework, 1996.
12. T. Kanungo, D. M. Mount, N. S. Netanyahu, C. D. Piatko, R. Silverman, and A. Y. Wu. An Efficient k-Means Clustering Algorithm: Analysis and Implementation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 24(7):881--892, 2002.
13. D. Liu, P. Ning, and K. Sun. Efficient Self-healing Group Key Distribution with Revocation Capability. In Proceedings of the 10th ACM conference on Computer and communications security (CCS 2003), pages 231--240. ACM Press, 2003.
14. W. Liu. Securing Mobile Ad Hoc Networks with Certificateless Public Keys. IEEE Transactions on Dependable and Secure Computing, 3(4):386--399, 2006.
15. H. Luo, P. Zerfos, J. Kong, S. Lu, and L. Zhang. Self-Securing Ad Hoc Wireless Networks. In Proceedings of the Seventh International Symposium on Computers and Communications (ISCC'02). IEEE Computer Society, 2002.
16. J. Luo, J.-P. Hubaux, and P.T. Eugster. DICTATE: DIstributed CerTification Authority with probabilisTic frEshness for Ad Hoc Networks. IEEE Transactions on Dependable and Secure Computing, 2(4):311--323, 2005.
17. B. Mandeville. The Fable of the Bees or Private Vices, Publick Benefits. 2, 1724/1924. http://oll.libertyfund.org/Texts/LFBooks/Mandeville0162/FableOfBees/0014-02\_Bk.html..
18. B.J. Matt. Toward Hierarchical Identity-based Cryptography for Tactical Networks. In Proceedings of the 2004 Military Communications Conference (MILCOM 2003), pages 727--735. IEEE Computer Society, November 2004.
19. J. M. McCune, E. Shi, A. Perrig, and M. K. Reiter. Detection of Denial-of-Message Attacks on Sensor Network Broadcasts. In IEEE Security and Privacy Symposium, 2005.
20. T. Moore, M. Raya, J. Clulow, P. Papadimitratos, R. Anderson, and J-P. Hubaux. Fast Exclusion of Errant Devices From Vehicular Networks. In Proceedings of the 5th conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON 2008), pages 135--143, 2008.
21. B. Parno, A. Perrig, and V. Gligor. Distributed Detection of Node Replication Attacks in Sensor Networks. In Proceedings of the 2005 IEEE Symposium on Security and Privacy (S&P 2005), pages 49--63. IEEE Computer Society, 2005.
22. M. Raya, D. Jungels, P. Papadimitratos, I. Aas, and J.-P. Hubaux. Certificate Revocation in Vehicular Networks. Technical Report LCA Report 2006006, Laboratory for computer Communications and Applications (LCA) School of Computer and Communication Sciences, Switzerland, 2006.
23. M. Raya, M. Hossein Manshaei, M. F'elegyhazi, and J-P. Hubaux. Revocation Games In Ephemeral Networks. In Proceedings of the 15th ACM conference on Computer and Communications Security, pages 199--210. ACM, 2008.
24. R.L. Rivest. Can We Eliminate Certificate Revocations Lists? In Proceedings of the Second International Conference on Financial Cryptography (FC 1998), pages 178--183, London, UK, 1998. Springer-Verlag.
25. D. Roberts, G. Lock, and D.C. Verma. Holistan: A Futuristic Scenario for International Coalition Operations. In In Proceedings of Fourth International Conference on Knowledge Systems for Coalition Operations (KSCO 2007, 2007.
26. K. Sigmund, C. Hauert, and M.A. Nowak. Reward and Punishment. In Proceedings of the Journal of the National Academy of Science, 98:757--762, 2001.
27. R. Anderson T. Moore, J. Clulow and S. Nagaraja. New Strategies for Revocation in Ad-Hoc Networks. In Proceedings of the 4th European Workshop on Security and Privacy in Ad Hoc and Sensor Networks (ESAS 2007), pages 232--246. Springer, July 2007.
28. Y. Wang, B. Ramamurthy, and X. Zou. KeyRev: An Efficient Key Revocation Scheme for Wireless Sensor Networks. In Proceedings of the 2007 IEEE International Conference Communications (ICC 2007), pages 1260--1265. IEEE Computer Society, 2007.
29. D. J. White and C. Ed. White. Markov Decision Processes. Wiley, John&Sons, Incorporated, 1 edition, 1993.
30. S. Yi and R. Kravets. MOCA: Mobile Certificate Authority for Wireless Ad Hoc Networks. In The 2nd Annual PKI Research Workshop (PKI 03), 2003.
31. Y. Zhang, W. Liu, W. Lou, Y. Fang, and Y. Kwon. AC-PKI: Anonymous and Certificateless Public Key Infrastructure for Mobile Ad Hoc Networks. In Proceedings of the International Conference on Communications (ICC 2005), pages 3515--3519. IEEE Computer Society, May 2005.
32. L. Zhou and Z.J. Haas. Securing Ad Hoc Networks. IEEE Network, 13(6):24--30, 1999.

Index Terms

• Security and privacy

  • Network security