Suraksha: An Implementation of Secure Group Communications

Abstract-Many emerging network applications (e.g., teleconference, information services, distributed interactive simulation, and collaborative work) are based upon a group communication model. As a result, securing group communications, i.e., providing confidentiality, authenticity, and integrity of messages delivered between group members, will become a critical networking issue. We formalize the notion of a secure group as a triple (U, K, R) where U denotes a set of users, K a set of keys held by the users, and R a user-key relation. We then introduce key graphs [1] to specify secure groups, with nodes containing information about the users and subgroups. For a special class of key graphs called tree, we present a strategy for securely distributing rekey messages after a join/leave and specify protocols for joining and leaving a secure group. A user-oriented rekeying strategy and join/leave protocol is implemented in a prototype key server we have built. Our implementation of secure group communications provides authentication, confidentiality and integrity of the messages delivered between the group members.

Key words-Confidentiality, group communications, group

key management, key distribution, multicast, privacy, rekeying,

security.

1.0 INTRODUCTION

MOST network applications are based upon the client–server paradigm and make use of unicast (or point-to-point) packet delivery. Many emerging applications, on the other hand, are based upon a group communications model. In particular, they require packet delivery from one or more authorized sender(s) to a large number of authorized receivers. In the Internet, multicast has been used successfully to provide an efficient, best effort delivery service to large groups [2]. We envision that deployment of network applications requiring group communications will accelerate in coming years. As a result, securing group communications, i.e., providing confidentiality, authenticity, and integrity of messages delivered between group members, will become a critical networking issue in the near future.

While the technical issues of securing unicast communications for client–server computing are fairly well understood, the technical issues of securing group communications are not. Conceptually, since every point-to-multipoint communication can be represented as a set of point-to-point communications, the current technology base for securing unicast communications can be extended in a straightforward manner to secure group communications. However, such an extension is not scalable to large groups.

For a more concrete illustration of this point, we outline a typical procedure for securing unicast communications between a client and a server. Initially, the client and server mutually authenticate each other using an authentication protocol or service; subsequently, a symmetric key is created and shared by them to be used for pair wise confidential communications. This procedure can be extended to a group as follows.

Let there be a trusted server, which is given membership information to exercise group access control. When a client wants to join the group, the client and server mutually authenticate using an authentication protocol. Having been authenticated and accepted into the group, each member shares with the server a key, to be called the member's individual key. In this paper, key means a key from a symmetric cryptosystem, such as DES [6], unless explicitly stated otherwise. For group communications, the server distributes to each member a group key to be shared by all members of the group. For a group of members, distributing the group key securely to all members requires messages encrypted with individual keys (a computation cost proportional to group size). Each such message may be sent separately via unicast. Alternatively, the messages may be sent as a combined message to all group members via multicast. Either way, there is a communication cost proportional to group size (measured in terms of the number of messages or the size of the combined message). Observe that for a point-to-point session, the costs of session establishment and key distribution are incurred just once, at the beginning of the session.

A group session, on the other hand, may persist for a relatively long time with members joining and leaving the group. Consequently, the group key should be changed frequently. To achieve a high level of security, the group key should be changed after every join and leave so that a former group member has no access to current communications and a new member has no access to previous communications. It is easy to see that sharing a group key enables confidential communications within a group. In addition to confidentiality, standard techniques such as digital signature and message digest can be used to provide authenticity, integrity, and nonrepudiation.

Let there be a trusted server that creates a new group key after every join and leave. After a join, the new group key can be sent via unicast to the new member (encrypted with its individual key) and via multicast to existing group members (encrypted with the previous group key). Thus, changing the group key securely after a join is not too much work. After a leave, however, the previous group key can no longer be used and the new group key must be encrypted for each remaining group member using its individual key. Thus, we see that changing the group key securely after a leave incurs computation and communication costs proportional to, the same as initial group key distribution. That is, large groups whose members join and leave frequently pose a scalability problem.

This security aspects applied to the group communication is used in a Group Chat application, that allows a large number of users or group members to join and leave the group at any time and hence securely communicate with other members using the keys supplied by the server.

