3.3.1 Design Goals

The design goals of SAK are similar to LEAP [12] and should satisfy the following criteria.

1. – SAK should support authentication, integrity, and confidentiality for the most common communication scenarios. These include the communication between two CNs of the same cluster, between a CN and a CH, among nodes in the same cluster, among all the nodes in the network.
2. – If one or a limited number of sensor nodes are compromised, the entire network should still be able to‐survive further with a limited number of adaptations.
3. – Due to the resource‐constrained nature of the sensor nodes, the protocol should be designed as efficiently as possible. This aims a to minimize the communication phases and the number of expensive cryptographic operations as much as possible.
4. – As there is a relatively high packet loss in sensor networks, message fragmentation should be avoided as much as possible. Using the adaptation layer 6LoWPAN for the compression of IP headers, a payload can contain approximately 70 bytes [19].

3.3.2 Setting

We consider a sensor network with a three‐layered architecture, being the BS, the nodes , and the CNs belonging to a particular CH . Let us assume that each sensor node (CHs and CNs) participating in the network, has a pre‐installed secret shared key with the BS, an identifier, some auxiliary key material derived from the identifier and different in structure for CHs and CNs, and a common network key . This information is stored in each sensor node, before the node is put into the field. The position of the nodes, i.e. combination of CN and CH, does not need to be known in advance, only the fact that a node will behave as CH or CN. Since CHs need to perform a considerably higher amount of processing, more powerful nodes are used for this task and distinction is easy.

Once the nodes are put in the field, the CH broadcasts its identity and a timestamp . Next, the key management protocol will describe how each node will be able to construct three on‐the‐fly‐different types of keys.

1. – Group node key . This key is shared among all nodes and CH in the cluster with CH, .
2. – Multicast key : This key is shared among a selected group of nodes by the CH .
3. – Individual cluster key . This key is uniquely shared between and the CH .
4. – Pairwise key . This key is shared between the nodes and in the same cluster.

When the BS sends a timestamp to the CHs in the network, the CHs are also able to derive a group key shared among the CHs and the BS, called the group cluster key . In addition, the CH can also derive on‐the‐fly the group node key , the multicast key , and the individual cluster key . Moreover, we also explain how we include authentication into the communication. Fig. 3.1 illustrates the involved entities for examples of different types of keys.

The communication capacity between the different entities in the nodes differs due to the difference in resources. The BS can in any case unicast or broadcast information directly to the CHs or the CNs. A CH communicates to the BS in a multi‐hop way, while it is able to unicast or broadcast directly to all nodes in its cluster. A sensor node communicates to its CH in single hop or multiple‐hop, dependant on its distance.

3.3.3 Notations

We represent a hash function by . The encryption operation of message under a key to obtain the ciphertext is denoted as , and the corresponding decryption operation as . Furthermore, the concatenation of values and is denoted by and the xor operation by .

3.3.4 Attack Model

The attackers may come from inside or outside the network. They are able to eavesdrop on the traffic, inject new messages, replay and change old messages, or spoof other identities. They may try to take the role of CN or CH.

Attackers can also compromise and capture a node, such that all security material is revealed. Note that we do not discuss the mechanisms to detect malbehavior of a node, e.g. by storing trust tables in each node. Therefore, we refer to the literature on intrusion detection mechanisms [20] to detect abnormal behaviour of a compromised node. On the other hand, we describe how to act when such a situation occurs, corresponding to the description of the scheme in change mode, Section 3.6.

3.4.1 Installation Phase

The installation differs for CH and CN. We will discuss both types. Let and be two master secret keys of the BS.

3.4.2 Group Node Key

The CH first chooses a random value and computes the group key

(3.4)

The CH broadcasts .

All the CNs in the neighbourhood of can now easily derive this group key. First the message is decrypted using the network key. Then, is extracted from and used to construct the group key, (see Equation 3.4). The result is compared with the last part of the decrypted message in order to verify the integrity.

This process is typically initiated by the CH, but can in theory also be activated by another CN. We show in Section 3.5 how authentication of the CH can be included in this process and how the CH can use this key in an authenticated way.

3.4.3 Individual Cluster Key

