Development of an extended topology-based lightweight cryptographic scheme for IEEE 802.15.4 wireless sensor networks

Abstract

Among the classes of wireless personal area networks, a wireless sensor network typically refers to a versatile and densely distributed sensing platform that enables the support of a wide variety of application domains. Among the various technical challenges addressed by more than one decade of research in wireless sensor networks, security across wireless links is by far one of the most critical ones and relates to the need of guaranteeing reliability and trustiness of the collected data. This article deals with the cryptographic aspects involved in securing wireless sensor networks, in terms of confidentiality and authentication. In particular, moving from some results previously achieved in our research activity, this article extends a cryptography scheme in order to better comply with the security requirements that arise from real-world wireless sensor network installations. The proposed scheme, called topology-authenticated key scheme 2, takes advantage of hybrid cryptography to provide security in the presence of resource-constrained sensor nodes using topology-authenticated keys to provide increased robustness to the scheme itself. The proposed extensions provide full practical support to star-topology wireless sensor networks and the article presents also some experimental results obtained by implementing the scheme on two different wireless sensor network platforms available for protocol stacks compliant with the IEEE 802.15.4 standard.

Keywords

Wireless sensor network security cryptographic scheme hybrid cryptography topology-authenticated key

Introduction

A wireless sensor network (WSN) is a network class where small, battery-powered sensor-equipped nodes (called sensor nodes or also motes) communicate using low-power, short-range, and low–data rate wireless technologies. WSNs are designed to provide high flexibility, high measurement redundancy, and potential wide sensor area coverage with small costs. A typical mote consists of a micro-controller unit and a radio transceiver powered by a battery pack. Computational power and available memory on a mote are normally highly constrained. As a consequence, software running on motes has to be as lightweight as possible. Moreover, such limitations led software developers to adopt low-level programming languages (and, sometimes, also assembly) to minimize both WSN software execution time and memory occupation. However, projects such as TinyOS,¹ ContikiOS², and RIOT-OS³ propose lightweight low-level software frameworks (assimilable to Operating Systems, hence the OS suffix) to enhance and make easier the software development process for WSNs. An important characteristic of these operating systems is the ready-to-use software primitives and components for, for example, resource management, communication protocols, and stacks, as well as the compatibility with different hardware platforms, so that developers can focus on writing the high-level logic of WSN applications, leaving the hardware heterogeneity issues to the OS code.

Depending on the context in which a WSN is deployed, the need for security in motes communications may arise. As any other network, confidentiality, integrity, and authentication can be enforced by means of cryptography, error detection/correction, and message authentication techniques. However, due to the hard constraints on computing power, memory, and available energy in WSN motes, standard state-of-the-art mechanisms and implementations of security-related algorithms are not always possible. In particular, considering confidentiality and authentications, the accepted techniques require the usage of public-key (i.e. asymmetric) cryptography, which implementations require an amount of memory (e.g. keys, temporary data, and look-up tables) and computing power (e.g. modular arithmetic, random number generation, factorization, exponentiation, and operations on points) which can represent an issue when combined with the actual applications on the motes. On the other hand, techniques involving symmetric cryptography, which are inexpensive and fast, require a key management mechanism to provide each mote the right key to use.

In order to overcome the described issues, a modern and effective approach is represented by the hybrid cryptography. Such techniques mix the public-key and symmetric cryptography in order to overcome the limitations of both approaches.

Background and motivations

Providing security primitives in traditional networks often implies the use of asymmetric cryptography mechanisms. This strategy guarantees an high degree of security, which is sustainable thanks to the ever increasing amount of available resources in terms of computation, memory, and energy. In fact, the robustness of asymmetric cryptography algorithms is highly dependent on the size of the keys that in turn affects the algorithms complexity and the performance of their implementations. In this sense, the elliptic curve cryptography (ECC)⁴ is able to provide a very high degree of security with keys shorter than the ones used in other state-of-art public-key algorithms (e.g. Rivest-Shamir-Adleman (RSA),⁵ ElGamal,⁶ etc.). On the other hand, while symmetric cryptography schemes can grant equivalent security and better performances, they require a mechanism for securely exchanging, updating and revoking the cryptographic keys among the parties. However, when the computation resources, the memory and the available energy become scarce, the complexity associated to asymmetric cryptography make it unfeasible in practice.

Although modified asymmetric cryptography schemes have been discussed,^7,8 in this context, the role of symmetric cryptography coupled to a key management technique becomes relevant again. In fact, key management is a fundamental problem in symmetric cryptography, and it has a wide coverage in literature.⁹

In the scheme proposed in this article, with respect to the existing key management solutions (see section “Comparison with state-of-the-art solutions”), keys are not fully distributed to each node of the network. Instead, they are the result of a dynamic generation phase based on partial key components (pre-distributed and locally stored in each node) as inputs, as in Pugliese and Santucci’s study.¹⁰ By combining components with low-complexity operations, nodes are able to compute the symmetric decrypt/encrypt key without any prior setup/negotiation.

More in detail, the proposed scheme (topology-authenticated key scheme (TAKS)) represents a quite extension of ephemeral Diffie–Hellman-like cryptographic protocol providing security over a resource-constrained network (typically ad hoc networks, for example, sensor networks for monitoring services) to establish both point-to-point and point-to-multipoint secure links among nodes. Such a scheme, called TAKS2, uses hybrid cryptography, and only partial components of symmetric keys are predistributed (and not the whole keys). It is an evolution of the original TAKS, that was earlier presented by Pugliese and colleagues.^10,11 The authentication mechanism of the scheme is based on nodes topology rather than on nodes identity, due to the limited lifetime of nodes in a resource-constrained network. Indeed, while nodes in infrastructure networks can rely on an external power supply and on a stable planned maintenance service with human intervention, the nodes in ad hoc networks can rely only on their own battery or some other energy harvesting mechanism, and maintenance services are usually remotely performed without human intervention. When an off-duty node is replaced with a new node, the new node identity enters in the network, but node topology remains unchanged and the authentication mechanism does not need any updating. Security features of TAKS2 include confidentiality (data encryption), data integrity, and sender authentication (signature). In TAKS2, the shared secret is a symmetric key generated by each party involved in the communication session upon a successful authentication process: each party verifies if the other party belongs to its authenticated network. The assignment parameter to each node is carried out by an external certification authority (CA), next the scheme parameters are pre-loaded into the nodes. Vector space rather than scalars over Galois fields has been introduced to allow the setup of truly scalable multicast communication sessions, hence without setting up multiple unicast sessions: the added dimensionality respect to scalars introduces a further degree of freedom for CA in the procedure of scheme parameters computation and assignment. From an engineering point of view, multicast sessions provide a relevant feature, especially for clustered networks, where time synchronization in data transmission is required as well as lighter memory storage: multicast sessions avoid traffic flooding, hence wasting of energy, when maintenance services are activated on such clustered networks (e.g. the updating of some configuration parameters in a specific portion of the network). With respect to classical solutions of key-assignment schemes on network, the scheme proposed in this article does not rely on pre-distribution of the complete keys but of a component of them: this is a nice property from a robustness point of view because the shared secret in elliptic curve TAKS (ECTAKS) is a function of both sender and receiver private key components, while in ordinary ephemeral Diffie–Hellman-like schemes typically the shared secret is a function of the complete sender whole private key and the receiver whole public key.

Moreover, the article reports the details of the implementation of the proposed scheme both in nesC/TinyOS 2.x, an operating system for a variety of families of sensor nodes,¹ and in bare-metal C language (supported by Atmel legacy libraries).¹² Finally, the article describes the experimental results obtained by means of real deployments on two hardware platforms: a clone of the famous Texas Instruments TelosB sensor node and a legacy sensor node provided by Atmel, both compliant with the IEEE 802.15.4 standard protocol. To resume, the main contributions of this article are:

TAKS2 SW design has been improved to consider also star topologies other than point-to-point ones (section “Introduction to 802.15.4”).

TAKS2 has been implemented on top of the MAC layer of two different IEEE 802.15.4–enabled WSN hardware platforms (section “TAKS2 design considerations”).

A testbed application has been developed to simulate a real-world monitoring scenario (sections “Basic network configuration” and “Scenarios description”).

This testbed has been used to validate the correctness of the scheme and to evaluate its performances in terms of computation time and memory occupation (sections “Performance evaluation” and “Results”).

Comparison with state-of-the-art solutions

Symmetric cryptography schemes, such as Advanced Encryption Standard (AES¹³), have usually very high performance and limited footprint in memory. Moreover, to improve performance, various micro-controllers and radio transceivers provide symmetric cryptography primitives directly as hardware accelerators. However, in symmetric schemes, the symmetric key needs to be known and available by every node before sending or receiving messages.

This requirement leads to the Key Distribution and Key Management issues frequently addressed in the literature. In fact, there are solutions based on key pre-distribution,¹⁴ which consist of the deterministic pre-distribution of keys. The trivial security solution consists in distributing a key for each pair of nodes, and, as extreme (and less secure) case, the same symmetric key for each node of the network. A derivation of the previous mechanism is the random pair-wise key schemes which consist of storing only a subset of all possible keys in each node.¹⁵ Nodes that wish to communicate have to negotiate a key with their peers, by selecting a random key from their subset. A simplification is possible if nodes locations are known, by providing to each node only the keys for the actual neighbors.¹⁶ In cluster-based networks, it is possible to adopt a cluster pre-distribution scheme. Clusters use different keys,¹⁷ while, within a cluster, the same key is used. Some mechanisms, for example, the master key pre-distribution⁹ define a master key which is used (combined with some previously exchanged nonce values) by nodes to re-create the symmetric key. Some schemes¹⁸ use different paradigms to distribute the keys, such as the use of mobile-agents capable of moving inside and distribute the cluster key dynamically and with reduced energy consumption. Alternative schemes use the key-matrix based dynamic key generation,¹⁹ the identity-based encryption²⁰ and the threshold cryptography²¹ to manage and distribute keys while reducing the energy consumption.

