Dual encryption protocol for scalable secure group communication6263435Abstract A logical tree structure and method for managing membership in a multicast group provides scalability and security from internal attacks. The structure defines key groups and subgroups, with each subgroup having a subgroup manager. Dual encryption allows the sender of the multicast data to manage distribution of a first set of encryption keys whereas the individual subgroup managers manage the distribution of a second set of encryption keys. The two key sets allow the sender to delegate much of the group management responsibilities without compromising security because a key from each set is required to access the multicast data. Security is further maintained via a method in which subgroup managers can be either member subgroup managers or participant subgroup managers. Access to both keys is provided to member subgroup managers whereas access to only one key is provided to participant subgroup managers. Nodes can be added without the need to generate a new encryption key at the top level which provides improved scalability. Claims What is claimed is: Description BACKGROUND AND SUMMARY OF THE INVENTION
TABLE 1
Notation Used in this Paper
s Sender
SGM Subgroup manager
LS.sub.i Local subgroup key managed by SGM i
M.sub.i Set of subgroup members of SGM i
.kappa..sub.i Set of nodes of the key distribution tree in the key group i
KEK.sub.i Key encrypting key corresponding to the key group
DEK Data encryption key used in encrypting multicast data
CC.sub.x Capability Certificate of x
AC.sub.x Authorization Certificate issued to x by s
KU.sub.x Public-key of x
KR.sub.x Private-key of x
EP Public-key encryption
ES Secret-key encryption
HV Hash value
x.fwdarw.y: w x sends "w" to y
FIG. 2 illustrates an exemplary logical tree structure in accordance with the invention. In this regard, the tree structure illustrated is merely exemplary (other tree structures are possible). Moreover, the tree structure illustrated is a logical tree structure; that is, the actual physical connections among nodes, and the route a communication would take are not restricted to this logical tree structure. The logical tree structure 10 thus serves as a framework or structure for managing membership in the multicast group and for managing access to multicast data. As depicted in FIG. 2, members of the multicast group are nodes of a tree. The top node 12 is the sender node. The sender node sends multicast data to one or more end-host nodes, depending on their authorization. The top node (sender) 12 has, in this illustration, three child nodes 14, 16 and 18. Each of these child nodes may define what we call a key group. In FIG. 2, child nodes 14 and 18, themselves, have children; node 16 is childless. Thus in this illustration there are two key groups, one containing node 14 and its children and one containing node 18 and its children. In the description that follows, we refer to the key group containing node 14 as key group 1. Key group 1 is shown in dotted lines designated by reference numeral 20. Logical tree 10 forms part of a key distribution tree as will be more fully explained below. The key distribution tree can be either an extension of a multicast data distribution tree or a virtual tree at the application level. In addition to the key groups, described above, the key distribution tree also defines what we call subgroups. Subgroups are represented by non-leaf nodes and their children. In FIG. 2, the leaf nodes have been designated as end-host members h.sub.i. In FIG. 2 the non-leaf nodes have been designated as either subgroup manager (SGM) participants p.sub.i or SGM members g.sub.i. Thus FIG. 2 illustrates four subgroups corresponding to the following SGM's: p.sub.1, g.sub.2, g.sub.1 and p.sub.2. For illustration purposes, lower case p.sub.2 's subgroup is shown in dashed lines at 22. Similar in structure is the top level subgroup shown in dashed lines at 24. The top level subgroup contains at its head the top node (sender node) 12. Each subgroup manager (SGM) is responsible for generating a secret key and sharing it with all the corresponding subgroup members in a secure fashion. For instance, in FIG. 2, p.sub.1 shares the subgroup key LS.sub.p1 with its children, g.sub.2 and h.sub.2. We refer to this key as a local subgroup key. The local subgroup key forms one part of the dual key protocol needed to access encrypted data. The sender node 12 generates another key that we call the key encrypting key or KEK. Sender node 12 generates a top level KEK for each of the key groups. Sender node 12 also generates a local subgroup key for the top level subgroup 24. The KEK's are used to hide data encryption keys from the participants of a multicast group. One KEK is generated for each of the key groups. These keys are distributed to the multicast members by the sender. A KEK is shared by all the nodes in a key group that are members of the multicast group. In this context, it is important to distinguish a member from a participant. Participants assist in enforcing the secure multicast protocol, but they do not have any access to the multicast data. In the exemplary embodiment shown in FIG. 2, there could be at most two key groups, corresponding to each of the sender's children that are also SGM's, namely participant SGM p.sub.1 and member SGM g.sub.1. The end-host member h.sub.1 could belong to either one of the key groups. All members and participants of the multicast group must be aware of the key group they belong to. We delegate the responsibility of propagating this information to the subgroup managers. The sender 12 assigns and distributes key group ID's to the subgroup managers that are members of the top level subgroup. Each SGM disseminates its key group ID to its subgroup members when they join the group. Thus, all the members and participants of the multicast session are aware of the corresponding key group ID. The join protocol, described below, serves as the mechanism for distributing the secret keys in accordance with the dual encryption scheme. Join Protocol Referring to FIG. 4, when a new host H.sub.1 wants to join the secure multicast group, it sends a message to all SGMs of the multicast group as illustrated at 101. The message includes host H.sub.1 's capability certificate 50. After sending its message to all SGMs of the group, host H.sub.1 waits until one of the SGMs answers. In this illustration, SGM g.sub.1 responds that it can handle the additional work load of another member in its subgroup. More specifically, the responding SGM first verifies that the capability certificate is approved or denied. Assuming the certificate is approved, the responding SGM sends a return message comprising its SGM I.D. 52 and its keygroup I.D. 54. In the illustrated example, SGM g.sub.1 responds first. Other SGMs, such as g.sub.2 or g.sub.3 may also respond, or not, depending on whether they can support the additional workload. Host H.sub.1 chooses the first positive response it receives (from SGM g.sub.1) thereby choosing it as its subgroup manager. The enrolling host H.sub.1 then sends a message to the sender S, comprising authentication information about itself, the responding SGM's identity 52 and the corresponding keygroup identity 54. The authentication information may be either in the form of a capability certificate 50, or other identifier used by the sender to consult an access control list (a database of all hosts that can join). The sender S uses the capability certificate 50 to decide whether H.sub.1 is an authorized member of the multicast group. It also checks to see if H.sub.1 has previously requested to join the multicast. This last verification guards against a misbehaving host, trying to join multiple subgroups simultaneously. After the new host's membership is validated, the sender generates message 104, containing a number of items including an authorization certificate 56. The data structure of the presently preferred authorization certificate is shown in FIG. 3. The authorization certificate contains the new host's identity (H.sub.1), the corresponding SGM's identity and the keygroup identity. Sender S.sub.1 signs the certificate with its private key, as illustrated diagrammatically by lock 58. The authorization certificate is an authentic record of the new host's affiliation to the multicast group. Sender S.sub.1 also sends the top level KEK encryption key 60 to the joining host. This KEK corresponds to the keygroup identity that H.sub.1 is now a part of. Sender S.sub.1 signs the top level KEK with its private key, as depicted diagrammatically by lock 62. Then the sender encrypts both authorization certificate 56 and KEK 60 with the host's public key for secrecy. The host's public key is depicted diagrammatically by lock 64. Note that sender S.sub.1 signs the authorization certificate and KEK separately. This allows H.sub.1 to produce the signed authorization certificate without having to disclose the KEK. Sender S.sub.1 updates its multicast membership database with the new host's authorization certificate. The membership database is used when the sender refreshes the KEK's. In the final phase of the join protocol, host H.sub.1 uses its private key to decrypt the sender's message (to unlock lock 64). It further uses the sender's public key to decrypt the KEK 60 and authorization certificate 56 (unlocking locks 62 and 64, respectively). Next, host H.sub.1 issues message 105 to SGM g.sub.1. This message supplies g.sub.1 with the new host's authorization certificate 56. Subgroup manager g.sub.1 then adds the new host to its subgroup members'list. SGM g.sub.1 then changes its subgroup key, signs it (lock 66), encrypts it with H.sub.1 's public key (lock 68) and sends it in message 106 to H.sub.1. The SGM's signature (lock 66) guards against masquerading attacks. The subgroup key, LS key 70, is changed to keep the new host from decrypting multicast data sent before it joined the group. Separately, SGM g.sub.1 multicasts its signed new subgroup key to all its subgroup members, encrypted with the old subgroup key. This is illustrated at step 107. As a result of the above-described procedure, new host H.sub.1 acquires the KEK key 60 and the LS key 70. Both keys are required to decrypt multicast data at host H.sub.1. FIG. 4 has thus illustrated an example of the join protocol. For readers who prefer a more succinct representation, refer to Table 2.
TABLE 2
Steps in the Join Protocol
(1) h.fwdarw.All SGMs: CC.sub.h
(2) g.fwdarw.h: SGM Id (g), Key group Id (.kappa..sub.i)
(3) h.fwdarw.s: CC.sub.h, g, .kappa.i
(4) s.fwdarw.h: EP.sub.KUh [EP.sub.KRs [AC.sub.h ], EP.sub.KRs
[KEK.sub.1 ]]
(5) h.fwdarw.g: AC.sub.h
(6) g.fwdarw.h: EP.sub.KUh [EP.sub.KRg [LS.sub.g ]]
(7) g.fwdarw.M.sub.g : ES.sub.LSg [EP.sub.KRg [LS.sub.g ]]
In view of the foregoing, it should be stressed that authorization certificates serve the important function of eliminating the possibility of an adversary with a valid capability certificate gaining access to all keys managed by the sender and all of the SGMs in the multicast group. In our protocol, the sender checks for duplicate joins by the same host, before issuing an authorization certificate. These certificates authorize the joining host to gain access to only one local subgroup key. Having thus described the join protocol by which a new host may join the secure multicast group, we now describe the join protocol used by subgroup managers. Subgroup managers (SGMs) that are members of the multicast group follow the join protocol described above for hosts. The only change is that the sender updates its SGM database. The join protocol used for SGMs that are merely participants is different, and somewhat more complex. The sender first verifies if the participant SGM is a former member of the multicast group. If the participant SGM is in the membership database, the corresponding KEK needs to be updated. To change a KEK, the sender sends a message to all the members which hold that KEK, asking them to request the new KEK. The members which need the new KEK respond with their authorization certificates. The sender verifies the authorization certificates, and constructs a list of members authorized to receive the updated KEK. The sender then changes the KEK, signs it, and encrypts it with the public keys of all of the members in the list. It then multicasts all the encrypted KEKs to the multicast group. Each member waiting for the new KEK decrypts the encrypted KEK intended for it. Finally, the sender updates its membership database, conforming to the authorization list it compiled above. After the verification process and possible modification of a KEK, the join process of a participant SGM follows the same protocol as described above for member SGMs. The only exception that a participant SGM does not receive a KEK. While the process of changing a KEK is somewhat computationally costly, KEKs need to be changed only when a former member of the multicast group wants to rejoin as a participant SGM. To avoid changing KEKs frequently, an application may deny the join request of a participant SGM if it is still in the membership database. Secure Communication The sender generates a data encryption key (DEK) to be used in a conventional encryption algorithm. In this regard, suitable algorithms can be found in Handbook of Applied Cryptography, A. Menezes, P. Van Oorschot, S. VanStone, CRC Press, 1997; and Network and InternetWork Security, W. Stallings, Prentice-Hall, Inc., 1995. The sender sends the multicast data encrypted with the DEK to the group. Next, the sender computes a one-way hash function of the data and sends the hash value (HV) along with the DEK to multicast members securely. The members also compute the hash value of multicast data and compare it to the HV received, to verify the integrity of the data. While the encrypted multicast data is sent through traditional multicast channels, the DEKs are distributed via the key distribution tree. We use the key distribution tree in FIG. 2 to illustrate the DEK distribution. The sender generates a key distribution packet (ES.sub.LSs [[ES.sub.KEK1 [DEK, HV]], [ES.sub.LSs [ES.sub.KEK2 [DEK, HV]]]), where LS.sub.s is the subgroup key of the top level subgroup. Each of the sender's children decrypts its part of the key distribution packet. Each of them then encrypts its piece of the packet with the subgroup key they manage and multicasts the encrypted DEK to its children. In our example in FIG. 2, P.sub.1 multicasts the encrypted packet that contains ES.sub.LSp1 [ES.sub.KEK1 [DEK, HV]], to g2 and h2. Similarly, other SGMs forward the encrypted DEK to their respective subgroup members. All the members of the multicast group with a local subgroup key and the corresponding KEK acquire the DEK and HV. The DEK is used by the members to decrypt the multicast data and HV is used to verify the integrity of multicast data. Note that the SGMs that are also members of the multicast group will have access to the corresponding KEK. Other SGMs will just participate in the secure multicast protocol by managing their corresponding subgroup key and forwarding the encrypted DEK. Table 3 lists the steps in the DEK distribution protocol. In the table, we assume that there are c key groups and that SGM g.sub.i, which is one of the sender's children, belongs to the key group K.sub.i.
TABLE 3
Steps in the DEK Distribution Protocol
s.fwdarw.M.sub.s : . . . ES.sub.LS.sub.s [ES.sub.KEK.sub.1
[DEK
HV]], . . . , ES.sub.L.sub.S.sub.s [ES.sub.KEK.sub.c [DEK,
HV]]
g.sub.i.fwdarw.M.sub.g.sub.i : . . . ES.sub.LS.sub.g.sub.i
[ES.sub.KEK.sub.i [DEK,HV]]
Leave Protocol The membership of a multicast group member may expire as per the membership duration information in the capability certificate. It is also possible that either the sender or the corresponding SGM may have to expel a misbehaving member. In either case, the ex-member of the multicast session must not be able to decrypt the multicast data. To do that, the corresponding SGM changes the local subgroup key. It then encrypts the new subgroup key with the public keys of each of its children and multicasts that information to them. Each of the children decrypts its part of that message and extracts the updated subgroup key. Revisiting our example in FIG. 2, if the host h.sub.9 leaves the multicast group, the corresponding subgroup manager, p.sub.2 changes the subgroup key and securely sends the new key to the hosts h.sub.8 and h.sub.10 separately. Note that the KEK known to the leaving host need not be changed right away. The sender can periodically change those keys depending on the frequency of hosts rejoining the group. Since any member needs to know both the corresponding subgroup key and the key encrypting key to decrypt the DEK, changing even one of them is sufficient. We list the steps of the leave protocol in Table 4. In the table, we assume that h.sub.i left from SGM g, where M.sub.g ={h.sub.1, h.sub.2, . . . , h.sub.m } and that LS'.sub.g is the new subgroup key.
TABLE 4
Steps in the Leave Protocol
g.fwdarw.M.sub.g : EP.sub.KUh.sub.i [EP.sub.KRg [LS'.sub.g
]],
. . . , EP.sub.KUh.sub.i-1 [EP.sub.KRg LS'.sub.g ]],
EP.sub.KRg [LS'.sub.g ]], EP.sub.KU.sub.i+1 [EP.sub.KRg
[LS'.sub.g ]],
. . . , EP.sub.KUh.sub.m [EP.sub.KRg [LS'.sub.g ]]
Dual encryption of the DEK simplifies the removal of an SGM from the multicast group. All we need to do is to remove the SGM, find a replacement and notify the subgroup members of the change. Note that each SGM is a member of a subgroup managed by its parent. The parent SGM removes the leaving SGM, following a procedure identical to that of removing a member of the multicast group. The sender needs to locate another SGM that replaces the leaving SGM. After finding a replacement, the sender notifies the members of the subgroup managed by the leaving SGM about their new subgroup manager. The sender also updates its lists of SGMs. The new SGM follows the join protocol to become either a participant or a member of the multicast group. After that, it generates the subgroup key and securely distributes that key to its subgroup members. Key Refresh The sender and the SGMs refresh their keys periodically to guard against eavesdropping. To change the subgroup key, a subgroup manager follows the same leave protocol procedure described above. In brief, the SGM changes the key, signs it and encrypts it with the public keys of all the subgroup members. It then locally multicasts the updated subgroup key to its subgroup members. Refreshing KEKs is a complex procedure is expected to be done infrequently. The sender can change a KEK following the mechanism described in join protocol section above. In general, KEKs may be refreshed depending on the frequency of hosts rejoining the multicast group. Tuning the Number of Key Encrypting Keys The number of KEKs can be between zero and the number of SGMs in the top level subgroup. When the number of KEKs is zero all the SGMs automatically receive access to multicast data. The use of a single KEK gives us the capability of denying access of multicast data to SGMs. However, the KEK may need to be refreshed/updated more often since it is shared by all of the members. As the number of KEKs increase the refresh/update frequency decreases. The upper bound to the number of KEKs is the number of SGMs that are also members of the top level subgroup. Notes on Implementing the Dual Encryption Protocol We conclude the description of the dual encryption protocol by a discussion on possible modes of implementation. The first issue involves the construction of the key distribution tree. The hierarchy can be an extension of a reliable multicast tree used in RMTP. In this regard, see S. Paul, K. Sabnani, J. Lin, and S. Bhattacharyya. Reliable Multicast Transport Protocol (RMTP), IEEE Journal on Selected Areas in Communications, 15(3):407421, April 1997. Alternatively, it can be implemented at the application level. In this description of DEP, we designate the sender as the group manager. In reality, it may not be possible for the sender to handle the workload of enforcing a secure multicast protocol. We suggest the use of a trusted third party to manage the secure multicast group in such cases. Next, we discuss the selection of subgroup managers. As described earlier, SGMs can either be routers or hosts in the Internet that are capable of handling the workload of managing a subgroup. Also, an SGM should not actively participate in disrupting the secure multicast protocol. Any router or host which meets these requirements can be chosen as an SGM. The requirements may be stricter if the SGM wants to be a member as well. The membership duration needs to be taken into consideration in this case. Locating the SGMs is the next problem. We suggest the use of anycast to the multicast group as a possible solution. Alternatively, routers in the network may maintain a database of SGMs corresponding to a secure multicast group. Newly joining host may then request the router for the SGM addresses. The number of members in each subgroup and the number of levels in the key distribution tree are other crucial design parameters. Recall that the subgrouping is to avoid the 1 affects n scalability problem. If a subgroup is very large we may run into scalability problems. Also note that all the SGMs translate the encrypted KEKs for their subgroup members. As the number of levels in the key distribution tree increases, the number of translations increase. With increased number of translations the latency in distributing the keys may become significant. While the invention has been described in its presently preferred embodiments, it will be understood that the invention is capable of certain modification and change without departing from the spirit of the invention as set forth in the appended claims.
|
Same subclass Same class Consider this |
||||||||||