In secured mode of “peer to peer” communicating model unicasting of the secured information has to be done. Then the number of keys to be maintained for this will keep on increasing as the number of users increase. Number of encryptions and decryptions will also increase at both the ends. Key management and space for storing the keys is the major problem with the secured mode of “peer to peer” communication. Considering users wants to communicate as a group can easily solve this. Because of multicasting and group key, key management is easier and space for storing the keys will also be reduced

2.0 SECURE GROUPS

This section deals with secure group, key graph, and user-oriented rekeying strategy. It also deals with join/leave protocol for all user-oriented rekeying strategy.

A secure group is a triple (U, K, R) where:

• U is a finite and nonempty set of users,

• K is a finite and nonempty set of keys,

• R is a binary relation between U and K,

R Ì U × K, called the user-key relation of the secure group. User u has key k if and only if (u, k) is in R. Each secure group has a trusted key server responsible for generating and securely distributing the keys in K to users in the group. Specifically, the key server knows the user set, U and the key set, K and maintains the user–key relation R. Every user in U has a key in K, called its individual key, which is shared only with the key server and is used for pair wise confidential communication with the key server. There is a group key in K, shared by the key server and all users in U. Each user to send messages confidentially to other members of the group can use the group key [1].

2.1 Key Graphs

A key graph is a directed acyclic graph G with two types of nodes: u-nodes representing users and k-nodes representing keys. Each u-node has one or more outgoing edges but no incoming edge. Each k-node has one or more incoming edges. If a k-node has incoming edges only and no outgoing edge, then this k-node is called a root.

Given a key graph G, it specifies a secure group (U, K, R) as follows.

1) There is a one-to-one correspondence between U and the set of u-nodes in G.

2) There is a one-to-one correspondence between K and the set of k-nodes in G.

3) (u, k) is in R if and only if G has a directed path from the u-node that corresponds to u to the k-node that corresponds to k. As an example, the key graph in Fig. 1 specifies the following secure group:

U = {u₁, u₂, u₃, u₄}

K = {k₁, k₂, k₃, k₄, k₁₂, k₂₃₄, k₁₂₃₄}

R = {(u_l, k_l), (u_l, k₁₂), (u_l, k₁₂₃₄), (u₂, k₂), (u₂, k₁₂), (u₂, k₂₃₄), (u₂, k₁₂₃₄), (u₃, k₃), (u₃, k₂₃₄), (u₃, k₁₂₃₄), (u₄, k₄), (u₄, k₂₃₄), (u₄, k₁₂₃₄)}.

Associated with each secure group (U, K, R) are two functions, keyset() and userset(), defined as follows:

keyset(u) = {k | (u, k) Î R}

userset (k) = {u | (u, k) Î R}.

Intuitively, keyset(u) is the set of keys that are held by user u in U, and userset(k) is the set of users that hold key k in K. For examples, referring to the key graph in Fig. 1, we have keyset(u₄) = {k₄, k₂₃₄, k₁₂₃₄} and userset(k₂₃₄) = {u₂, u₃, u₄}.