In this context, while TAKS2 does not achieve the same performance of a pure symmetric scheme, it resolves the secure key distribution problem with a small impact on performance. On the other side, public-key schemes (e.g. RSA and ECC) solve the key distribution problem and provide a higher degree of security at the cost of increased impact on performance and memory. For example, in a typical WSN node with a 8-bit micro-controller, the modular arithmetic operations, such as addition and multiplication, have to be implemented by means of algorithms which operate byte-wise on the numbers/points, introducing a non-negligible impact on performance and memory. In TAKS2, instead, the complexity and impact of such operations are moved to the key components generation: once the key components are available to nodes, the operation to combine them so obtaining the symmetric key (i.e. $TAK (\cdot)$ ) has a very lightweight impact on performance. This advantage also affects the communication throughput, since faster encryption/decryption operations result in faster communications.

In comparison with other hybrid-cryptography schemes,²²⁻²⁵ TAKS is suitable for real-world WSN motes, has lower average overhead both in timing performance and memory occupation, and provides the possibility of choosing different approaches for symmetric encryption/decryption and for authentication of received messages. In Table 1, we present a brief comparison of common general cryptographic solutions and TAKS2, while in Table 2 a comparison with other state-of-the-art hybrid cryptographic schemes for WSN is shown. TAKS supports all the hardware platforms supported by the TinyOS¹ operating system, whereas in most of the state-of-the-art hybrid cryptography schemes the OS/hardware support is not clear or limited to software simulations. The performance overhead (apart from the networking stack overheads) is comparable or better than the other schemes with a memory occupation which is beaten only by adopting external hardware modules (as in Hu et al.²⁷). TAKS provides its own lightweight key exchange protocol (described by Pomante et al.¹¹ and reported in this article), symmetric key encryption with no restriction on the key size or the cipher used and an authentication primitive based on the message authentication code (MAC) check. Other schemes, instead, have only a single^23,24 or fewer cryptographic capabilities.

Table 1.

Comparison of TAKS2 against other solutions.

	RSA	ElGamal	ECIES	AES	TAKS2
Type Key bit-length order	Public-Key	Public-Key	Public-Key	Symmetric	Hybrid
	Thousands	Thousands	Hundreds	Hundreds	Hundreds
WSN performance overhead	High	High	High	Low	Low
WSN memory overhead	Moderate	Moderate	Moderate to High	Low	Low
Encryption + Authentication	Separated (RSA sign.)	Separated (DSA)	Separated (ECDSA)	Yes (CCM/GCM modes)	Yes
Secure against node capture	Yes	Yes	Yes	No	Yes

WSN: wireless sensor network; AES: Advanced Encryption Standard; TAKS2: topology-authenticated key scheme 2; DSA = digital signature algorithm; ECIES = elliptic curve integrated encryption scheme; ECDSA = elliptic curve digital signature algorithm; CCM = counter with CBC-MAC mode; GCM = Galois counter mode.

Table 2.

TAKS2 comparison with other state-of-art hybrid-cryptography schemes. The table compares different features: the supported operating systems, the overhead (i.e. additional delay) introduced in communications, the amount of additional memory required to support the scheme, the adopted key exchange protocol (if any), the symmetric encryption and decryption protocols (if any) and the authentication protocol (if any).

Scheme	Supported platform	Perf. overhead TX/RX	RAM/ROM overhead	Key exchange	Symmetric encryption/decryption	Authentication
SCUR²⁶	TinyOS	?	?	Pre-distributed	Rabbit	None
SecFleck²⁷	Hardware-module	∼800 ms/∼800 ms	1082 B/52 B	RSA-based	XTEA	RSA-based
Yue et al.²²	?	∼1000 ms, ∼1000 ms	?	?	AES/ECC	MAC-based
EHKM²³	Simulations	?	N/A, ∼1500 B	ECDH	None	None
Attiya et al.²⁴	TOSSIM + MICA2	∼26 ms (only key mgn)	∼34 kb, ∼2.7 kb	Cluster-based	None	None
Manjunath et al.²⁵	Simulations	∼8 s	?	ECDH	?	Certificate-based
TAKS2 (this work)	TinyOS	∼30 ms, ∼15 ms	∼10 kb, ∼700 B	TAKS	Any, Selectable	MAC-based

RAM: random access memory; ROM: read only memory; TX: transmitter; RX: receiver; MAC: message authentication code; AES: Advanced Encryption Standard; TAKS: topology-authenticated key scheme; SCUR = secure communications in wireless sensor networks using rabbit; XTEA = eXtended tiny encryption algorithm; EHKM = efficient hybrid key management; ECC = elliptic curve cryptography; ECDH = elliptic curve diffie-hellman.

The question mark (“?”) denotes that no information about the referenced feature has been found.

Paper organization

The next sections of the article are organized as follows. In section “TAKS,” original TAKS scheme is resumed along with the enhancements of its second version, that is, TAKS2. Section “Security analysis” covers the security analysis of TAKS2. Section “Computational and spatial complexity analysis” describes the theoretical computational and spatial complexity of TAKS2. In section “Design and implementation issues,” design and implementation issues over two different WSN platforms are discussed while, in section “Verification and performance evaluation,” the verification and the performance evaluation processes, with related experimental results, are described in detail. Finally, section “Conclusions and future works” concludes the article with some comments and planned future works.

TAKS

TAKS is a cryptographic scheme to provide passive security at link layer. TAKS is a hybrid deterministic key establishment protocol (KEP) to establish both pair-wise and cluster-wise secure links. Its security functions include confidentiality (data encryption/decryption), data integrity, and sender authentication (signature). The symmetric key is generated by the parties on a successful authentication process (TAKS Authentication) based on the verification that the involved parties belong to a predefined planned network topology (PNT). We define qualitatively a PNT to be the network topology planned by the network planner in order to fulfill given requirements. In this context, the eligible neighbor nodes are defined as the nodes authorized to communicate with a target node. A PNT represents the network topology as it is expected to be at service runtime: therefore, the PNT can be considered as the authenticated network topology (ANT) for that portion of network.

Each node pre-stores a set of TAKS security parameters (denoted as local configuration data, LCD) namely the local key component (LKC), a set of transmitted key components (TKCs) and and a set of topology vectors (TVs), each TV associated to a node belonging to the ANT. LKC takes the role of private key of the node while TKCs and TVs take the role of public key of the node/cluster of nodes. An (external) CA binds LKC to the node ID and TKCs/TVs to the nodes IDs (or Cluster IDs) associated to the ANT. Therefore, the membership of a node to a specific ANT is certified by the assignment of the associated TV. Any node in a specific ANT is an authenticated node. A TAK is generated if the involved parties belong to the same ANT (hence the attribute of “topology-authenticated key”). The PNT is implemented as a distributed data structure, in which the information on the available communication links are stored for each node in the network. In particular, each node portion of the PNT contains (at minimum) the subset of TKCs and TVs relative to each one available to the node. Additional information could be stored if required by the TAKS implementation. TAKS2 is the enhanced version:¹¹ both represent a hybrid cryptography scheme, since they do not rely explicitly on asymmetric or symmetric keys to secure the WSN data transmissions. In literature, there exist other hybrid cryptography schemes^25,28,29 but TAKS2 is the only scheme proving WSNs with a secure encryption mechanism along a topology-based authentication with minimal performance overhead and memory footprint.

Description of the cryptographic scheme

Before describing the inner mechanisms of the cryptographic scheme, we present the security level definitions that will be adopted in the rest of the article:¹¹

Public: general public information, accessible by anyone (attackers included).

Restricted: network-level private information (accessible by nodes in the network).

Private: node-level private information.

Secret: planner-level private information.

As a requirement of the scheme, a data structure called LCD has to be stored inside the WSN nodes. The LCD contains the definition of scheme parameters, including the key partial components and topology information. Topology definition can be physical (e.g. with geographical position of nodes) or logical (i.e. in terms of which node pairs can communicate) depending if the scheme is applied on physical/MAC layer or upper layers, respectively. LCD includes:

The local key component (LKC);

The (ephemeral) transmit key component (TKC);

And planned network topology (PNT).

LKC is a component that is kept secret and stored in the target node, while TKC is a public component that is distributed to every node enabled to communicate with the target node. PNT is a set of TVs used to describe the relationship (one-to-one or one-to-many) among eligible neighbor nodes for pair-wise and cluster-wise link configuration, respectively. The security of the proposed scheme is based on the confidentiality of some offline secret parameters (denoted as “TAKS primitives” in the following sections) used to generate the keys.

In the following paragraph, we introduce the scheme (details can be found in Pugliese and colleagues’ studies).^10,11