This phase leads to the derivation of the individual shared key between and and requires only one communication phase between and . We may assume here that is aware of the identity of , since it has received the broadcast message from the previous step. We now describe in more detail the different steps to be performed by the participants. There are two possibilities, either initiated by the CN or the CH.

3.4.3.1 CN to CH

The following steps are executed by .

1. – First is derived from .
2. – In addition, also computes from its stored values
   (3.5)
3. – Next, chooses a random value , which will serve as an individual cluster key and computes:
   
4. – The following message is then sent to :
   (3.6)

The receives this message and performs the following computations:

This check corresponds with an identity check since only the node with the correct pre‐installed values by the BS is able to derive the identity related information in the form of . In addition, the integrity on the derived key is also verified. Only if the right value for is found, this equality holds. If the check is positive, then can conclude that the node with identifier belongs to the network and its corresponding shared key equals to .

3.4.4 Pairwise Key Derivation

Here, node establishes a key with . There is a straightforward way to realize this if you let the CH generate the key and securely send it to the involved nodes in its cluster using and . However, we propose a protocol here that allows the construction of a pairwise key, only shared between the sensor nodes and not with the CH.

The idea is based on the fact that the nodes of the cluster and not the CH share the secret value . On the other hand, the CH shares with each individual node the value . Consequently, the node needs to request unique information from the CH (based on ) on node , corresponding with phase 1. If is correctly authenticated, this info is sent from CH to in phase 2, which puts in the knowledge of uniqe information only shared by . Finally in phase 3, the key can be constructed using this information and the value by in order to uniquely share a key with without involvement of the CH. Let us now describe these three phases into more detail.

1. – Phase 1: Here, requests some unique information, able to distinguish from the cluster group. Therefore, it first generates a random value and sends a key request . The first part of the message is to derive the individual cluster key as described in Equation 3.6.
   
2. – Phase 2: first derives the key as described in the previous paragraph. Then, if can correctly decrypt the last part of the message, the following computations are performed:
   • A new value for .
   • A value to distinguish , asked by : . Only the CH is able to compute this value since the other CNs have no knowledge on .

   The value is sent to .

3. – First, the key should be derived, as explained in the previous paragraph, in order to decrypt the message. Note that instead of sending as in Equation 3.8, only a ciphertext is sent. If after decryption, the first part of the plain text contains the random value , the integrity of the key is verified.

   Next, a random value is chosen, which will serve as pairwise key. An additional random value is chosen. Now, the following computations are performed.

   

   The values are sent to .

4. – Phase 3: Key derivation by In the last step, the receiver node , starts with decrypting the last part of , by computing the key . If the last part of the decrypted message is equal to the random value , the node concludes that the key request is coming from a validated node of the cluster since only the CH is able to compute the value of . The originator of the message is verified since it is included in the key computation. After successful decryption, the node can continue its computations with the random value from . From , the key can be easily computed. Finally, the integrity of the key is checked with comparing the outcome of the message and the received .

3.4.5 Multicast Key

In case of doubt on the trust of the CNs in its network, it might be interesting, for example, for the CH to select the group of receivers. Another possibility might be that the message is only meant for nodes with a certain functionality or a certain property. We describe the operations performed by the CH and the operations by the CNs.

3.4.6 Group Cluster Key

The BS is able to establish the group cluster key by just broadcasting a key request for a group cluster key, together with a random value to all the CNs. The corresponding key is then

We show how authentication can be guaranteed in here and how to use this key in an authenticated way in Section 3.5.

3.5.1 Authentication by CN

Due to the particular construction of the security material in each CN, every CN can authenticate itself with the CH (and the BS) by computing , with the message to be sent including a counter/random/timestamp in order to ensure randomness. The message, will unambiguously authenticate the CN with the CH and/or BS. Only in case of a problem, the situation is communicated in the group.

3.5.2 Authenticated Broadcast by the CH

Suppose the CH wants to send the message , authenticated and encrypted, in its cluster, where the list of participants is known. These participants include the nodes that have sent messages to the CH during the last timeframe. There are two straightforward ways to deal with this.

1. – The CH can use the same method as described in the derivation of the multicast key in the previous section.
2. – The CH can use the group key and again exploit the particular construction of the security materials of the CNs and CH (cf. equations 3.1 and 3.3), by adding to the transmitted message , the following values:
   

   Note that the message should include a counter to avoid replay. Each part in this message corresponds with a different CN in the cluster of .

