Scalable Attestation Resilient to Physical Attacks for Embedded Devices in Mesh Networks
Florian Kohnhäuser Niklas Büscher Sebastian Gabmeyer Stefan Katzenbeisser



acmcopyright































































2


Scalable Attestation Resilient to Physical Attacks
for Embedded Devices in Mesh Networks
    

Florian Kohnhäuser

       Technische Unversitat Darmstadt, Germany

       kohnhaeuser@seceng.informatik.tu-darmstadt.de

Niklas Büscher

       Technische Unversitat Darmstadt, Germany

       buescher@seceng.informatik.tu-darmstadt.de

Sebastian Gabmeyer

       Technische Unversitat Darmstadt, Germany

       gabmeyer@seceng.informatik.tu-darmstadt.de

Stefan Katzenbeisser

       Technische Unversitat Darmstadt, Germany

       katzenbeisser@seceng.informatik.tu-darmstadt.de

    January 27, 2017
===========================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================





Interconnected embedded devices are increasingly used in various scenarios, including industrial control, building automation, or emergency communication. As these systems commonly process sensitive information or perform safety critical tasks, they become appealing targets for cyber attacks. A promising technique to remotely verify the safe and secure operation of networked embedded devices is remote attestation. However, existing attestation protocols only protect against software attacks or show very limited scalability. In this paper, we present the first scalable attestation protocol for interconnected embedded devices that is resilient to physical attacks. Based on the assumption that physical attacks require an adversary to capture and disable devices for some time, our protocol identifies devices with compromised hardware and software. Compared to existing solutions, our protocol reduces communication complexity and runtimes by orders of magnitude, precisely identifies compromised devices, supports highly dynamic and partitioned network topologies, and is robust against failures. We show the security of our protocol and evaluate it in static as well as dynamic network topologies. Our results demonstrate that our protocol is highly efficient in well-connected networks and robust to network disruptions.









<ccs2012>
<concept>
<concept_id>10002978.10002991.10002993</concept_id>
<concept_desc>Security and privacy Access control</concept_desc>
<concept_significance>500</concept_significance>
</concept>
<concept>
<concept_id>10002978.10003014.10003017</concept_id>
<concept_desc>Security and privacy Mobile and wireless security</concept_desc>
<concept_significance>500</concept_significance>
</concept>
<concept>
<concept_id>10003033.10003034</concept_id>
<concept_desc>Networks Network architectures</concept_desc>
<concept_significance>500</concept_significance>
</concept>
</ccs2012>


[500]Security and privacy Access control
[500]Security and privacy Mobile and wireless security
[500]Networks Network architectures



definitionDefinition
theoremTheorem
































 
 























TEETrusted Execution Environment
ROMRead-Only Memory
MPUMemory Protection Unit
DoSDenial of Service







 
 

 






§ INTRODUCTION



Nowadays, networked embedded devices are increasingly present in every aspect of our lives. This paradigm, often referred to as the Internet of Things (IoT), is expected to constantly evolve in scale and complexity, reaching 20.8 billion devices by 2020 <cit.>. Technologies like Bluetooth Smart, IEEE 802.15.4, Wi-Fi Direct, ZigBee, or Z-Wave enable embedded devices to form large wireless mobile ad hoc networks (MANETs). In MANETs, all devices cooperate in the distribution of data in the network, thus establishing a decentralized and self-organized network topology. Interconnected embedded devices are frequently used in industrial control, building automation, military communication, or sensor networks. As such systems often process privacy-sensitive information or perform safety-critical tasks, their malfunction or misuse can cause serious damage. Unfortunately, software for embedded systems is typically written in unsafe programming languages and often reluctantly maintained. Additionally, even though an adversary requires significant resources to physically tamper with a device <cit.>, (secure) hardware on embedded systems is usually not hardened against physical tampering; thus, interconnected embedded devices are appealing targets for cyber attacks <cit.>.



To detect and mitigate such attacks, it is important to monitor the correct operation of embedded devices and detect any malfunctioning or misuse as early as possible. For this purpose, attestation protocols have been introduced, which allow a third party, the verifier, to check the integrity of a remote device, the prover. Since traditional single device attestation protocols are impractical in large mesh networks due to their overhead of attesting each device individually, scalable attestation protocols have recently been proposed <cit.>. These protocols perform an efficient attestation of large networks by distributing the attestation burden across all devices in the network. All scalable attestation protocols are based on the assumption that an adversary can only manipulate the software of provers. Thus, they cannot withstand an adversary who is able to perform physical attacks and tamper with the hardware of provers. Yet, an adversary can rather easily capture a device and tamper with its hardware as devices forming MANETs are often distributed over wide public areas and consist of a multitude of devices. Hence, a scalable attestation protocol that is resilient to physical attacks is much needed.











Ibrahim et al. <cit.> presented a first approach to solve this problem by combining existing scalable attestation approaches <cit.> with absent detection <cit.> to detect both software and hardware attacks. The absent detection protocol is based on the assumption that a strong adversary, who physically tampers with a device, must temporarily take the device offline for a certain amount of time, e.g., to disassemble the device and extract secret keys <cit.>. To detect offline and thus physically compromised devices, each device periodically emits a heartbeat that needs to be received, verified, and logged by every other device in the network. Although a functional solution to the problem, the protocol suffers from several shortcomings. First, the amount of exchanged messages per heartbeat period scales quadratically with the number of devices in the network. This causes scalability issues in large networks with respect to network communication, energy consumption, and runtime performance. Furthermore, the protocol is very error-prone, since a single defective transmission of a heartbeat suffices to cause a false positive, where a healthy device is mistakenly regarded as compromised. Aggravating this, the protocol is only able to attest the state of the overall network and cannot identify particular compromised devices. Hence, a single false positive causes the entire network to be considered as compromised. Finally, the protocol relies on the assumption that during protocol execution the network topology is static and connected, which is a very strong limitation for wireless mesh networks.








In this paper, we present the first scalable attestation protocol () for interconnected embedded devices that is resilient to physical attacks. To protect against strong adversaries, we build on the established assumption that an adversary needs to take a device offline to physically tamper with it <cit.>. In our protocol, a single leader device periodically emits a new heartbeat that is propagated in the network. To obtain the newest heartbeat from a neighboring device, a device must authenticate itself with the previous heartbeat. Since a device that is under physical attack has to be absent for at least one heartbeat period, it will miss this period's heartbeat and thus be unable to obtain any further heartbeats. To prevent a collusion between compromised devices, heartbeats are stored in lightweight secure hardware and transmitted encrypted via secure channels. During the actual attestation, devices that fail to authenticate with the newest heartbeat are regarded as physically compromised, whereas devices with a compromised software are detected based on existing software attestation techniques. In case of an outage of the leader, a new leader device is determined through a leader election process. By optionally storing the attestation result in each device, our protocol is able to efficiently attest highly dynamic and partitioned network topologies.

