# Analysis and Improvement of Key Distribution Scheme for Secure Group Communication

Authors: Jia Ning Luo; Ming Hour Yang
Journal: Journal of Electrical and Computer Engineering
 (2016)

---

## Abstract

In a secure group communication, messages between a group coordinator and members are protected by session keys. If a group’s membership changes, the session keys should be updated to insure forward secrecy and backward secrecy. Zhou and Huang proposed a key-updated scheme based on ciphertext-policy attribute encryption algorithm to improve the security of key-update mechanism, but their scheme is vulnerable: a malicious group member may send forged key-update messages to control the group. In this paper, we analyze the vulnerability in Zhou and Huang’s scheme and propose an enhanced scheme. In our scheme, only the group initiator can update group keys and the verification of key-update mechanism is improved to prevent malicious insiders from controlling the group. We also give a security and performance analysis of our scheme.


---

## Body

## 1. Introduction

In recent years, social networks such as Google+, Facebook, and Twitter are receiving wide popularity and provide much convenience in people’s daily life. In a social network, people can maintain their own social circles freely, such as adding or removing their friends and sharing messages to specific members within a group.Social networks are based on cloud computing technology. In a cloud service, users’ data and documents are not stored in their computers, but on cloud servers. In most cases, users’ data is not encrypted and, therefore, is vulnerable to system vulnerabilities, unauthorized access, and privacy leak under government’s censorship [1–3].The secure multicast technique can be used to enhance users’ privacy in social networks [4]. For secure multicast, the confidentiality of group communication is secured because group members share a session key to de/encrypt their communications. Once a group member leaves a group or a new member joins a group, their group key must be renewed. A group coordinator has to rekey the group. He needs to ensure that a new group key is delivered to every new member through a secure channel and that every old member’s key is updated simultaneously. By this, new members are not able to access previous messages, and those who have left a group cannot access the group’s new messages. This guarantees the forward and backward secrecy in group communication and has made key updating an important issue for secure multicast.Chang et al. [5] propose Flat Table (FT) for key management in a binary tree. A group coordinator only needs to store log⁡N keys and each member can join  N-1 subgroups. To have higher flexibility of data encryption, Attribute-Based Encryption (ABE) [6–9] and Ciphertext-Policy Attribute-Based Encryption (CP-ABE) [10] are proposed. Bethencourt et al. [11] propose CP-ABE for multicast key management. It features complex access control on encrypted data. Zhou and Huang [12] combine FT and CP-ABE to present Efficient Group Keying (EGK). EGK is more efficient for a group coordinator to rekey his group, and the size of its ciphertext is fixed. No matter how its membership changes, the size of its ciphertext remains the same. EGK is also able to keep its storage within O(log⁡N), where N denotes the maximum members. Huang et al. also come up with secure virtual trust routing and multicasting, aiming to apply EGK to networking routing [13]. Jia et al. propose a layered EGK architecture [14]. Huang et al. proposed a cloud solution of EGK [15]. As each mobile device is seen as a service node, they propose to process mobile cloud data through trust management and private data isolation.However, we have discovered certain security issues in the EGK model. For example, a malicious group member may launch the following attacks within EGK. (1) He may perform Man-in-the-Middle (MITM) attacks to intercept group communications and modify the group coordinator’s messages. (2) He may masquerade as the coordinator and forge the key-update message and become the new coordinator. In Jia et al.’s EGK-based scheme [14], we have also found the threat of desynchronization because the group members cannot verify whether the messages are sent from the coordinator.In this paper, we analyze the security issues in EGK and propose a new secure key management scheme. Our scheme resists the MITM attack and masquerade attack. The rest of this paper is organized as follows. In Section2, we analyze the vulnerability of EGK. We describe our scheme in Section 3 and give a performance analysis in Section 4. A conclusion is drawn in Section 5.


## 2. EGK Scheme

Zhou and Huang [12] propose an Efficient Group Keying (EGK) method that is based on Ciphertext-Policy Attribute-Based Encryption (CP-ABE). Following CP-ABE’s policy, EGK takes each bit of group members’ ID as an attribute. The group key is calculated by using the combination of specific group members.When a new member joins a specific group, the coordinator generates a new group key and sends it to the new member by a secure channel and uses the old group key to encrypt the new one and sends it to the members. When a member leaves the group, the coordinator uses the Quine-McCluskey algorithm [16] to update the new group key.The notations used in EGK are listed in Notations.


### 2.1. Initial Stage

At this stage, a group coordinator creates a group and the maximum membership of the group isN. The length of an ID is designed as n=log⁡N. The total number of LB’s is 2n, and the total number of PB’s is 2n too. Consider LB=B0,B0-,B1,B1-,…,Bn-1,Bn-1-; Bi denotes that the ith bit of ID is 1; Bi- denotes that the ith bit of ID is 0. Consider PB={pB0,pB0-,pB1,pB1-,…,pBn-1,pBn-1-}; consider pBi, pBi-∈Zq; PB maps LB, pB0 maps B0, pB0- maps B0, and so on. Then, the coordinator generates a master key MK={β,gα,gβ,e(g,g)α,LB,PB} and sets the parameters of a bilinear map function, such as q, G0, G1, g, and e. At last, he generates a hash function H and defines the public parameter Params={G0,e,g,H}.


### 2.2. Assign Private Key to Group Member

