## 5 The Cryptographic Suite
### Group Key Management  
Each time a node leaves the system, the GW generates and distributes a new group key \(g\). This is done to avoid that an old node is able to read new messages. As to rekeying protocol, we chose S2 RP, a secure and scalable rekeying protocol for resource-constrained devices [29, 30]. 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 digest of it. So, verification is very computing efficient and does not require any additional information, e.g., MACs or digital signatures, which would cause a great message expansion. Secondly, S2 RP requires a number of rekeying messages that is logarithmic in the number of nodes so making the key distribution phase highly scalable. In short, the key authentication mechanism levers on _key-chains_, a technique based on [PERSON]'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 3). 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. Therefore, given an authenticated key in the key-chain, anybody can authenticate the next revealed keys by simply applying a 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)})\). 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. We denote them by \(k\) and \(k^{+}\), respectively. Notice that \(k=h(k^{+})\). To reduce the communication overhead, the gateway GW maintains a logical key tree (see Figure 4) where each internal node is associated to a key-chain and each leaf is associated with a node's node-key (_i.e._, the secret key that the node shares with GW). We denote by \(k_{i}\) the current key of the hash-chain associated with the internal tree node \(i\). Keys in the hash chain are only used in the rekeying process and thus are called _key encryption keys_ (KEKs). Each node maintains a _key-ring_ that contains every KEK \(k_{i}\) such that the sub-tree rooted at node \(i\) contains the leaf associated with the node-key. Hence, with reference to Figure 4, the _key-ring_ of node  
Figure 3: Key chain. \(v_{4}\) is \(\{k_{1},k_{2},k_{5}\}\). As it turns out, key \(k_{1}\), associated to the key tree root, is shared by all nodes and thus can act as the group-key, _i.e._, \(g\equiv k_{1}\). In order to have an idea of how the protocol works, let us consider the logical key tree in Figure 4. Let us now assume that node \(v_{4}\) leaves the group. All keys in its key ring are considered compromised and GW has to broadcast the respective next keys \(k_{1}^{+},k_{2}^{+},k_{5}^{+}\) by means of the following rekeying messages:  
(1) GW \(\to\)\(v_{3}\): \(E_{e_{v_{3}}}(k_{5}^{+})\)  
(2) GW \(\to\)\(v_{3}\): \(E_{k_{3}^{+}}(k_{2}^{+})\)  
(3) GW \(\to\)\(\{v_{1},v_{2}\}\): \(E_{k_{4}}(k_{2}^{+})\)  
(4) GW \(\to\)\(\{v_{1},v_{2},v_{3}\}\): \(E_{k_{2^{+}}}(k_{1}^{+})\)  
(5) GW \(\to\)\(\{v_{5},v_{6},v_{7},v_{8}\}\): \(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, \(n_{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 protocol requires \(O(\log n)\) rekeying messages, where \(n\) is the number of nodes. Furthermore, given the key-chain authentication mechanism, every rekeying message needs to carry only the next key (in its encrypted format).