Postscript document

Security

 

The STR protocol suite and the structure of its group key form a special case of the TGDH key agreement recently presented in [KPT00]. (The latter defines a more general tree-based Diffie-Hellman key agreement.) As such, STR benefits from the provable security of TGDH protocols. Briefly, in [KPT00] it is shown that group key secrecy is reducible to the Decision Diffie-Hellman (DDH) problem [MvOV97].

However, the basic property of group key secrecy is not sufficient for the security of the entire protocol suite. Recall the desired security properties defined in Section 3. We will show that STRoffers not only group key secrecy but also weak forward and backward secrecy properties. Furthermore, we show that STRcan provide key independence by modifying the protocol slightly.

We now present an informal argument for weak forward and backward secrecy.

The group key secrecy property implies that the group key cannot be derived from the blinded keys alone. At least one secret key $K$ is needed to compute all secret keys from $K$ up to the root key. Hence, we need to show that the joining member $M$ cannot obtain any keys of the previous key tree. First, $M$ picks its secret share $r$, blinds it and broadcasts $r$ as part of its join request. Once $M$ receives all blinded keys on its co-path, it can compute all secret keys on its key path. Clearly, all these keys will contain $M$'s contribution ($r$); hence, they are independent of previous secret keys on that path. Therefore, $M$ cannot derive any previous keys.

Similarly, we argue that STRprovides weak forward secrecy. When a member $M$ leaves the group, the rightmost member of the subtree rooted at the sibling node changes its secret share. Then, $M$'s leaf node is deleted and its parent node is replaced with its sibling node. This operation causes $M$'s contribution to be removed from each key on $M$'s former key path. Hence, $M$ only knows all blinded keys, and the group key secrecy property prevents $M$ from deriving the new group key.

As presented in Section 4, the STRprotocols do not provide key independence. This means that an active attacker who somehow acquires a group key used before an additive event (join or merge) can use the knowledge of that key to compute a newer key used after such an event. The same does not hold for subtractive events (leave and partition) since a sponsor always changes its session random following each such event.

The join and merge protocols can be modified slightly to provide key independence as explained in the join and merge protocol: Upon each join or merge event, a sponsor (both sponsors, in case of a merge) changes its session random and recomputes its blinded key before proceeding with the rest of the protocol.

This simple change results in key independence since each membership change is followed by at least one session random change. (Of course, we assume that individual members are honest and do not leak their session randoms to the adversary. This behavior can be regarded as equivalent to revealing the group key.)