We show that our protocol is secure against an adversary who compromises all but one device in the network. Finally, we demonstrate the practicability of our protocol in static and dynamic networks. In summary, provides the following improvements over existing work:



















  * can precisely identify devices whose hardware and/or software is compromised, if less than half of all devices in the network are compromised.


  * is very efficient. Compared to the best previous work <cit.>, we reduce the number of sent messages per time period from O(n^2) to O(n)[In fact, when detecting physically compromised devices through their absence, O(n) transmitted messages per time period is the best possible solution, since each device must at least send or receive one message to show that it is present.], thus, achieving scalability to millions of devices (where n denotes the total number of devices in the network).

  * is robust against network and device failures by
 (1) relying on a one-to-many delay-tolerant link in contrast to a many-to-many continuous link, as used in the best previous work <cit.>, and
 (2) offering a recovery mechanism, the leader election protocol, that minimizes the amount of false negatives.


  * provides a novel efficient aggregation scheme, e.g., attests of 4,000 devices fit into 1kB. This allows to attest highly dynamic and partitioned network topologies efficiently.


  * is the first scalable attestation protocol that is evaluated in dynamic network topologies.



















Outline The rest of the paper is organized as follows. In  <ref> we summarize existing work. In  <ref> the system model, device requirements, and adversary model are presented. In  <ref>, we describe our novel attestation approach to detect physically compromised devices. Then, in  <ref> we extend the attestation protocol to execute a recovery protocol on failures, verify the software integrity of devices, and support dynamic topologies during attestation. The performance of is evaluated in  <ref>. Finally, we conclude in  <ref>.











§ RELATED WORK





















































Device Attestation
Remote attestation is a mechanism that allows a third party, the
verifier, to check the integrity of a remote system, the
prover. Protocols that target the attestation of a single embedded
device are either
software-based <cit.> or
hardware-based <cit.>. Software-based techniques
require no secure hardware, but rely on assumptions that have been
shown to be hard to achieve in
practice <cit.>. Hardware-based attestation
mechanisms provide much stronger security guarantees by relying on
lightweight security architectures. Nevertheless, single-device
approaches are impractical in mesh networks due to the large overhead
of attesting each device individually.

Recently, protocols started to focus on an efficient attestation of
multiple embedded devices. Park et al. <cit.> proposed
to compare the integrity measurements of multiple devices. Yet, their
approach requires identical devices and only enables a probabilistic
attack detection rate. Asokan et al. <cit.> present a
highly efficient attestation scheme for large-scale networks of
embedded devices that requires only ROM and a simple MPU. In
their scheme, each device attests its neighbors and reports the
aggregated result back to its parent, eventually received by the
verifier. Ambrosin et al. <cit.> enhance this work
by introducing a novel signature scheme that enables anyone to
publicly verify the attestation result and allows the network to
contain untrustworthy aggregator devices, such as routers or cloud
severs. Yet, besides the work by Ibrahim et. al <cit.>, which has been discussed in  <ref>, existing works consider the adversary to compromise only the software on devices. In mesh networks, this assumption may not hold, since an adversary can comparatively easy capture a device and physically tamper with it.















Capture Detection
Several works have been proposed on the detection of node capture attacks, where an adversary physically approaches and manipulates a device. They all build on the assumption that an adversary needs to take a device offline, in order to tamper with it <cit.>. Conti et al. suggested that a node is collaboratively flagged as captured if it fails to re-meet with any other node within a fixed time interval <cit.>. In the approach by Ho <cit.>, nodes use statistical methods to detect absent neighbor devices in static network topologies. Recently, Agrwal et al. proposed to deploy multiple TPM-equipped cluster heads in the network, which check the integrity of the software as well as the physical presence of all nodes in the cluster <cit.>. Nevertheless, existing approaches are unable to detect devices with compromised software <cit.>, require the deployment of additional hardware <cit.>, are only applicable in static network topologies <cit.>, or lack scalability <cit.>.















Secure Data Aggregation Since ad hoc networks are often deployed to collect sensory data, many efficient and integrity-preserving aggregation schemes for mesh networks have been proposed. Unfortunately, these schemes rely on very costly asymmetric cryptographic operations <cit.>,
require to maintain a specific network topology during aggregation <cit.>, or need multiple communication rounds <cit.>, which both is undesirable, as
it leads to communication overhead in dynamic network topologies. Thus, a lightweight aggregation scheme suitable for remote attestation of embedded devices that supports dynamic topologies and allows the identification of compromised devices is missing.
























































§ PRELIMINARIES



System Model
In our model, we consider embedded devices that can be heterogeneous in terms of hardware capabilities and software resources, e.g., devices with different software, computational power, storage capacity, or security functionalities. All embedded devices are connected in a mesh network topology. This topology can be static, where devices remain stationary and the network is connected, or dynamic, where devices can move freely and the network can be temporarily partitioned. However, in dynamic network topologies, we assume that devices meet each other regularly due to their mobility. Devices that are unreachable for some time  are regarded as compromised, since it is uncertain whether they will ever contribute to the network again. We further assume that each device i gets initialized and deployed by a trusted network operator 𝒪, once ( <ref>).

After deployment, the goal of 𝒪 is to ensure the correct and safe operation of all devices 1, 2, ..., n in the network. Therefore, 𝒪 regularly verifies the integrity of all devices by executing the proposed attestation protocol. The attestation protocol determines all devices whose software is in a trustworthy, i.e., unmanipulated and up-to-date, state and whose hardware has not been tampered with. We refer to these devices as healthy devices, in contrast to compromised devices. Executing the protocol, 𝒪 is able to learn the precise identity of all healthy and all compromised devices. This may serve as a first step towards physically locating and recovering compromised devices. In order to perform the attestation protocol, 𝒪 requires a connection to at least one device in the network.





Device Requirements

We assume that each device i provides the minimal hardware properties for remote attestation, according to the work by Francillon et al. <cit.>. In practice, these properties can be implemented with ROM and a simple MPU. ROM stores the protocol code and cryptographic keys, and the MPU ensures an uninterruptible execution of the protocol code and allows only protocol code to access the cryptographic keys. Recently, it has been shown that these minimal hardware properties are available even on many low-cost commodity embedded devices <cit.>. Additionally, our attestation protocol relies on authentic time measurements. In order to prevent malware from tampering with the device clock, each device must provide a write-protected real-time clock. Protected real-time clocks are already built-in many existing commodity embedded devices <cit.>. We henceforth refer to the execution space, where all required hardware properties are fulfilled, as TEE.




Adversary Model


In this work, we regard a powerful adversary , who is able to
mount attacks on the network as well as the software and hardware of devices.
In detail, is granted full control over all
messages in the network (Dolev-Yao model).
Thus, can eavesdrop, modify,
delete, or synthesize all message between any two entities.[We note that the model allows DoS attacks, such as jamming or cutting wires. These attacks cannot be prevented against a physically present adversary. However, DoS attacks have no influence on the security of our scheme, as cannot use them to forge a healthy system state.]


Moreover, is allowed to compromise the software of all
devices in the network. This gives full control over the devices'
execution state and storage, yet, no access to the protected contents
inside the TEE.
We further allow to capture and physically tamper with up to all 
but one device in the network, when attesting the overall network state,
and up to half of all devices in the network, when knowledge on the
precise identity of compromised devices is required. 
For the physically compromised devices,
is able to access device secrets and code inside the TEE
and is allowed to manipulate the clock. We note that it is impossible
to guarantee a secure device attestation, if all devices in the network
have physically been compromised <cit.>.
Finally, as in <cit.> we assume that mounting a physical attack
requires at least a time , in which the device is offline,
e.g., to decapsulate the device and to launch a microprobing attack.
Depending on the device's level of tamper resistance and the
adversaries resources, such attacks typically require hours up to
weeks in specialized laboratory environments <cit.>.











































§ 


In the following, we describe the protocol, which identifies devices in the network have physically been tampered with. Note that the detection of hybrid attacks, i.e., attacks that target hardware and software, is discussed in the next section ( <ref>).  consists of three different phases. In the initialization phase ( <ref>), the trusted network operator 𝒪 initializes each device once, before the deployment of the network. The heartbeat phase ( <ref>) is periodically executed during the operation of the network. In this phase, all physically uncompromised devices maintain a valid state by sharing a common group key, namely the heartbeat. We will show how the heartbeat is periodically regenerated and propagated in the network and demonstrate that physically compromised devices are unable to obtain the heartbeat. Finally, in the attestation phase ( <ref>), 𝒪 initiates an attestation of the network and obtains a report, which exhibits all physically compromised devices.





 §.§ Initialization Phase


Preliminaries
Devices can either be in a healthy or compromised hardware
state. We discretize the time into non-overlapping time periods
t ∈{1,2,3,...} of fixed length . We reference the starting times
of each time period with T_1, T_2, T_3, .... The real time T_clock can be
read by any device from a reliable read only clock , which for simplicity
is assumed to be synchronized between all devices. Each devices keeps track of
the current time period t, running from time T_t until T_t+1.  In the
remainder of this section, we assume an implementation of a function
(t)  that returns a constant , iff the real time is within the
time period indicated by parameter t, i.e, T_t ≤ T_clock < T_t+1
and otherwise . 



Enrollment
In the enrollment phase, the network operator 𝒪 initializes the
TEE of all devices with the following secrets. First, devices store two 
initial heartbeats  and , which function as a group secret between
all healthy devices.
Second, each device is equipped with a device-dependent symmetric key _i,
used during attestation to generate a device unique attest,
and an asymmetric key pair (_i, _i), employed to establish
secure channels between devices. Finally, devices record the current time period
t, their own device identifier i, and the identifier of the leader device min, which is the
first device 1 in the network. Table <ref> provides
a summary of relevant definitions.

For explanatory reasons, we assume an initial enrollment of all devices. However, also allows devices to be enrolled at any point in time by issuing the current heartbeat.











 §.§ Heartbeat Phase



Basic Idea
The heartbeat protocol is the core protocol of our approach. It excludes
devices from the network that are offline for more than one time period and, hence,
are assumed to be physically tampered with. During protocol execution,
a so-called leader device emits a new secret group key, named
heartbeat, that is propagated in the network. Obtaining this heartbeat
requires a device to authenticate with the heartbeat of the previous time period.
Therefore, devices that are offline in an arbitrary time period T_a miss the
heartbeat that is propagated in T_a and thus are unable to obtain a heartbeat
in any subsequent time period T_a+1, T_a+2, .... Since any communication
between devices in all protocols is secured using the newest heartbeat as a key,
physically compromised devices are unable to participate any more.
In the following, we describe the heartbeat transmission protocol, formalized in
Figure <ref>, which is run between two neighboring devices to
transfer the heartbeat from one device to the other.









Heartbeat Transmission Protocol
The emission of the new heartbeat in every time period is initialized
by the leader device. As soon as the leader
observes that the real time T_clock has reached the start of a new
time period ((t) returns ), the leader first
updates the heartbeat of the current time period  to the most recently
exchanged heartbeat .
We remark that heartbeats could also be indexed by the time period in which
they are active in, e.g., _1,_2, _3, …. However,
as only two heartbeats are relevant for any device, only these two, i.e.,
the current and next heartbeat, are stored and referenced.
After updating the current heartbeat, the leader samples a new heartbeat 
for the subsequent period t+1 and increments its time pointer t by one.
Consequently, the time period described by the
pointer is now ahead of the real time T_t > T_clock. 
A time pointer ahead of the real time indicates a device that it
is in possession of a heartbeat for the upcoming time period.
The leader initialization code is illustrated below.







  t:
 
  ←

  ^n

  ← + 1 

  broadcast(_new)









Next, the leader informs its
neighbors about the new heartbeat with a message _new.
For simplicity, we henceforth assume that two neighboring devices
have already established a shared secret _ij by performing
a key exchange using their public keys authenticated with the current heartbeat.
















































On receiving
_new from any device i, a device j will enter
its TEE and check whether the next time period has been reached.
If this is the case, j will update
its current heartbeat to the previously communicated one. Afterwards,
j encrypts a fixed string, e.g., '0', under the current
heartbeat  XOR-ed with the channel key _ij shared by
both devices and sends the result to i. We refer to this
XOR-ed key, as the session key.
 

A healthy i can decrypt the message by also computing the session
key. A successful decryption proves that j is in possession of
the current heartbeat (and the channel key) and is therefore eligible for the 
next heartbeat. Then, i answers with a
message _hb containing the next heartbeat , also encrypted
with the session key. On successful decryption, device j stores the
new heartbeat as . Afterwards j increments its time
period pointer and then announces this new heartbeat to its neighbors with
_new.  Figure <ref> illustrates the heartbeat
transmission phase in a network with 6 healthy devices and one adversarial
device A that was physically compromised in time period t = 2.

We note, that the heartbeat protocol relies on the availability of the leader
device, which constitutes a single point of failure. In
 <ref> we present an extension that makes 
the heartbeat protocol more robust against device outages, network 
partitioning, or targeted denial of service attacks.














































 §.§ Attestation Phase



Basic idea. The attestation protocol allows the operator
𝒪 to check the state of all devices in the network. For this purpose,
𝒪 issues an attestation request that is answered by all devices with
an attestation report. Propagating the attestation request through the network arranges a spanning tree whose root is 𝒪. This enables an efficient transmission and aggregation of attestation reports along the spanning tree to 𝒪.
supports two variants of attestation. The first variant allows to attest
the overall network state and is secure against an adversary who compromises all but one device.
However, it only outputs a Boolean result, namely whether all devices are healthy or not.
The second variant precisely identifies compromised devices by id and in this way
increases the protocol's robustness and applicability in practice. Yet, it requires
more than half of all devices in the network to be healthy.








Attestation protocol. The protocol is formalized in
Figure <ref>. The operator
𝒪 initially connects to a device i in the network and emits
an attestation request. The request contains the concatenation of a current
timestamp ts and the number of devices n in the network,
encrypted under the device's key _i,
which is only shared between i and 𝒪.
By verifying the authenticity and timeliness of the request
(ts),
denial of service attacks through replays can be prevented. 
Next, the attestation request, consisting of the concatenation of ts and n,
is propagated by i to its neighboring devices. This and all following
communication between two devices is secured with the pairwise session key,
i.e., the current heartbeat XOR-ed with the channel key. Any
device that receives an attestation request first verifies the request and
then also propagates the request to its neighboring devices. These
steps are repeated until the attestation request reaches devices, whose
neighbors already have received the request. In this way, a spanning tree is
constructed. Leaf devices that cannot propagate the request any further
return an attestation report to their parent device from which they initially obtained the attestation request.
The attestation report contains their own attest, which consists of ts encrypted under their own device key.