When a new member joins a group, the group coordinator gives to the member a uniqueID and associates the member with an attribute AID. For example, there is a group whose maximum membership is 64, and the length of the ID is log2⁡64. The coordinator assigns ID=001011 to the new member and accordingly associates the member with the attribute AID={B5-,B4-,B3,B2-,B1,B0}. Then, he runs the algorithm KeyGen(MK, AID) to generate a private key for the new member:(1)
He generates a random valueγ∈Zq∗.(2)
He calculatesD=gα+γ/β.(3)
According toAID, he calculates ∀Bi∈AID:DB=gγBi.(4)
He performs the mapping ofLB and PB, ∀Bi∈AID:DB=gγpBi.(5)
He generates a private keySKID={D=gα+γ/β,∀Bi∈AID:DB=gγpBi} for the new member.(6)
At last, the coordinator sendsID, AID,  SKID, and current session key  SEK to the new member through a secure channel.


### 2.3. Encryption/Decryption Algorithms

When a group coordinator is going to multicast a message, he can use a different bit-assignment to assign specific members to decrypt the message. Then, he has to run the Quine-McCluskey algorithm to minimize all group members’ IDs. The IDs are compared in pairs and reduced until there is no pair with only one bit different. The irreducible IDs are taken as attributes for encryption:Si, where 1≤i≤m and m denotes the number of irreducible IDs. After the coordinator runs the encryption algorithm for each attribute, he generates the encrypted messages for multicast: ENCParams,MK,S1,M, ENCParams,MK,S2,M,…,ENCParams,MK,Sm,M. For example, a group coordinator is going to multicast three members whose IDs are 001001, 001011, and 111000, respectively. After minimization through Quine-McCluskey algorithm, the IDs are reduced as 111000 and 0010x1, where x denotes a negligible bit. Next, the coordinator maps the reduced IDs with LB as attributes S1 and S2. Consider S1={B0,B2-,B3,B4-,B5-} and S2={B0-,B1-,B2-,B3,B4,B5}.With the attributes, the coordinator runs the encryption algorithmENCParams,MK,Si,M in detailed steps as follows:(1)
convertingSi’s LB into PB,(2)
calculatingSumSi=∑Bi∈SipBi,(3)
generating a random valuetSi∈Zq∗,(4)
calculatingC0Si=Me(g,g)αtSiSumSi,(5)
calculatingC1Si=gβtSiSumSi,(6)
calculatingC2Si=gtSi,(7)
generating a ciphertextCTSi={Si,C0Si,C1Si,C2Si}.After group members receive the encrypted messages, they use their private key and the public parameter to run the decryption algorithm, DEC(Params,SK,CTSi):(1)
The group member verifies whetherCTSi’s Si matches his own attribute AID. If the two match, the member proceeds to the next step. If they do not match, the decryption algorithm ends.(2)
He convertsSi’s LB into PB and calculates the sum: F=∏AID∈SigγpBi=gγ∑AID∈SipBi=gγSumSi.(3)
He calculatesA1=eC1Si,D=e(gβtSiSumSi,gα+γ/β)=e(g,g)α+γtSiSumSi.(4)
He calculatesA2=eC2Si,F=e(gtSi,gγSumSi)=e(g,g)γtSiSumSi.(5)
He calculatesA3=A1/A2=e(g,g)αtSiSumSi. C0Si/A3 = Me(g,g)αtSiSumSi/e(g,g)αtSiSumSi=M.


### 2.4. Key-Update Stage

When a new member joins a group, the group coordinator generates a new group keySEK′ and uses the previous group key SEK to encrypt SEK′ to the new member. Then, he sends ID, AID, SKID, and SEK to the new member through a secure channel. If a member leaves a group, the rekeying process will be divided into two parts: the group coordinator and the group member.The group coordinator has to run the following steps:(1)
Generating a random valueα′∈Zq∗.(2)
Updating his master keyMK={β,gα′,gβ,eg,gα′,LB,PB}.(3)
Generating a rekeying messageKU=g(α′-α)/β.(4)
Running Quine-McCluskey algorithm to minimize the remaining members’ IDs until there arem irreducible IDs; these IDs are taken as attributes Si,  1≤i≤m.(5)
Using each attribute to run the encryption algorithm ENC(Params,MK,Si,M).After receiving the ciphertext, the group members run the following steps:(1)
Performing the decryption algorithm DEC(Params, SK,CTSi) and retrieving KU=M.(2)
MultiplyingKU by his private key’s D and obtaining D′, D′=KU·D=gα′-α/β·gα+γ/β=gα′+γ/β.(3)
Updating his session keySEK′=H1(KU).


## 2.1. Initial Stage

At this stage, a group coordinator creates a group and the maximum membership of the group isN. The length of an ID is designed as n=log⁡N. The total number of LB’s is 2n, and the total number of PB’s is 2n too. Consider LB=B0,B0-,B1,B1-,…,Bn-1,Bn-1-; Bi denotes that the ith bit of ID is 1; Bi- denotes that the ith bit of ID is 0. Consider PB={pB0,pB0-,pB1,pB1-,…,pBn-1,pBn-1-}; consider pBi, pBi-∈Zq; PB maps LB, pB0 maps B0, pB0- maps B0, and so on. Then, the coordinator generates a master key MK={β,gα,gβ,e(g,g)α,LB,PB} and sets the parameters of a bilinear map function, such as q, G0, G1, g, and e. At last, he generates a hash function H and defines the public parameter Params={G0,e,g,H}.


## 2.2. Assign Private Key to Group Member

When a new member joins a group, the group coordinator gives to the member a uniqueID and associates the member with an attribute AID. For example, there is a group whose maximum membership is 64, and the length of the ID is log2⁡64. The coordinator assigns ID=001011 to the new member and accordingly associates the member with the attribute AID={B5-,B4-,B3,B2-,B1,B0}. Then, he runs the algorithm KeyGen(MK, AID) to generate a private key for the new member:(1)
He generates a random valueγ∈Zq∗.(2)
He calculatesD=gα+γ/β.(3)
According toAID, he calculates ∀Bi∈AID:DB=gγBi.(4)
He performs the mapping ofLB and PB, ∀Bi∈AID:DB=gγpBi.(5)
He generates a private keySKID={D=gα+γ/β,∀Bi∈AID:DB=gγpBi} for the new member.(6)
At last, the coordinator sendsID, AID,  SKID, and current session key  SEK to the new member through a secure channel.