Generalized definition of function keyset() to any subset U ’ of U, and function userset() to any subset K ’ of K, in a straightforward manner, i.e., keyset(U ') is the set of keys each of which is held by at least one user in U ’, and userset(K ’) is the set of users each of which holds at least one key in K ’.

When a user u leaves a secure group (U, K, R), every key that has been held by u and shared by other users in U should be changed. Let k be such a key. To replace k, the server randomly generates a new key k_new and sends it to every user in userset(k) except u. To do so securely, the server needs to find a subset K ’ of keys such that userset(K ') = userset(k) - {u} and use keys in K ' to encrypt k_new for distribution [1].

2.2 Keying Strategies And Protocols

A user who wants to join (leave) a secure group sends a join (leave) request to the key server, denoted by s. For a join request from user u, we assume that the user selects a user name that is not already present in the group and also a password to identify him/her. Thus a join request initiates an authentication exchange between u and s. If user u is not authorized to join the group, server s sends a join-denied reply to u. If the join request is granted, we assume that the session key distributed as a result of the authentication exchange will be used as the individual key k_uof u. To simplify protocol specifications below, we use the following notation:

s ó u : authenticate u and distribute k_u.

to represent the authentication exchange between server s and user u, and secure distribution of key k_u to be shared by u and s.

After each join or leave, a new secure group is formed. Server s has to update the group's key graph by replacing the keys of some existing k-nodes, deleting some k-nodes (in the case of a leave), and adding some k-nodes (in the case of a join). It then securely sends rekey messages containing new group/subgroup keys to users of the new secure group.

2.3 Joining a Tree Key Graph

After granting a join request from u, server s creates a new u-node for user u and a new k-node for its individual key k_u. Server s finds an existing k-node (called the joining point for this join request) in the key tree and attaches k-node k_u to the joining point as its child.

To prevent the joining user from accessing past communications, all keys along the path from the joining point to the root node need to be changed. After generating new keys for these nodes, server s needs to securely distribute them to the existing users as well as the joining user. For example, as shown in Fig. 2, suppose u₉is granted to join the upper secure group in the figure. The joining point is k-node k₇₈ in the upper key graph, and the key of this k-node is changed to k₇₈₉ in the lower key graph. Moreover, the group key at the root is changed from k_1-8 to k_1-9. Users u₁, u₂... u₆ only need the new group key k_1-9, while users u₇, u₈, and u₉ need the new group key k_1-9 as well as the new subgroup key k₇₈₉.

To securely distribute the new keys to the users, the server constructs and sends rekey messages to the users. A rekey message contains one or more encrypted new key(s), and a user needs to decrypt it with appropriate keys in order to get the new keys. The user-oriented approach is used to used to construct and send the rekey messages.

2.3.1 User-Oriented Rekeying

Consider each user and the subset of new keys it needs. The idea of user-oriented rekeying is that for each user, the server constructs a rekey message that contains precisely the new keys needed by the user and encrypts them using a key held by the user. For example, as shown in Fig. 2, for user u₉ to join the upper secure group in the figure, server s needs to send the following three rekey messages:

s {u₁,…,u₆}: {k_1-9}k_1-8

s {u₇,u₈} : {k_1-9, k₇₈₉}k₇₈

s u₉ : {k_1-9, k₇₈₉)k₉.

Note that users u_{1, …,}u₆ need to get the new group key k_l-9. There is no single key that is shared only by u_{1, …,}u₆. However, key k_l-8 can be used to encrypt the new key k_l-9 for u_{1, …,}u₆ without security breach since users u₇ and u₈ will also get this new group key from another rekey message.

User-oriented rekey messages can be constructed as follows. For each k-node x whose key has been changed, say, from k to k', the server constructs a rekey message by encrypting the new keys of k-node x and all its ancestors (up to the root) by the old key k. This rekey message is then sent to the subset of users that need precisely these new keys. Either unicast or subgroup multicast may be used. Moreover, one rekey message is sent to the joining user, which contains all of the new keys encrypted by the individual key of the joining user. This approach needs h-rekey messages [1](h-height of the tree).

2.4 Leaving a Tree Key Graph

After granting a leave request from user u, server s updates the key graph by deleting the u-node for user u and the k-node for its individual key from the key graph. The parent of the k-node for its individual key is called the leaving point. To prevent the leaving user from accessing future communications, all keys along the path from the leaving point to the root node need to be changed. After generating new keys for these k-nodes, server s needs to securely distribute them to the remaining users. For example, as shown in Fig. 2, suppose u₉ is granted to leave the lower secure group in the figure.

The leaving point is the k-node for k₇₈₉ in the lower key graph, and the key of this k-node is changed to k₇₈ in the upper key graph. Moreover, the group key is also changed from k_l-9 to k_l-8 . Users u_l, . . .,u₆ only need to know the new group key k_l-8 . Users u₇ and u₈ need to know the new group key k_1-8 and the new subgroup key k₇₈. To securely distribute the new keys to users after a leave, same rekeying strategies are used.

2.4.1 User-Oriented Rekeying

In this approach, each user gets a rekey message in which all the new keys it needs are encrypted using a key it holds. For example, as shown in Fig. 2, for user u9 to leave the lower secure group in the figure, server s needs to send the following four rekey messages:

s {u₁,u₂,u₃} : {k_1-8}k₁₂₃

s {u₄,u₅,u₆} : {k_1-8}k₄₅₆

s u₇ : {k_1-8,k₇₈}k₇

s u₈ : {k_{1-8 ,}k₇₈}k₈.

User-oriented rekey messages for a leave can be constructed as follows. For each k-node x whose key has been changed, say, from k to k', and for each unchanged child y of x, the server constructs a rekey message by encrypting the new keys of k-node x and all its ancestors (up to the root) by the key K of k-node y. This rekey message is then multicasted to userset(K) [1].

3.0 UML State Diagram

A state diagram (also called a state chart diagram) shows the sequence of states that an object goes through during its life in response to outside stimuli and messages. The state is the set of values that describes an object at a specific point in time and is represented by state symbols and arrows connecting the state symbols represent the transitions. A state diagram represents the state of the method execution and the activities in the diagram represent the activities of the object that performs the method. The purpose of the state diagram is to understand the algorithm involved in performing a method. The

Fig. 3 and Fig. 4 represent the state diagram of a server and a user (client) respectively.

4.1 Server Implementation

The server subsystem is implemented as a concurrent server that spawns a new child thread for every new client connection established, using the JAVA socket Programming and JAVA Thread Programming concepts. The server subsystem creates a socket and binds a well-known address to the socket, so that all the clients can make a connection to that well known address of the server. The main server then waits for a new connection to arrive from any client. Once the client makes a connection request and succeeds, the server checks the user authentication information sent by the client and sends the list of keys that applies to that particular user.

The implementation of the server module for the secure group communication model consists of the following sub modules.

4.1.1 Initialization of the Tree (tree. java)

The server stores the information corresponding to all the logged in users in a key graph, which is implemented as a tree. The tree is implemented to have a height of three. The top level indicates the root node, consisting of the group key. The middle level of nodes in the key tree represents the various subgroups in the group. The bottom most level in the tree represents the users of the respective subgroups.

The nodes in the tree consist of the following information about the respective users:

The user’s name
The user’s session key
The user’s IP address
A Boolean variable specifying whether the user is active

When the server is started, the key tree initializer creates the root node and a certain number of subgroup nodes and initializes these nodes with the keys for the respective subgroups. The subgroup keys are generated using a random number generator function. As the users are accepted into the group they added to their respective subgroups, that is a node corresponding to the new user is created and attached to the node corresponding to the user’s subgroup.

Initial Key Tree: with two active subgroups and three active users.

4.1.2 Processing of the client requests (server. java)

The main purpose of a server is to process the client requests and to provide them the service requested. Any communication between the client and the server will be encrypted using the either DES or RSA algorithm and will not be make any sense to the intruders. The server handles the following five types of requests from the clients.

Public key request: For the client to initialize its secure communication with the server, it has to establish a session key that the client shares with the server. For the establishment of such a key and to preserve the confidentiality of the session key, the server uses the RSA algorithm. Since the client does not have any coded information about the server’s public key, it sends a request for the key at runtime. For such a request, the server sends back its public key to the respective clients.
Join request: This request indicates that a particular user wants to join the group and hence sends a user name and password, that he prefers. On receiving such a request, the server searches its Oracle database to check for the pre-existence of the same user name. In case the same user name is already reserved by some other user, the server sends an error message to the respective client, otherwise the new users details will be entered into the user details database and the client will be sent an acknowledgement. As a new user joins the group, the rekey messages are sent to all the other users in the group.
Leave request: This request indicates that a user wants to leave the group permanently. This message will be encrypted using the user’s session key. On receiving the leave request, the server removes the details corresponding to the user from the user details database and it also removes the node corresponding to the user from the key tree. Rekey messages are sent to all other users, so that the user who just left the group cannot access the future group communications.
Login request: This request consists of the user’s login name, password and a proposed session key for that login session. This message will be encrypted using the server’s public key. Only the server can decrypt it, since it has the private key. The server will cross check the correctness of the user name and password as against the information in the user details database, and sends a suitable message to the user.
Logout request: When the user wants to terminate the present session with the group, he/she sends the logout request to the server, encrypted with the user’s session key. As a response to this request the server deactivates the node corresponding to the user in the key tree.

4.1.3 Join protocol (keyGraph.java)

When a user joins into the existing group, a new secure group is created and hence requires the old keys to be updated in the key tree as well as intimate the users about the new keys. This is necessary so that the new user cannot access the previous communications in the group. This paper deals with the implementation of user-oriented rekeying strategy, where each user gets a rekey message containing precisely the new keys needed by that user encrypted with the key held by the user. The pseudo code for our implementation of the user-oriented rekeying protocol is as below:

SendRekeyMessageAfterJoin(new_user,user’s_subgroup)

{ for ( every subgroup in the main group )

{ if ( subgroup != user’s_subgroup )

{ for (all users in the subgroup)

SendMessage({new_group_key}old_group_key )

}

else {

for ( every user in subgroup )

{ if ( user != new_user )

SendMessage({new_group_key +new_subgroup_key}old_subgroup_key )

else

SendMessage({new_group_key +new_subgroup_key}session_key )}}}

4.1.4 Leave Protocol (keyGraph.java)

When a user leaves a group forever, the existing keys in the tree hierarchy needs to be changed using a leave protocol and the new keys must be securely communicated to all users, except the one who just left. This implementation uses user-oriented rekeying strategy to send the rekey messages to the users. This rekeying after a user leave is essential because the user who left the group must not be able to access the future communications. The pseudo code for our implementation of the user-oriented rekeying protocol is as below:

SendRekeyMessageAfterLeave

(left_user,user’s_subgroup)

{ for ( every subgroup in the main group )

{ if ( subgroup != user’s_subgroup )

{ for ( all users in the subgroup )

{ SendMessage({new_group_key}subgroup_key )

}

} else

{ for ( every user in subgroup )

{ if ( user != left_user )

{

SendMessage({new_group_key +new_subgroup_key}session_key ) }}}}

4.2 Client Implementation

The client program is implemented as a pair of threads, one that waits for rekey messages from the server and another that waits for the messages from other clients within the group. Both of these threads start running once the login process is over. Even the client side uses the same cryptographic algorithms, as the ones implemented in the server module, like the RSA and DES algorithms.

The user interfaces for both the server side as well as the client side are implemented using JAVA Swing components, which is a set of classes that provides more powerful and flexible graphical user interface components. The main procedures implemented in the client module are as follows:

4.2.1 Login Process (Client. java)

Once the server starts running, any client that wants to join and communicate with the group members needs to authenticate itself to the server, through the authentication or login process and obtain a set keys consisting of the group key, subgroup key and the user session key. The login process can be summarized as in the steps below:

Initially the client expresses its willingness to communicate with the server through a request for the server’s public key.

Server ß { send public key request }

As an acknowledgment to the client’s request, the server sends its public key to the requested client without encrypting it, as the public key does not requires to be a secret.

Client ß {server’s Public_Key}

Having received the server’s public key the client sends the user’s name, password and a proposed session key to the server, encrypting it with the public key. Since only the server possesses the private key, it can decrypt this message and checks the validity of the user.

Server ß {Name, Password, Session_Key}

Public_Key

If the user authentication is successful, the server sends the keys applicable to the user encrypted with the user’s proposed session key.

Client ß {Group_Key, Subgroup_Key, Unique_Session_Key }Session_Key

4.2.2 Message Transfer Module (MessageTransfer.java)

This module handles the transfer of messages between the clients. When the user authenticates himself to the server, the user also gets the multicast address to which they can attach for sending messages as well as to listen for the arrival of messages from other clients. These user messages are encrypted using the group key and sent as a datagram to all the users who have attached to the multicast address. Only authorized users will be having the group key and hence can decrypt the message.

4.2.3 Rekey Message Handler Module (Client. java)

A client can receive a rekey message at any time during its active participation in the group communication. The actual rekey message consists of the various keys i.e., group key and subgroup key, that has changed and required by the respective user. But the message sent to the client consists of encrypted rekey message as well as a message digest computed on the actual message, encrypted with the server’s private key. On receiving this, the client decrypts the actual rekey message using a suitable key and then computes the message digest MD-1. The client then decrypts the message digest that the server had sent using the server’s public key to get MD-2. It then compares the two message digests MD-1 and MD-2. If both are equal, then the client’s keys are updated to the values specified by the rekey message. Otherwise the rekey message is discarded as it has failed to confirm that the server sent it.

Key Tree after user “NewUser” joined the group: Since a user has joined the group at SubGroup-1, new keys have been applied at root and SubGroup-1.

Key Tree after the user “NewUser” logged-in: As the user logged-in, his node in the key tree is made active.

Key Tree after user “paran” logged out: As the user logged-out, his node in the key tree is made inactive.

Key Tree after user “NewUser” left the group: Once the user permanently leaves the group, his node is completely removed from the key tree.

5.0 CONCLUSION

We have implemented secure group communications to study the security and key management features. Our implementation consists of a key graph that holds information about the system users in a hierarchical order. The Join/Leave protocols using the user-oriented rekeying strategy have been implemented in an efficient manner to update the keys at the server as well as the clients. Efficient cryptographic algorithms like RSA and DES algorithms have been implemented to preserve the confidentiality and integrity of messages transferred between the server and the clients, as well as those that are transferred between clients.

The overhead of encrypting rekey messages with every users session key has been considerably reduced using the concept of subgroups and subgroup keys. Though this paper deals with the implementation of secure group communication model using a chat application, this model can be easily extended to other applications such as teleconferencing, distributed interactive simulation, information services like instant news service or share market related application and any other application that involves secure communication between a group of users.

5.1 Limitations of the work

The centralized server may become a bottleneck for performance when a large number of requests are flooded towards the server at a single instant.
The failure of the centralized server may collapse the entire communication model.
The 64-bit key used for DES encryption process may be insufficient to preserve the secrecy of the messages.
The system can be made more efficient using other rekeying strategies.
Since the control of the leave command is given to the client, it will continue to listen to group communications even then it is not the active member for communication.

5.2 Future enhancements to this work

The key server for sending rekey messages can be eliminated by having the clients to negotiate and decide on the new keys themselves.
We have limited the height of the tree to 3. This can be increased to have more number of groups and users.
More effective cryptographic algorithms like triple-DES; IDEA or Blowfish may be used to make the information exchange more secure.
We can make the server to automatically disable the client if it is not involved in the group communication for a long period of time after joining the group.

ACKNOWLEDGMENT

The authors wish to thank the anonymous reviewers for their constructive comments.

REFERENCES

[1] C.K. Wong, M. Gouda, and S.S. Lam, “Secure Group Communications

Using Key Graphs,” IEEE/ACM Trans. Networking, February 2000.

[2] S.E.Deering, “Multicast routing in internetworks and extended LANs,” in

Proc.ACM SIGCOMM’88, Aug. 1988, pp.55-64.

[3] A.O. Freier, P.Karlton, and P.C.Kocher, The SSL Protocol Version 3.0,

1996. Work in progress, Netscape Communication.

[4] J.G. Steiner, C. Neuman, and J. I. Schiller, “Kerberos: An authentication

service for open network systems,” in Proc. USENIX Winter Conf., Feb.

1988, pp. 191-202

[5] T.Y.C. Woo, R. Bindignavle, S. Su, and S.S Lam, “SNP: An interface fo

secure network programming,” in Proc. USENIX’94 Summer Technical

Conf., Boston, M.A, June 1994.

[6] William Stallings, “Cryptography and Network Security: Principles and

Practice,” Second Edition, Prentice Hall.

[7] http://vsys-www.infomatic.uni-hamburg.de /documents/docs /jdk1.3/api

/java

2.1 Key Graphs

U-nodes

2.2 Keying Strategies And Protocols

2.3 Joining a Tree Key Graph

4.0 experiments

REFERENCES