## 4 Secure Cooperation
### Key Management Service  
Each time a node leaves the system, the KMS generates and distributes a new group key. This is done to avoid that an old vehicle is able to read new messages. The scalability of the rekeying service depends on the chosen rekeying protocol. In UAN, we chose S2 RP, a secure and scalable rekeying protocol for resource-constrained devices [25]. S2 RP is particularly suitable for UAN for two reasons. First of all, S2 RP provides a very efficient proof of key authenticity. Actually, S2 RP verifies the authenticity of a key by computing a hash function. So, verification is very computing efficient and does not require any additional information, e.g., MACs or digital signatures, which would cause message expansion. Secondly, S2 RP requires a number of rekeying messages that is logarithmic in the number of vehicles, thus making the key distribution phase highly scalable. In short, the key authentication mechanism levers on key-chain, a technique based on the Lamport's one-time passwords. A key-chain is a set of symmetric keys so that each key is the hash pre-image of the previous one (see Figure 9). Hence, given a key \(K^{(i)}\) in the key-chain, anybody can compute all the previous keys \(K^{(j)},j\leq i\), however nobody, but the key-chain creator, can compute any of the next keys \(K^{(j)},j>i\). Keys are revealed in the reversed order with respect to creation order. Given an authenticated key in the key-chain, anybody can authenticate the next revealed keys by simply applying an hash function. For example, if \(K^{(i)}\) is an authenticated key, than anyone can verify the authenticity of \(K^{(i+1)}\) by verifying that \(K^{(i)}=h(K^{(i+1)})\). To reduce the communication overhead, KMS maintains a logical key tree (see Figure 10). Each internal node contains a key-chain, whereas each leaf is associated with a vehicle and contains the vehicle-key, _i.e._, the secret key that the vehicle shares with KMS. We call current key of a key-chain the last revealed key of the key-chain and next key the hash pre-image of that key. Furthermore, we denote by \(K_{i}\) and \(K_{i}^{+}\) respectively the current and next key of the key-chain associated to tree node i. Notice that \(K_{i}=h(K_{i}^{+})\). Each vehicle maintains a _key-ring_ that contains every key \(K^{i}\) such that the sub-tree rooted at node i contains the leaf associated with the vehicle-key. Hence, with reference to Figure 10, the key-ring of vehicle \(v_{4}\) is \(\{K_{1},K_{2},K_{3}\}\). As it turns out, key \(K_{1}\), associated to the key tree root, is shared by all vehicles and acts as the group-key. Let us now assume that vehicle \(v_{4}\) leaves the group. All keys in its key ring are considered compromised and KMS has to broadcast the respective next keys \(\{K_{1}^{+},K_{2}^{+},K_{3}^{+}\}\) by means of the following rekeying messages:  
1. \(KMS\to v_{3}:\qquad E_{K_{3}}(K_{5}^{+})\)
2. \(KMS\to v_{3}:\qquad E_{K_{5}^{+}}(K_{2}^{+})\)
3. \(KMS\to v_{1},v_{2}:\qquad E_{K_{4}}(K_{2}^{+})\)
4. \(KMS\to v_{1},v_{2},v_{3}:\qquad E_{K_{2}^{+}}(K_{1}^{+})\)
5. \(KMS\to v_{5},v_{6},v_{7},v_{8}:\qquad E_{K_{3}}(K_{1}^{+})\)Upon receiving a rekeying message, after it has been properly decrypted, the authenticity of the next key therein contained is verified by computing its hash and comparing the result to the corresponding current key. For instance, upon receiving rekeying message 5, \(v_{6}\) decrypts the message by means of \(K_{3}\) and verifies the authenticity of \(K_{1}^{+}\) by ascertaining that \(K_{1}=h(K_{1}^{+})\). As it turns out the rekeying message, the rekeying message is verified by computing the hash and comparing the result to the corresponding current key. For instance, upon receiving rekeying message 5, \(v_{6}\) decrypts the message by means of \(K_{3}\) and verifies the authenticity of \(K_{1}^{+}\) by ascertaining that \(K_{1}=h(K_{1}^{+})\). As it turns out the rekeying message, the rekeying message is verified by computing the hash and comparing the result to the corresponding current key.