## 2.3. Encryption/Decryption Algorithms

When a group coordinator is going to multicast a message, he can use a different bit-assignment to assign specific members to decrypt the message. Then, he has to run the Quine-McCluskey algorithm to minimize all group members’ IDs. The IDs are compared in pairs and reduced until there is no pair with only one bit different. The irreducible IDs are taken as attributes for encryption:Si, where 1≤i≤m and m denotes the number of irreducible IDs. After the coordinator runs the encryption algorithm for each attribute, he generates the encrypted messages for multicast: ENCParams,MK,S1,M, ENCParams,MK,S2,M,…,ENCParams,MK,Sm,M. For example, a group coordinator is going to multicast three members whose IDs are 001001, 001011, and 111000, respectively. After minimization through Quine-McCluskey algorithm, the IDs are reduced as 111000 and 0010x1, where x denotes a negligible bit. Next, the coordinator maps the reduced IDs with LB as attributes S1 and S2. Consider S1={B0,B2-,B3,B4-,B5-} and S2={B0-,B1-,B2-,B3,B4,B5}.With the attributes, the coordinator runs the encryption algorithmENCParams,MK,Si,M in detailed steps as follows:(1)
convertingSi’s LB into PB,(2)
calculatingSumSi=∑Bi∈SipBi,(3)
generating a random valuetSi∈Zq∗,(4)
calculatingC0Si=Me(g,g)αtSiSumSi,(5)
calculatingC1Si=gβtSiSumSi,(6)
calculatingC2Si=gtSi,(7)
generating a ciphertextCTSi={Si,C0Si,C1Si,C2Si}.After group members receive the encrypted messages, they use their private key and the public parameter to run the decryption algorithm, DEC(Params,SK,CTSi):(1)
The group member verifies whetherCTSi’s Si matches his own attribute AID. If the two match, the member proceeds to the next step. If they do not match, the decryption algorithm ends.(2)
He convertsSi’s LB into PB and calculates the sum: F=∏AID∈SigγpBi=gγ∑AID∈SipBi=gγSumSi.(3)
He calculatesA1=eC1Si,D=e(gβtSiSumSi,gα+γ/β)=e(g,g)α+γtSiSumSi.(4)
He calculatesA2=eC2Si,F=e(gtSi,gγSumSi)=e(g,g)γtSiSumSi.(5)
He calculatesA3=A1/A2=e(g,g)αtSiSumSi. C0Si/A3 = Me(g,g)αtSiSumSi/e(g,g)αtSiSumSi=M.


## 2.4. Key-Update Stage

When a new member joins a group, the group coordinator generates a new group keySEK′ and uses the previous group key SEK to encrypt SEK′ to the new member. Then, he sends ID, AID, SKID, and SEK to the new member through a secure channel. If a member leaves a group, the rekeying process will be divided into two parts: the group coordinator and the group member.The group coordinator has to run the following steps:(1)
Generating a random valueα′∈Zq∗.(2)
Updating his master keyMK={β,gα′,gβ,eg,gα′,LB,PB}.(3)
Generating a rekeying messageKU=g(α′-α)/β.(4)
Running Quine-McCluskey algorithm to minimize the remaining members’ IDs until there arem irreducible IDs; these IDs are taken as attributes Si,  1≤i≤m.(5)
Using each attribute to run the encryption algorithm ENC(Params,MK,Si,M).After receiving the ciphertext, the group members run the following steps:(1)
Performing the decryption algorithm DEC(Params, SK,CTSi) and retrieving KU=M.(2)
MultiplyingKU by his private key’s D and obtaining D′, D′=KU·D=gα′-α/β·gα+γ/β=gα′+γ/β.(3)
Updating his session keySEK′=H1(KU).


## 3. Security Issues in EGK

### 3.1. Malicious Member and Man-in-the-Middle Attack

In EGK, a malicious member may decrypt the group coordinator’s message and send the forged message to the members who are associated with the same attributes. The victim members may update their keys and consequently cause desynchronization with the coordinator. Thus, the group coordinator is replaced and the malicious member plays the man in the middle. He takes control of the group. Detailed steps are as follows.A malicious member decryptsCTSi, a valid ciphertext of earlier sessions. He calculates F, A1, A2, and A3:(1)
He retrievese(g,g)αtSiSumSi from CTSi as A3; that is, A3=e(g,g)αtSiSumSi.(2)
He generates a random valuex and requires ∃α2∈Zq∗, so that x=(α2-α)/β; that is, xβ=α2-α. He also forges a rekeying message M′=gx.(3)
He multipliesM′ by A3 and the result is C0′=M′e(g,g)αtSiSumSi.(4)
He sends a forged ciphertextCTSi′:{Si,C0Si′,C1Si,C2Si}.Therefore, the malicious member can bypass the encryption algorithm ENC and sends a forged ciphertextCTSi′ without the group coordinator’s master key MK. After receiving CTSi′, the members run the decryption algorithm DEC. Detailed steps are as follows:(1)
CalculatingF=∏AID∈SigγPBi=gγ∑AID∈SiPBi=gγSumSi.(2)
CalculatingA1=eC1Si,D=e(g,g)α+γtSiSumSi.(3)
CalculatingA2=eC2Si,F=e(g,g)γtSiSumSi.(4)
CalculatingA3=A1/A2=e(g,g)αtSiSumSi.(5)
CalculatingC0Si′/A3 = M′e(g,g)αtSiSumSi/e(g,g)αtSiSumSi=M′.After decryption, they retrieve the rekeying messageM′=g(α2-α′)/β and process to rekey themselves. They calculate D′=D·M′=g(α2+γ)/β and then calculate the current session key SEK′=H(M′).Under such MITM attacks, the compromised members’ private keys becomeD=gα2+γ/β, which is desynchronous with their group coordinator’s gα′ in his master key MK. Here, we assume that the group coordinator sends a new rekeying message KU=M=gα′′-α′/β, uses Quine-McCluskey algorithm to minimize the members’ IDs until there are n irreducible IDs and their attributes are Si,  1≤i≤n, and multicasts the ciphertext to each member ENCParams,MK,S1,M, ENCParams,MK,S2,M,…,ENCParams,MK,Sn,M. The compromised members receive their ciphertext and run the following steps for decryption:(1)
Calculation ofF=∏AID∈SigγpBi=gγ∑AID∈SipBi=gγSumSi.(2)
Calculation ofA1=eC1Si,D=e(g,g)α2+γtSiSumSi.(3)
Calculation ofA2=eC2Si,F=e(g,g)γtSiSumSi.(4)
Calculation ofA3=A1/A2=e(g,g)α2tSiSumSi.(5)
Calculation ofC0Si/A3 = Me(g,g)α′tSiSumSi/e(g,g)α2tSiSumSi.After the division in step (5), the compromised members are unable to retrieve the key-update messageM. However, the malicious member can repeat the same rekeying process and successfully update the group’s private keys and session key. Then, the malicious member is able to replace the coordinator and take control of the group.


### 3.2. Full Modification of Group Coordinator’s Ciphertext

A malicious member may modify the whole ciphertext, exceptSi, in the following steps:(1)
CalculatingB1Si=eC1Si,M=egβtSiSumSi,gα′-α/β=e(g,g)(α′-α)tSiSumSi.(2)
CalculatingB2Si=C0Si·B1/M=e(g,g)αtSiSumSi·e(g,g)α′-αtSiSumSi=e(g,g)α′tSiSumSi.(3)
CalculatingB3Si=(B2Si)x=e(g,g)α′tSiSumSi·(α2-α′/β)=e(g,g)(α2-α′α′tSiSumSi)/β.(4)
MultiplyingM′ by B3Si to forge C0Si′=M′·B3Si=M′e(g,g)(α2-α′α′tSiSumSi)/β.(5)
CalculatingC1Si′=(C1Si)x=(C1Si)(α2-α′)/β=g(α2-α′)tSiSumSi.(6)
CalculatingC2Si′=(C2Si)x=(C2Si)(α2-α′)/β=g(α2-α′tSi)/β.(7)
Sending the forged messageCTSi′: {Si,C0Si′,C1Si′,C2Si′}.After receivingCTSi′, the group members run the decryption algorithm DEC(Params,SK,CTSi):(1)
The group members verify whether the receivedSi matches their own AID. If the two are verified, they proceed to the next step. Otherwise, they end the algorithm.(2)
They convert theSi-associated LB into PB and then calculate the sum F=∏AID∈SigγpBi=gγ∑AID∈SipBi=gγSumSi.(3)
They calculateF=∏AID∈SigγpBi=gγ∑AID∈SipBi=gγSumSi.(4)
They calculateA1=eC1Si′,D=e(g(α2-α′)tSiSumSi,g(α′+γ)/β)=e(g,g)((α2-α′)α′+γtSiSumSi)/β.(5)
They calculateA2=eC2Si′,F=eg(α2-α′tSi)/β,gγSumSi=e(g,g)((α2-α′)γtSiSumSi)/β.(6)
They calculateA3=A1/A2=e(g,g)α2-α′α′+γtSiSumSi/β/e(g,g)((α2-α′)γtSiSumSi)/β=e(g,g)(α2-α′)(α′+γtSi·SumSi-α2-α′γtSiSumSi)/β=e(g,g)((α2-α′)α′tSiSumSi)/β.(7)
They calculateC0Si′/A3 = M′e(g,g)(α2-α′α′tSiSumSi)/β/e(g,g)((α2-α′)α′tSiSumSi)/β = M′.After the decryption procedure, they retrieveM′=g(α2-α′)/β, calculate D′=D·M′=g(α2+γ)/β, and update their current session key SEK′=H(M′).In EGK, even though a malicious member is unable to decrypt his group coordinator’s ciphertext, he can forge a message and then try the steps of Sections3.1 and 3.2. Maybe some members are able to decrypt two ciphertexts, for example, Si and Sj, but they can still receive the forged message. Since they do not verify the sender, they just retrieve M′ and update their keys and hence the desynchronization between them and their group coordinator.


## 3.1. Malicious Member and Man-in-the-Middle Attack

In EGK, a malicious member may decrypt the group coordinator’s message and send the forged message to the members who are associated with the same attributes. The victim members may update their keys and consequently cause desynchronization with the coordinator. Thus, the group coordinator is replaced and the malicious member plays the man in the middle. He takes control of the group. Detailed steps are as follows.A malicious member decryptsCTSi, a valid ciphertext of earlier sessions. He calculates F, A1, A2, and A3:(1)
He retrievese(g,g)αtSiSumSi from CTSi as A3; that is, A3=e(g,g)αtSiSumSi.(2)
He generates a random valuex and requires ∃α2∈Zq∗, so that x=(α2-α)/β; that is, xβ=α2-α. He also forges a rekeying message M′=gx.(3)
He multipliesM′ by A3 and the result is C0′=M′e(g,g)αtSiSumSi.(4)
He sends a forged ciphertextCTSi′:{Si,C0Si′,C1Si,C2Si}.Therefore, the malicious member can bypass the encryption algorithm ENC and sends a forged ciphertextCTSi′ without the group coordinator’s master key MK. After receiving CTSi′, the members run the decryption algorithm DEC. Detailed steps are as follows:(1)
CalculatingF=∏AID∈SigγPBi=gγ∑AID∈SiPBi=gγSumSi.(2)
CalculatingA1=eC1Si,D=e(g,g)α+γtSiSumSi.(3)
CalculatingA2=eC2Si,F=e(g,g)γtSiSumSi.(4)
CalculatingA3=A1/A2=e(g,g)αtSiSumSi.(5)
CalculatingC0Si′/A3 = M′e(g,g)αtSiSumSi/e(g,g)αtSiSumSi=M′.After decryption, they retrieve the rekeying messageM′=g(α2-α′)/β and process to rekey themselves. They calculate D′=D·M′=g(α2+γ)/β and then calculate the current session key SEK′=H(M′).Under such MITM attacks, the compromised members’ private keys becomeD=gα2+γ/β, which is desynchronous with their group coordinator’s gα′ in his master key MK. Here, we assume that the group coordinator sends a new rekeying message KU=M=gα′′-α′/β, uses Quine-McCluskey algorithm to minimize the members’ IDs until there are n irreducible IDs and their attributes are Si,  1≤i≤n, and multicasts the ciphertext to each member ENCParams,MK,S1,M, ENCParams,MK,S2,M,…,ENCParams,MK,Sn,M. The compromised members receive their ciphertext and run the following steps for decryption:(1)
Calculation ofF=∏AID∈SigγpBi=gγ∑AID∈SipBi=gγSumSi.(2)
Calculation ofA1=eC1Si,D=e(g,g)α2+γtSiSumSi.(3)
Calculation ofA2=eC2Si,F=e(g,g)γtSiSumSi.(4)
Calculation ofA3=A1/A2=e(g,g)α2tSiSumSi.(5)
Calculation ofC0Si/A3 = Me(g,g)α′tSiSumSi/e(g,g)α2tSiSumSi.After the division in step (5), the compromised members are unable to retrieve the key-update messageM. However, the malicious member can repeat the same rekeying process and successfully update the group’s private keys and session key. Then, the malicious member is able to replace the coordinator and take control of the group.


## 3.2. Full Modification of Group Coordinator’s Ciphertext

A malicious member may modify the whole ciphertext, exceptSi, in the following steps:(1)
CalculatingB1Si=eC1Si,M=egβtSiSumSi,gα′-α/β=e(g,g)(α′-α)tSiSumSi.(2)
CalculatingB2Si=C0Si·B1/M=e(g,g)αtSiSumSi·e(g,g)α′-αtSiSumSi=e(g,g)α′tSiSumSi.(3)
CalculatingB3Si=(B2Si)x=e(g,g)α′tSiSumSi·(α2-α′/β)=e(g,g)(α2-α′α′tSiSumSi)/β.(4)
MultiplyingM′ by B3Si to forge C0Si′=M′·B3Si=M′e(g,g)(α2-α′α′tSiSumSi)/β.(5)
CalculatingC1Si′=(C1Si)x=(C1Si)(α2-α′)/β=g(α2-α′)tSiSumSi.(6)
CalculatingC2Si′=(C2Si)x=(C2Si)(α2-α′)/β=g(α2-α′tSi)/β.(7)
Sending the forged messageCTSi′: {Si,C0Si′,C1Si′,C2Si′}.After receivingCTSi′, the group members run the decryption algorithm DEC(Params,SK,CTSi):(1)
The group members verify whether the receivedSi matches their own AID. If the two are verified, they proceed to the next step. Otherwise, they end the algorithm.(2)
They convert theSi-associated LB into PB and then calculate the sum F=∏AID∈SigγpBi=gγ∑AID∈SipBi=gγSumSi.(3)
They calculateF=∏AID∈SigγpBi=gγ∑AID∈SipBi=gγSumSi.(4)
They calculateA1=eC1Si′,D=e(g(α2-α′)tSiSumSi,g(α′+γ)/β)=e(g,g)((α2-α′)α′+γtSiSumSi)/β.(5)
They calculateA2=eC2Si′,F=eg(α2-α′tSi)/β,gγSumSi=e(g,g)((α2-α′)γtSiSumSi)/β.(6)
They calculateA3=A1/A2=e(g,g)α2-α′α′+γtSiSumSi/β/e(g,g)((α2-α′)γtSiSumSi)/β=e(g,g)(α2-α′)(α′+γtSi·SumSi-α2-α′γtSiSumSi)/β=e(g,g)((α2-α′)α′tSiSumSi)/β.(7)
They calculateC0Si′/A3 = M′e(g,g)(α2-α′α′tSiSumSi)/β/e(g,g)((α2-α′)α′tSiSumSi)/β = M′.After the decryption procedure, they retrieveM′=g(α2-α′)/β, calculate D′=D·M′=g(α2+γ)/β, and update their current session key SEK′=H(M′).In EGK, even though a malicious member is unable to decrypt his group coordinator’s ciphertext, he can forge a message and then try the steps of Sections3.1 and 3.2. Maybe some members are able to decrypt two ciphertexts, for example, Si and Sj, but they can still receive the forged message. Since they do not verify the sender, they just retrieve M′ and update their keys and hence the desynchronization between them and their group coordinator.


## 4. Secure Key Distribution Scheme for Multicast Communication

### 4.1. Initial Stage

At this stage a group coordinator creates a multicast group withN maximum members, generates system parameters G0,G1,q,g,ande, defines two hash functions H1 and H2, generates three random values α,βandt, requires α,β,t∈Zq∗, sets the length of ID as n=log⁡N, creates 2log2⁡N bit-assignment sets LB={B0,B0-,B1,B1-,…,Bn-1,Bn-1-}, where Bi denotes that the ith bit of ID is 1 and Bi- denotes that the ith bit of ID is 0, and creates sets of bit-assignment secrets PB={pB0,pB0-,sB1,pB1-,…,pBn-1,pBn-1-}, where pBi, pBi-∈Zq. PB maps LB. That is, pB0 maps B0, pB0- maps B0-, and so on. Further, a group coordinator generates his master key MK={β,t,gα,gβ,e(g,g)α,LB,PB} and the public parameter Params={G0,e,g,Ppub,H1,H2}, where Ppub=gt.


### 4.2. Key Distribution

When a new member joins the group, the group coordinator assigns a unique ID to the member and associates him with an attributeAID. Then, the group coordinator runs KeyGen(MK,AID) to generate a key:(1)
He generates a random valueγ∈Zq∗.(2)
He calculatesD=gα+γ/β.(3)
He usesAID to compute ∀Bi∈AID:DB=gγBi.(4)
He mapsPB with LB, ∀Bi∈AID=gγpBi.(5)
He generates a private keySKID={D=gα+γ/β,∀Bi∈AID:DB=gγpBi}.At last, the group coordinator multicasts ID, AID, SKID, and current session key SEK to the new member through a secure channel.


### 4.3. Encryption and Decryption Algorithm

When a group coordinator needs to multicast his group, he assigns a unique set of bit-assignment to each group member, so that each member is able to decrypt their ciphertext. Also, the coordinator uses the Quine-McCluskey algorithm to minimize remaining members’ IDs and then calculates attributesSi. He runs ENC to encrypt Si and members run DEC to decrypt it.The group coordinator runs ENC(Params,MK,Si,M) that(1)
calculatesh=H2(M),(2)
converts theSi-associated LB into PB,(3)
calculatesSumSi=∑Bi∈SipBi,(4)
calculatesC0Si=Me(h,g)αtSumSi,(5)
calculatesC1Si=hβtSumSi,(6)
calculatesC2Si=ht,(7)
generatesCTSi: {Si,C0Si,C1Si,C2Si}.After receiving the ciphertext, group members verify whether their ownAID matches Si’s bit-assignment. If verified, they run the decryption algorithm DEC(Params,SK,CTSi). Besides, during decryption, they have to check if the sender of M is their group coordinator. Steps are as follows:(1)
Conversion of theSi-associated LB into PB.(2)
CalculatingF=∏AID∈SigγpBi=gγ∑AID∈SipBi=gγSumSi.(3)
CalculatingA1=eC1Si,D=e(h,g)α+γtSumSi.(4)
CalculatingA2=eC2Si,F=e(h,g)γtSumSi.(5)
CalculatingA3=A1/A2=e(h,g)αtSumSi.(6)
DividingC0Si by A3 and the result is M = C0Si/A3.(7)
Calculatingh=H2M.(8)
Verifying ifeh,Ppub=eh,gt=e(C2Si,g).


### 4.4. Key-Update Stage

If a new member joins a group, the group coordinator generates a new session keySEK′ and uses the previous session key SEK to encrypt it to his group members. Also, through a secure channel, the coordinator multicasts ID, AID, SKID, and SEK to the members. If a member leaves a group, the coordinator and his members proceed to different steps.Group coordinator performs the following:(1)
He generates a random valueα′∈Zq∗.(2)
He updates his master keyMK=β,gα′,gβ,eg,gα′,LB,PB.(3)
He generates a rekeying messageKU=g(α′-α)/β.(4)
He uses the Quine-McCluskey algorithm to minimize remaining members’ IDs until there arem irreducible IDs and these IDs are taken as attributes Si, 1≤i≤m.(5)
He runs ENC(Params,MK,Si,M) for each attribute.Group members perform the following:(1)
After receiving the ciphertext, each group member runs DEC(Params,SK,CTSi) and retrieves M=KU.(2)
They multiplyKU by D and the result is D′=KU·D=g(α′-α)/β·gα+γ/β=g(α′+γ)/β.(3)
They update their session keySEK′=H1(KU).


## 4.1. Initial Stage

At this stage a group coordinator creates a multicast group withN maximum members, generates system parameters G0,G1,q,g,ande, defines two hash functions H1 and H2, generates three random values α,βandt, requires α,β,t∈Zq∗, sets the length of ID as n=log⁡N, creates 2log2⁡N bit-assignment sets LB={B0,B0-,B1,B1-,…,Bn-1,Bn-1-}, where Bi denotes that the ith bit of ID is 1 and Bi- denotes that the ith bit of ID is 0, and creates sets of bit-assignment secrets PB={pB0,pB0-,sB1,pB1-,…,pBn-1,pBn-1-}, where pBi, pBi-∈Zq. PB maps LB. That is, pB0 maps B0, pB0- maps B0-, and so on. Further, a group coordinator generates his master key MK={β,t,gα,gβ,e(g,g)α,LB,PB} and the public parameter Params={G0,e,g,Ppub,H1,H2}, where Ppub=gt.


## 4.2. Key Distribution

When a new member joins the group, the group coordinator assigns a unique ID to the member and associates him with an attributeAID. Then, the group coordinator runs KeyGen(MK,AID) to generate a key:(1)
He generates a random valueγ∈Zq∗.(2)
He calculatesD=gα+γ/β.(3)
He usesAID to compute ∀Bi∈AID:DB=gγBi.(4)
He mapsPB with LB, ∀Bi∈AID=gγpBi.(5)
He generates a private keySKID={D=gα+γ/β,∀Bi∈AID:DB=gγpBi}.At last, the group coordinator multicasts ID, AID, SKID, and current session key SEK to the new member through a secure channel.