Choose a large prime number $p$ such that $p >> N$ where $N$ is the total number of nodes in the WSN. Let $U$ be a tri-dimensional vector space over $GF (p)$ with $\bar{u} \in U$ as generic vector. $\bar{u}$ is represented by $(u_{x}, u_{y}, u_{z})$ with $u_{x}, u_{y}, u_{z} \in GF (p)$ .

Let be a function, called $TAK (\cdot, \cdot)$ with the following characteristics:

R1. It must be a surjective function and $TAK (\bar{u}, \bar{u}') \neq 0, \forall \bar{u}, \bar{u}' \in U$ .

R2. $TAK (\bar{u}, h (\bar{u}')) = TAK (\bar{u}', - h (\bar{u})), \forall \bar{u}, \bar{u}' \in U$ , where $h ()$ is an arbitrary vector function in $U$ .

R3. $T A K (α \bar{u}, {\bar{u}}^{'}) = T A K (\bar{u}, α {\bar{u}}^{'}) = α T A K (\bar{u}, {\bar{u}}^{'}), \forall \bar{u}, {\bar{u}}^{'} \in U$ and $α \in GF (p)$ .

The $TAK (\cdot, \cdot)$ function is used to generate the topology-authenticated keys from the pre-distributed components.

Let $g (\cdot, \cdot)$ be a function satisfying the following requirements:

R4. It must be a surjective function.

R5. $g (p, v) = 0$ only for a predefined set of distinct values of $p, v$ .

The $g (\cdot, \cdot)$ function is used to verify the authenticity of every incoming message.

In Figure 1, a representation of the proposed scheme is shown.

Figure 1.

TAKS2 scheme description.

Given the set of eligible neighbors nodes of node $n_{i}$ (the set $σ (i)$ , the PNT of node $n_{i}$ is defined to be the set of TVs $TV (i) = {TK C_{σ (i)}}$ . Along the PNT, each node stores also its $TK C_{i}$ and $LK C_{i}$ .

In every communication, a nonce value $α \in GF (p)$ has to be generated. If the node $n_{i}$ wants to communicate with $n_{j}$ , it builds a message payload containing:

The result of the symmetric key encryption of the message, the cipher text (c), using $SS = α TAK (LK C_{i}, TK C_{j})$ as a symmetric key.

The key reconstruction information (KRI, d), where $d \in U$ and $d = - α TK C_{i}$ ;

A MAC $(τ)$ (denoted as $MAC (\cdot)$ ) and computed using any secure cryptographic keyed hash function with $α TAK (LK C_{i}, TK C_{j})$ as key.

As shown in Figure 1, $alpha$ and all the values generated from it (e.g. $SS$ , $d$ , etc.) are generated for each communication and never stored.

Upon the reception of a message, the node $n_{j}$ calculates back the symmetric key to correctly decrypt the content of the message. The key is computed with $TAK (LK C_{j}, d)$ because:

\begin{matrix} α TAK (LK C_{i}, TK C_{j}) = α TAK (LK C_{j}, - TK C_{i}) \\ = TAK (LK C_{j}, - α TK C_{i}) \\ = TAK (LK C_{j}, d) \end{matrix}

The message authenticity function $g (\cdot, \cdot)$ has to return zero when original encryption key and computed decryption key are identical. As shown in Figure 1, this computation uses $τ$ to verify whether this condition is met.

Starting from the first version, TAKS has evolved into TAKS2.^10,11 This second version has the following main features:

TVs in a node can now coincide with the TKCs of its eligible neighbors. This reduces the memory occupation in nodes when pair-wise communications are adopted.

In TAKS2, the transmission protocol uses only a single phase for the setup of the scheme, that is, no prior exchange of the TKCs between nodes is needed. This is possible thanks to the $d$ information contained in each message.

In TAKS2, authentication is performed by a standard authentication function (e.g. HMAC).

The main drawback in TAKS2 is the ephemeral TKC to be transmitted each time a new $SS$ is needed. Although this increases message size and thus energy consumption per transmission, in monitoring applications, the sample rate depends on the dynamics of the monitored system: if high transmission rates are needed, key size (hence message size) should be reduced without degrading security. In this context, as described in the previous section, TAKS2 can adopt ECC in order to reduce key size.³⁰

Formal apparatus of TAKS/TAKS2

Building blocks of the proposed scheme are as follows:

Hybrid-key cryptography.

Topology-based network authentication.

Hybrid-key cryptography

Let nodes $n_{i}$ and $n_{j}$ be a pair of nodes. The following definitions are assumed:

(a) Let $GF (p)$ be a prime-based Galois Field such that $p >> N$ with $N$ equal to the number of nodes in the network and $p$ a large prime number such that $p - 1$ has a suitable large prime divisor ( $p$ should be a safe prime number). Otherwise, let $GF (p^{n})$ be an extended Galois Field with $p$ prime (e.g. $p = 2$ ), $n$ an integer and $p^{n} >> N$ . Hereinafter simply $GF (\cdot)$ .

(b) Let $U$ a vector space of dimension $d$ (suppose $d = 3$ ). Let $KL \subseteq U$ , $KT \subseteq U$ and $KV \subseteq U$ .

(c) Let $\bar{u} = (u_{1}, u_{2}, u_{3}, . . ., u_{d})$ be a vector over $GF (\cdot)$ and $k \bar{u} \in GF (\cdot)$ = $(k u_{1}, k u_{2}, . . ., k u_{d})$ for $k = 1, 2, 3, . . . p - 1$ .

(d) Select $\bar{a_{i}}, \bar{a_{j}}, \bar{m} \in U$ such that $({\bar{a}}_{i} \times {\bar{a}}_{j}) \neq 0$ . $\bar{a_{i}}, \bar{a_{j}}, \bar{m}$ are secret. The set $A = {a_{i}}$ defines the TAKS node IDs (these IDs are used only during the key components computation).

(e) Let $b \in GF (\cdot)$ be a multiplicative generator in $GF (\cdot)$ . $b$ is secret.

(f) Let $\bar{c} \in U$ . $c$ is secret.

(g) Parameters $A, b, \bar{c}, \bar{m}$ are called TAK generators.

(h) Let $\bar{LKC} \in KL \subseteq U$ the LKC. $LKC$ is secret.

(i) Let $\bar{TKC} \in KT \subseteq U$ the TKC. $TKC$ is public.

(j) Let $\bar{t} \in KV \subseteq U$ the TV. $\bar{t}$ is public.

(k) Let $\bar{LKC}, \bar{TKC}, \bar{t}$ be result of public hardly invertible (i.e. one-way) functions of the TAK generators $(A, b, \bar{c}, \bar{m})$ .

(l) Let $U'$ be a vector space same dimension of $U$ which elements $\bar{u'} = (u'_{1}, u'_{2}, . . ., u'_{d})$ are in $Z$ .

(m) Let $gf 2 z : U \to U'$ be a function which convert any $\bar{u} \in U$ in a correspondent $\bar{u'} \in U'$ such that $u = u'$ .

(n) Let: $\bar{{a'}_{i}} = gf 2 z (\bar{a_{i}}), \bar{{a'}_{j}} = gf 2 z (\bar{a_{j}}), \bar{m'} = gf 2 z (\bar{m})$ and $\bar{c'} = gf 2 z (\bar{c})$ .

Pair-wise TAKS2

In pair-wise communications, the scheme can be simplified using the following additional definitions:

(o) Let $f (\bar{u'}) = k b^{\bar{m'} \cdot \bar{u'}}$ be a scalar function where $\bar{m'} \in U'$ satisfied (d) and $k \in GF (\cdot)$ is an arbitrary constant.

(p) Let be ${\bar{s}}_{i} = \bar{m} f ({\bar{a}}_{i})$ and ${\bar{s}}_{j} = \bar{m} f ({\bar{a}}_{j})$ .

(q) Let ${\bar{k}}_{l}_{i} = \bar{LK C_{i}}$ , ${\bar{k}}_{l}_{j} = \bar{LK C_{j}}$ , ${\bar{k}}_{t}_{i} = \bar{TK C_{i}} = \bar{t_{i}}$ , ${\bar{k}}_{t}_{j} = \bar{TK C_{j}} = \bar{t_{j}}$ be defined as:

${\begin{matrix} {\bar{k}}_{l}_{i} = {\bar{a}}_{i} k b^{\bar{m'} \cdot {\bar{a}}_{i}'} \\ {\bar{k}}_{t}_{i} = {\bar{s}}_{i} \times {\bar{a}}_{i} \end{matrix} {\begin{matrix} {\bar{k}}_{l}_{j} = {\bar{a}}_{j} k b^{\bar{m'} \cdot {\bar{a}}_{j}'} \\ {\bar{k}}_{t}_{j} = {\bar{s}}_{j} \times {\bar{a}}_{j} \end{matrix}$

(r) Expressions for ${\bar{k}}_{l}$ , ${\bar{k}}_{t}$ and $f (\bar{u'})$ are public according Kerckhoffs principle.

Theorem 1 (pair-wise TAKS2 generation)

Let $n_{i}$ and $n_{j}$ be a node pair. Fix $\bar{m}$ , $\bar{c}$ , $b$ and let ${\bar{a}}_{i}, {\bar{a}}_{j} \in A$ be a generic couple of TAKS node IDs in $A$ compliant to definitions (d) and let $f (\bar{u})$ be a function defined as (o.) and $α$ a random value in $GF (\cdot)$ . If expressions for ${\bar{k}}_{l}_{i}$ , ${\bar{k}}_{t}_{i}$ and for ${\bar{k}}_{l}_{j}$ , ${\bar{k}}_{t}_{j}$ are the same as (n) then

\begin{matrix} TAK = α TAK ({\bar{k}}_{l}_{i}, {\bar{k}}_{t}_{j}) = α TAK ({\bar{k}}_{l}_{j}, - {\bar{k}}_{t}_{i}) = α {\bar{k}}_{l}_{i} \cdot {\bar{k}}_{t}_{j} \\ = - α {\bar{k}}_{l}_{j} \cdot {\bar{k}}_{t}_{i} \end{matrix}

Proof

Applying the definition of $TA K_{i}$

\begin{matrix} TA K_{i} = α TAK ({\bar{k}}_{l}_{i}, {\bar{k}}_{t}_{j}) = α {\bar{k}}_{l}_{i} \cdot {\bar{k}}_{t}_{j} = α {\bar{a}}_{i} f ({\bar{a'}}_{i}) \cdot ({\bar{s}}_{j} \times {\bar{a}}_{j}) \\ = α {\bar{a}}_{i} k b^{\bar{m'} \cdot {\bar{a'}}_{i}} \cdot (\bar{m} b^{\bar{m'} \cdot {\bar{a'}}_{j}} \times {\bar{a}}_{j}) \\ = α k b^{\bar{m'} \cdot ({\bar{a'}}_{i} + {\bar{a'}}_{j})} {\bar{a}}_{i} \cdot (\bar{m} \times {\bar{a}}_{j}) = β {\bar{a}}_{i} \cdot (\bar{m} \times {\bar{a}}_{j}) \end{matrix}

Applying the definition of $TA K_{j}$

\begin{matrix} TA K_{j} = α TAK ({\bar{k}}_{l}_{j}, - {\bar{k}}_{t}_{i}) \\ = - α {\bar{k}}_{l}_{j} \cdot {\bar{k}}_{t}_{i} \\ = - α {\bar{a}}_{j} f ({\bar{a'}}_{j}) \cdot ({\bar{s}}_{i} \times {\bar{a}}_{i}) \\ = - α {\bar{a}}_{j} k b^{\bar{m'} \cdot {\bar{a'}}_{j}} \cdot (\bar{m} b^{\bar{m'} \cdot {\bar{a'}}_{i}} \times {\bar{a}}_{i}) \\ = - α k b^{\bar{m'} \cdot ({\bar{a'}}_{j} + {\bar{a'}}_{i})} {\bar{a}}_{j} \cdot (\bar{m} \times {\bar{a}}_{i}) = - β {\bar{a}}_{j} \cdot (\bar{m} \times {\bar{a}}_{i}) \end{matrix}

Using the vector algebra property $\bar{x} \cdot (\bar{y} \times \bar{z}) = \bar{y} \cdot (\bar{z} \times \bar{x})$ , we have

\begin{matrix} TA K_{i} = β {\bar{a}}_{i} \cdot (\bar{m} \times {\bar{a}}_{j}) = β {\bar{a}}_{j} \cdot ({\bar{a}}_{i} \times \bar{m}) = \\ = - β {\bar{a}}_{j} \cdot (\bar{m} \times {\bar{a}}_{i}) = TA K_{j} \end{matrix}

So, in TAKS2:

The transmitter TAK is the scalar product between the LKC and the TV associated to the destination node.

The receiver TAK is the scalar product between the LKC and the TKC.

Furthermore, fixing $\bar{m}$ , $\bar{c}$ , $b$ and letting ${\bar{a}}_{i}, {\bar{a}}_{j} \in A$ , the following properties hold:

$TAK \neq 0$ since $\bar{m'} \cdot ({\bar{a}}_{i} \times {\bar{a}}_{j}) \neq 0$ from (b) and $f (\bar{u}) \neq 0$ from R1.

The LKC components are different for different nodes since ${\bar{k}}_{l}_{i} ∥ {\bar{a}}_{i}$ and ${\bar{k}}_{l}_{j} ∥ {\bar{a}}_{j}$ with ${\bar{a}}_{i} \times {\bar{a}}_{j} \neq 0$ . Hence ${\bar{k}}_{l}_{i} \times {\bar{k}}_{l}_{j} \neq 0$ .

The TKC components are different for different nodes since ${\bar{k}}_{t}_{i} ∥ \bar{m'} \times {\bar{k}}_{l}_{i}$ and ${\bar{k}}_{t}_{j} ∥ \bar{m'} \times {\bar{k}}_{l}_{j}$ and ${\bar{k}}_{l}_{i} \times {\bar{k}}_{l}_{j} \neq 0$ .

Topology-based authentication

As by Pugliese and Santucci,¹⁰ TAKS/TAKS2 authentication is based on two main elements: a verification function $g (\cdot, \cdot)$ and a set of TVs, one for each eligible neighbors nodes of $n_{i}$ .

With the definition of $TV (i) = {TK C_{σ (i)}} = {{\bar{k}}_{t}_{σ (i)}}$ as the set of $σ (i)$ TV stored in node $n_{i}$ , we can directly set ${\bar{t}}_{j} \equiv {\bar{k}}_{t}_{j}$ .

Given a user-selected keyed hash function,³¹ $MAC (\cdot)$ we define the authentication function as $g (p, v) = g (S S_{j}, S S_{i}) = MAC (S S_{j}) - MAC (S S_{i})$ . This latter definition is compliant with R4 and R5 requirements defined in the previous section.

Theorem 2 (network topology authentication)

In a node pair $n_{i}$ and $n_{j}$ , if $MAC (S S_{j})$ computed by receiver $n_{j}$ is equal to $MAC (S S_{i})$ sent by transmitter $n_{i}$ , then $n_{i}$ is network topology authenticated by $n_{j}$ .

Proof

Node $n_{j}$ computes $S S_{j} = {\bar{k}}_{l}_{j} \cdot d$ . Node $n_{i}$ computes $S S_{i} = α {\bar{k}}_{l}_{i} \cdot {\bar{k}}_{t}_{j}$ . If $g (S S_{j}, S S_{i}) = 0$ , we have that $MAC (S S_{j}) = MAC (S S_{i})$ . Cryptographic hash function collision property³⁰ implies that $S S_{j} = S S_{i}$ or that ${\bar{k}}_{l}_{i}$ , ${\bar{k}}_{l}_{j}$ , ${\bar{k}}_{t}_{i}$ , and ${\bar{k}}_{t}_{j}$ are compliant to R2 and R3. Thus, $n_{i}$ is network topology authenticated by $n_{j}$ .

Security analysis

Security analysis can be performed along three proofs: entropy highness of the secret share, robustness (or reliability) of data transmissions for a single node (node level) and for a set of connected nodes (network level). The former deals with the goodness and effectiveness of the generated TAK as a cryptographic key for an high-entropy encoding. The latter with the complexity of the reverse problem associated to the cryptosystem to derive the private key materials from publicly known parameters: the lower the complexity, the lower the reliability can be assured by the cryptosystem in data transmission: at a node level this means the evaluation of the computational complexity of the reverse problem. However, in case of a compromised node (e.g. the node has been physically captured by the attacker), next problem would become how reliability in data transmission for other nodes could be reduced in case where one or more nodes were compromised. Therefore, robustness at network level can be straightforwardly defined as the maximum percentage of compromised nodes that cannot reduce reliability in data transmissions for the other nodes in the network.

Let us start with TAK entropy evaluation. TAK entropy relies on the randomness of the secret TAKS primitives $\bar{m}$ , $\bar{c}$ , $\bar{a}$ , and $b$ . By definition, these primitives are randomly chosen. Key components $\bar{k_{l}}$ and $\bar{k_{t}}$ are injective functions of secret TAKS primitives as well as TAK function defined as the scalar products, again an injective function, between vectors ${\bar{k_{l}}}_{i}$ and ${\bar{k_{t}}}_{j}$ or, equivalently, between vectors ${\bar{k_{l}}}_{j}$ and ${\bar{k_{t}}}_{i}$ : therefore, randomness is preserved from TAKS primitives to TAK. Randomness of ${\bar{k_{t}}}_{i}$ ( ${\bar{k_{t}}}_{j}$ ) can be further enhanced by a random multiplicative factor to be locally applied to build the ephemeral $\bar{k_{t}}$ is being transmitted from node $i$ (node $j$ ) to node $j$ (node $i$ ). Therefore, particular care has been used in designing and implementing the pseudo-random number generator (PRNG) algorithm in the nodes.

For what concerns TAKS robustness at single node and network levels, the following proofs can be provided.

Scheme robustness at single node level: In TAKS2, the reverse problem derives the secret TAKS primitives $\bar{m}$ , $\bar{c}$ , $\bar{a}$ , and $b$ from the knowledge of $\bar{k_{l}}$ , $\bar{k_{t}}$ , and the (public) expression of $f (\cdot)$ . Prudentially, we include also $\bar{k_{l}}$ even if this is the private key component because both $\bar{k_{l}}$ , $\bar{k_{t}}$ are preloaded in the node and therefore exposed to attacks ranging from power analysis or side-channel attacks to physical capture.

Proof

Each equation in (q) shows that the functional relationship between ${\bar{k_{l}}}_{j}$ , ${\bar{k_{t}}}_{i}$ , $\bar{m}$ , $\bar{c}$ , $\bar{a}$ , and $b$ to be a discrete logarithm which is a problem of well-known complexity by cryptologists (also denoted as the Diffie–Hellman problem)

\begin{matrix} \bar{k_{l}} = \bar{a} b^{\bar{m} \cdot (\bar{a} + \bar{c})} \\ \bar{k_{t}} = (\bar{m} \times \bar{a}) b^{\bar{m} \cdot \bar{a}} \end{matrix}

Scheme robustness at network level: Given a network with N nodes, a cryptographic scheme is $T$ -secure if an attacker should capture at least $T + 1 < N$ nodes and therefore should compromise at least $T + 1$ sets of their preloaded key materials to gain enough information to derive the other $N - (T + 1)$ key materials preloaded in the other nodes of the network or, in other words, compromising only $T$ sets of preloaded key materials cannot reduce the reliability in data transmissions for the other $N - T$ nodes.

The maximum value for $T$ depends on the capability of network protocols to rearrange connection among the residual $N - T$ nodes without degradation of the overlying services. However, usually is provided the proof for the case $T = N$ so that any choice for $T$ is covered. It can be proved that TAKS is $N$ -secure (i.e. $T = N$ ).

Proof

Equations in (q) should be both solved for $\bar{a}$ , $\bar{m}$ , $\bar{c}$ , and b to derive $\bar{k_{l}}$ , $\bar{k_{t}}$ and therefore, all TAKs in the network. According to the definition of $T$ -Security, the proof is iteratively developed: in case node $i$ has been captured, equations in (q) return $\approx p^{4}$ free solutions for ( $\bar{a}$ , $\bar{m}$ , $\bar{c}$ , $b$ ), hence $\approx p^{4} - 1$ spurious solutions for TAK. A solution is defined spurious when part of it is computed by assigning arbitrary values to some unknowns due to lack of information on them (in this case $\approx p^{4} - 1$ constraints are missing) and the corresponding TAK results incorrect and useless for the attacker. Therefore, another node, say node $j = 2$ , should be captured to compromise another set of key materials: equations in (q) now return $\approx p^{4} - p$ free solutions for ( $\bar{a}$ , $\bar{m}$ , $\bar{c}$ , $b$ ), hence $\approx p^{4} - p - 1$ spurious solutions for TAK. Note that the constraint $a_{i} \times a_{j} \neq 0$ indicates that $a_{i}$ and $a_{j}$ cannot be parallel which eliminates $\approx p$ solutions for ( $\bar{a}$ , $\bar{m}$ , $\bar{c}$ , $b$ ). Next step for the node $j = 3$ , equations (q) would return $\approx p^{4} - 2 p$ free solutions for ( $\bar{a}$ , $\bar{m}$ , $\bar{c}$ , $b$ ), hence $\approx p^{4} - 2 p - 1$ spurious solutions for TAK. Note that the constraint $a_{i} \times a_{j} \neq 0$ shall be applied twice (for nodes $j$ with $j = 2$ and $j = 3$ ) and $\approx 2 p$ solutions for ( $\bar{a}$ , $\bar{m}$ , $\bar{c}$ , $b$ ) shall be eliminated.

Iteratively, if the node $j = n$ has been captured and its set of key materials compromised, equations in (q) return $\approx p^{4} - np$ free solutions for ( $\bar{a}$ , $\bar{m}$ , $\bar{c}$ , $b$ ), therefore still $\approx p^{4} - np - 1$ spurious solutions for TAK: as $N << p$ , there are still $p^{4} - Np \approx p^{4}$ spurious solutions for TAK even for $n = N$ .

Computational and spatial complexity analysis

In this section, we describe the computational and spatial complexity of proposed scheme regardless of which symmetric encryption/decryption algorithm and MAC function are adopted. Table 3 shows the computational complexity of TAKS2. Also, assuming that:

$n$ is the adopted key size (in bytes).

$# σ (i)$ is the cardinality of the set $σ (i)$ .

Data are made of words of 1 or multiple bytes.

The generation of a random word costs $O (1)$ .

The sum of two words costs $O (1)$ .

The multiplication of two words costs $O (1)$ .

Then:

To generate a $n$ -bytes random byte-stream $(rand ())$ , we need to generate $(1 / s) O (n)$ random words, so the cost is $O (n)$ ( $s$ is the size of the word in bytes).

To add two $n$ -bytes number, we need to perform $O (n)$ additions of word, so a full addition costs $O (n)$ .

To multiply two $n$ -bytes number, we need to perform $O (n (n + 1) / 2)$ multiplications and $O (n)$ additions. So a multiplication costs $O (n^{2})$ .

An inner product of two vectors of $n$ -bytes components, consists of three $n$ -bytes multiplications and two $n$ -bytes additions, so an inner product costs $O (n^{2})$ .

To compute TAK at the destination node, we need to search for the right TKC/TV (e.g. linear search: $O (# σ (i))$ ) and to compute the inner product with the LKC, for a total cost of $O (n^{2} + # σ (i))$ .

Table 3.

Computational complexity of TAKS2 functions.

Function	t(n)	$O_{t} (n)$
$rand ()$	$n$	$O (n)$
$get_tak ()$	$# σ (i) + 3 n + 3 \frac{n (n + 1)}{2}$	$O (n^{2} + # σ (i))$
$multiply ()$	$\frac{n (n + 1)}{2} + n$	$O (n^{2})$
$inner_product ()$	$3 \frac{n (n + 1)}{2} + 2 n$	$O (n^{2})$

In a point-to-point communication scenario, since sending a complete message using TAKS2 consists of executing the functions $rand ()$ , $get_tak ()$ , and $multiply ()$ , the total computational complexity of TAKS2 encryption is $O (n^{2} + # σ (i)) \approx O (n^{2})$ . The decryption step performed by the destination node has a complexity equal to the complexity of an $inner_product ()$ , so $O (n^{2})$ .

The spatial complexity is analyzed as follows. Assuming:

Each key component (LKC, TKC) requires k bytes to be stored in the node memory.

The $α$ random value, the key reconstruction information $KRI$ and the $SS$ require k bytes each.

Each node has to store its LKC and the TKCs of each neighbor node inside the PNT.

We can state that:

$α$ , $KRI$ , SS, and $τ$ require a constant memory size $(O (1))$ .

Each node has to reserve an additional space of $O (k + n * k) = O (n * k)$ for storing the PNT, where $n$ is the maximum number of neighbor nodes (i.e. the maximum degree that can be found in the WSN topology graph).

Design and implementation issues

The topic of this section is the design and implementation of TAKS2 for a real-world star topology WSN. First, a basic background on 802.15.4 is provided, followed by specific considerations for TAKS2; then, implementation issues are analyzed for software architecture and details about two different available MAC layers are explained.

Introduction to 802.15.4

The IEEE 802.15.4³² is the reference standard on low rate wireless personal area networks (abbr. LR-WPAN). It describes the first two layers of the ISO/OSI networking protocol stack (the physical layer and the MAC layer). The IEEE 802.15.4 defines two types of nodes: the full function devices (FFD) and the reduced function devices (RFD). While the RFD are devices capable to perform only basic computation and data retrieval, the FFD are more complex and computational powerful devices, capable also to act as WPAN coordinator of the network. The WPAN coordinator (i.e. coordinator) is the device responsible of creating, maintaining, and synchronizing the network.

The standard defines some basic network topologies (e.g. basic peer-to-peer, star topology, and cluster tree) and two WPAN types. The nodes in a beacon-enabled WPAN have an isochronous channel access obtained through the use of beacon frames emitted by the coordinator. Instead, in a beaconless WPAN, the nodes communicates without such frames. In both cases, the CSMA-CA channel access mechanism is used: in the case of beacon-enabled PANs, the slotted CSMA-CA is used, while the unslotted CSMA-CA (ALOHA) is used in the beaconless PANs.

In the case of beacon-enabled PANs, the standard defines a Superframe structure (Figure 2). This structure can be further divided into the active and the inactive portion. Inside the active portion, a set of optional contention-free slots can be defined to reserve communication slots to a chosen set of devices (up to 7).

Figure 2.

The IEEE 802.15.4 superframe structure.³²

Each of the two provided layers offers a set of services via a corresponding set of interfaces. The services offered by the PHY layer to the MAC layer are the PHY data service (PD) and the PHY management service (PLME). The services provided by the MAC layer to the higher layers are the MAC data service (MCPS), and the MAC management service (MLME).

While the IEEE 802.15.4 PHY layer is commonly implemented in radio chips, the MAC layer specification has not a wide selection of available implementations. This is due the fact that applications often use simpler techniques for accessing the communication channel instead of implementing a 802.15.4 compliant MAC layer. Despite this aspect, in literature exist some valid implementations of the 802.15.4 MAC layer. In this article, we consider two well-known implementations: the TKN154³³ and the Atmel Stack MAC layer.³⁴

TAKS2 design considerations

In order to provide an efficient TAKS2 architecture design, the features of the IEEE 802.15.4 standard have been taken into consideration in the design phase.

First of all, in order to provide a seamless and efficient integration with the IEEE 802.15.4 standard, TAKS2 is designed to operate directly at the MAC layer although it is possible, in general, to implement TAKS also in upper layers. TAKS2 cryptographic primitives are made available to the MAC layer services, for example, during the device association, to achieve a better control over incoming and outgoing transmissions and smaller latency during encryption, decryption, and authentication.

As a consequence, a device inside a TAKS2-enabled WSN has to pass two kinds of association before being able to transmit and receive data from the coordinator. The first is the IEEE 802.15.4 MAC association step (via the MLME-ASSOCIATE interface defined in the standard), while, the second is the TAKS2 association, a primitive that enables a device-coordinator link to be validated through the TAKS2 authentication function defined in the previous sections.

TAKS2 uses a set of finite state machines (FSMs; Figure 3) to control the behavior of cryptographic primitives. In particular, each device node has a tri-state machine with the following states:

Unknown—the device is not currently associated to the coordinator.

Associated—the device is associated (via the IEEE 802.15.4 association mechanism) to the coordinator.

Ready—the associated device is authenticated also via the TAKS2 association. In this state, the device can exchange messages with the coordinator.

Figure 3.

FSM used by TAKS2 for the device nodes.

The coordinator keeps and updates a copy of the state of each device FSM, so that is also possible for it to monitor the overall WSN state. TAKS2 uses a set of additional data structures (Figure 4) to support the IEEE 802.15.4 standard:

The Address Pool represents the set of available device addresses. Each entry in the data structure contains the short and extended 802.15.4 address and an availability flag.

The Neighbor Table stores a set of neighbor control blocks (NCB), one for each device. An NCB contains the address information of the device (short and extended address), its FSM state and the private cryptographic information (key reconstruction information, SS and TKC/TVs).

Figure 4.

TAKS2 data structures.

SW architecture and implementation issues

In this section, we describe two implementations of TAKS2 based on the design described in the previous section. One adopts the TKN154 MAC layer and the other is based on the Atmel proprietary stack. The main goal is to demonstrate the feasibility of using TAKS2 on top of well-known IEEE 802.15.4-compliant network stacks. In the following sections, the two implementations are discussed and the feasibility of introducing TAKS is analyzed. Then, both of them are verified and compared to highlight the advantages and disadvantages of each one, with particular attention to their performance results.

Software architecture

The software architecture adopted in both implementation is shown in Figure 5. The architecture uses the bridge design pattern in order to provide a non-intrusive, de-coupled, and flexible approach to connect the target MAC layer with the TAKS2 components. In Figure 5, the IEEE 802.15.4 MAC layer (bottom box) offers two of the available services (MCPS-Data and MLME-ASSOCIATE) to the bridge, which calls the TAKS2 key generator and the inner symmetric block cipher to provide to the upper layer the TAKS2 primitives. For sake of example, in the figure, the MAC layer shown is based on the TKN154 while the block cipher is based on the AES cipher in cipher block chaining (CBC) mode with a key length of 192 bits. The bridge layer takes care of: monitoring MAC layers requests; building proper responses; retrieving the TAKS2 key components; and combining them according the scheme to generate the shared secret, which is then used as symmetric key in the AES encryption/decryption. Such an architecture allows TAKS2 implementations to adapt and evolve, supporting new features and new symmetric ciphers without the need of a code refactoring process. Also, since the bridge layer can optionally be disabled, it offers also a compile-time on-demand security option, so that a WSN network operator can choose which node has to use TAKS2 (increasing the communication security) or to use direct MAC layer primitives (increasing the performances) seamlessly.

Figure 5.

TAKS2 implementations common architecture.

TKN154

The TKN154 is an open-source implementation of the 802.15.4 MAC layer from the Telecommunication Network Group of the Technical University of Berlin. The TKN154 is based on TinyOS 2.x operating system, it is written in the nesC language, and it is compatible with node platforms which use the CC2420 radio chip (e.g. TelosB, T-Mote, and MicaZ). The TKN154 offers four major features:

The TKN154 source code is released under an open-source license.

The code is organized to be as independent as possible from the underlying hardware platform. Hardware-dependent code is separated through interfaces from the rest of the code.

Most of the features of the 802.15.4 standard are kept in separated components, making possible to enable or disable them selectively.

The whole TKN154 architecture is organized in various abstraction levels, allowing it to be highly customizable.

One drawback of the TKN154 is the pre-requisites needed by a platform to be fully compatible with it. The most evident of these prerequisites is a proper and stable hardware timer, which should be able to output a 62.5 kHz frequency clock with a maximum error of 40 ppm.

Atmel MAC

The TKN154 project is not the only 802.15.4 MAC implementation available: Atmel provides a proprietary network stack³⁴ for its AVR platforms which complies on the 802.15.4 standard. The stack is organized into sub-layers. Among those, the platform abstraction layer (PAL), the transceiver abstraction layer (TAL), and the MAC core layer (MCL) constitute the part of the stack that can be seen as the MAC layer. The first provides hardware-dependent code needed to interface to available peripherals, the TAL takes care of frame handling, power management, CSMA handling and general state transitions while, the MCL implements the basic 802.15.4 MAC standard primitives, such as the MAC Management Service (MLME).

Random number generation

The $α$ value in the scheme has to be randomly generated to ensure it is unpredictable by attackers. This aspect is critical since a vulnerability in the random number generation can affect the security of the overall scheme. In particular, $α$ has to be generated by a PRNG which has some specific properties that make it suitable for cryptography (CSPRNG). A PRNG is defined by a deterministic algorithm which is able to generate, given an input value called seed, a pseudo-random numbers sequence. The output sequence of a PRNG, approximately, has the same statistical properties of a sequence generated by a truly random process. In the cryptography context, it is fundamental that the PRNG generates a pseudo-random numbers sequence which is unfeasible to be entirely reconstructed starting from a sub-sequence of it: an attacker could listen to the sequence, retrieve the seed and hence, learn the future pseudo-random values. In TAKS2, the $α$ value in the scheme is generated by a PRNG based on Mersenne Twister algorithm.³⁵ In order to increase randomness of the value, we have used the sensing functionality of WSN nodes (i.e. the temperature and the humidity sensors) combined with LQI and RSSI values coming from the radio transceiver. Given the unfeasibility to learn about the values of the physical phenomena in the area around the WSN nodes, we have used such values to create the seed for our implementation of the Mersenne Twister algorithm.

Verification and performance evaluation

In order to check the correctness of the implementations of the scheme and their performance, in this section, we describe the verification phase of TAKS2. A set of scenarios, each one using a different operating conditions for devices and coordinator, has been selected to test TAKS2 components. For each scenario, we have verified the correctness and the effectiveness of the TAKS2 implementations when deployed in a star topology (the verification of the basic point-to-point configuration can be found in Pomante et al.’s¹¹ study).

Basic network configuration

The basic network configuration used in the verification phase (Figure 6) consists of a star-topology WSN formed by one cluster head node (coordinator) connected to nine different cluster member nodes (device).

Figure 6.

Performance evaluation network topology.

This is a common topology that is used in data collection environments, where the cluster members are meant to retrieve data while the cluster head collects, elaborates, and transmits them.

The sensor nodes used in the experiments are the following:

For the TKN154-based implementation, we have adopted the Advanticsys CM5000³⁶ (Figure 7), a clone of the more famous TelosB³⁷ node. This node embeds an MSP430 micro-controller unit, a CC2420 radio chip (IEEE 802.15.4 compliant), a 48 kb of flash memory, and 10 kb of RAM.

For the Atmel MAC implementation, we have adopted the nodes included inside the Atmel REB212BSMA-EK kit³⁸ (Figure 8). They are based on the Atmel ATMega1281 micro-controller unit with 128 kb of flash, 8 kb of RAM memory, and the AT86RF212B (IEEE 802.15.4 compliant) radio transceiver.

Figure 7.

CM5000 WSN Node.

Figure 8.

Atmel REB212BSMA: Node.

Testbed application

During the experiments, the coordinator and the devices have been programmed with a testbed application. This testbed performs a typical monitoring application using directly the interfaces provided by the MAC layer. In this way, we can verify the correctness of TAKS2 primitives and the communication between TAKS2 and the MAC layer in a realistic environment. In such a testbed, the nodes have the following roles:

Each device periodically samples its installed sensors (i.e. temperature and humidity), builds a message with the retrieved measures and sends it to the coordinator.

The coordinator receives messages, parses their content, aggregate the measurements, and sends the result to the PC via the UART port.

This testbed is deployed in two flavors, the un-secure version (i.e. no TAKS2) and the secure version (i.e. using TAKS2). The two versions differ on the components involved in the communication: the un-secure testbed communicates using no additional layers, while the secure version uses TAKS2 via the bridge layer discussed in section “Computational and spatial complexity analysis.” The two versions of the testbed have been deployed and tested on the CM5000 WSN nodes (using the TKN154 MAC) and on the REB212BSMA kit nodes (using the Atmel 802.15.4 MAC). The discussion of the obtained results is reported in the following paragraphs.

Scenarios description

In order to verify the implementations and to evaluate performances, we have used both the un-secure and secure versions of the testbed application against five different scenarios, each one with a different set of network parameter (more information about these parameters can be found in IEEE 802.15.4-2015³²) values. The network parameters we have considered are shown in Table 4.

Table 4.

MAC parameters sets.

Scenarios	1	2	3	4	5
Beacon interval	61,440	30,720	122,880	61,440	30,720
Scan duration	61,440	30,720	122,880	61,440	30,720
Scan duration (coord.)	123,840	123,840	123,840	62,400	31,680
Scan duration short	62,400	31,680	123,840	62,400	31,680
Scan duration long	123,840	62,400	246,720	123,840	62,400

The selected length (in bits) for the elements in $GF (p)$ and the key components (LKC, TKC) has been set to 192, which it is a good compromise between memory size and security level.

Verification results

The verification of both TAKS2 implementations with the two testbed versions across the different MAC parameters sets has been successful: by analyzing the outputs of the communications between the coordinator toward the PC, it is possible to reasonably state that TAKS2 works as intended: the $SS$ reconstruction (on the receiver side) is correct, the authentication code is verified and the encrypted messages are successfully decrypted (Figure 9 shows a screen-capture of the TKN154 testbed). This result highlights the feasibility of adopting TAKS2 in real-world WSN-based monitoring applications in order to secure the communication among the sensor nodes.

Figure 9.

TAKS2: data from a sender node (left) and a receiver node (right) sent to PC via UART.

Performance evaluation

Following the initial verification, a performance evaluation has been conducted in order to analyze the overhead related to the usage of the scheme. So, in this section, we first introduce the metrics that have been defined to evaluate the performance, then we report some of the obtained results, mainly focusing on the scheme impact on performances.

Metrics

In order to evaluate the performance of TAKS2 scheme implementations and the impact on the MAC layer performance, we have defined two set of metrics. The first set is composed of metrics related to the overall MAC layer performance:

MAC layer association (MAC Assoc). This is the time needed by a device node to successfully perform the IEEE 802.15.4 association process (MLME-ASSOCIATE) with the coordinator.

Transmission time (TX time). This is the delay between the MAC data request (MCPS-DATA.request) and actual transmission of the first frame of the message.

Reception time (RX Time). This is the delay between the MAC layer data arrival (MCPS-DATA.indication) and when such data are passed to the higher layers.

Frame Error Rate. This is the number of unsuccessfully received frames by the MAC layer with respect to the total transmitted frames.

The second set of metrics has been used to evaluate the performances of TAKS primitives (e.g. encryption, decryption, key generation, etc.):

TAKS2 key computation time (TX key gen): This is the time required by TAKS2 to successfully generate a Shared Secret from the key components.

TAKS2 key retrieval time (RX key gen): This is the time required by TAKS2 to successfully recreate the proper Shared Secret from the $KRI$ and the receiver’s key components.

TAKS2 Association Delay (TAKS2 Assoc): This is the delay introduced by the TAKS2 Association, which takes place after the IEEE 802.15.4 default MAC association process (MLME-ASSOCIATE).

Results

In order to correctly evaluate the MAC layer and TAKS2 performance, we have conducted tests considering all the parameters set reported in Table 4. The tests have been replicated for the un-secure and TAKS2-enabled versions of the testbed for both the MAC layer implementations. The results reported in this section are the average values of the metrics described in section “Verification and performance evaluation” performed across the different parameter sets and each device node. The results for the TKN154-based implementation are shown in Table 5 for un-secure testbed application and in Table 6 for the secure version, while, in Tables 7 and 8, we show the results related to the Atmel Stack. The total memory overhead of the secure version for storing the LCD in our test scenario (Figure 6) has been ∼400 bytes for the cluster-head node and ∼200 bytes for the other nodes. The size of additional code required to implement the $TAK (\cdot)$ function has been ∼400 bytes for the TKN154 testbed and ∼300 bytes for the Atmel testbed. Additional memory is required by the adopted symmetric cipher (i.e. AES) implementation. In our case, for the TKN154 testbed application, the memory required by the AES implementation (as a TinyOS component) has been ∼1300 bytes, while, for the Atmel-based testbed, the memory required has been ∼800 bytes.

Table 5.

Un-secure stack (TKN154).

	Min (ms)	Max (ms)	Avg
Tx time	9.86	51.55	11.44
Rx time	6.34	6.75	6.34
MAC Assoc	16.59	48.35	23.89
Frame error rate (± 0.05%)	1%
Tx key gen	−	−	−
Rx key gen	−	−	−
TAKS2 Association	−	−	−

MAC: message authentication code; TAKS: topology-authenticated key scheme.

Table 6.

Secure stack (TKN154).

	Min (ms)	Max (ms)	Avg
Tx time	35.84	85.41	39.34
Rx time	26.50	29.12	27.34
MAC Assoc	16.62	48.40	23.92
Frame error rate (± 0.05%)	1.8%
Tx key gen	13.31	13.70	13.44
Rx key gen	5.12	5.31	5.18
TAKS2 Association	11.26	32.42	13.26

MAC: message authentication code; TAKS: topology-authenticated key scheme.

Table 7.

Un-secure stack (Atmel).

	Min (ms)	Max (ms)	Avg
Tx time	21.48	187.01	28.49
Rx time	0.62	0.67	0.63
MAC Assoc	16.69	48.68	27.34
Frame error rate (± 0.05%)	0%
Tx key gen	−	−	−
Rx key gen	−	−	−
TAKS2 Association	−	−	−

MAC: message authentication code; TAKS: topology-authenticated key scheme.

Table 8.

Secure stack (Atmel).

	Min (ms)	Max (ms)	Avg
Tx time	61.62	203.82	71.67
Rx time	2.65	2.84	2.73
MAC Assoc	17.35	49.90	28.79
Frame error rate (± 0.05%)	0.15%
Tx key gen	35.23	177.21	42.31
Rx key gen	6.82	6.88	6.84
TAKS2 Association	17.35	49.9	28.79

MAC: message authentication code; TAKS: topology-authenticated key scheme.

Result analysis

The results show that in the TKN154 secure version of the testbed, the performance loss introduced in Tx/Rx operations is around $20 ms$ (from $+ 150 %$ to $+ 330 %$ ). In the same tables, it is possible to observe that TAKS2 does not interfere with the standard 802.15.4 MAC association. The frame error rate is almost the same for the un-secure and secure version of the testbed, although the longer transmission times reported in the secure version slightly affected the rate $(+ 0.8 %)$ . From the values, it is noticeable that the transmission time (TX time) in both the secure and un-secure results shows a higher deviation. This is due to different factors, although the higher contribution is related to the channel access protocol (CSMA). Finally, in the secure version, the Tx key gen and the Rx key gen show an average $8 ms$ difference. This difference is expected, since the key computation step during transmission is different and requires more operations (e.g. the random number computation, the $SS$ retrieval, etc.). The Atmel MAC results show a relevant performance loss $(+ 100 %)$ in transmission time with respect to the TKN154 MAC in both secure and un-secure versions of the testbed. However, the reception time and the frame error rate are considerably better in the Atmel MAC. This shows that, probably, the Atmel MAC implementation trades longer transmission times for a better success rate. Moreover, as in the TKN154 version, the Atmel MAC secure version of the testbed shows a relevant difference between the Tx key gen and the Rx key gen. Finally, Atmel Tx key gen computation time is more than three times the TKN154 one. The reason of this difference is partly due to the different computations required during transmission and also due to the different code style of the key generation primitives (i.e. the TKN154 uses TinyOS 2.x as lower-level code, while the Atmel MAC uses its own low-level code substrate).

Considering a typical monitoring application deployed on a WSN, for example, a star-topology with the local PAN coordinator acting also as sink-node a the center, the performance overhead could be neglected if the transmission frequency is less than the maximum time required to sample, encrypt, associate, and transmit the measurements. As the results show, baseline TAKS2 implementation on common WSN nodes is effective in the case of slow-monitoring application. In order to make TAKS2 effective also for higher transmission frequency, the following solutions could be adopted while preserving the security level:

Encrypting and sending multiple samples per transmission.

Providing a platform-specific implementation of TAKS2 to gain advantages from the platform-specific features (e.g. hardware multiplicators).

On the memory impact, both implementations use less than 2 kb of additional memory to store data and code required by the scheme. Considering state-of-the-art cryptographic schemes and their implementation on WSN platforms (e.g. AES, RSA, ECC-ECIES), we can state that, generally, TAKS requires more memory than pure symmetric schemes (since TAKS itself requires a symmetric encryption scheme), but less than any public-key schemes. In fact, considering public-key schemes such as the ECC-based encryption scheme ECIES³⁹ and using the least possible memory, each node is still required to store, in addition to its private and public keys, at minimum, the curve domain parameters for each supported curve and the code required to implements elliptic curve basic point operations (in the order of tens of kilobytes).

Conclusions and future works

This article has presented the evolution of a hybrid cryptography scheme, based on the generation of topology-authenticated keys, specifically designed for WSN platforms. The scheme has been demonstrated formally by proving that the scheme is N-secure, which guarantees that attackers should retrieve N node keys before being able to compromise the security of the WSN. In order to validate the scheme, we have developed two implementation of TAKS2, based on two state-of-art IEEE 802.15.4 MAC layers. A testbed application has been developed to evaluate their performances. The validation and performance evaluation results have shown that the scheme provides security with a performance loss which is negligible in common environmental monitoring applications, that is, when slow-changing physical phenomena is monitored (e.g. temperature, light intensity, humidity, etc.). While TAKS2 is, by design, a lightweight scheme, yet the performance overhead introduced on the WSN nodes (which are resource-constrained by themselves) make TAKS2 less effective in those situations when an high-frame throughput (along security) is required (e.g. audio/video streaming, high data-rate data exchanges etc.).

The work described in this article is part of a wider research project that aims to create a secure framework for WSN to provide a encryption/decryption scheme associated with an Intrusion Detection System (IDS).⁴⁰ In the future, we plan to implement the schema also for cluster-tree WSNs and to adapt it to be compliant to the key management protocol (KMP) as defined in the recent IEEE 802.15.9-2016⁴¹ standard. The final goal is to integrate all such features in a MW for WSN (e.g. Agilla2)⁴² able to provide efficient and effective security services.

Footnotes

Handling Editor: Amiya Nayak

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work has been partially supported by the ECSEL RIA 2015 SAFECOP project.

ORCID iD

Luigi Pomante

References

TinyOS. Home page, http://www.tinyos.net

ContikiOS. Home page, http://www.contiki-os.org/

RIOT-OS. Home page, https://www.riot-os.org/

Lara-Nino

Diaz-Perez

Morales-Sandoval

. Elliptic curve lightweight cryptography: a survey. IEEE Access 2018; 6: 72514−72550.

Rivest

Shamir

Adleman

. A method for obtaining digital signatures and public-key cryptosystems. Commun ACM 1978; 21(2): 120–126.

Elgamal

. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE T Inform Theory 1985; 31(4): 469–472.

Shim

K-A

. A survey of public-key cryptographic primitives in wireless sensor networks. IEEE Commun Surv Tut 2016; 18(1): 577–601.

Kodali

. Implementation of ECC with hidden generator point in wireless sensor networks. In: 2014 sixth international conference on communication systems and networks (COMSNETS), Bangalore, India, 6–10 January 2014, pp.1–4. New York: IEEE.

Camtepe

Yener

. Key distribution mechanisms for wireless sensor networks: a survey. Technical Report TR-05-07. Troy, NY: Rensselaer Polytechnic Institute, March 2005.

10.

Pugliese

Santucci

. Pair-wise network topology authenticated hybrid cryptographic keys for Wireless Sensor Networks using vector algebra. In: 5th IEEE international workshop on wireless sensor networks security (WSNS2008), Atlanta, GA, 29 September–2 October 2008. New York: IEEE.

11.

Pomante

Pugliese

Marchesani

, et al. Definition and development of a Topology-based cryptographic scheme for Wireless Sensor Networks. In: Zuniga

Dini

(eds) Sensor systems and software—lecture notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering. New York: Springer, 2013, pp.47–64.

12.

Atmel IEEE 802.15.4 libraries, https://www.microchip.com/design-centers/wireless-connectivity/embedded-wireless/802-15-4/software/ieee-802-15-4-mac

13.

Rijndael proposal (AES), https://csrc.nist.gov/csrc/media/projects/cryptographic-standards-and-guidelines/documents/aes-development/rijndael-ammended.pdf

14.

Arjmandi

Lahouti

. A key pre-distribution scheme based on multiple block codes for wireless sensor networks. In: 7th international symposium on telecommunications (IST’2014), Tehran, 9–11 September 2014, pp.857–860. New York: IEEE.

15.

Ahlawat

Dave

. A resilient and seamless rekeying scheme based on random key distribution for WSN. In: 2017 international conference on computer, communications and electronics (COMPTELIX2017), Jaipur, India, 1–2 July 2017, article no. 8003987, pp.321–327. New York: IEEE.

16.

Liao

Wang

, et al. A method of pair-wise key distribution and management in distributed wireless sensor networks. In: Zhang

Olariu

Cao

, et al. (eds) Lecture notes in computer science (including subseries lecture notes in artificial intelligence and lecture notes in bioinformatics, LNCS 4864). Berlin, Heidelberg: Springer, 2007, pp.834–844.

17.

Mukherjee

Neogy

Roy

. Building wireless sensor networks: theoretical and practical perspectives. Boca Raton, FL: CRC Press, 2017.

18.

Kuchipudi

Qyser

AAM

Balaram

VVSSS

. A dynamic key distribution in wireless sensor networks with reduced communication overhead. In: 2016 international conference on electrical, electronics, and optimization techniques (ICEEOT), Chennai, India, 3–5 March 2016, pp.3651–3654. New York: IEEE.

19.

Dinker

Sharma

. Polynomial and matrix based key management security scheme in wireless sensor networks. J Discre Math Sci Cryptograph 2019; 22(8): 1563–1575.

20.

Liu

Chen

. A scheme for key distribution in wireless sensor network based on Hierarchical Identity-Based Encryption. In: 2015 IEEE 12th international conference on networking, sensing and control, Taipei, 9–11 April 2015, pp.539–543. New York: IEEE.

21.

Hamsha

Nagaraja

. Analysis of security mechanism using threshold cryptography for hierarchical wireless sensor networks. In: 2017 international conference on communication and signal processing (ICCSP), Chennai, India, 6–8 April 2017, pp.1938–1941. New York: IEEE.

22.

Yue

Wang

Zhu

. Hybrid encryption algorithm based on wireless sensor networks. In: 2019 IEEE international conference on mechatronics and automation, Tianjin, China, 4–7 August 2019. New York: IEEE.

23.

Zhang

Pengfei

. An efficient and hybrid key management for heterogeneous wireless sensor networks. In: The 26th Chinese control and decision conference (2014 CCDC), Changsha, China, 31 May–2 June 2014. New York: IEEE.

24.

Akram

Naureen

Riaz

, et al. Evaluation of hybrid security system with cluster based key management for wireless sensor networks. In: 2007 international conference on intelligent and advanced systems, Kuala Lumpur, Malaysia, 25–28 November 2007. New York: IEEE.

25.

Manjunath

Anand

Nagaraja

. An hybrid secure scheme for secure transmission in grid based Wireless Sensor Network. In: 2015 IEEE international advance computing conference (IACC), Bangalore, India, 12–13 June 2015, pp.472–475. New York: IEEE.

26.

Tahir

Javed

Ahmad

, et al. SCUR: secure communications in wireless sensor networks using rabbit. In: Lecture notes in engineering and computer science, 2017.

27.

Corke

Shih

W-C

, et al. secFleck: A public key technology platform for wireless sensor networks. In: Roedig

Sreenan

(eds) European conference on wireless sensor networks (Lecture Notes in Computer Science). Berlin, Heidelberg: Springer, 2009, pp.296–311.

28.

Kavitha

Caroline

. Hybrid cryptographic technique for heterogeneous wireless sensor networks. In: 2015 international conference on communications and signal processing (ICCSP), Melmaruvathur, India, 2−4 April 2015, pp.1016−1020. New York: IEEE.

29.

Kim

Yun

Kim

. Hybrid public key authentication for wireless sensor networks. In: 2017 12th international conference for internet technology and secured transactions (ICITST), Cambridge, 11−14 December 2017, pp.142−143. New York: IEEE.

30.

Pugliese

Pomante

Santucci

. Secure platform over wireless sensor networks. Vienna: InTech, 2012.

31.

Rogaway

Shrimpton

. Cryptographic hash-function basics: definitions, implications, and separations for preimage resistance, second-preimage resistance, and collision-resistance. In: Roy

Meier

(eds) FSE2004 (LNCS 3017). Berlin, Heidelberg: Springer, pp.371−388.

32.

IEEE 802.15.4-2015 − IEEE standard for low-rate wireless networks (Revision of IEEE Std 802.15.4-2011), 22 April 2016, pp.1−709, https://ieeexplore.ieee.org/document/7460875

33.

Hauer

. TKN15.4: an IEEE 802.15.4 MAC implementation for TinyOS 2. TKN Technical Report TKN-08-003, Berlin, March 2009, http://www.tkn.tu-berlin.de/fileadmin/fg112/Papers/TKN154.pdf

34.

Atmel (now Microchip) 802154. MAC website, http://www.microchip.com/design-centers/wireless-connectivity/embedded-wireless/802-15-4/software/ieee-802-15-4-mac

35.

Saito

Matsumoto

. SIMD-oriented fast Mersenne Twister: a 128-bit pseudorandom number generator. In: Saito

Matsumoto

(eds) Monte Carlo and Quasi-Monte Carlo methods 2006. Berlin, Heidelberg: Springer, 2008, pp.607−622.

36.

MTM-CM5000-MSP product website, https://www.advanticsys.com/shop/mtmcm5000msp-p-14.html

37.

TelosB product datasheet, http://www.memsic.com/userfiles/files/Datasheets/WSN/telosb_datasheet.pdf

38.

Atmel REB212BSMA hardware user manual, https://www.mouser.com/datasheet/2/268/Atmel-42097-WIRELESS-AT02876-REB212BSMA-Hardware-U-1368556.pdf

39.

Agrawal

Tiwari

. A review on IoT security architecture: attacks, protocols, trust management issues, and elliptic curve cryptography. In: Shukla

Agrawal

Sharma

, et al. (eds) Social networking and computational intelligence. Singapore: Springer, 2020, pp.457−465.

40.

Pomante

Tiberti

Pugliese

, et al. TinyWIDS: a WPM-based intrusion detection system for TinyOS2.x/802.15.4 Wireless Sensor Networks. In: Fifth workshop on cryptography and security in computing systems (CS2), Manchester, 24 January 2018. New York: ACM.

41.

IEEE 802.15.9-2016 − IEEE recommended practice for transport of key management protocol (KMP) datagrams, 17 August 2016, pp.1−74, https://ieeexplore.ieee.org/document/7544442

42.

Agilla2 Github project page, https://github.com/luigi-pomante/Agilla2