Every non leaf device merges its own attest (and identifier) with all received attestation 
reports and propagates the merged report to its parent device.
Eventually, i merges a final report that contains all healthy devices
in the network. This final report is encrypted under _i and transmitted
to 𝒪, who verifies the report, as described in the next paragraph.

We note that the attestation must be completed in time 
or 𝒪 has to periodically check the presence of i
during attestation.
Otherwise, can physically tamper with i to extract an aggregate
and induce attests of physically compromised devices.
Figure <ref>
illustrates the attestation phase in a network with 6 healthy devices and one
adversary device A that was physically compromised.


Report Aggregation and Merging
An aggregated attestation report consists of two parts. The first part contains
a description of all device identifiers that are in the aggregate. The second part
consists of the aggregated attests.

For a small number of devices, the description is a list of device identifiers,
else it is an n-bit vector, where a one at position
k indicates that k is contained in the aggregate.
The attests themselves are aggregated by XOR-ing all
individual attests. 
Multiple attestation reports are aggregated by merging their device descriptions and XOR-ing their aggregated attests.




When attesting the overall network state, the attestation report consists of only
the aggregate, as a device identification is not required.
This decreases the size of the report significantly ( <ref>).
Therefore, to increase efficiency, it is useful to run the attestation
with precise device identification only, if an attestation of the overall network state fails.
















Report Verification
Given a device description, 𝒪 recomputes the attests for all devices,
whose id is contained in the description. Given no description, 𝒪 recomputes
the attests for all devices.
If the recomputed aggregate equals the reported aggregate and if at least
n/2 attests are included in the report, then the report is assumed to
be valid. Only then, all attested devices are assumed to be healthy and
the verification returns a bit vector, where a zero/one at position k
indicates that k is compromised/healthy.




































 §.§ Security Analysis


Intuitively, an attestation protocol is secure, when the
network operator 𝒪 will testify a healthy system state, if not
a single device has physically been compromised. We refer to such
an attestation scheme as non-informative secure.
Moreover, an informative secure attestation protocol allows 𝒪 to
distinguish between healthy and compromised devices.
We follow the idea of Asokan et al. <cit.> and
prove the security of our protocol by an adversarial experiment
(k). In this experiment, the adversary  is given access
to a network of n initialized devices  that execute
the heartbeat and attestation protocol.
 can interact with all devices
according to the attacker model presented in  <ref>.





















Moreover, we assume any adversary to be computationally bound (PPT).
Hence, is able to interact a polynomial number of times k
with devices in the network (and the authenticated encryption scheme).
Furthermore,  is allowed to trigger
and observe attestations by 𝒪.
After at most k interactions, a final attestation is initiated by 𝒪.


The output of (k) is then a bit vector returned by 𝒪 after
verification of the final request. A bit vector with only zeros
indicates a compromised network, whereas every bit set to one indicates
a healthy device, cf.  <ref>.
We capture the intuitive idea of secure attestation in
the following definition.

Secure Attestation Scheme.  An network attestation scheme
for n devices is secure if

    [(k) = 1^n] ≤ negl(k)

for any PPT and 0 < c < n, where c is the number of compromised devices.
An attestation scheme is informative and secure if

    [(k)[j] = 1] ≤ negl(k)
 for any PPT and every compromised
device j, where [j] is the j'th bit in the result vector
and the total number of compromised devices c is 
less than n/2.

Note that the definition of a non-informative secure attestation scheme
is similar to the definition given in <cit.>, which is
defined without device identification in mind.

Security of 
The security of is summarized
in Theorem <ref>.





is an informative and secure attestation protocol when the
length of a heartbeat period  is at most /2, assuming 
security of the PRNG and authenticated encryption
scheme that guarantees confidentiality (IND-CPA) and
authenticity (INT­-CTXT).



In the following paragraphs,
we sketch a proof to show that is an informative secure
attestation scheme.
The sketch is split in two parts. First, we sketch a proof for 
Theorem <ref>, which formalizes the security
of the heartbeat protocol, before arguing the security of
the full protocol.








Any PPT is unable to gain access to any heartbeat _t, which is used to
secure the communication in time period t, before
time period t+1, assuming < /2, security of the PRNG, secure channels between devices and an authenticated encryption scheme that guarantees IND-CPA and INT-CTXT.


Intuitively, the security of the heartbeat protocol is achieved
by using an interactive protocol that requires the receiving device to
prove its knowledge about the current heartbeat to the sending device.
Only then, the next heartbeat is exchanged.
This active participation makes it impossible
for offline devices to follow the continuous `stream' of heartbeats.

Proof Sketch - Heartbeat

We observe that no two heartbeats are linked. 
Hence, it is impossible to derive any _t
from _1,_2,…,_t-1 without breaking the security
of the PRNG. Moreover, assuming synchronized clocks, every healthy device stores
at most two heartbeats in any time period t, namely _t-1,
_t or _t,_t+1. When compromising a single device in time
period t and assuming an attack time of ≥ 2 ·,
the attack will be successful not earlier than in time period t+2.
The TEE of the compromised device will then leak 
at most heartbeat _t+1, but no later heartbeats, as 
these are not present in the TEE.
We observe that with any attack time < 2 ·,  would be able
to compromise a device without missing a single heartbeat period, and thus
render the protocol insecure.

We show that  is unable to gain access to the current heartbeat
by interacting with healthy devices without breaking the security
of the authenticated encryption scheme. During the heartbeat exchange,
all messages sent between two devices i and j are encrypted with a session
key that is the XOR of the pairwise channel key _ij and the current heartbeat _t at time t.
Thus, the session key is only known to i and j at time t.
We observe that with access to only one (or none)
of the two keys,  is unable to create or to decrypt a message that
is accepted by i or j without breaking the INT-CTXT and 
IND-CPA security of the encryption scheme. Hence, even when compromising
further devices and extracting (past) heartbeats, is unable to
decrypt any past or future communication between i and j, as is missing the pairwise channel key _ij. Similarly, after compromising
a device and gaining access to all channel keys, is still
missing  the current heartbeat to construct the session key, required to
interact with neighboring devices.




The same arguments hold for all messages sent between devices in the
aggregation protocol, since they are all encrypted using the pairwise session key.



















Proof Sketch - Attestation 



The attest of a single device i is
the encryption of the timestamp ts, issued by 𝒪, under i's
device key _i. Thus, is only able to forge an attest for
a healthy i with non-negligible probability when being able to
break the IND-CPA security of the encryption scheme.
Yet, to win , has to report at least n/2 (informative) or
n (non-informative) valid attests, while being allowed to only compromise up to c < n/2 
or c<n devices. Consequently, since is unable to forge an attest for a healthy
device with non-negligible probability, has to merge the attests of compromised
devices with attests created by healthy devices. 



During the actual attestation protocol, two cases can be distinguished.
First, the device
i that 𝒪 approaches for the attestation
is compromised. In this case,  can create an attestation report
for all compromised device. However, without access to a valid heartbeat 
and thus session key, 
can only create a valid attestation request message _att
with non-negligible probability, when breaking the INT-CTXT security
of the encryption scheme. Hence, no healthy device will contribute an
attest.



Similar, in the second case, where 𝒪 first approaches a
healthy device, is, for the same argument as described above,
unable to decipher or induce any message in the
attestation protocol between healthy device.
Furthermore, the security of a XOR aggregation scheme, as used here,
is shown in <cit.> and consequently,
is non-informative secure, when only accepting
a complete aggregation report that includes the attests of all devices. 
Furthermore, it is informative secure, when accepting 
reports with at least n/2 attests,
because attests can be attributed towards their device id.
Finally, we remark that the `honest majority' assumption c<n/2 is required, as
otherwise a dishonest majority could fake a healthy systems state.





















§ PROTOCOL EXTENSIONS



In the following, we present three significant extensions to . First, we make the heartbeat transmission phase more robust against failures ( <ref>). Next, we extend to verify the integrity of the software on all devices in the network ( <ref>). Finally, we propose an extension that allows efficient attestation in highly dynamic and disruptive network topologies ( <ref>).








 §.§ Leader Election Protocol


The leader election phase extends the heartbeat transmission phase, to make it more robust against failures. In particular, devices that fail to receive the current heartbeat elect a new leader device that takes over the tasks of the previous leader, i.e., the periodic emission of a new heartbeat. In this way, the heartbeat protocol is able to recover from device outages, network partitioning, or targeted denial of service attacks.

The leader election protocol is initiated by every device that fails to receive the heartbeat within a time _hb that is shorter than the heartbeat period  (_hb < ). Devices execute the leader election protocol inside their TEE and use the remaining leader election time _le =  - _hb to determine the device with the smallest id, which then becomes the new leader device
(bully algorithm). For this purpose, devices initially generate their own heartbeat and then announce this heartbeat together with their device id to all neighboring devices. Devices store the smallest device id that they received in the leader election phase, including the corresponding heartbeat. Whenever a device updates its smallest received id and heartbeat, it broadcasts both to their neighboring devices. Thus, the new smallest id and heartbeat are quickly propagated in the network. A device recognizes itself as the new leader device, if it only receives messages from devices with higher device ids. Note that the original leader has the smallest id in the entire network, hence, the protocol also tolerates a return of the original leader. In Appendix <ref>, we formalize the leader election protocol, describe it in more detail, and demonstrate its security.




 §.§ Attestation of Software Integrity


In order to attest the correct and safe operation of all devices in the network, it is crucial to ensure that devices are in a trustworthy software state, free from malicious or broken software. For this purpose, we propose that the network operator 𝒪 defines a set of trustworthy software states tss in the attestation request, when initiating an attestation of the network. Tss specifies all software configurations that are permitted by 𝒪, e.g., because they represent the correct and most recent software states. When devices perform the attestation protocol, they invoke the execution of a software integrity measurement function in their TEE. This function measures the integrity of installed software and compares these measurements to the reference values specified in tss. In this way, each device determines whether it is in a trustworthy or untrustworthy software state. Devices being in an untrustworthy software state immediately abort the attestation phase and instead execute a recovery routine that allows the device to restore a trustworthy software state, e.g., via secure code updates <cit.>. Since untrustworthy devices do not participate in the execution of the attestation protocol, 𝒪 receives a report which exclusively contains devices that are in a trustworthy software and uncompromised hardware state. In Appendix <ref>, we extensively explain changes that need to be done to the enrollment phase and the attestation protocol to enable such a hybrid attestation. Furthermore, we discuss the security of the extension.



 §.§ Attestation of Dynamic Networks



Approach
The attestation protocol in ( <ref>) arranges a spanning tree, which allows for an efficient aggregation and transmission of the attestation report to the network operator 𝒪. This approach works efficiently as long as the network topology stays static during attestation, for instance, as devices in the network only move as a whole (herd mobility) or within local limits (micro-mobility). However, in dynamic network topologies with highly mobile devices and frequent link disruptions, it is impractical to maintain a spanning tree topology. In such networks, communication with a parent device could introduce a significant delay
or become highly inefficient, as the parent device could move away. Even worse, the parent device may be temporarily out of range and thus be disconnected from the network. 

Therefore, instead of routing the attestation along a virtual topology, we propose a distributed (greedy) aggregation, where attestation reports are collected and aggregated by all devices in the network. Thus, after 𝒪 initiates the attestation protocol, each device first generates its own attestation report, stores this report, and broadcasts it to all neighboring devices. When a device receives an attestation report, it merges this report with its stored report. On observing new attests, the device broadcasts the updated report to all its neighboring devices. In this way, all devices in the network eventually store the same attestation report and 𝒪 can obtain the attestation result from an arbitrary device in the network.

To reduce the communication complexity, an aggregation scheme for the above mentioned approach must allow to merge multiple reports with intersecting attests into one. This requirement renders the aggregation function described in  <ref> inapplicable, because its XOR operation risks the removal of intersections of attests from the aggregate. 
Because of this and following the analysis of aggregation protocols in  <ref>, we present a novel aggregation scheme for dynamic networks that is particularly tailored to the application scenario.













Secure & Efficient Attestation Report Aggregation










The here proposed scheme achieves statistical security and is slightly less powerful
than the spanning tree aggregation scheme, as it allows an adversary to
compromise at most c < n/2 - s devices, with 2^-s being the statistical
security level.
In our scheme, an attestation report also consists of two parts, namely
the device description and the secure aggregate itself. 
The device description is a n-bit vector where a bit is set for every
device included in the aggregate. The aggregate consists of an
n_s =(n+s)-bit vector, where a single bit indicates the attest of a
device. A device i that receives an attestation request with
timestamp ts, creates its own attest using a collision
resistant cryptographic hash function  by computing
a = (dk_i || ts) in its TEE. Subsequently, i 
sets a bit at position i in the device identifier as well as
a bit at offset compress(a) in the secure aggregate, where
compress is a function that reduces the hash value to a value of
length n_s bits. Note that compress does not need to be 
cryptographically secure, but it should achieve a close to uniform 
output distribution for uniformly distributed input.
All other bits in both vectors are set to 0.
In order to merge multiple attestation reports, a device
computes the bit-wise OR of all attestation reports. This can be done
very efficiently and allows to aggregate reports with intersections of
devices. 
Both the secure aggregate and the list of device identifier could be
compressed, for instance, by using a run-length encoding. Nevertheless,
even without compression, a very short attestation report
is achieved with a length of only 2n+s bits, e.g., 266 bytes for
1000 devices and a security level of s=128 bit, which is a significant
improvement over a naïve concatenation of attests that requires more
than 16k bytes. Even though, has a good chance to guess
a small number of attests correctly, the security of the scheme is based
on the hardness to guess (at least) s attests correctly.
A detailed security analysis of this scheme is given in
Appendix <ref>.




















































































§ EVALUATION



Next, we evaluate ( <ref>) and its three protocol extensions ( <ref>). In  <ref>, we describe our setup, give details of the implementation, and present our measurements. Then, we report on our network simulation results for both static ( <ref>) and dynamic network topologies ( <ref>).



 §.§ Implementation & Measurements



Setup
We implemented our protocol on Stellaris EK-LM4F120XL microcontrollers. The Stellaris is a low-cost embedded system from Texas Instrument which features an 80 MHz ARM Cortex-M4F microprocessor and 256 kB of Flash memory. To enable wireless mesh connectivity based on the ZigBee standard, we equipped the Stellaris microcontrollers with Anaren's CC2530 BoosterPacks.




Cryptographic Runtime Measurements
We im­ple­men­ted the hash function using SHA-512 and employed AES in Galois/Counter Mode (AES-GCM) as an authenticated encryption scheme. For the key exchange, we used Elliptic Curve Diffie-Hellman (ECDH) with Curve­25519 <cit.>. Table 2 shows an excerpt of our cryptographic runtime measurements on the Stellaris microcontroller.



We would like to stress that our implementation is based on platform independent and unoptimized C code.[We used SUPERCOP's ed25519 implementation (<https://ed25519.cr.yp.to/software.html>) and SharedAES-GCM (<https://github.com/mko-x/SharedAES-GCM>).] Assembler optimized code for low-end embedded systems can improve the performance of cryptographic operations by orders of magnitudes <cit.>. We presume that similar performance improvements are also possible on the Stellaris.




Network Runtime Measurements
For unicast messages between two neighboring devices in the mesh network, we measured an average throughput of 35.0 kbps on the application layer. Although the theoretical maximum throughput in ZigBee networks is 250 kbps, other performance evaluations revealed similar performance losses in reality <cit.>. In addition, we measured an average end-to-end delay between two neighboring devices of 13.5 ms with the smallest message size and 18.5 ms with the biggest message size.




Memory Costs
In our implementation, devices store their own ECDH key pair (64 bytes), the current and the next heartbeat (each 16 bytes), the leader device id (4 bytes), k secure channel keys and device ids (each 20 bytes), and a timestamp (4 bytes). The number k of stored secure channel keys can be adjusted to the particular memory requirements, since devices can establish channel keys right away by performing an ECDH key exchange with a neighboring device ( <ref>). Additionally, devices need to temporarily store data: the public key of a neighboring device (32 bytes) during key exchange, a session key (16 bytes) during heartbeat transmission, and the attestation report during attestation. The size of the attestation report is dependent on the number n of devices and the usage of the dynamic network extension. If it is used with a security level of 128 bit, the report amounts to n/4 + 16 bytes, if not, to n/8 + 16 bytes. However, as reports can be compressed using run-length encoding, their actual size is much lower for most devices in the network. In total, devices require 104 + k · 20 bytes of permanent storage and at most n/4 + 16 bytes of temporary storage.





 §.§ Simulation Results for Static Networks


Setup.
We first evaluated our protocol in static network topologies, where all devices are connected and stationary. Thus, there are no link breaks or abrupt delays in the network communication. We used  <cit.> to simulate a homogeneous network with ten to multiple million Stellaris devices. Following the typical evaluation methodology in scalable attestation protocols <cit.>, we implemented our protocol on the application layer and used computational and network delays based on our measurements (see  <ref>).














Heartbeat Protocol Runtime
We simulated the runtime of the heartbeat protocol in various topologies. Figure <ref> shows the runtime for a binary, 4-ary, and 8-ary tree topology with up to 550.000 devices, where the heartbeat leader device is located at the root of the tree. The figure demonstrates that in tree network topologies, protocol runtime increases logarithmically with the number of devices in the network. Under these conditions, the heartbeat protocol achieves an outstanding performance, requiring less than 2.3 seconds to reach 500.000 devices in an 8-ary-tree and less than 1.7 seconds in a binary tree topology. Even with multiple million devices, runtime remains below 2 seconds in a binary-ary tree topology. Only the first run of the heartbeat protocol in the network requires little more time, since neighboring devices initially need to exchange public keys and perform key exchanges to establish shared secrets. Yet, even with the additional key exchanges runtime remains below 5.1 seconds for more than 500.000 devices.







Attestation Protocol Runtime
We configured the attestation protocol to use the software attestation extension ( <ref>) and thus to attest the hardware and software state of all devices in the network. To verify the integrity of installed software, devices compute a SHA512 digest over a 30 kB software and compare the digest to an expected value that is specified in the attestation request. 
For attestation we used the spanning tree attestation approach ( <ref>).





Figure <ref> shows the runtime for a binary and 8-ary tree topology with up to 550.000 devices, where the network operator is located at the root of the tree. Additionally, we varied the type of the attestation report, containing either the precise ids of healthy devices (solid lines) or the state of the overall network (dashed lines). The figure demonstrates that reporting precise device identifier introduces a notable overhead. When reporting the overall network state, attestation runtime increases barely with the number of devices in the network, remaining below 2 seconds even for networks with multiple million devices in almost any tree topology. Yet, when reporting precise device ids, runtime increases to more than 152 seconds for 500.000 devices due to the large size of the attestation report, which increases proportionally with the network size. Nevertheless, we consider that 2.5 minutes is an acceptable timeframe to obtain a report that precisely lists which devices 
are in a compromised state.





Communication Costs 
During heartbeat transmission, all devices, except for the leader device, receive  msg_new (1 byte), send msg_req (17 bytes), and receive msg_hb (17 bytes) to obtain the newest heartbeat, using a one byte message identifier. 
If devices need to (re-)establish a secure channel key, they need to mutually exchange their public keys, which causes an additional message overhead of 32 bytes. For instance, in a binary tree topology, devices transmit in total 104 bytes, or 296 bytes with the initial key exchange, in each heartbeat transmission period. 

During the execution of the attestation protocol, all devices receive one msg_V (17 bytes) or msg_att (17 bytes).

Also, devices send a msg_att to all neighbor devices that have not yet received msg_att and afterwards receive a msg_agg from them (≤ n/8 + 16 bytes). If the device's software integrity is attested ( <ref>), msg_V and msg_att contain the set of trustworthy software states tss, in our evaluation a 64 bytes hash digest. In short, assuming a binary tree topology and n = 1000 devices, during a run of the attestation protocol, each non-leaf device transmits at most 666 bytes and each leaf device 222 bytes.








Summary
We demonstrated that our protocol is highly efficient in static network topologies. In comparison to the previously best attestation protocol that is secure against physical attacks <cit.>, we reduce the number of transmitted messages per time period from 𝒪(n^2) to 𝒪(n). 
To illustrate this advantage, in binary-tree topologies our approach is 27 times faster with 2000 devices and 3800 times faster with 500,000 devices when interpolating their results. The comparison already considers the fastest variant presented in <cit.>, which requires each device to store and manage n symmetric keys. In our protocol, devices must only store the keys of neighboring devices, e.g., 3 in a binary tree topology.



When attesting the state of the entire network, both protocols (<cit.> and ) show a runtime that scales logarithmically with n. Nevertheless, in contrast to <cit.>, also allows to determine the ids of compromised devices with low overhead even in larger networks.







 §.§ Simulation Results for Dynamic Networks


Setup
We further evaluated our protocol in highly dynamic and disruptive networks to investigate its robustness in complex scenarios. To model device mobility, we randomly deployed devices in a 1000m x 1000m square area and applied a random waypoint mobility model, which is commonly used in literature on absence detection <cit.>. Consequently, each device repeatedly selects a random speed as well as a random destination within the area and then moves towards the destination at the selected speed. The random device movement causes the network to be constantly partitioned, especially for sparse networks. In order to investigate effects like link disruptions, varying network delays, and signal interference that emerge due to the movement of devices, we modeled an 802.15.4 physical and medium access control layer using the  module. Modeling both layers as well as device mobility requires a lot of computational power. This is a known issue in MANET simulations, which leads to huge simulation runtimes <cit.>. For these reasons, we were only able to run simulations with a few hundred devices. Nevertheless, as we will show in this section, the main hurdle of our protocol is to perform well in sparse networks. Scalability of our approach in dense networks, where all devices are permanently interconnected, is shown in the previous section. In addition to the above mentioned simulation parameters, we set the wireless communication range to 50m (50% of the distance specified in the ZigBee standard), the device speed to a random value between 5 and 15 m/s, and the heartbeat as well as the leader election period to 2.5 minutes (detecting physical attacks that require more than 10 minutes).










Heartbeat Protocol Robustness
We investigated the robustness of the heartbeat protocol in worst cases, which are highly dynamic and disruptive network topologies. In particular, we examined the time until the protocol produces false positives, i.e., healthy devices that are regarded as physically compromised, because they did not receive the heartbeat on time. Figure <ref> illustrates the average runtime of the heartbeat protocol until a certain amount of false positives occur. The figure shows that the number of devices in the network has a vital influence on the robustness of the heartbeat protocol. Since devices move completely at random, the network must be sufficiently dense so that devices meet each other frequently enough to exchange the newest heartbeat on time. In fact, there is an exponential correlation between robustness and device density, which causes the average error-free heartbeat runtime to quickly increase from 2.4 days for 60 devices to weeks with more than 90 devices. To illustrate the sparseness in this scenario, 60 statically connected devices could cover at the maximum 29% of the area and 90 devices 43.4%. Nevertheless, as shown by the boxplot, the runtime between multiple simulation results differ widely. This makes it hard to guarantee robustness for sparse network scenarios. Investigating the false negatives, we identified the main cause in the random movement of devices. Commonly, a single device hides away, i.e., does not encounter other devices, and thus has no chance to receive the newest heartbeat on time. This cannot be prevented by faster computations or smaller communication delays in our protocol, but only be increasing the duration of the heartbeat phase.
We also observed that this hiding of a single device has barely any cascading effect on other devices. Hence, as shown in Figure <ref>, if tolerating a minimal amount of false positives, significant longer protocol runtimes are possible.













Next, we analyzed the effectiveness of the leader election extension by simulating an outage of the heartbeat leader device. Figure <ref> shows the largest fraction of devices that agreed on a common new leader with an increasing time interval for the leader election phase. It again illustrates the importance of the network density. In dense networks, leader election information can spread faster and thus reach more devices in shorter time. Nevertheless, even in relatively sparse networks with 60 devices, a time interval of 150 seconds is on average sufficient to let all functioning devices agree upon a new common leader. This also highlights our robustness against targeted DoS attacks, where an adversary attempts to disrupt the heartbeat protocol by breaking the heartbeat leader device.



Attestation Protocol Runtime
For the evaluation of the attestation protocol in dynamic networks, we used our dynamic attestation extension ( <ref>) with a statistical security level s of 128 bits. Figure <ref> shows a boxplot of the elapsed time between the emission of the attestation request and the moment when all devices in the network store the final attestation result, i.e., a report that contains all devices, for an increasing number of devices in the network. With an increasing network density, attestation reports spread faster and the overall attestation protocol runtime decreases. However, this effect is not as distinct as with the heartbeat protocol, where we observed an exponential correlation between protocol performance and network density. This is because, in contrast to the heartbeat protocol, where a single message is flooded in the network, each device must contribute with a message, i.e., its individual attestation report, to a global attestation aggregate. Furthermore, the size of the attestation report increases proportional with the network size, though, being reasonably small for common network sizes (e.g., 2.5kB for 10,000 devices). Figure <ref> also shows that the runtime of the attestation protocol varies little. This guarantees that the final result is with high probability reached within a certain time frame, e.g., 5 minutes for 100 devices.




Communication Costs
Message costs in dynamic network topologies are, except for the attestation report, the same as in static network topologies ( <ref>). However, due to link failures, some messages are transmitted more often in dynamic topologies. In our simulations, we varied the network size between 40 and 100 devices and let devices actively poll their neighbors for the newest heartbeat after 10 seconds. Our results revealed that, depending on the network size, each device sends on average 19.4 to 21.0 msg_new (poll heartbeat) and 1.04 to 1.12 msg_req as well as msg_hb messages. Hence, in total, devices transmit on average 114 bytes in each heartbeat transmission phase. Compared to static network topologies ( <ref>), this is less than 10% communication cost overhead.

Nevertheless, because the attestation result is distributed to all devices, the actual attestation consumes considerably more communication in disruptive networks. Conducting the same simulations as described above, we observed that each device exchanges on average 12.4 attestation reports in networks with 40 devices, 16.0 with 60 devices, 18.9 with 80 devices, and 21.5 with 100 devices. Each exchange requires a device to send one msg_att and receive one msg_agg. Note that the dynamic attestation report in msg_agg has a size of at most n/4 + 16 bytes. Thus, in total, devices transmit on average 1375 bytes in networks with 100 devices, which is 4.2 times more than in static network topologies.









Summary
We showed that our heartbeat and attestation protocols are robust and efficient, even in highly partitioned and unpredictably changing network topologies. In fact in an exemplary low connectivity scenario, with a maximum possible area coverage of 43% for randomly moving devices, the heartbeat protocol still runs on average 65 days without producing a single false positive with =10 minutes. We further illustrated the effectiveness of the leader election protocol, by completely recovering networks from device outages in less than 130 seconds in the same setting. Finally, we demonstrated the robustness of our attestation protocol in dynamic networks and showed that its performance is dominated by network connectivity as opposed to the protocol's communication complexity.





















§ CONCLUSION & FUTURE WORK


We presented the first scalable attestation protocol for mesh networked embedded devices that is resilient to physical attacks. Compared to existing solutions, our protocol reduces the number of transmitted messages per time period from 𝒪(n^2) to 𝒪(n), thus scaling to millions of devices and outperforming existing solutions by orders of magnitude. In addition to attesting the overall state of the network, is able to precisely identify devices that run compromised software or have been physically manipulated. 
We demonstrated that our protocol is robust and efficient, even in very dynamic topologies, as it can perform an attestation or recover from device outages within minutes.

In future work we plan to investigate our protocol in specific network application scenarios, such as drone-based delivery systems or wireless sensor networks. Moreover, we want to make use of MANET simulators that are optimized for scalability and/or parallelism, in order to be able to simulate thousands of moving devices.



















abbrv







§ PROTOCOL EXTENSIONS




 §.§ Leader Election Protocol



Heartbeat Transmission Extension
The leader election protocol is shown in Figure <ref> and extends the heartbeat transmission phase described in  <ref>. We henceforth divide each time period T_1, T_2, T_3, ... of length  in two phases: the heartbeat phase, whose length is _hb (formerly ), and the leader election phase, whose length is _le =  - _hb. Furthermore, we assume that the function (t) returns the constant  if T_t ≤ T_clock < T_t + _hb, the constant  if T_t + _hb≤ T_clock < T_t+1, and  otherwise.

Every device i that did not receive a heartbeat within _hb, indicated by t, will generate its own heartbeat ^i, set the current leader device id to its own id (min^i←i), and update its time pointer by one. In a next step i informs its neighbors about the new heartbeat with a message _le.




Two devices that already initialized the leader election phase negotiate the heartbeat as follows.
First, a leader election request message _le_req is generated by
j that contains a session key to secure the remaining communication.
Then, i sends the smallest received device id min^i and the
corresponding heartbeat to j. Initially these are i's own id and generated heartbeat.
Device j will then compare its previous smallest id min^j
with the just received id.
If min^i < min^j, j will update min^j  to min^i
and set ^j to  ^i.
Finally, j will inform i of the result of the comparison,
which is also stored by i.
Both devices will then continue to further broadcast
the new heartbeat. The protocol terminates 
implicitly, once the smallest device id has been identified.
We note that a leader, who is absent
during the heartbeat phase, can rejoin by participating in the leader election phase.
In  <ref>, we analyze the effectiveness of the 
leader election protocol.

Security
The leader election protocol uses the same two-key mechanism, i.e., the session key constructed by heartbeat and channel key, as the original heartbeat protocol to secure all messages. This makes it impossible for an adversary to synthesize or to decrypt a message that is accepted or sent by healthy devices. Otherwise, could break the IND-CTXT or IND-CPA security of the encryption scheme. Hence, the actual leader election process can only be hindered, yet not controlled by .




 §.§ Attestation of Software Integrity


To achieve a secure attestation of hardware and software the following extensions
to are required:

Enrollment Phase Extension
In the enrollment phase, the network operator selects an arbitrary software integrity measurement function  and stores its implementation in the TEE of each device 1, ..., n in the network. Traditionally, these mechanisms measure the integrity of a software by computing a hash value over its binary code <cit.>, though recent approaches are also able to measure the runtime behavior of a software, for the purpose of detecting sophisticated code-reuse attacks <cit.>. In the following, we abstract from these implementation details and use  as a black box that takes an input i, e.g., a description of what to measure, and generates a measurement m, which represents the current software state of a device (i: ).







Attestation Protocol Extension
Before invoking the attestation protocol, 𝒪 specifies a set of trustworthy software states tss. Tss consists of multiple (input, measurement)-pairs (tss = {(i_1, m_1), (i_2, m_2), ..., (i_x,m_x)}) and a description which network device should use which input (e.g., devices from type 1 should use i_1, etc.). A pair (i_k, m_k) in tss indicates that the expected measurement for the input i_k is m_k (). In this way, tss specifies all measurements that are permitted by 𝒪, e.g., because they represent the correct and most recent software states.

During the execution of the attestation protocol, tss is distributed to all devices in the network. For this purpose, 𝒪 initially incorporates tss into _ (_ ← _itsntss). In a similar way, by incorporating tss into _att (_att←_curtstss), devices forward tss to neighboring devices. Afterwards, each device i measures its local software configuration by extracting its appropriate (i_k, m_k) pair and executing the measurement function  with the input i_k in its TEE. Subsequently, i checks whether the output generated by  matches m_k and if this is the case continues with the execution of the attestation protocol, as explained in Section <ref>. If both values do not match, i invokes a recovery routine, which allows the device to restore to a trustworthy state by performing a secure code update protocol with 𝒪. Executing this extended attestation protocol, 𝒪 receives a msg_res that only contains ids of devices that are in a trustworthy software and uncompromised hardware state. Note that the protocol could easily be further extended to precisely report devices which are in an untrustworthy software but uncompromised hardware state, e.g., by introducing an additional _agg_s and _res_s that is specifically generated and aggregated by untrustworthy devices and transmitted to 𝒪.





Security
The security of the protocol extension results from the security of the main protocol ( <ref>), the secure hardware properties ( <ref>), and the adversary model ( <ref>). Since the protocol extension is executed in the TEE of devices, malware is unable to tamper with the protocol code, execution, or any stored protocol data (e.g., secret keys). Thus, an adversary, who compromises the software of a device, is only able to prevent protocol execution or manipulate the input/output to/from the protocol. However, preventing protocol execution has no influence, since untrustworthy devices stop executing the attestation protocol, anyway. Manipulating the input or output to or from the protocol has no affect, as all inputs and outputs are secured using authenticated encryption with secrets that are only accessible within the TEE. Additionally, all inputs and outputs are dependent on a session-specific timestamp ts issued by 𝒪. Therefore, replay attacks are likewise worthless. These measures also prevent Dolev-Yao network adversaries from compromising security. By contrast, a physical attacker is able to tamper with the protocol code, data, or execution. However, as explained in the security analysis of the main protocol ( <ref>), a physical attacker is unable to obtain the current heartbeat , which is required to participate in the attestation protocol or heartbeat protocol.




 §.§ Efficient Attestation Report Aggregation



Security As already shown in the security analysis of the
aggregation protocol ( <ref>), is unable
to exchange any message with healthy devices during attestation.
This argument also holds for the efficient aggregation scheme, as only
the aggregation inside the TEE is modified and not the protocol itself.
Consequently, the security of the efficient aggregation scheme, depends on the
hardness of attestation report itself.






An attestation report is accepted
if at least n / 2 valid attests are contained in the report. By assumption
 is only allowed to compromise up to c < n/2 - s devices and thus, can only
compute up to c valid attests. The remaining n/2 - c attests have to be
guessed by . The security of our aggregation scheme is formalized in
Theorem <ref>.



Assuming collision resistance of the hash function, any PPT ,
compromising up to c < n/2 - s devices can successfully forge
an efficient attestation report that is accepted by 𝒪 with
probability of at most 2^-s for any n>2· s.


Proof Sketch The attestation report consists of two bit vectors,
the first vector annotates the
devices included in the network and the second vector annotates the actual
attests (each attest is a single bit in the attest vector).
To successfully include one additional attest into the report,
 has to set an additional bits in the device vector and to guess
the correct bit in the attest vector. A single mismatch between the 
aggregate computed by 𝒪 and the reported aggregate
results in a reject of the attestation report.
As the position of an attest bit for a single device is computed by
((_its)), we
observe that  could break the collision resistance 
of the hash function, if  would achieve non-negligible advantage
in guessing an attest bit correctly without access to the device key. 
Assuming a uniform distribution of the attestation bit, 
 will guess its position correctly with probability 1/n_s.
However,  can follow a better strategy than randomly guessing all positions
of the n/2-c bits that are required for a valid attestation report.
We note that due to the relatively small set of bit positions, collisions
between multiple devices are likely. The best strategy the can follow
is thus, to guess collisions with the c bits that can set correctly 
in the attest vector.
A collision with any of the attest bits occurs with probability of at most
c/n_s (collisions within the attests of compromised devices are
also possible).
With this strategy,  can achieve a winning probability of
at most (c/n_s)^n/2-c. We observe that
c/n_s = n/2-s/n+s≤1/2
and by assumption n/2 - c ≥ s and thus, 
 wins the game with probability of less than 2^-s.


We remark that for the sake of technical simplicity of the proof,
the attestation vector is set to a fixed length n_s = n + s.
This is required to make it a hard task for  to guess the zero bits
in the attest vector for smaller n, when setting all bits in the device
vector. For lager n, n_s could be chosen smaller than n+s.
















































































