## 4.3. Encryption and Decryption Algorithm

When a group coordinator needs to multicast his group, he assigns a unique set of bit-assignment to each group member, so that each member is able to decrypt their ciphertext. Also, the coordinator uses the Quine-McCluskey algorithm to minimize remaining members’ IDs and then calculates attributesSi. He runs ENC to encrypt Si and members run DEC to decrypt it.The group coordinator runs ENC(Params,MK,Si,M) that(1)
calculatesh=H2(M),(2)
converts theSi-associated LB into PB,(3)
calculatesSumSi=∑Bi∈SipBi,(4)
calculatesC0Si=Me(h,g)αtSumSi,(5)
calculatesC1Si=hβtSumSi,(6)
calculatesC2Si=ht,(7)
generatesCTSi: {Si,C0Si,C1Si,C2Si}.After receiving the ciphertext, group members verify whether their ownAID matches Si’s bit-assignment. If verified, they run the decryption algorithm DEC(Params,SK,CTSi). Besides, during decryption, they have to check if the sender of M is their group coordinator. Steps are as follows:(1)
Conversion of theSi-associated LB into PB.(2)
CalculatingF=∏AID∈SigγpBi=gγ∑AID∈SipBi=gγSumSi.(3)
CalculatingA1=eC1Si,D=e(h,g)α+γtSumSi.(4)
CalculatingA2=eC2Si,F=e(h,g)γtSumSi.(5)
CalculatingA3=A1/A2=e(h,g)αtSumSi.(6)
DividingC0Si by A3 and the result is M = C0Si/A3.(7)
Calculatingh=H2M.(8)
Verifying ifeh,Ppub=eh,gt=e(C2Si,g).


## 4.4. Key-Update Stage

If a new member joins a group, the group coordinator generates a new session keySEK′ and uses the previous session key SEK to encrypt it to his group members. Also, through a secure channel, the coordinator multicasts ID, AID, SKID, and SEK to the members. If a member leaves a group, the coordinator and his members proceed to different steps.Group coordinator performs the following:(1)
He generates a random valueα′∈Zq∗.(2)
He updates his master keyMK=β,gα′,gβ,eg,gα′,LB,PB.(3)
He generates a rekeying messageKU=g(α′-α)/β.(4)
He uses the Quine-McCluskey algorithm to minimize remaining members’ IDs until there arem irreducible IDs and these IDs are taken as attributes Si, 1≤i≤m.(5)
He runs ENC(Params,MK,Si,M) for each attribute.Group members perform the following:(1)
After receiving the ciphertext, each group member runs DEC(Params,SK,CTSi) and retrieves M=KU.(2)
They multiplyKU by D and the result is D′=KU·D=g(α′-α)/β·gα+γ/β=g(α′+γ)/β.(3)
They update their session keySEK′=H1(KU).


## 5. Security Analysis

### 5.1. Malicious Member and MITM Attack

We assume a malicious member is in a group coordinator’s communication group. He receives the latest rekeying message and then forges a fake one to other group members. The forged message may arrive before the group coordinator’s rekeying message and successfully rekey the members. By this, the malicious member can cause asynchrony between group members and their coordinator.After receiving group coordinator’sCTSi, the malicious member retrieves Si, C0Si, C1Si, and C2Si and calculates A1, A2, and A3. He tries to forge a message C0Si′=M′·A3 and sends the fake ciphertext CTSi′={Si,C0Si′,C1Si,C2Si} to other members. Following the decryption algorithm, the members decrypt the fake ciphertext CTSi′ and retrieve M′. According to the 7th step of decryption, they calculate h=H2M′. At the 8th step, they calculate eh,Ppub=eh,gt, which does not match e(C2Si,g), hence an unsuccessful attack.


### 5.2. Malicious Member and Asynchrony

We assume a malicious member belongs to a group coordinator’s communication group. He is able to decrypt and retrieve the coordinator’s rekeying message. He forges a rekeying message and sends it to other group members.CTSi is the previous ciphertext from the group coordinator: (1)CTSi:Si,C0Si=Meh,gαtSumSi,C1Si=hβtSumSi,C2Si=ht,M=KU=gα′+α/β.WithCTSi and M, the group members have updated their private keys D=g(α′+γ)/β. The malicious member forges a rekeying message M′. Since he has had H2, he uses it to calculate H2(M′) and tries to generate C0Si′=M′e(H2M′,g)α′tSumSi. He has to use CTSi to run the following steps:(1)
Summing up the previous attributesSi; thus, F=∏AID∈SigγpB=gγ∑AID∈SipB=gγSumSi.(2)
CalculatingA1′=eC1Si,D=e(H2(M),g)α′+γtSumSi.(3)
CalculatingA2=eC2Si,F=e(H2(M),g)γtSumSi.(4)
CalculatingA3′=A1′/A2=e(H2(M),g)α′tSumSi.SinceA3′=e(H2(M),g)α′tSumSi, it does not match e(H2(M′),g)α′tSumSi.


### 5.3. Backward Secrecy

If a group coordinator removes a member from the group, he updates his own master key and runs the encryption algorithm ENC to generate a rekeying messageKU to the remaining members. After receiving KU, the members update their private keys SK·D′=SK·D·KU and calculate a new session key SEK′=H2(KU). Because the removed member does not have KU, he cannot calculate a new private key and session key.


### 5.4. Forward Secrecy

