Présentation des protocoles de gestion de groupes (extrait du rapport de fin d'étude)

Note : cette page est actuellement disponible en anglais uniquement.

Group communication has been studied for a while, in wired and wireless networks. With the emergence of security needs in wireless network and more specifically in ad hoc networks (for military's applications or consumers ones, for instance with multi-players games or tele conferences), several protocols suggest a way to get secured group communications. To provide group communication privacy, we need to have a common secret key. Efficiently managing group keys in mobile networks, such as ad hoc networks, is difficult as every time the group changes (a node joins or leaves the group), the group key needs to be modified.

Existing group protocols

A variety of solutions have been proposed for group management. Some of them rely on centralized management, for instance Simple Key Distribution Center (SKDC). The logical key hierarchy (LKH) protocol [WGL98] is another group management protocol in which each member gets a place in a cryptographic tree managed by a centralized server which performs all the group management operations.

Other papers study decentralized algorithms. In decentralized group management protocol, each node of a group has partial keys. When we put all of them together, we are able to create the group key, needed to (de)cipher communications. Several proposals have been suggested to manage the group key. The clique suite proposed by Steiner and al [AST00] is one of them. In this protocol, every member introduces its partial-key into the result generated by its preceding member and sends the new result to its following member. Kim and al [KPT00] propose TGDH, which arranges keys in a tree structure (see the following section). TGDH is similar to the One-Way Function Tree (OFT) protocol [SM03] except that TGDH uses Diffie-Hellman instead of one-way functions for the group key generation.

LKH [WGL98]

The logical key hierarchy (LKH) protocol [WGL98] is a centralized protocol which relies on a virtual hierarchy. Such hierarchy can be a star or a tree, as describes below. The group management authority, the server, is denoted s. Though this protocol does not met all our requirements (such as the Per- fect Forward Secrecy defined later), it gives a good introduction on the key management in tree-based solutions.

Group definition

In LKH, 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, called the user-key relation of the secure group. User u has key k if and only if is (u, k) 2 R.

The figure 2.1 gives an example of a group structure and its modeling in LKH.

Figure 2.1: LKH example - (a) LKH representation of a group (b) Corresponding group graph

Associated with each secure group, two main functions for key management are defined,

• keyset(), the set of keys that are held by a user. keyset(u) = k|(u, k) 2 R
• userset(), e set of users that hold a key k. userset(k) = u|(u, k) 2 R

Group classification

The major problem of a generic representation of a group is the group management operations specifications. Thus, in LKH, two standard groups, the star and the tree models, are specified (they are implementation of the generic model). The group management operations are then specified in these models.

Star: each user in U has only two keys: its individual key and a group key that is shared by every user in U. In this model, the central node is the server s.
Tree: the key graph is a single-root graph, defined by two parameters:

• the height h, which is the length of the longest path in the tree,
• the degree d, which is is the maximum number of incoming edges of a node in the tree.

Group management operations

Using the abstract functions keyset() and userset(), abstract group managements operations can be specified though their implementations are dependent of the considered graph model.

Join operation: a user u who wants to join a secure group sends a join request to the key server, denoted by s. A join request initiates an authentication exchange between u and s. If the user u is authorized to join the group, the server s adds u to the group structure and managed the different new keys, depending on the group structure (star, tree or other). Actually, we must assure that all the keys in keyset(u) were not used before u joins the group.

Leave operation: 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. To replace such a key k by knew, the server s randomly generates a new key and sends it to every concerned user 2 U except u. To do it securely, the server needs to find a subset K0 of keys such that userset(K0) = [ k02K0 userset(k0) = userset(k)−u and use k 2 K0 to encrypt the new key knew for distribution.

LKH illustrates the principle of key Independence defined in section 2.2.1 which states that if a node is not a group member at the time t, then it must not be able to get group keys used at time t with passive attacks, even if it is a group member at time t0 (t0 < t or t0 > t).

TGDH [KPT00]

An interesting aspect in TGDH and the other tree-based solutions is that the protocols try to dispatch the group key calculus on nodes of the group, depending on the tree structure. As our proposition relies on TGDH, we present the main aspect of this solution. More explanations are available in [KPT00].

Cryptographic principles

The TGDH cryptographic algorithm relies on the Diffie-Hellman solution adapted to the group management problem. Thus, the arithmetic operations are performed in a group of prime order p with the generator α, where p (prime integer) and α (exponentiation base) are the ones described in the Diffie- Hellman protocol [Res99]. As described in the following section, the notion of Group Diffie-Hellman is due to the fact that the group key is generated using the Diffie-Hellman problem. Each member possesses two personal keys: a private partial-key Kv and a public one BKv, where BKv = α^Kv mod p. The public group key is a function of the other nodes public keys and the current node private key. Let's say: for v, groupkey = f(Kv,BK0, ...,BKv−1,BKv+1, ...BKn), where n is the group size and f is the group key function.

When the number of nodes increases, the number of parameters for f raises up too. However, the evaluations f(Kv,BK1,BK2, ...,BKw) and f(Kw,BK1,BK2, ...,BKv) may perform similar partial calculi (on BK1 and BK2). In order to prevent several nodes to perform similar calculi, we use the cryptographic tree to dispatch the global key evaluation.

The following example explain how the group key is computed and how the calculi are dispatched on the group's nodes. Let us suppose we have 6 members. One of the trees that TGDH can produce is represented in the figure 2.2. One should remember that the intermediate nodes (i.e. the ones that are not leaves) such as <2,0> are virtual nodes, which means that they have no real existence and that their keys are computed from their children : Kl,v = (BKl+1,2v+1)Kl+1,2v mod p. In this figure, the copath of the node M1 is represented (in dark line). The copath of a member is the set of neighbour nodes (virtual or not) associated to the path we got when we want to reach the root of the tree.

The important aspect is that only the BKs on the copath are needed to evaluate the group key. When we use keys of virtual nodes, it means that the BK is already a computation of children's BKs. For instance, the BK of <2,3> is a computation of those of M5 and M6. Thus, the function f(Kv, ..BK5,BK6, .BKw) is replaced by f(Kv, ..BKparent, ...BKw), which reduces the number of operations a node has to perform.

Figure 2.2: TGDH tree example

By comparison, when M1 wants to compute the group key it needs to perform f with 3 BKs, and not 5 (the other members).

To be more precise, the group key function f can be described using the following formulae: f = 8< : BKKv 0 , if n = 0 f(BKKv 0 ,BK1), if n = 1 f(BKKv 0 ,BK1, ...,Bkn) otherwise where the BK keys are are keys of the nodes in the copath of the considered v node. Moroever, the order of the BK keys is important: the key ith BK key used in f is the key of the ith node in the copath, starting from v (i = 0). For instance, for the node M1, we have group_key = f(K1,BK(< 3, 1 > ),BK(< 2, 1 >),BK(< 1, 1 >)) = f(K1,BK2,BK3,BK(< 1, 1 >)) In TGDH specifications, we have five membership events:

• Join: a new member is added to the group
• Leave: a member is removed from the group
• Merge: a subgroup is added to the group
• Partition: a subgroup is isolated from the group
• Key refresh: the group key is updated

As Merge and Partition are respectively meta-events of Join, and Leave, we describe only the two first events. Full explanations are available in [KPT00].

Join protocol

Let us suppose we have n nodes in the group. The new member Mn+1 initiates the join protocol by sending a join request message that contains its own blinded key BK. When current group members receive this message, they first determine the insertion node in the tree. If the cryptographic tree is well balanced, Mn+1 joins at the root node. Otherwise, the insertion node is the shallowest rightmost node, where the join does not increase the height of the key tree. The sponsor is the rightmost leaf node in the sub-tree designed by the insertion node (see figure 2.3).

When the sponsor is found, it creates a new intermediate node, and promotes the new intermediate node to be the parent of both the insertion node and the new member node. The sponsor broadcasts then the new tree, which contains all blinded keys.

Leave protocol

Let us suppose that a member Ml leaves the group. In this case, the sponsor is the right-most leaf node of the sub-tree rooted at the leaving member's sibling node, as shown in figure 2.4. The former sibling of Ml is promoted to replace Ml's parent node. The sponsor generates a new secret, computes all keys on its copath, and broadcasts the new set of blinded keys to the group. This information allows all members to recompute the new group key.

Figure 2.3: TGDH - join protocol

Figure 2.4: TGDH - leave protocol

Security definitions

Security properties

In cryptographic protocols, several security properties have to be satisfied in order to keep the confidence in the group security. We present here those properties our algorithms preserve. Most of them are taken from the clique protocols specification [AST00]. These different properties have to be satisfied in order to comply with two basic properties : outsider cannot read and outsider cannot send. (note : some of these properties were already guaranteed by TGDH, we mark them by T)

Group management

• station authentication: upon receiving a message from a node, we should be able to detect if the claiming node is the real one (no masquerade attack). This is provided by the signature mechanism, using the RSA keys.
• keys independence (T): this property can be divided in two basics one, as described in the Hi-KD [HBBC05] protocol :
  • Forward confidentiality: an old node must not be able to get a group key used after having left the group
  • Backward confidentiality: a new node must not be able to retrieve group secret keys used before it joined the group.
  These two properties are ensured by the key update mechanism upon each group event and the Diffie-Hellman properties (it is impossible to get a private key, no matter which public keys an attacker has).
• non-contributory protocol: all the nodes in the group do not play the same roles, but a node's role cannot be chosen by itself.
• message freshness: in order to prevent malicious nodes from performing message replays, the protocol must certify the freshness of each message. In our solution, this is assured by nonces.

Group key

• key agreement protocol (T): a protocol is said to be a key agreement protocol if the secret key is computed from two or more parties and that no party can predict the resulting value.
• implicit key authentication(T): each member Mi of the group M is assured that no member Mq /2 M can learn the group key unless it is disclosed by a dishonest member Mj 2 M.
• key integrity (T): the group key is computed only by using values issued by indoor members of the group. Extraneous contribution(s) to the group key cannot be tolerated even if it does not provide the attacker(s) with any additional knowledge.
• Perfect Forward Secrecy (PFS) (T): the compromise of a key (long-term or session's key) cannot result in the compromise of past session keys.
• known key attack resistance: compromise of session keys does not allow: 1) a passive adversary to compromise keys of other sessions, or 2) an active adversary to impersonate one of the protocol parties. The signature mechanism prevents an adversary to impersonate a node, unless it manages to obtain this node's RSA private key.
• passive attacks resistance: a protocol is said to be resistant to passive attacks if it can prevent people from discovering secrets (such as the group key) by passive attacks, like eavesdropping. The group encryption mechanism, associated to group key updates (in order to prevent the group from using the same key during a long time), prevents attackers from discovering the current session key.

As all these properties are satisfied by our algorithms, we are able to keep the confidence in the group security.

Keys and signature management

Key validity

As we are in a distributed environment, updating a key is not immediate. Thus, it should be taken into account that an old group key should not be revoked immediately after the new one is built.
In [BBB+06], several advices are given about key management. One aspect, the cryptoperiod, has to be taken into account for key validity. «A cryptoperiod is the time span during which a specific key is authorized for use by legitimate entities, or the keys for a given system will remain in effect». In fact, a BK (or K) key in S-TGDH has three states. The first one, pre-partial key, refers to the fact that the key as been created, but is not a part of the global secret key of each node (for instance due to the propagation delay for an update operation). Then we got the partial-key and finally the post-partial key. Some of the node use old keys (in post-partial state) and others use new keys (in pre-partial state), due to delays.

This can be summed up in figure 2.5. The time for each phase depends on the network, but also on the sensitivity of the information.

Figure 2.5: Cryptoperiod explanation

Key size

An important aspect in cryptographic protocols is the key size. Nowadays, asymmetric key protocols use keys of 1024 bits length (and symmetric ones of 128 bits). According to a report [Wil01] of Lorraine C. Williams, 2048 bits length for asymmetric key and 128 bits length for symmetric key is far enough for the moment.
We thus recommend the use of these key lengths (depending on the country laws). For the global key, the use of a hash128 or hask256 functions is sufficient.

Nonces management

Two kinds of nonces can be used in cryptographic protocols. The first kind of nonces, based on random variables, assumes that all nodes know the previous used values. However, they should know all the nonces used since the RSA keys has been created, and not only since the group has been created.
Thus, this solution is not well adapted to our problem. The second kind of nonces relies on temporal nonces [HPJ01]. This solution, most interesting for group management, implies several requirements such as :

• nodes should be able to synchronize their clocks
• the propagation time can be evaluated

For the first requirement, solutions as GPS can be used. Several synchronization protocols exist in ad hoc networks, but we think GPS is better due to traffic increase problems.