自愈式密钥分配的研究
|
摘要
在保密通信过程中,确保通信安全的办法就是不断的分发新的会话密钥。通信消息经过这个会话密钥加密后传送。对于群组通信,特别是大规模的动态群组通信中,参与应用的用户可以在任何时间加入或离开由多方用户组成的一个群组。这种成员关系的动态性使得非法用户很容易地从群组通信中偷听和窃取数据。同时,在现有的网络环境,尤其是无线网络、无线自组织网络环境下,通信设施容易被敌手破坏,用户设备的靠电池供电,这就要求在计算开销、存储开销上必须高效。自愈式密钥分配使得用户能够恢复丢失的会话密钥,无需再向管理员发送密钥请求,这可以减少网络堵塞,减轻了管理员的负担。本文由此开展了对自愈式密钥分配的研究工作。
本文首先全面深入地综述了密钥分配技术的相关研究工作,介绍了自愈式密钥分配的关键技术,总结了其设计模型。在此基础上,提出改进的设计模型,在性能上进行了比较。自愈式密钥分配的自愈性可以采用容错纠错技术,当前的容错纠错技术已经不能满足需求。采用多项式秘密共享技术来达到自愈性。共享型密钥分配模型其广播通信量与最大会话次数和能被删除的最大用户数有关。在增长型密钥分配模型中,采用增加额外信息的办法来达到自愈的目的,每次广播的消息都包含了前面的广播消息。如果某次未收到管理员的广播消息时,那么用户可以利用后面收到的广播消息恢复出丢失的会话密钥,其特点是广播通信量随会话次数的增加而增加。在迭代型密钥分配模型中,会话密钥通过哈希函数进行迭代,只有群组中的用户才能通过哈希函数迭代出会话密钥。迭代模型消除了最大会话密钥的限制,同时广播信息量大大减少,因为在某次广播消息丢失时,不再向前面的模型那样通过共享信息或额外信息恢复会话密钥,而是通过迭代法恢复会话密钥。
对于共享型、增长型模型其广播通信量较大,对实际应用环境要求网络要有较好的通信效率。本文提出通信优化模型将存储开销变为(t + 1)logq,通信开销变为( 2t + 2+j)logq,迭代模型将通信开销变为(t + 1+j)logq,特别适合无线通信的应用。
One method for enabling secure communication is perodic distribution of a new key to group members. All messages exchanged within the group during a fixed interval of time ,or session are comunicated securely through encryption under this session key. In group communication especially dynamic group communication in which users join or move out frequently,an adversary can easily get information which is not entitled to .In an unreliable network ,especially in mobile wireless networks,the adversary may intentionally disrupt the wireless communication,devices are powered by batteries,it is necessary to adapt efficient key distribution scheme in term of memory storage and communication complexity.In self-healing key distribution scheme users are capable of recovering lost group keys on their own ,without requesting addition transmissions from the group manager,thus cutting back on network traffic,decreasing the load on the group manager,and reducing the risk of user explosure through traffic analysis.
At first, this paper concludes previous key distribution in detail.then give the defition of self-healing key distribution.analysises some existing constructions, presents new constructions which is more efficient in term of memory storage and communication complexity. Error correction techniques is not enough for application.In previous paper, polynomial-based secret sharing technique is used to ressit packet loss.In sharing scheme, broadcast size is decided by max number of sessions and number of revoked members.In growing scheme,users recover past and future session keys using additional information from two received broadcast messages.the broadcast size grows if the session continues.In iterative scheme,session key is recovered by the iteratice of hash function only if he is a member of the group. The construction eliminated the limitation of m sessions in previous and reduce the size of broadcast size comparing to the sharing scheme and growing scheme.
In sharing scheme and growing scheme,the broadcast size is big, so the network must work efficiently.In newly commmunication construction the storage overhead is (t + 1)logq,the communication overhead is ( 2t + 2+j)logq,In newly iterative construction the communication overhead is (t + 1+j)logq which is fit for wireless networks.
本文首先全面深入地综述了密钥分配技术的相关研究工作,介绍了自愈式密钥分配的关键技术,总结了其设计模型。在此基础上,提出改进的设计模型,在性能上进行了比较。自愈式密钥分配的自愈性可以采用容错纠错技术,当前的容错纠错技术已经不能满足需求。采用多项式秘密共享技术来达到自愈性。共享型密钥分配模型其广播通信量与最大会话次数和能被删除的最大用户数有关。在增长型密钥分配模型中,采用增加额外信息的办法来达到自愈的目的,每次广播的消息都包含了前面的广播消息。如果某次未收到管理员的广播消息时,那么用户可以利用后面收到的广播消息恢复出丢失的会话密钥,其特点是广播通信量随会话次数的增加而增加。在迭代型密钥分配模型中,会话密钥通过哈希函数进行迭代,只有群组中的用户才能通过哈希函数迭代出会话密钥。迭代模型消除了最大会话密钥的限制,同时广播信息量大大减少,因为在某次广播消息丢失时,不再向前面的模型那样通过共享信息或额外信息恢复会话密钥,而是通过迭代法恢复会话密钥。
对于共享型、增长型模型其广播通信量较大,对实际应用环境要求网络要有较好的通信效率。本文提出通信优化模型将存储开销变为(t + 1)logq,通信开销变为( 2t + 2+j)logq,迭代模型将通信开销变为(t + 1+j)logq,特别适合无线通信的应用。
One method for enabling secure communication is perodic distribution of a new key to group members. All messages exchanged within the group during a fixed interval of time ,or session are comunicated securely through encryption under this session key. In group communication especially dynamic group communication in which users join or move out frequently,an adversary can easily get information which is not entitled to .In an unreliable network ,especially in mobile wireless networks,the adversary may intentionally disrupt the wireless communication,devices are powered by batteries,it is necessary to adapt efficient key distribution scheme in term of memory storage and communication complexity.In self-healing key distribution scheme users are capable of recovering lost group keys on their own ,without requesting addition transmissions from the group manager,thus cutting back on network traffic,decreasing the load on the group manager,and reducing the risk of user explosure through traffic analysis.
At first, this paper concludes previous key distribution in detail.then give the defition of self-healing key distribution.analysises some existing constructions, presents new constructions which is more efficient in term of memory storage and communication complexity. Error correction techniques is not enough for application.In previous paper, polynomial-based secret sharing technique is used to ressit packet loss.In sharing scheme, broadcast size is decided by max number of sessions and number of revoked members.In growing scheme,users recover past and future session keys using additional information from two received broadcast messages.the broadcast size grows if the session continues.In iterative scheme,session key is recovered by the iteratice of hash function only if he is a member of the group. The construction eliminated the limitation of m sessions in previous and reduce the size of broadcast size comparing to the sharing scheme and growing scheme.
In sharing scheme and growing scheme,the broadcast size is big, so the network must work efficiently.In newly commmunication construction the storage overhead is (t + 1)logq,the communication overhead is ( 2t + 2+j)logq,In newly iterative construction the communication overhead is (t + 1+j)logq which is fit for wireless networks.
引文
[1]李子臣.信息论与编码.徐州:中国矿业出版社,2006:13-39
[2] C. Wong and S. Lan. Keystone: A Group Key Management Service. In International Conference on Telecommunications, ICT 2000.
[3] A. Perrig, D. Song and J.D.Tygar.ELK, a New Protocol for Efficient Large-Group Key Distribution. In IEEE Symposium on Security and Privacy,2001:247-262.
[4] M. Naor and B. Pinkas. Efficient Trace and Revoke Schemes. In Proceedings of Financial Cryptography 2000,Lecture Notes in Computer Science(2001)1962:1-20.
[5] T. Matsumoto and H. Imai. On the Key Predistribution System: A Practical Solution to the Key Distribution Problem. In Advances in Cryptology-Cryto’87,Lecture Notes in Computer Science 293:185-193.
[6] G. Hanaoka, T. Nishika, Y. Zheng and H. Imai. An Efficient Hierarchichal Identity-Based Key-Sharing Method Resistant Against Collusion-Attacks. In Advances in Cryptology-Asiacrypt’99:348-362.
[7] J. Staddon, S. Miner, M. Franklin, D. Balfanz, M. Malkin and D. Dean, Self-healing key distribution with revocation, IEEE Symposium on Security and Privacy,May 12-15,2002,Berkeley,California.
[8] Blundo C, Darco P, Santis A, et al. Design of self-healing key distribution schemes[C]//Design Codes and Crytography,New York:ACM Press,2004:15-44.
[9] D. Liu, P. Ning and K. Sun, Efficient self-healing distribution with revocation capability, Proceedings of the 10-th ACM Conference on Computer and Communications Security, October 27-31,2003,Washington,DC.USA.
[10] Li Hui,CHEN Ke-fei, WEN Mi,ZHENG Yan-fei, A more efficient Group Key Distribution Scheme for wireless Ad hoc networks. Shanghai Jiaotong Univ,2008,13(1):64-66.
[11]陈少真.密码学基础.北京:科学出版社,2008:298-302。
[12] Deering S, Host extensions for IP multicasting, IETF RFC1112,1989.
[13] Quinn B, Almeroth K, IP multicast application: Challenges and solutions, IETF RFC3170,2001.
[14] Fenner W. Internet group management protocol, version 2. IETF RFC2236,1997.
[15] Cain B, Deering S, Kouvelas, Fenner B, Thyagarajan A. Internet group management protocol, version 3. IETF RFC3376,2002.
[16] Krusus PS, Macker JP, Techniques and issues in multicast security. In Proceedings of the Military Communications Conference, Boston,1998:1028-1032.
[17] Canetti R, Pinkas B. A taxonomy of multicast security issues. Internet Draft,2000.
[18] Snoeyink J, Suri S, Varghese G. A lower bound for multicast key distribution. In Proceedings of the IEEE INFOCOM 2001.Anchorage,2001:422-431
[19] Wallner D, Harder E, Agee R. Key management for multicast: Issues and architectures. IETF RFC2627,1999.
[20] Zhu WT,Xiong JP,Li JS,Hong PL.A study of the key distribution in secure multieast Journal of Software,2003,14(12):2052~2059.
[21] Sandro, Rafaeli, Hutchison D. A survey of key management for secure group communication. ACM Computing Surveys,2003,3(35):45-48.
[22] Mcgrew, Sherman, Key establishment in large dynamic groups. Glenwood,1998(5):56-59.
[23] Canetti R, Caray J, Itkis G,et al. A taxonmy and some efficient constructions. New York, In Proc of the INFOCOM’99,1999(7):70-87.
[24] Waldvogel M, Garonni G, Sun D, et al. Versatile group key management. IEEE Journal on Selected Areas in Communications,1999,17(9):1614-1631.
[25] Kim Y, Perrig A, Tsudik G. Simple and fault-tolerant key agreement for dynamic collaborative groups. In Proc of the 7th ACM Conf. on Computer and Communications Security,2000,52(5):235-244.
[26] Oliver C. Authenticated Group Diffie-Hellman Key-Exchange. Theory and Practice.Phd, Louvain-la-Neuve,Belgique, October,2002(8):23-26.
[27]李先贤,怀进鹏,刘旭东.群密钥分配的动态安全性及其方案。计算机学报,2002,25(4):337-345.
[28] Dinsmore P T,Balenson D M, Heyman Metal. Policy-based security management for large dynamic groups-An overview of the DCCM project. USA,In Proc the DARPA Information Suiviv-ability Conference&Exposition,2000,5(2):64-73.
[29] Setiner M, Taudik Q, Waidnet M. A new approach to group key agreement. Technical. Report,RZ 2984, IBM Research,1997.
[30] Steiner Michael, Tsudik Gene, Waidner Michael. Diffie-Hellman key distribution extended to group communication. ACM Conference on Computer and CommunicationSecurity,1996,5(2):38-41.
[31] J. Anzai, N. Matsuzaki and T. Matsumoto. A Quick Group Key Distribution Scheme with“Entity Revocation”. Advances in Cryptology-ASIACRYPT’99,Lecture Notes in Computer Science,1716,1999:333-347.
[32] M. Naor and B.Pinkas, Efficient Trace and Revoke Schemes. Financial Cryptography 2000,Lecture Notes in Computer Science 1962,2001:1-20.
[33] A.Shamir . How to Share a Secret. Communications of the ACM 22:612-613.
[34] D.R.斯廷森.密码学理论与实践,国防科学技术保密通信重点实验室,1997:178-188
[35] D. M. Wallner, E. J. Harder and R. C. Agree, Key Management for multicast: Issues and Archtectures. Internet Draft tp://ftp.ietf.org/internet-drafts/draft-wallner-key-arch-01.txt.
[36] C.K.Wong, M. Gouda and S.S.Lan, Secure Group Communication Using Key Graphs, Proceedings of SIGCOMM’98,1998:68-79.
[37] R. Cannetti, J. Garay, G. Itkis, D. Micciancio, M. Naor and B.Pinkas. Issues in Multicast security: A Taxonomy and Efficient Constructions, Proceedings of INFOCOM’99,1999:708- 716.
[38] D. A. McGrew and A. T. Sherman. Key Establishment in ;arge Dynamic Groups Using One-Way Function Tree. Manuscript,1998.
[39] J. W. Byers, M. Luby, M.mitzejkacuer, et al, A Digital Fountain Approach to Reliable Distribuion of Bulk Data, Proceedings of the ACM SIGCOMM’98,1998.
[40] M. O. Rabin, The Information Dispersal Algorithm and Its Applications. Sequences: Combinatorics, Compression, Security and Transmission:406-419.
[41] R. Canetti, T. Malkiin and K. Nissim, Efficient Communication- Storage Tradeoffs for Multicast Encryption. Advances in Cryptology EUROCRYPT’99, Lecture Notes in Computer Science1592,1999:459-474.
[42] I. Chang, R. Engel, D. Kandlur , et al. Key Management for Secure Internet Multicast Using Boolean Function Minimization Techniques. Proceedings of INFOCOM’99,1999:689-698.
[43] G. Di Crescenzo, O. Kornievskaia, Efficient multicast encryption schemes, Security in Communication Network(SCN02),Lecture Notes in Computer Science, Vol.2576, 2003:119-123.
[44] R. Safavi-Naini and H. Wang, New Constructions for multicast re-keying schemes using perfect hash families, 7th ACM Conference on Computer and Communication Security, ACM Press,2000:228-234.
[45] B. Chor, A. Fiat, M. Naor and Pinkas, Traitor tracing, IEEE Transactions on Information Theory, Vol.46, No. 3,2000:893-910.
[46] C. Dwork, J. Lotspiech and M. Naor, Digital signets: Self-enforcing protection of digital information, Proceedings of the 28th Symposium on the Theory of Computation,1996:489-498
[47] A. Fiat and T. Tessa, Dynamic traior tracing, Journal of cryptology,vol.14,2001:211-223.
[48] E. Gafni, J. Staddon and Y. L. Yin, Efficient methods for integrating traceability and broadcast encryption, Advances in Cryptology-Crypto’99, Lecture Notes in Computer Science, Vol.1666,1999:372-387.
[49] A. Kiayias and M. Yung, Traitor tracing with constant transmission Rate, Advances in Cryptology-Eurocrypt’02, Lecture Notes in Computer Science,Vol.2332,2002;450-465.
[50] B. Pfitzmann, Trials of traced traitors, information hiding, Lecture Notes in Computer Science,Vol.1174,1996:49-64.
[51] D. R. Stinson and R. Wei, Key preassigned traceability schemes for broadcast encryption, Proceedings of SAC’98, Lecture Notes Computer Science,Vol.1556,1999:144-156
[52] R. Safavi-Naini and Y. Wang, Sequential traitor tracing ,Lecture Notes in Computer Science, Vol.1880,2000:316-332.
[2] C. Wong and S. Lan. Keystone: A Group Key Management Service. In International Conference on Telecommunications, ICT 2000.
[3] A. Perrig, D. Song and J.D.Tygar.ELK, a New Protocol for Efficient Large-Group Key Distribution. In IEEE Symposium on Security and Privacy,2001:247-262.
[4] M. Naor and B. Pinkas. Efficient Trace and Revoke Schemes. In Proceedings of Financial Cryptography 2000,Lecture Notes in Computer Science(2001)1962:1-20.
[5] T. Matsumoto and H. Imai. On the Key Predistribution System: A Practical Solution to the Key Distribution Problem. In Advances in Cryptology-Cryto’87,Lecture Notes in Computer Science 293:185-193.
[6] G. Hanaoka, T. Nishika, Y. Zheng and H. Imai. An Efficient Hierarchichal Identity-Based Key-Sharing Method Resistant Against Collusion-Attacks. In Advances in Cryptology-Asiacrypt’99:348-362.
[7] J. Staddon, S. Miner, M. Franklin, D. Balfanz, M. Malkin and D. Dean, Self-healing key distribution with revocation, IEEE Symposium on Security and Privacy,May 12-15,2002,Berkeley,California.
[8] Blundo C, Darco P, Santis A, et al. Design of self-healing key distribution schemes[C]//Design Codes and Crytography,New York:ACM Press,2004:15-44.
[9] D. Liu, P. Ning and K. Sun, Efficient self-healing distribution with revocation capability, Proceedings of the 10-th ACM Conference on Computer and Communications Security, October 27-31,2003,Washington,DC.USA.
[10] Li Hui,CHEN Ke-fei, WEN Mi,ZHENG Yan-fei, A more efficient Group Key Distribution Scheme for wireless Ad hoc networks. Shanghai Jiaotong Univ,2008,13(1):64-66.
[11]陈少真.密码学基础.北京:科学出版社,2008:298-302。
[12] Deering S, Host extensions for IP multicasting, IETF RFC1112,1989.
[13] Quinn B, Almeroth K, IP multicast application: Challenges and solutions, IETF RFC3170,2001.
[14] Fenner W. Internet group management protocol, version 2. IETF RFC2236,1997.
[15] Cain B, Deering S, Kouvelas, Fenner B, Thyagarajan A. Internet group management protocol, version 3. IETF RFC3376,2002.
[16] Krusus PS, Macker JP, Techniques and issues in multicast security. In Proceedings of the Military Communications Conference, Boston,1998:1028-1032.
[17] Canetti R, Pinkas B. A taxonomy of multicast security issues. Internet Draft,2000.
[18] Snoeyink J, Suri S, Varghese G. A lower bound for multicast key distribution. In Proceedings of the IEEE INFOCOM 2001.Anchorage,2001:422-431
[19] Wallner D, Harder E, Agee R. Key management for multicast: Issues and architectures. IETF RFC2627,1999.
[20] Zhu WT,Xiong JP,Li JS,Hong PL.A study of the key distribution in secure multieast Journal of Software,2003,14(12):2052~2059.
[21] Sandro, Rafaeli, Hutchison D. A survey of key management for secure group communication. ACM Computing Surveys,2003,3(35):45-48.
[22] Mcgrew, Sherman, Key establishment in large dynamic groups. Glenwood,1998(5):56-59.
[23] Canetti R, Caray J, Itkis G,et al. A taxonmy and some efficient constructions. New York, In Proc of the INFOCOM’99,1999(7):70-87.
[24] Waldvogel M, Garonni G, Sun D, et al. Versatile group key management. IEEE Journal on Selected Areas in Communications,1999,17(9):1614-1631.
[25] Kim Y, Perrig A, Tsudik G. Simple and fault-tolerant key agreement for dynamic collaborative groups. In Proc of the 7th ACM Conf. on Computer and Communications Security,2000,52(5):235-244.
[26] Oliver C. Authenticated Group Diffie-Hellman Key-Exchange. Theory and Practice.Phd, Louvain-la-Neuve,Belgique, October,2002(8):23-26.
[27]李先贤,怀进鹏,刘旭东.群密钥分配的动态安全性及其方案。计算机学报,2002,25(4):337-345.
[28] Dinsmore P T,Balenson D M, Heyman Metal. Policy-based security management for large dynamic groups-An overview of the DCCM project. USA,In Proc the DARPA Information Suiviv-ability Conference&Exposition,2000,5(2):64-73.
[29] Setiner M, Taudik Q, Waidnet M. A new approach to group key agreement. Technical. Report,RZ 2984, IBM Research,1997.
[30] Steiner Michael, Tsudik Gene, Waidner Michael. Diffie-Hellman key distribution extended to group communication. ACM Conference on Computer and CommunicationSecurity,1996,5(2):38-41.
[31] J. Anzai, N. Matsuzaki and T. Matsumoto. A Quick Group Key Distribution Scheme with“Entity Revocation”. Advances in Cryptology-ASIACRYPT’99,Lecture Notes in Computer Science,1716,1999:333-347.
[32] M. Naor and B.Pinkas, Efficient Trace and Revoke Schemes. Financial Cryptography 2000,Lecture Notes in Computer Science 1962,2001:1-20.
[33] A.Shamir . How to Share a Secret. Communications of the ACM 22:612-613.
[34] D.R.斯廷森.密码学理论与实践,国防科学技术保密通信重点实验室,1997:178-188
[35] D. M. Wallner, E. J. Harder and R. C. Agree, Key Management for multicast: Issues and Archtectures. Internet Draft tp://ftp.ietf.org/internet-drafts/draft-wallner-key-arch-01.txt.
[36] C.K.Wong, M. Gouda and S.S.Lan, Secure Group Communication Using Key Graphs, Proceedings of SIGCOMM’98,1998:68-79.
[37] R. Cannetti, J. Garay, G. Itkis, D. Micciancio, M. Naor and B.Pinkas. Issues in Multicast security: A Taxonomy and Efficient Constructions, Proceedings of INFOCOM’99,1999:708- 716.
[38] D. A. McGrew and A. T. Sherman. Key Establishment in ;arge Dynamic Groups Using One-Way Function Tree. Manuscript,1998.
[39] J. W. Byers, M. Luby, M.mitzejkacuer, et al, A Digital Fountain Approach to Reliable Distribuion of Bulk Data, Proceedings of the ACM SIGCOMM’98,1998.
[40] M. O. Rabin, The Information Dispersal Algorithm and Its Applications. Sequences: Combinatorics, Compression, Security and Transmission:406-419.
[41] R. Canetti, T. Malkiin and K. Nissim, Efficient Communication- Storage Tradeoffs for Multicast Encryption. Advances in Cryptology EUROCRYPT’99, Lecture Notes in Computer Science1592,1999:459-474.
[42] I. Chang, R. Engel, D. Kandlur , et al. Key Management for Secure Internet Multicast Using Boolean Function Minimization Techniques. Proceedings of INFOCOM’99,1999:689-698.
[43] G. Di Crescenzo, O. Kornievskaia, Efficient multicast encryption schemes, Security in Communication Network(SCN02),Lecture Notes in Computer Science, Vol.2576, 2003:119-123.
[44] R. Safavi-Naini and H. Wang, New Constructions for multicast re-keying schemes using perfect hash families, 7th ACM Conference on Computer and Communication Security, ACM Press,2000:228-234.
[45] B. Chor, A. Fiat, M. Naor and Pinkas, Traitor tracing, IEEE Transactions on Information Theory, Vol.46, No. 3,2000:893-910.
[46] C. Dwork, J. Lotspiech and M. Naor, Digital signets: Self-enforcing protection of digital information, Proceedings of the 28th Symposium on the Theory of Computation,1996:489-498
[47] A. Fiat and T. Tessa, Dynamic traior tracing, Journal of cryptology,vol.14,2001:211-223.
[48] E. Gafni, J. Staddon and Y. L. Yin, Efficient methods for integrating traceability and broadcast encryption, Advances in Cryptology-Crypto’99, Lecture Notes in Computer Science, Vol.1666,1999:372-387.
[49] A. Kiayias and M. Yung, Traitor tracing with constant transmission Rate, Advances in Cryptology-Eurocrypt’02, Lecture Notes in Computer Science,Vol.2332,2002;450-465.
[50] B. Pfitzmann, Trials of traced traitors, information hiding, Lecture Notes in Computer Science,Vol.1174,1996:49-64.
[51] D. R. Stinson and R. Wei, Key preassigned traceability schemes for broadcast encryption, Proceedings of SAC’98, Lecture Notes Computer Science,Vol.1556,1999:144-156
[52] R. Safavi-Naini and Y. Wang, Sequential traitor tracing ,Lecture Notes in Computer Science, Vol.1880,2000:316-332.