When a new member joins a group, the group coordinator generates a new session keySEK′ and uses the previous session key SEK to encrypt SEK′ to his group members. Then, he sends SEK′ to the new member through a secure channel. In doing so, the new member is unable to access previous messages.


## 5.1. Malicious Member and MITM Attack

We assume a malicious member is in a group coordinator’s communication group. He receives the latest rekeying message and then forges a fake one to other group members. The forged message may arrive before the group coordinator’s rekeying message and successfully rekey the members. By this, the malicious member can cause asynchrony between group members and their coordinator.After receiving group coordinator’sCTSi, the malicious member retrieves Si, C0Si, C1Si, and C2Si and calculates A1, A2, and A3. He tries to forge a message C0Si′=M′·A3 and sends the fake ciphertext CTSi′={Si,C0Si′,C1Si,C2Si} to other members. Following the decryption algorithm, the members decrypt the fake ciphertext CTSi′ and retrieve M′. According to the 7th step of decryption, they calculate h=H2M′. At the 8th step, they calculate eh,Ppub=eh,gt, which does not match e(C2Si,g), hence an unsuccessful attack.


## 5.2. Malicious Member and Asynchrony

We assume a malicious member belongs to a group coordinator’s communication group. He is able to decrypt and retrieve the coordinator’s rekeying message. He forges a rekeying message and sends it to other group members.CTSi is the previous ciphertext from the group coordinator: (1)CTSi:Si,C0Si=Meh,gαtSumSi,C1Si=hβtSumSi,C2Si=ht,M=KU=gα′+α/β.WithCTSi and M, the group members have updated their private keys D=g(α′+γ)/β. The malicious member forges a rekeying message M′. Since he has had H2, he uses it to calculate H2(M′) and tries to generate C0Si′=M′e(H2M′,g)α′tSumSi. He has to use CTSi to run the following steps:(1)
Summing up the previous attributesSi; thus, F=∏AID∈SigγpB=gγ∑AID∈SipB=gγSumSi.(2)
CalculatingA1′=eC1Si,D=e(H2(M),g)α′+γtSumSi.(3)
CalculatingA2=eC2Si,F=e(H2(M),g)γtSumSi.(4)
CalculatingA3′=A1′/A2=e(H2(M),g)α′tSumSi.SinceA3′=e(H2(M),g)α′tSumSi, it does not match e(H2(M′),g)α′tSumSi.


## 5.3. Backward Secrecy

If a group coordinator removes a member from the group, he updates his own master key and runs the encryption algorithm ENC to generate a rekeying messageKU to the remaining members. After receiving KU, the members update their private keys SK·D′=SK·D·KU and calculate a new session key SEK′=H2(KU). Because the removed member does not have KU, he cannot calculate a new private key and session key.


## 5.4. Forward Secrecy

When a new member joins a group, the group coordinator generates a new session keySEK′ and uses the previous session key SEK to encrypt SEK′ to his group members. Then, he sends SEK′ to the new member through a secure channel. In doing so, the new member is unable to access previous messages.


## 6. Performance Evaluation

In our secure multicast group communication protocol, a group coordinator has to store a set of a public parameter, a master key, and a session key, that is,{Params,MK,SEK}. It consists of five real numbers, two hash functions, one mapping function, and two sets of bit-assignments.As for our computational load, a group coordinator calculates one hash function, one mapping, and three exponentials when running the encryption algorithm. When a group member decrypts a ciphertext, the decryption algorithm requires four mappings and one hash. As listed in Table1, if there are m attributes after the minimization, our key-updating requires m times of encryption, that is, m hash functions, m mappings, and 3m exponentials.Table 1
Comparison of computational load.
EGK
Our scheme
Encryption
Decryption
Encryption
Decryption
Coordinator
(
e
+
3
E
p
)
m
0
(
h
+
e
+
3
E
p
)
m
0
Member
0
3e
0
h
+
4
eCompared with EGK, our encryption algorithm requires sender verification; therefore, it needs to compute one more hash. And our decryption algorithm requires group members to verify messages, so it needs to compute one more hash and one more mapping.Take Facebook as an example. We assume that it uses our scheme; its member limit is 5000 (N=5000); each user is a group coordinator; each user is also a member of his friends’ groups. Thus, each user has a master key, (N+1) public parameters, and (N+1) session keys, as shown in Table 2.Table 2
Storage.
Master key
Public parameter
Session key
Coordinator
1
0
1
Member
0
N
N
Total
1
N
N
+
1In our scheme, a group coordinator’s communication load is in linear increase with the minimized attributes. If there arem attributes after minimization, he has to generate m rekeying messages. Each message consists of one Si and three variables C0Si, C1Si, and C2Si (see Table 3).Table 3
Communication loads for rekeying.
EGK
Our scheme
Coordinator
(Si,C0Si,C1Si,C2Si)m
(Si,C0Si,C1Si,C2Si)mDespite having one more hash and one more public parameter compared to EGK, our system’s storage requirement is the same as EGK’s. And the two schemes’ communication loads are also the same.


## 7. Conclusion

In this paper, we analyze Zhou and Huang’s key distribution scheme for multicast group communication and find it prone to MITM and desynchronization attacks. These security issues can cause a group coordinator to lose the control over his group and fail to rekey his members. We propose a scheme to enhance the security of EGK. Our scheme guarantees forward and backward secrecy, prevents message modification and forgery during rekeying, requires sender verification, and therefore prevents MITM attacks in group communication.We hope our secure multicast group communication scheme can be applied to cloud services and social networking sites, so that users can enjoy these services in a secure environment without further loads. And users’ privacy and data integrity can also be secured.



---

*Source: 2750268-2016-03-23.xml*