An efficient MAC scheme for secure network coding with probabilistic detection

Abstract

Network coding is vulnerable to pollution attacks, which prevent receivers from recovering the source message correctly. Most existing schemes against pollution attacks either bring significant redundancy to the original message or require a high computational complexity to verify received blocks. In this paper, we propose an efficient scheme against pollution attacks based on probabilistic key pre-distribution and homomorphic message authentication codes (MACs). In our scheme, each block is attached with a small number of MACs and each node can use these MACs to verify the integrity of the corresponding block with a high probability. Compared to previous schemes, our scheme still leverages a small number of keys to generate MACs for each block, but more than doubles the detection probability.Meanwhile, our scheme is able to efficiently restrict pollution propagation within a small number of hops. Experimental results show that our scheme is more efficient in verification than existing ones based on public-key cryptography.

Keywords

secure network coding / pollution attacks / homomorphic message authentication codes (MACs) / probabilistic detection

References

[1] Ahlswede R, Cai N, Li S R, Yeung R W. Network information flow. IEEE Transactions on Information Theory, 2000, 46(4): 1204-1216

[2] Koetter R, Médard M. An algebraic approach to network coding. IEEE/ACM Transactions on Networking, 2003, 11(5): 782-795

[3] Li S, R. Yeung RW, Cai N. Linear network coding. IEEE Transactions on Information Theory, 2003, 49(2): 371-381

[4] Ho T, Koetter R,Médard M, Karger D, Effros M. The benefits of coding over routing in a randomized setting. In: Proceedings of 2003 International Symposium on Information Theory. 2003

[5] Ho T, Leong B, Koetter R, Médard M, Effros M, Karger D. Byzantine modification detection in multicast networks using randomized network coding. In: Proceedings of 2004 International Symposium on Information Theory. 2004

[6] Jaggi S, Langberg M, Katti S, Ho T, Katabi D, Médard M. Resilient network coding in the presence of byzantine adversaries. In: Proceedings of the 26th IEEE International Conference on Computer Communications. 2007, 616-624

[7] Kehdi E, Li B. Null keys: limiting malicious at tacks via null space properties of network coding. In: Proceedings of the 28th IEEE International Conference on Computer Communications. 2009, 1224-1232

[8] Yeung, R W, Cai N. Network error correction, part I: basic concepts and upper bounds. IEEE Communications in Information and Systems, 2006, 6(1): 19-36

[9] Cai N, Yeung R W. Network error correction, part II: lower bounds. IEEE Communications in Information and Systems, 2006, 6(1): 37-54

[10] Silva D, Kschischang F, Koetter R. A rank-metric approach to error control in random network coding. In: Proceedings of 2007 IEEE Information Theory Workshop on Information Theory for Wireless Networks. 2007, 1-5

[11] Gkantsidis C, Rodriguez P. Cooperative security for network coding file distribution. In: Proceedings of the 25th IEEE International Conference on Computer Communications. 2006, 1-13

[12] Charles D, Jian K, Lauter K. Signatures for network coding. International Journal of Information and Coding Theory, 2009, 1(1): 3-14

[13] Zhao F, Kalker T, Médard M, Han K J. Signatures for content distribution with network coding. In: Proceedings of 2007 International Symposium on Information Theory. 2007, 556-560

[14] Yu Z, Wei Y, Ramkumar B, Guan Y. An efficient signature-based scheme for securing network coding against pollution attacks. In: Proceedings of the 27th IEEE International Conference on Computer Communications. 2008, 1409-1417

[15] Boneh D, Freeman D, Katz J, Waters B. Signing a linear subspace: signature schemes for network coding. In: Proceedings of the 12th International Conference on Practice and Theory in Public Key Cryptography. 2009, 68-87

[16] Jiang Y, Zhu H, Shi M, Shen X, Lin C. An efficient dynamic-identity based signature scheme for secure network coding. Computer Networks, 2010, 54(1): 28-40

[17] Yu Z, Wei Y, Ramkumar B, Guan Y. An efficient scheme for securing XOR network coding against pollution attacks. In: Proceedings of the 28th IEEE International Conference on Computer Communications. 2009, 406-414

[18] Agrawal S, Boneh D. Homomorphic MACs: MAC-based integrity for network coding. In: Proceeding of the 7th International Conference on Applied Cryptography and Network Security. 2009, 292-305

[19] Li Y, Yao H, Chen M, Jaggi S, Rosen A. RIPPLE authentication for network coding. In: Proceedings of the 29th IEEE International Conference on Computer Communications. 2010, 2258-2266

[20] Dong J, Curtmola R, Nita-Rotaru C. Practical defenses against pollution attacks in intra-flow network coding for wireless mesh networks. In: Proceedings of the 2nd ACM Conference on Wireless Network Security. 2009, 111-122

[21] Perrig A, Tygar J D, Song D, Canetti R. Efficient authentication and signing of multicast streams over lossy channels. In: Proceedings of 2000 IEEE Symposium on Security and Privacy. 2000

[22] Eschenauer L, Gilgor V D. A key-management scheme for distributed sensor networks. In: Proceedings of the 9th ACM Conference on Computer and Communications Security. 2002, 41-47

[23] Shamus Software Ltd. MIRACL, Multiprecision Integer and Rational Arithmetic C/C++ Library

RIGHTS & PERMISSIONS

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg