# lwAKE: A Lightweight Authenticated Key Exchange for Class 0 Devices

Authors: Juan Jose Echevarria; Jon Legarda; Janire Larrañaga; Jonathan Ruiz-de-Garibay
Journal: International Journal of Distributed Sensor Networks
 (2016)

---

## Abstract

Device-to-Device (D2D) communication enables devices in proximity to establish a wireless direct link. However, these devices may be severely constrained in terms of memory, CPU, and processing resources. Hence, a D2D communication with a constrained device implies new challenges as it does not have the resources required to be secured with standard cryptography. We propose lwAKE for class 0 devices (RFC 7228), which uses one-way cryptographic functions and zero-knowledge proofs to provide mutual authentication and a secure key establishment. We specify the protocol using the High Level Protocol Specification Language and then verify the security properties using the model checkers OFMC and CL-AtSe. The significance of the protocol stands in a key reuse for any successive authentication. Experimental results show that this shortened authentication mode reduces the computational load greatly.


---

## Body

## 1. Introduction and Related Work

In a Device-to-Device (D2D) communication, authentication plays a very important role. However, devices featuring severe constraints on power, memory, and processing resources imply new challenges for the design of security protocols. RFC 7228 introduces a classification and a terminology for constrained devices which concern data and code size limitations. This classification consists of three classes of constrained devices. We will focus on class 0 devices, which are very constrained sensor-like devices with data/code sizes below 10/100 kB. Thus, authentication in this D2D scenario relies on two parties: the class 0 constrained device (C0) and the device that wants to authenticate and communicate with C0. This device (D0) may be constrained or not.Most efforts in the design of authentication protocols for C0 devices are primarily focused on RFID tags. Peris-Lopez et al. [1] introduced an ultralightweight RFID authentication protocol that uses index-pseudonyms and a limited collection of binary and rotation operations. However, secrets are updated after a successful protocol round; thus, Yousuf and Potdar [2] blocked the last message to desynchronize the protocol.Tian et al. [3] introduced another ultralightweight RFID authentication protocol based on novel rotation and permutation operations. The protocol claims that it avoids desynchronization attacks because the reader sends the last message. Ahmadian et al. [4] proved that blocking that last message also breaks the protocol.Liu and Bailey [5] used random numbers and one-way cryptographic functions. On request, the tag always responds with its constant identifier, which makes the tag traceable. Besides, Naser et al. [6] used that unique identifier to impersonate the tag using the responses of legitimate readers.Cho et al. [7] proposed a protocol that claims to fulfil the authentication without disclosure of the shared secrets. Safkhani et al. [8] prove the protocol to be prone to desynchronization with a success probability of 1 in only one protocol run. Impersonation attacks are also exposed with a success rate of 1/4 in two runs.In order to avoid impersonation attacks, Li and Teraoka [9] proposed the use of renewable identifiers. Nevertheless, the fact of using renewable identifiers introduces two issues: increased memory usage and desynchronization attacks against the next valid identifier.Juels and Weis [10] proposed HB+, which provides a symmetric authentication scheme suited to constrained devices. However, it only provides provable security against passive adversaries. In order to make HB+ resilient against active adversaries, Hammouri and Sunar [11] merged physically unclonable functions (PUF) with the HB+ authentication scheme. A PUF is a physical entity that is embedded in the device, which means this protocol cannot be used in devices that do not have that physical entity built-in.There are also works that try to fit the public-key cryptography (PKI) as used in most Internet security standards in C0 devices, as in Sample et al. [12]. However, PKI was not designed with energy nor computation constraints in mind. It requires high memory and expensive computations, and C0 devices do not have those resources; for example, Pendl et al. [13] executed a scalar multiplication using the Montgomery powering ladder in 1.6 seconds at a frequency of 6.7 MHz. This execution time is not practical for a C0 device.Finally, presented works only focus on the authentication. In a D2D communication, we also need to encrypt all messages of the communication session. In this paper, we propose a lightweight authenticated key exchange for C0 devices which establishes the session key and authenticates the devices involved in the key exchange. Furthermore, the protocol conveys a zero-knowledge proof and reduces the number of computations in successive sessions.The remainder of the paper is structured as follows. We first introduce the proposed authentication protocol for C0 devices. Afterwards, we present the automated analysis of the protocol using two model checkers. Then, we show some energy measurements in our C0 testbed. Finally, the paper ends with a conclusion.


## 2. Lightweight Authenticated Key Exchange

The proposed protocol provides mutual authentication and key exchange using a limited collection of cryptographic functions and bitwise operations. Furthermore, it presents a second mode that reuses the former session key for any successive authentication. The notation of the protocol is shown in Notation of the Protocol section.


### 2.1. Initial Authentication

Our protocol keeps two secrets,K
1 and K
2, that are preconfigured in C0 and D0. To produce the session key and the cookies we use a keyed hash function optimized for speed on short messages (SIPHASH), developed by Aumasson and Bernstein [14].Next we show the steps of this authentication mode:(1)
D0 generates a nonce (n
o
n
c
e
1) and sends a request message with it.
(2)
C0 generates a nonce (n
o
n
c
e
2) and computes the session key (K) and its evidence (p
r
o
o
f
c). Finally, this information is masked in a one-time cookie. The next set of equations show the key and cookie generation algorithms:(1)
K
=
H
K
1
,
K
2
,
n
o
n
c
e
1
,
n
o
n
c
e
2
p
r
o
o
f
c
=
n
o
n
c
e
1
⊕
K
32
–
63
+
n
o
n
c
e
2
c
o
o
k
i
e
c
=
H
K
1
,
n
o
n
c
e
1
⊕
p
r
o
o
f
c
≪
32
n
o
n
c
e
2
.
(3)
D0 receives the cookie and validates it. The next set of equations show the cookie extraction:(2)
n
o
n
c
e
2
=
c
o
o
k
i
e
c
⊕
H
K
1
,
n
o
n
c
e
1
&
0
x
F
F
F
F
F
F
F
F
p
r
o
o
f
c
=
c
o
o
k
i
e
c
⊕
H
K
1
,
n
o
n
c
e
1
≫
32
.
(4)
D0 recoversn
o
n
c
e
2, computes the session key, and verifies p
r
o
o
f
c. If valid, C0 is authenticated and D0 generates a pseudonym identifier for C0 (C
I
D) to be used on successive authentications. Additionally, it computes its evidence (p
r
o
o
f
d) with another part of the key:(3)
p
r
o
o
f
d
=
n
o
n
c
e
2
⊕
K
0
–
31
+
n
o
n
c
e
1
⊕
C
I
D
.
(5)
Finally, D0 computes the cookie and forwards it to C0:(4)
c
o
o
k
i
e
d
=
H
K
2
,
n
o
n
c
e
2
⊕
p
r
o
o
f
d
≪
32
∣
C
I
D
.
(6)
C0 now checks the legitimacy of D0. The next set of equations show the cookie validation algorithm:(5)
C
I
D
=
c
o
o
k
i
e
d
⊕
H
K
2
,
n
o
n
c
e
2
&
0
x
F
F
F
F
F
F
F
F
p
r
o
o
f
d
=
c
o
o
k
i
e
d
⊕
H
K
2
,
n
o
n
c
e
2
≫
32
.
(7)
If the evidence is valid, C0 stores its pseudonym and the session key(
K
). The session key could now be used as the cryptographic key to encrypt the data.The success of the authentication phase depends on the verification of the session key between C0 and D0. Each one has to check that the other end has come to the same session key. Nevertheless, the session key is never completely sent. In other words, the protocol conveys a zero-knowledge proof and requires knowing more than the session key to break it.


### 2.2. Successive Authentication

The aim of this mode is to reduce the computing costs in successive connections. Next we show the steps of this authentication mode:(1)
D0 generates a nonce (n
o
n
c
e
a) and calculates two messages (A
,
B). Then, it sends the messages with its identifier (D
I
D). The initial z equals 0:(6)
A
=
n
o
n
c
e
a
⊕
K
z
-
z
+
31
x
=
n
o
n
c
e
a
&
0
x
3
F
B
=
C
I
D
⊕
K
x
-
x
+
31
+
n
o
n
c
e
a
.
(2)
After receiving the messages, C0 gets D0’s shared secrets.
(3)
Next, C0 infers the value of the nonce (n
o
n
c
e
a) from A and checks the legitimacy of D0 calculating a local version of B. If valid, D0 is authenticated.
(4)
Then, C0 generates another nonce (n
o
n
c
e
b), calculates the messages E and F, and sends a response:(7)
E
=
C
I
D
⊕
n
o
n
c
e
b
+
K
z
+
x
-
z
+
x
+
31
y
=
n
o
n
c
e
b
&
0
x
3
F
F
=
n
o
n
c
e
a
⊕
K
y
-
y
+
31
+
n
o
n
c
e
b
⊕
K
x
-
x
+
31
.
(5)
D0 first infers the nonce (n
o
n
c
e
b) from E and then authenticates C0 calculating a local version of F. If valid, mutual authentication is proved.
(6)
Finally, newz is computed only if the connection termination runs properly, which avoids desynchronization: (8)
z
=
n
o
n
c
e
a
⊕
n
o
n
c
e
b
&
0
x
3
F
.Note that the session key (K) is 64 bits long, and thus the bits selected by x, y, and z will roll over on overflow; for example, if z is 63, the partial session key in message A will be K
63
-
30. Moreover, the fact that message A changes with each iteration, because of z, prevents replay attacks. Successive authentications will keep using this mode unless C0 and D0 distrust each other.


## 2.1. Initial Authentication

Our protocol keeps two secrets,K
1 and K
2, that are preconfigured in C0 and D0. To produce the session key and the cookies we use a keyed hash function optimized for speed on short messages (SIPHASH), developed by Aumasson and Bernstein [14].Next we show the steps of this authentication mode:(1)
D0 generates a nonce (n
o
n
c
e
1) and sends a request message with it.
(2)
C0 generates a nonce (n
o
n
c
e
2) and computes the session key (K) and its evidence (p
r
o
o
f
c). Finally, this information is masked in a one-time cookie. The next set of equations show the key and cookie generation algorithms:(1)
K
=
H
K
1
,
K
2
,
n
o
n
c
e
1
,
n
o
n
c
e
2
p
r
o
o
f
c
=
n
o
n
c
e
1
⊕
K
32
–
63
+
n
o
n
c
e
2
c
o
o
k
i
e
c
=
H
K
1
,
n
o
n
c
e
1
⊕
p
r
o
o
f
c
≪
32
n
o
n
c
e
2
.
(3)
D0 receives the cookie and validates it. The next set of equations show the cookie extraction:(2)
n
o
n
c
e
2
=
c
o
o
k
i
e
c
⊕
H
K
1
,
n
o
n
c
e
1
&
0
x
F
F
F
F
F
F
F
F
p
r
o
o
f
c
=
c
o
o
k
i
e
c
⊕
H
K
1
,
n
o
n
c
e
1
≫
32
.
(4)
D0 recoversn
o
n
c
e
2, computes the session key, and verifies p
r
o
o
f
c. If valid, C0 is authenticated and D0 generates a pseudonym identifier for C0 (C
I
D) to be used on successive authentications. Additionally, it computes its evidence (p
r
o
o
f
d) with another part of the key:(3)
p
r
o
o
f
d
=
n
o
n
c
e
2
⊕
K
0
–
31
+
n
o
n
c
e
1
⊕
C
I
D
.
(5)
Finally, D0 computes the cookie and forwards it to C0:(4)
c
o
o
k
i
e
d
=
H
K
2
,
n
o
n
c
e
2
⊕
p
r
o
o
f
d
≪
32
∣
C
I
D
.
(6)
C0 now checks the legitimacy of D0. The next set of equations show the cookie validation algorithm:(5)
C
I
D
=
c
o
o
k
i
e
d
⊕
H
K
2
,
n
o
n
c
e
2
&
0
x
F
F
F
F
F
F
F
F
p
r
o
o
f
d
=
c
o
o
k
i
e
d
⊕
H
K
2
,
n
o
n
c
e
2
≫
32
.
(7)
If the evidence is valid, C0 stores its pseudonym and the session key(
K
). The session key could now be used as the cryptographic key to encrypt the data.The success of the authentication phase depends on the verification of the session key between C0 and D0. Each one has to check that the other end has come to the same session key. Nevertheless, the session key is never completely sent. In other words, the protocol conveys a zero-knowledge proof and requires knowing more than the session key to break it.


## 2.2. Successive Authentication

The aim of this mode is to reduce the computing costs in successive connections. Next we show the steps of this authentication mode:(1)
D0 generates a nonce (n
o
n
c
e
a) and calculates two messages (A
,
B). Then, it sends the messages with its identifier (D
I
D). The initial z equals 0:(6)
A
=
n
o
n
c
e
a
⊕
K
z
-
z
+
31
x
=
n
o
n
c
e
a
&
0
x
3
F
B
=
C
I
D
⊕
K
x
-
x
+
31
+
n
o
n
c
e
a
.
(2)
After receiving the messages, C0 gets D0’s shared secrets.
(3)
Next, C0 infers the value of the nonce (n
o
n
c
e
a) from A and checks the legitimacy of D0 calculating a local version of B. If valid, D0 is authenticated.
(4)
Then, C0 generates another nonce (n
o
n
c
e
b), calculates the messages E and F, and sends a response:(7)
E
=
C
I
D
⊕
n
o
n
c
e
b
+
K
z
+
x
-
z
+
x
+
31
y
=
n
o
n
c
e
b
&
0
x
3
F
F
=
n
o
n
c
e
a
⊕
K
y
-
y
+
31
+
n
o
n
c
e
b
⊕
K
x
-
x
+
31
.
(5)
D0 first infers the nonce (n
o
n
c
e
b) from E and then authenticates C0 calculating a local version of F. If valid, mutual authentication is proved.
(6)
Finally, newz is computed only if the connection termination runs properly, which avoids desynchronization: (8)
z
=
n
o
n
c
e
a
⊕
n
o
n
c
e
b
&
0
x
3
F
.Note that the session key (K) is 64 bits long, and thus the bits selected by x, y, and z will roll over on overflow; for example, if z is 63, the partial session key in message A will be K
63
-
30. Moreover, the fact that message A changes with each iteration, because of z, prevents replay attacks. Successive authentications will keep using this mode unless C0 and D0 distrust each other.


## 3. Security Validation

Many security protocols do not succeed in their stated goals due to the absence of formal automated analysis. Manually computed validations, even the formal ones, share the limitation of the human processing.We use AVISPA, a suite of back-end model checkers commonly used for automated validation and verification of cryptographic protocols developed by Armando et al. [15].From its four back-end model checkers, we use OFMC and CL-AtSe because they support Exclusive-OR properties. CL-AtSe applies constraints on the active intruder knowledge by running the protocol in all possible ways by using redundancy elimination techniques [16]. OFMC uses symbolic techniques and optimizations to perform a bounded analysis for modelling an active intruder in a demand-driven way [17].The protocol and the assumptions are specified in the High Level Protocol Specification Language (HLPSL). HLPSL is a specification language developed by von Oheimb [18] that uses formal semantics based on Lamport’s temporal logic of actions for modelling security-sensitive protocols.However, HLPSL does not support the arithmetic operators lwAKE uses. Hence, to validate our protocol, we model approximations that consider the security properties that are most important for those operators. We make the modelling assumption that the agents should simply compute a function of the target parameter, the one computed with the unsupported operator, on the basis that an intruder cannot compute the parameter without knowing the secret used in the function. We want to highlight that these are not simplifications, just approximations that consider the security properties of an addition and still render valid the security analysis. Arithmetic addition is basically a bitwise XOR with an AND and a left shift.We model the message exchange using two agents: C0 and D0. To emulate the actions of an arbitrary adversary, the model uses the Dolev-Yao intruder [19]. In addition to the knowledge of the protocol, it can eavesdrop and generate and intercept messages and use them as an input for its knowledge base and deduction process.Next, we verify two properties referred to as security properties in IETF documents. First, we evaluatemessage authentication. This security property checks if the received message has been created by a certain device. The aim of this simulation is to validate the mutual authentication of the protocol. This means that C0 and D0 must authenticate each other for the two authentication modes. OFMC and CL-AtSe return a SAFE status with 3 sessions, which means the protocol complies with mutual authentication.Finally, we evaluateconfidentiality. This security property states that the protocol parameters are not made available or disclosed to unauthorized devices. In such attack, the adversary tries to impersonate or deceive a legitimate device through the reuse of the information obtained in previous authentications.As the model only supports single traces, we run several simulation rounds using the previous messages in the attacker’s knowledge set to check whether it is possible to reveal a previous session or not.OFMC results in a SAFE status with 6 bounded sessions and 640 visited nodes with a depth of 8 plies for the initial authentication mode. In the successive authentication mode, the SAFE status is achieved with 6 sessions, 328 visited nodes, and 6 plies. CL-AtSe results in a SAFE status with 6 sessions and 324 analysed states for the initial authentication mode, while the successive mode results in 194 analysed states. This means that the protocol meets the confidentiality property.To summarize, during the initial authentication, C0 and D0 compute the session key and exchange a zero-knowledge proof of it. If the random number generator is properly designed, an attacker cannot predict it. Conversely, a successive authentication relies on the rotation of the session key and random numbers to protect the confidentiality. Furthermore, the first message of this authentication mode changes on every authentication round, which prevents the reuse of that message.


## 4. Energy Measurements

This section describes a small energy benchmark of the proposed protocol in our C0 testbed [20]. The testbed uses an 8-bit ATmega640 microcontroller with 64 kB of ROM and 8 kB of RAM. Besides, the current in its active mode is 20 mA (5 V @ 16 MHz).Table1 shows some energy measurements for the different modes of the protocol.Table 1
Measurements.
Mean execution time
Energy
mAh
Initial auth. (1st round)
6300μs
0.63 mJ
3.5
e
-
5
Initial auth. (2nd round)
4400μs
0.44 mJ
2.4
e
-
5
Initial auth. (1st + 2nd)
10700μs
1.07 mJ
5.9
e
-
5
Successive auth.
170μs
0.017 mJ
9.4
e
-
7We can see that the cryptographic function takes the most part of the execution time, especially appreciable in the first round of the initial authentication as we compute two cryptographic functions. These results prove that our protocol can greatly reduce the battery drain from reusing the session key in a successive authentication (193.72% difference).


## 5. Conclusion

This work is a step forward to the design of energy-efficient authentication protocols for C0 devices that need to communicate securely on a relatively frequent basis. Experimental results prove that running the authentication with the key reuse makes our solution more lightweight.However, we were unable to simulate some skilful attacks with the automated validation tool. Despite being harder to execute, we address the notion that the successive authentication mode is more prone to attacks because of the limited collection of bitwise operations. Future work will focus on a thorough evaluation of the diffusion properties of this mode.



---

*Source: 6236494-2016-05-30.xml*