It is clear that the second method is more efficient. However, both methods have the disadvantage that the message linearly increases with the number of participating CNs. There are two possible ways to overcome this issue:

1. – Restricting the number of the CNs in each cluster. For instance, if we assume the hash values of size 160‐bit (20 bytes), a message of size 10 bytes, and a payload of 70 bytes as with 6LoWPAN, there can be at most 3 CNs in the cluster in order to not fragment the message ().
2. – Distribution of the authentication check. The CH divides the group of CNs into groups of size 3. To each message, the group number is added in consecutive order. If this order is not respected or the authentication check of a node belonging to that group mentioned in the message is unsuccessful, doubts are sent to the CH and BS in unicast mode. Consequently, each message is checked by a part of the nodes belonging to the cluster and it is assumed that no more than 3 nodes are malicious.

3.5.3 Authenticated Broadcast by the BS

This authentication should pass the two layers in hierarchical order. First, the BS should be authenticated by the CHs and next the CHs should be authenticated by the CNs in its cluster. The second authentication is discussed above and thus we focus now on the first one. For the authentication of the BS to the CHs, the same technique as described above can be used, adding to the message the values

where each part corresponds with each CH in the network. However, as the CHs are less constrained than the CNs, packet fragmentation should not form too large an issue.

3.6.1 Capture of CN

First, it should be mentioned that the derivation by a CN of an individual cluster key, pairwise key, and group node key is only possible if the key is known. Consequently, the focus of protection (e.g. using techniques of code obfuscation for example) should be put on this value.

Let us now suppose that the CN is captured or compromised. This has the following consequences.

1. – No further pairwise keys and individual cluster keys are allowed to be derived with the captured or compromised node.
2. – The group node key and the network key are known. Consequently, no information in the global network can be secured with the network key and in the local network with the group node key.
3. – Also can be derived. This value is used to establish group node keys in all other clusters. Consequently, from the moment is leaked, a node that wants to securely share the group node key with a new cluster needs to use its individual cluster key. Note that is also used to derive the pairwise key between two CNs without involvement of the CH.

To summarize, inside the infected cluster only existing pairwise keys and individual cluster keys, different from the captured node, remain secure. Using the multicast key, the infected node can be excluded. In the other not infected clusters, only existing group node keys, pairwise keys and individual cluster keys remain secure. A group key cannot be updated using a broadcast message of the CH.

Consequently, the first step to execute by the BS is to share the information on the compromised node by broadcast communication in an authenticated way. Next, in order to make the system fully functional again, the BS should update the value and . In practise, it means that first all CNs should receive an updated version of both and , allowing them to update the values and . Also the CHs should receive an updated value of and . Since the shared key between BS and each CN and CH is not leaked, the updated info can be communicated using unicast communication to each entity. Fortunately, this situation will be very rare.

3.6.2 Capture of CH

We can assume that this situation is very unlikely as the CH is supposed to be a more powerful device, possessing more possibilities to guarantee secure storage of the secret parameters. However, if the CH is captured, is leaked and thus an attacker can create new valid combinations for and , thus creating fake nodes which cannot be verified by legitimate CHs. However, they can be detected by the BS in case the BS is storing the registered IDs of the CNs since the newly maliciously constructed parameters do not involve the registered IDs. Note that the other CHs cannot create valid individual cluster key or pairwise key requests, since they do not know , required to build the message from Equation 3.6. Moreover, the other nodes in the network can still continue to communicate securely by using the key .

Consequently, the variable requires an update. The BS sends a message to all the CHs by unicast communication using the current shared key between CH and BS, containing an updated version of and . Also for each node, the new versions of should be calculated by the BS and the update values for should be sent to the CN using unicast communication with the old .

Finally, it must be said that when a malicious CN and CH collaborate, the two main important secrets and are revealed and thus require a complete update. However, the knowledge of these both secrets, still do not reveal the individual shared keys for CNs and for CHs with the BS.

3.6.3 Changes for Honest Nodes

Here, we discuss the situations where an honest node replaces one cluster with another and where a node is added to or removed from the network.

3.7.1 Resistance Against Impersonation Attack

In this type of attack, the adversary (inside or outside the network) tries to take over the role of CN or CH.

