A Secure Peer Discovery Protocol (SPDP) David A. McGrew Cisco Systems, Inc. July, 2001 1. Introduction We present a protocol which allows two entities to discover whether or not they belong to the same secure group, without revealing their other group memberships to each other, and without revealing any group memberships to any other parties. This protocol can also find the largest common segment of the "chain of trust" which the entities share. This protocol can be used by network devices to discover other trusted devices in the absence of any centralized database. Example uses include peer discovery within VPNs (as with Tunnel Endpoint Discovery), zero-configuration and self-organizing networks (such as Bluetooth). Goals: * enable two entities to discover the groups to which they both belong * preserve anonymity (that is, do not reveal other group membership information to any parties whatsoever) * avoid denial of service vulnerabilities for receivers * limit computational cost and storage requirements 2. SPDP Alice and Bob each has a set of groups to which they belong. Our goal is to enable them to find out which groups they have in common. Each group has two keys set aside for this purpose, which are called the group initiator key I_g and group responder key R_g. These keys are shared throughout the group. These keys are used in a message authentication function M(k,m), which computes a MAC of a message m using a key k. The protocol is a four-message exchange, as follows: 1. Alice sends a challenge CA to Bob. 2. Bob sends a challenge CB back to Alice. The concatenation N = CA || CB of these challenges is used as a nonce. 3. For each group g in which she is a member, Alice computes the quantity M(I_g, N). The quantity is called the initiator's group authenticator, or IGA. She sends the entire list of these values to Bob. For each group g in which he is a member, Bob computes the initiator's group authenticator M(I_g, C). Bob takes the list from Alice, and looks for matches with the authenticators on his own list. A match indicates common membership in a group. 4. Bob constructs a response list as follows. For each initiator's group authenticator in the list from Alice, Bob creates an corresponding entry in response list. If the entry corresponds to a common group, then it's value is set to the responder's group authenticator M(R_g, N). Otherwise, the value is chosen uniformly at random. Bob sends the response list to Alice. For each group to which she belongs, Alice computes the group responder's authenticator and compares it to the corresponding value in the response list. A match indicates common membership. After an error-free run of this protocol, Alice and Bob have discovered common group memberships. This protocol could be followed by a key derivation, in which a pairwise communication key is derived from a group communication key. Such a derivation can use the message authentication function M(), and does not require an additional message exchange. Alternatively, Alice and Bob could ask the group controller of a common group (who is a trusted third party) to provide a pairwise key for Alice and Bob, using a third-party key distribution protocol such as Bellare and Rogaway's 3PKD. 3. Active Attacks and Countermeasures SPDP as defined above is vulnerable to active attacks. It is clear that an attacker who can block initial SPDP messages might subvert the protocol. This clearly puts an upper limit on the resistance to active attacks of any peer discovery protocol. However, SPDP has an even worse vulnerability. It is possible for an active attacker to subvert the protocol by setting all of the group authenticators to random values. If this is done to the initiator's group authenticator list, then it will appear to both Alice and Bob that they have no groups in common. If this is done to the responder's group authenticator list, then any match found by Bob will not be found by Alice, resulting in a synchronization problem. This vulnerability can be avoided by having the challenges C_A and C_B also be commitments to a message authentication keys a_A and a_B, respectively. Alice computes the MAC of the initiator's list, and sends that along with that list in Step 3. Bob computes the MAC of the responder's list, and sends that along with the list in Step 4. Using additional messages, Alice and Bob exchange the actual values of a_A and a_B, and each verify the MAC of the authenticator list and the earlier cryptographic commitment. Notice that if an attacker changes the values of any messages, then the MAC won't be valid and/or the commitment won't be valid. In a real instantiation of this protocol, the identities of the participants (e.g. IP or Ethernet addresses, port numbers) would be included in the authenticated portion of the messages. 4. Discussion Note that Bob looks for any matches between the IGAs which he computes and the list of those values from Alice in Step 2, while Alice looks for matches in specific entries in the list. The protocol is not quite symmetric, since Bob could always decide not to reveal one of his group memberships to Alice, possibly based on information revealed to him by Alice. It may be possible to remedy this problem through cryptographic commitment to data. On the other hand, this asymmetry is not important in the usage scenarios outlined above. Alice could add spurious authenticators in her message so that it appeared that she belonged to more groups than she actually does. Clearly, this makes no difference to Bob. A weak MAC could be used for the authenticator, and any matches could be followed up with a strong MAC check. Even better, a progressively verifiable MAC such as TMMH or UMAC could be used. 5. Group Hierarchies In many cases, secure groups are organized in hierarchies. In such a case, SPDP can take advantage of the hierarchies to reduce the responder's computational effort. A common example is a corporate hierarchy, which contains groups of vice presidents, directors, and managers. Consider the case in which all direct reports of an employee share a common key. Membership in the lowest group (the first-level manager's group) implies membership in the highest level group (the group of all employees). If the initiator indicates these implications in the message in Step 3, then the responder need only check the lower-level IGAs if the highest-level IGA matched. This can reduce the responder's computational load considerably. We now outline a simple method which uses group hierarchies to reduce the responder's computation without revealing any information about the hierarchies to which the initiator belongs. For simplicity, we call a hierarchy of group memberships a trust chain, and call the highest-level membership the start of the chain and the lowest-level membership the end of the chain. The initator orders the IGAs in the list so that each trust chain appears in order, from start to end. The responder computes responder's group authenticators only for the chain starts of his trust chains, and looks for matches in the IGA list from the initator. For each match, he computes the next IGA on his trust chain, and compares it to that in the list, continuing as long as there are matches (and the next IGA is not another chain start). This simple method works well, but assumes that no chain will ever start in the middle of another chain. The validity of this assumption will depend on the usage of the protocol. Note that this procedure is analagous to the "path validation" in a public key certificate infrastructure, though SPDP provides better anonymity. 6. Denial of Service (DoS) It is essential that the computation and storage burdens of the receiver cannot overwhelm its resources. One modification to SPDP which may decrease its vulnerability is to add a field to the message sent in Step 3, such that it will be immediately apparent to the responder upon receipt of that message whether or not the sender has actually received the message in Step 2. This would enable the responder to discard those messages, and thus avoid the costly operations in Step 3, whenever the attacker did not provide the proper source address in the initial message. Of course, an attacker who provides the proper address cannot remain anonymous. This modification can be done by requiring that the initiator include the responder's challenge C_B in the message of step 3. The responder's first step in processing the message is to check this value, and drop it if it is invalid. This limits the responder's exposure to anonymous DoS attacks to the generation, storage, and verification of a challenge. 7. Provable Security SPDP is simple enough that it may be provably secure, given the security of the MAC and cryptographic commitment primitives. SPDP contains elements of Bellare and Rogaway's Authenticated Key Exchange protocol. It may be possible to adapt the security proof of that protocol to cover SPDP. One difference is in Step 3, in which the responder looks for matches between any elements of a set, rather than a match between a particular pair of elements. 8. Protocol Extensions One worthwhile adaptation would be to allow the initiator or responder to use pre-computation to reduce the computational cost of a run of the protocol. Another worthwhile extension would be to let the responder precompute a list of authenticators, which could then be put into a directory or some other network storage device. Of course, this data could only be for one run of the protocol.