A novel establishing and managing secure group key method - Nguyen Dao Truong

Công nghệ thông tin & Cơ sở toán học cho tin học Nguyen Dao Truong, “A novel establishing and managing secure group key method.” 138 A NOVEL ESTABLISHING AND MANAGING SECURE GROUP KEY METHOD Nguyen Dao Truong* Abstract: The one-way function tree (OFT) is an efficient group key management scheme. Many methods have been proposed to improve it against different types of internal attack. However, these previous works have not considered external attacks such as man in the middle (MITM). This is a very dangerous attack because it can intervene in the key establishment and key agreement process. This paper proposes a novel method to prevent man in the middle attack by combining the OFT scheme with digital signatures scheme which is used to authenticate the participants. Beside, the proposed method can also prevent the collusion attack. Từ khóa: One-way function tree, Replay attack, Collusion attack, Man in the middle (MITM). 1. INTRODUCTION OFT [3,4] is a centralized group key management scheme. It is based on the Logical Key Hierarchy scheme [5,6] and works as a key managing structure. It adds one-way functions to the LHK. The total communication overhead of the group manager (group manager) when a member is eliminated is reduced to log2n, where n is the total number of members in the group. It is reduced by a half comparing to LKH. Beside, OFT has some vulnerabilities. First is the vulnerability under a sophisticated membership-evolving attack, such as collusion attack that Horng pointed out [1]. Next is the vulnerability under an external attack and Man in the middle attack is an example [2]. In order to improve OFT scheme’s invulnerability, Ku and Chen researched these attacks and proposed other collusion attack methods [7]. Xu et al. also show the ability to attack between two members of the system [8]. However, these researches and proposed improvements only focused on internal attacks or collusion attack in specific despite the fact that these networks are increasingly exposed to public external networks. In this paper, we propose a security enhanced solution for the OFT scheme by using digital signatures [13] in establishing, distributing group key in order to assure security against external attacks like MITM attacks [2]. 2. RELATED WORK 2.1. Previous work In paper [7], Ku and Chen showed collusion attacks based on OFT scheme’s vulnerabilities that Horng pointed out in [6]. Then, these authors improved the OFT scheme. In their improved schemes, they updated every key on the path from evicted node to the root node. However, total time cost for that action is approximately h2 + h, where h is the height of the key tree. In order to reduce communication overhead of group manager, Xu et al. [8] studied the vulnerabilities to collusion attacks between two arbitrary members. They discovered that with two arbitrary members, it is not always able to find unkown key’s informations. Therefore, group manager does not need to update all secret keys everytime a member is eliminated. In [9], Liu et al. synthesized previous research results and analyzed Xu main idea. Liu gived an anti-example to prove that Xu’s conditions for collusion attack are not really necessary. Afterward, Liu proposed to improve OFT to HOFT (self-homomorphic one-way function tree). The new scheme is proved to be immune to collusion attack by Liu. In [10], the authors developed OFT into Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 52, 12 - 2017 139 two scheme, ROFT (Repeated one-way function tree) and NOFT (Node one-way function tree) with minimum cost increased. Afterall, all these previous works only focused on prevent collusion attack or internal attack in another words. In today connected IoT world, prevention against internal threats only is not enough. The key management scheme must be immune to man in the middle attack[2]. Therefore, in this paper we proposed to improve the OFT scheme invulnerability against these attacks. Beside, the proposed scheme is also effective against internal attack and met system’s attacks immunity requirements. 2.2. The OFT scheme The OFT scheme is a group key management scheme, propsed by Sheman and his colleages [3]. It is based on combination of Logical Key Hierachy (LKH) scheme and using one-way function in key management [4,5]. In OFT scheme, there is a centralized group manager who is in charge of updating, storing, and distributing keys. OFT scheme’s management structure is a binary key tree. Each internal node i in the tree contains: a node key ki, a blinded node key yi, where blinded node key yi is output of one-way function that take node key ki as input. The blinded node key yi is used to compute the node keys of the upper nodes in the key tree. Key of the root node is the group key. The blinded node key yi is calculated by formula   ,i iy g k which g() is a one-way function. ki is used to encrypt the updated key information when rekeying. Every members of the group stores the blinded node key of the siblings of the nodes in the path from its leaf node to root node. Therefore, every members can use its leaf node’s key and blinded node key to compute other node keys in the path from bottom up. Figure 1. Structure of one way function key tree. In Figure 1, node i is an internal node of the key tree. The left children tree is 2i, the right children tree is 2i+1. Corresponding to each node i is the sub-group Gi, in which consist of mi members. Members in the sub-tree (sub-group) Gi can compute the sub-group key at node i by formula     2 2 1, ,i i ik f g k g k  where ,f g is cryptographic functions that immune to cryptographic attacks. In this paper, we use a one-way function as function g and a trapdoor one-way functions that symmetry over g (which means f: K×K K,      1 2 1 2, , ,f k g k f g k k where K is the key space). They can calculate iy as following:  .i iy g k These members store sy of node s (sibling of node i). Thus, they can compute the sub-group key at node p (parent node of node i) by formula Công nghệ thông tin & Cơ sở toán học cho tin học Nguyen Dao Truong, “A novel establishing and managing secure group key method.” 140  , .p s ik f y y Similarly, every members can calculate all the node key (sub-group key) in the path from that node to the root and obtain the root node key which is the group key. Updating (adding, evicting) group’s members will adjust the tree’s structure (demonstrated in Section 3) and update corresponding key (described in Section 4). 3. BINARY TREE STRUCTURE FOR GROUP 3.1. Building binary tree for group The binary tree’s structure of group G consist of n members is built based on following rules: - Subgroup 0,1G is called 0 height subgroup of G,  0,1 0,G n . - If h height subgroup  , ,,h j h jG h m has more than 1 member  , 1h jm  , then this subgroup is divided into two h+1 height subgroup, with the number of left and right members are 1,2 1h jm    and 1,2h jm   respectively. Where j is the jth subgroup from left to right that has same height. In the group binary tree’s structure of group G, if leaf nodes are noted as  , , ,, , 1,(1 )h j h j h jG h m m j n   and other nodes noted as  , ,, ,i j i jG i m (0 1,i h   1 2 )ij  then the total number of members in group is computed by formula , 1,2 1 1,2 ,i j i j i jm m m      (0 1,1 2 ). ii h j      0,1 0,10,G m  1,1 1,11,G m  3,1 3,1G  1,2 1,21,G m  2,1 2,12,G m  2,2 2,22,G m  2,3 2,32,G m  2,4 2,42,G m  3,2 3,1G  3,3 3,1G  3,4 3,1G  3,5 3,1G  3,6 3,1G  3,7 3,1G  3,8 3,1G 2,1 2m  2,2 2m  2,3 2m  2,4 2m  1,1 4m  1,2 4m  0,1 8m  Figure 2. Binary tree for group G with 8 members. For example, the group G has n members, denoted as  1 2, , ..., .nG A A A At each nodes ( , ),II h m of the tree, where hI is the height of node I, m is the number of members in group. The set of members which belong to subgroup at node I is  1 2, , ..., .mS A A A The structure of G group’s binary tree is illustrated in Figure 2. The height ih of node i is the total number of nodes in the path from root to that node. In Figure 2, 1 2 3 4 5 6 7 8, , , , , , ,h h h h h h h h are all equals to 3, where 1 8,...,h h are heights Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 52, 12 - 2017 141 corresponding to members A1, ..., A8 respectively. Therefore, the height of the binary tree H(G) or H is  max , 1... ,iH h i n  2log .n H n  Algorithm 1. Building tree structure for group Input: there are n members Output: Binary tree T for group G. Tree GroupTreeBuid() { Int n1= 2log n   ; Int n2 = n - n1; Tree T1 = BuidBinaryTree(n1); Tree T2 = BuidBinaryTree(n2); Return CombineTree(T1,T2);} 3.2. Adding new member to group When a new member is added to the group, the group manager will chose a leaf node , j which is nearest to the root. Node j will be modified, the existing member of node j will be moved to node 2j (left children of j), the new member will became node 2j+1 (right children of j). Algorithm 2 demonstrates how to restructure the group. Algorithm 2. Rebuild the binary tree when a new member is added Input: Group management tree T, new member An+1 Output: Updated Group management tree T. Tree AddMemtoTree(T, An+1) { x = SelectLeafNode(T); xold = Member(x); (xleft, xright) = Split(x); xleft  xold; xright  An+1; Return (T);} 3.3. Evict a member from group When a member attached to leaf node j is evicted from group, if node s (sibling of node j) also is a leaf node then leaf node s will be moved to node p (parent node of j and s). If node s is the root of another sub tree (sub group), s will be moved to node p to form a new sub tree that have root at node s (closer to the root). The rebuilding the group’s structure is followed the algorithm 3. Algorithm 3. Rebuild the binary tree when a member is evicted Input: OFT tree T, member Aj; Output: Updated OFT tree T; Tree RemoveMemfromTree(T, Aj) { y = LeafNode(Aj); p = ParentNode(y); s = siblingNode(y); if s is LeafNode then p  Member(s) Else p = s; Return T;} 4. PROPOSED SCHEME 4.1. Establishing group key The establishing group key k for group G has been discussed in section 3. In many previously proposed OFT schemes [3-4, 7-12], there is no authentication in establishing Công nghệ thông tin & Cơ sở toán học cho tin học Nguyen Dao Truong, “A novel establishing and managing secure group key method.” 142 key process. Today, due to the needs of connecting to outside networks, it is very necessary to authenticate the group members in order to avoid handshakes attacks such as MITM. Our scheme proposed to include the authentication by using digital signatures [13]. Detailed of establishing secure group key is demonstrated in Algorithm 4. In this algorithm, th is number of subgroups with the same height h in the tree structure of group G, 0,1k is group key, sign() is signature, ver() is signature verification function, A is group manager of left subgroup, B is group manager of right subgroup. Algorithm 4. Establishing secure group key Phase I ( 1, )iA i n ();ik random Phase II Left subgroup Right subgroup For h = H-1 down to 0 do ,h ik , is subgroup key ( 1, )h i hG i t A B  1,2 1 1,2 1 ;h i h iy g k    1,2 1( );A A h is sign y    1,2 1,2 ;h i h iy g k  1,2( );B B h is sign y   1,2 1 ,h i Ay s  B A  1,2 ,h i By s 1,2( ( , ) )B h iif ver s y true then   , 1,2 1 1,2, ;h i h i h ik f k y   1,2 1( ( , ) )A h iif ver s y true then    , 1,2 1,2 1, ;h i h i h ik f k y   0,1( )Return k 4.2. Updating key when a new member is added to group The updating key process when a new member is added to group is executed in two periods: - First period (old key is still valid): The most important thing of the key establishment and management protocol is to maintain normal operation of the system, all current members must operate normally with their distributed key. The key establishing process when a new member joining to the group is executed as algorithm 5. - Second period (old key is expired): After the old group key expired, if there is a new member added then two tasks must be done: First is reconstructing the tree as Rebuild the binary tree when a new member is added algorithm (Section 3). Second is re-establishing the group key as algorithm 6. Figure 3 describes an example that simulate the updating key process when a new member is added to group. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 52, 12 - 2017 143 Algorithm 5. Updating key process when a new member is added and the old group key is still valid. oldG (Old Group) B(New member) Initiation oldG have the old group key oldGk and B has new key .Bk Phase I 1A (Old group manager)  ; old oldG G y g k 1 ( ); old oldG A G s sign y B (New member)  ;B By g k ( );B B Bs sign y  ,G Gold oldy s B  , 1 B By sA  Phase II 1A ( ( , ) )B Bif ver s y true then  , ; new oldG G B k f k y B ( ( , ) ) old oldG G if ver s y true then  , ; new oldG B G k f k y 0,1K 1,1K 2,1K 2,2K 2,3K 3,8K3,1K 3,2K 3,3K 3,4K 3,5K 3,6K 3,7K 1,2K 2,4K ' 0,1K     ' '0,1 1,1 1,2,K f g K g K 1,1K     ' '1,2 2,3 2,4,K f g K g K 2,1K 2,2K 2,3K ' 1,2K ' 2,4K     ' '2,4 3,7 3,8,K f g K g K ' 3,8K     '3,8 4,1 4,2,K f g K f K 4,1K 4,2K 3,1K 3,2K 3,3K 3,4K 3,5K 3,6K 3,7K Figure 3. Updating key when a new member is added. Algorithm 6. Updating key process when a new member is added and the old group key is expired. Input: OFT T, new member An+1 Output: Updated T. 1. x = SelectLeaftoAdd(T); , ( );i jK Key x 2. OldMember = Member(x); (a, b) = Split(x); a = OldMember; b = An+1 3. ();bk random      ' , ,i j a bK f g k g k ( K ’ 3,8 in figure 3) 4. Group manager (GM) encrypt new key ',i jK by old key ,i jK then send unicast to An:   , ' ,: ( )i j unicast n K i jGM A E K 5. While parentNode(b) is not NULL do { p = parentNode(b);     ,left rightp p pk f g k g k b = p;} Công nghệ thông tin & Cơ sở toán học cho tin học Nguyen Dao Truong, “A novel establishing and managing secure group key method.” 144 Figure 3 includes:     '3,8 4,1 4,2, ;K f g K g K     ' '2,4 3,7 3,8, ;K f g K g K     ' '1,2 2,3 2,4, ;K f g K g K     ' '0,1 1,1 1,2, .K f g K g K 6. GM encrypts these new keys by the corresponding old key then send multicast the updated key to other corresponding member, then sends unicast to new node      , 1 ' ' , 1 ,: ( ,...) ; : ( ,...)i j An multicast unicast m K i j n K i jGM A E K GM A E K    7. GM sends reminding messages to all sibling members of that node in the path from new node to the root. The messages reminds them that there is a new member the group and they must update all their keys. 8. GM sends unicast the parent node key of the new node to its siblings. As illustrated in figure 3:     8 ' ' ' ' 8 0,1 1,2 2,4 3,8: ( , , , )A unicast KGM A E K K K K . 4.3. Updating key when a member is evicted from group The updating key process when a member is evicted from group is executed as algorithm 7. An example simulate the updating key process when a member is evicted from group is described in figure 4. 0,1K 1,1K 2,1K 2,2K 2,3K ' 3,8K3,1K 3,2K 3,3K 3,4K 3,5K 3,6K 3,7K 1,2K 2,4K ' 0,1K     ' '0,1 1,1 1,2,K f g K g K 1,1K     ' '1,2 2,3 2,4,K f g K g K 2,1K 2,2K 2,3K ' 1,2K 3,1K 3,2K 3,3K 3,4K 3,5K 3,6K ' 2 ,4K Figure 4. Updating key when a member is evicted from group. Algorithm 7. Updating key when a member is evicted from group Input: OFT T, Evicted member Aj Output: Updated T. 1. Rebuild the binary tree as algorithm 3. 2. Group manager (GM): ' '( ); (); ; s s ss j A A A A sibling A K random k K   (In figure 4 ' 2,4K is assigned to A7.) 3. b = Node(As); While parentNode(b) is not NULL do { p = parentNode(b);     , ;left rightp p pk f g k g k b = p;}. In Figure 4:          ' ' ' '1,2 2,3 2,4 0,1 1,1 1,2, ; , .K f g K g K K f g K g K  4. GM encrypts these new keys by the corresponding old key then send multicast the updated key to other corresponding member, then send unicast to the node that just moved to parent node. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 52, 12 - 2017 145       , ' , ' , : ( ,...) ; : ( ,...) i j As multicast K i j unicast s K i j GM A E K GM A E K   5. GM sends reminding messages to all sibling members of that node in the path from new node to the root. The messages reminds them that there is an evicted member and they must update all their keys. 6. GM sends unicast the parent node key of the new node to its siblings. As illustrated in figure 4:     7 ' ' 7 0,1 1,2: ( , )A unicast KGM A E K K . 4.4. Comparison of proposed scheme and other’s Table 1 shows the detailed comparison between the proposed scheme and other previous works, where AC is collusion attack, RA is replay attack, MITM is man in the middle attack, h is the height of key tree, L is the key size, CE is the computational cost to encrypt, CD is the computational cost to decrypt, CH is the computational cost to calculate hash function, Cf is the computational cost to calculate one-way trap-door function, CM is the computational cost to calculate the Modulo operation, Csign is the computational cost to sign the digital signatures, Cver is the computational cost check the signatures, S is the number of nodes from evicted or added node to the root. The proposed OFT guarantee to immune against internal attack such as collusion attack and external attack such as MITM. Furthermore, the computational cost of the proposed scheme when the old group key (session key) is still valid is always much lower comparing to previous schemes. However, in the case of expired old group key, the total computational cost of adding or evicting member is increased because of signing and authenticating signatures. Specifically, when evicting member from group, the computational cost and communication cost are equivalent because it is compulsory to reconstruct the managing group key tree right after the elimination of that member, then all informations related to that member must be updated. Table 1. Comparison of computational cost between proposed scheme and other’s. Schemes Agains t MITM Agains t AC Agains t RA GM Com. cost (join; evict) GM’s computational cost (join ;evict) Total computational cost of members (join; evict) Propos ed OFT Group key is valid Yes Yes Yes 1; ( 1)h L  2 ;H sign ver E DC C C C C     ( 1) ( 1)E Hh C h C     2 ;H sign ver E DC C C C C     2D HC h C  Group key is expire d (2 1) ;h L  ( 1)h L  (2 1) ( 1) ;E Hh C h C     ( 1) ( 1)E Hh C h C     2 ( 1) ;D HC h C   2D HC h C  ROFT, NOFT [10] No Yes Yes (2 1) ;h L  ( 1)h L  (2 1) (2 1) ;E Hh C h C     ( 1) ( 1)E Hh C h C     2 (2 1) ;D HC h C   2D HC h C  OFT [3,4] No No No (2 1) ;h L  ( 1)h L  (2 1) ( 1) ;E Hh C h C     ( 1) E Hh C h C    2 ;D HC h C  D HC h C  Ku et al. [7] No Yes No (2 1) ;h L  ( 1)h L  (2 1) ( 1) ;E Hh C h C     2 2( 1) ( )E Hh h C h h C      2 ;D HC h C  2(1 / 2)D Hh C h C   Công nghệ thông tin & Cơ sở toán học cho tin học Nguyen Dao Truong, “A novel establishing and managing secure group key method.” 146 Xu et al. [8] No Yes No (2 1) ;h L  ( 1)h L  (2 1) ( 1) ;E Hh C h C     ( 1) ( 2)E Hh C h C     2 ;D HC h C  D HC h C  HOFT [9] No Yes No (2 1) ;h L  ( 1)h L   (2 1) 2 1 ( 1) ; E M f h C S h C h S h C             ( 1) 2 ( 1) E M f h C h C h C         1 2 ( ) ; H M f h C h C h S h C         ( 1)D M fC h C h C     5. CONCLUSION The establishing and managing group key is the most important factor to ensure the continuity of the communication when a member is evicted from or added to the group. This paper proposes the improved OFT scheme used for managing group key that has outstanding advantages compared to previous schemes. Firstly, the proposed scheme is immune to external attacks like MITM. It can also invulnerability against internal attack such as collusion attack because it reconstructs the managing key tree and refresh all informations of previous old key. REFERENCES [1]. G. Horng, “Cryptanalysis of a key management scheme for secure multicast communications”, IEICE Trans. Commun E85-B (5) pp. 1050-1051 (2002). [2]. Peter Maynard, Kieran McLaughlin, Berthold Haberler, “Towards Understanding Man-In-The-Middle Attacks on IEC 60870-5-104 SCADA Networks”, Proceedings of the 2nd International Symposium for ICS&SCADA Cyber Security Research, (2014). [3]. A.T. Sherman, D.A. McGrew, “Key establishment in large dynamic groups using one-way function trees”, IEEE Trans. Softw. Eng Vol.29, Issue 5, pp. 444-458, (2003). [4]. D. Balenson, D. McGrew, A. Sherman, “Key Management For Large Dynamic Groups: One-Way Function Trees and Amortized Initialization”, Internet Research Task Force, (2000). [5]. D.M. Wallner, E.J. Harder, R.C. Agee, “Key Management for Multicast: Issues and Architectures”, Internet Engineering Task Force, (1998). [6]. C.K. Wong, M. Gouda, S.S. Lam, “Secure group communication using key graphs”, IEEE/ACM Trans. Netw. Vol.8, Issue 1, pp. 16-30, (2000). [7]. W.C. Ku, S.M. Chen, “An improved key management scheme for large dynamic groups using one-way function trees”, in: Proceedings International Conference Parallel Processing Workshops, Kaohsiung, Taiwan, pp. 391-396, (2003). [8]. X. Xu, L. Wang, A. Youssef, B. Zhu, “Preventing collusion attacks on the one-way function tree (OFT) scheme”, in: Proceedings 5th International Conference Applied Cryptography and Network Security, Zhuhai, China, pp. 177-193, (2007). [9]. J. Liu, B. Yang, “Collusion-resistant multicast key distribution based on homomorphic one-way function trees”, IEEE Trans. Inf. Forensics Security. Vol.6, Issue 3, pp. 980-991, (2011). [10]. Yanming Sun, Min Chen, Abel Bacchus, Xiaodong Lin, “Towards collusion-attack- resilient group key management using one-way function tree”, Computer Networks, Vol.104, pp. 16-26, (2016). [11]. C. Beaver, D. Gallup, W. Neumann and M. Torgerson, “Key management for SCADA,” Technical report, Sandia, (2002). Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 52, 12 - 2017 147 [12]. Robert Dawson, Colin Boyd, Ed Dawson, Juan Manuel Gonzalez Nieto, “SKMA A Key Management Architecture for SCADA Systems,” In Proc. Fourth Australasian Information Security Workshop, Vol.54, pp. 138-192, (2006). [13]. Al Imem Ali, “Comparison and evaluation of digital signature schemes employed in NDN Network”, International Journal of Embedded systems and Applications(IJESA) Vol.5, No.2, (2015). TÓM TẮT MỘT PHƯƠNG PHÁP MỚI THIẾT LẬP VÀ QUẢN LÝ KHÓA NHÓM AN TOÀN Cây khóa hàm một chiều (OFT) là một lược đồ quản lý khóa nhóm hiệu quả. Tuy nhiên, các công trình nghiên cứu, cải tiến cho đến nay chỉ tập trung vào những yếu tố tấn công bên trong và đưa ra các đề xuất chống lại những tấn công này mà chưa xem xét đến những tấn công bên ngoài như kiểu tấn công xen giữa. Đây là kiểu tấn công rất nguy hiểm trong quá trình can thiệp vào giai đoạn bắt tay thiết lập và thỏa thuận khóa. Bài báo đề xuất một giải pháp mới chống tấn công bên ngoài như kiểu tấn công xen giữa bằng cách kết hợp lược đồ OFT với chữ ký số để xác thực chính xác các bên tham gia, từ đó chống lại những tấn công kiểu xen giữa này. Bên cạnh đó chính lược đồ cải tiến này cũng chống lại kiểu tấn công bên trong, dạng tấn công thông đồng. Từ khóa: OFT (one-way function tree), Tấn công phát lại, Tấn công thông đồng, Tấn công xen giữa (MITM). Nhận bài ngày 13 tháng 9 năm 2017 Hoàn thiện ngày 10 tháng 10 năm 2017 Chấp nhận đăng ngày 20 tháng 12 năm 2017 Địa chỉ: Học viện Kỹ thuật Mật mã. *Email : truongnguyendao@gmail.com.