1. – CH role: It would mean that the adversary is capable of generating a group node key, an individual cluster key, or information for a pairwise key establishment. Although, since each of these operations rely on the knowledge of both and , only the legitimate CH is able to do this.

   Even inside, CNs are not able to derive , since is not installed at node . Also CHs inside the network are not aware of .

2. – CN role: A node, not installed with valid information from the BS, is not able to send legitimate info to the CH since it cannot derive and , required to identity itself.

   Again, an inside CN knows , but not from that node and thus cannot take over the role of that sensor node identified with . Also an inside CH cannot take over the role of a sensor node for a communication to the BS, since it does not know and is not able to derive from the messages send in the network.

However, we should note that in the very rare situation where a malicious CN and malicious CH collaborate, this attack would become possible.

3.7.2 Resistance Against Node Capture

If a node is captured and the stored keys (protected by code obfuscation or other techniques) cannot be retrieved, the whole system is still secure. In case the key can be retrieved somehow, the procedure from the scheme in change mode, as explained in the previous section, should be followed.

If the CH is captured, although even more difficult since it is considered to have more resources and thus more capabilities to protect itself with, for instance, tamper proof hardware, the CNs inside the cluster can still communicate securely using the key , since the CH is not aware of . The procedure for key material update, as explained in the scheme in change mode, should be also followed.

3.7.3 Resistance Against Replay Attacks

Since the computation of an individual cluster key or the request for info at the CH in a pairwise key phase is performed in a one‐phase communication using random values, a replay attack will be noticed immediately. Note that the random values could be also replaced by counters, timestamps, or hashes of the transmitted message if these include a counter.

3.8.1 Number of Communication Phases

Table 3.1 enumerates the different keys used in the schemes and discusses the most important characteristics of the establishment process, in particular, the number of communication phases and the timing for establishment. As can be concluded from Table 3.1, we have one additional key, the multicast key , compared with LEAP. For most of the keys, the derivation in LEAP requires more communication phases. Moreover, SAK is also more flexible since the keys are ad hoc constructed and not limited to the construction at installation time like LEAP. Only the pairwise keys among nodes in the same cluster require one additional communication phase. This follows from the fact that our protocol has the additional feature that the CH is not aware of the established key. In case the CH would generate the key and forward it to both nodes, the key could also be constructed in two phases.

Key	Type	SAK	LEAP
	Network key	Installed	Installed
	Key with BS	Installed	Installed
	Multicast key	1 phase and ad hoc	Nonexistent
	Group key	1 phase and ad hoc	Constructed by CH and in unicast
			comm. sent to other nodes of cluster
	Key CN‐CH	1 phase and ad hoc	2 phases, only in limited time frame
			at installation time
	Pairwise key	3 phases and ad hoc	2 phases, only in limited time frame
		at installation time

Note that the impact of node capture and the corresponding update procedure is more or less similar. This follows on from the fact that all communication in SAK is also authenticated, which makes it possible to localize the source of the problem as in LEAP.

3.8.2 Storage Requirements

In SAK, each CN has to store three auxiliary parameters and 2 critical parameters (). By critical parameters, we mean parameters to be stored by preference in tamper proof hardware or protected by means of code obfuscation techniques. Initial values for them are pre‐installed. This key material allows the node to efficiently construct any type of keys, on‐the‐fly and ad hoc.

In LEAP, the individual and network key are also pre‐installed. The other keys need to be computed in a strict timeframe and are also stored at the node, preferably in tamper‐proof hardware. Moreover, in order to guarantee authentication, every node needs to store a one‐way hash chain with length corresponding to the number of messages to be send in authenticated way.

3.8.3 Packet Fragmentation

When the 6LoWPAN protocol is used, packets with a payload length of 70 bytes or less are never fragmented. However, when a packet is larger, fragmentation occurs. The number of required fragments is given by

(3.10)

with the size of the payload expressed in bytes. This follows on from the fact that the first fragment is limited to 64 bytes and all subsequent fragments are a maximum of 72 bytes.

For the construction of group key and the individual cluster key , there is no fragmentation. For the pairwise individual key, the packets sent by the CNs are fragmented in 2, the one from the CH to the CN is not fragmented. Finally, the packets transmitted in the multicast key and for authenticating the group key, fragmentation is also required.