How to Authenticate a Device? Formal Authentication Models for M2M Communications Defending against Ghost Compromising Attack

Abstract

In Machine-to-Machine (M2M) communications, authentication of a device is of upmost importance for applications of Internet of Things. As traditional authentication schemes always assume the presence of a person, most authentication technologies cannot be applied in machine-centric M2M context. In this paper, we make the first attempt to formally model the authentication in M2M. We first model four attacking adversaries that can formulate all possible attacks in M2M, which are channel eavesdropping attack, credential compromise attack, function compromise attack, and ghost compromise attack. Next, we propose four models to tackle those corresponding adversaries, namely, credential-based model, machine-metrics-based model, reference-based model, and witness-based model. We also illustrate several concrete attacking methods and authentication approaches. We proof the authentication security for all proposed models and compare them for clarity. Our models present soundness and completeness in terms of authentication security, which can guide the design and analysis of concrete authentication protocols. Particularly, we construct a uniform authentication framework for M2M context and point out all possible authentication mechanisms in M2M.

1. Introduction

Machine-to-Machine (M2M) communication is a typical communication fashion in the Internet of Things (IoT). It has been envisioned as one of the most promising Internet-accessing approaches in the IoT for long-distance remote devices. M2M networking interface enables wide area communications for mobile or static devices, so that it is quit convenient and easy to deploy remote devices rapidly. M2M thus becomes a typical communication method for most IoT applications such as remote environmental sensing, long-distance controlling, moving object locating, and tracing. Besides, M2M communication further incorporates various novel applications such as smart grid [1], tele-medicine [2], and smart vehicles [3].

As remote devices are always located faraway in unattended or malicious environments, it is very likely that the devices may be hacked by attackers. For example, the software system in devices may be injected or infected by certain malicious codes, which may modify or fabricate forthcoming outgoing data. Moreover, the devices may perform arbitrary (Byzantine) misbehavior after being compromised. Thus, the data sent by remote sensing devices must be authenticated. Otherwise, remote receivers in the other end will receive a lot of garbage information and consequently respond falsely.

We note that the authentication in M2M context is quite different from traditional authentication. Roughly speaking, traditional authentication usually assume the entity being authenticated is a person, or human is involved in authentication procedures. Simply speaking, the authentication methods usually rely on three aspects: “what you know, what you have, and who you are.” As the entity authentication in M2M is not a person, the traditional methods such as “what you know and who you are” may not be applied. For example, password-based authentication (by manually inputting password) cannot be applied in M2M context. The biometric-based authentication such as fingerprint recognition cannot be applied in M2M context neither.

Furthermore, traditional authentication methods for wireless sensor networks (WSNs) may not be able to smoothly migrate to M2M situations. That is, the authentication methods in WSNs usually rely on certain secrete credentials in cryptographic building blocks, for example, secrete keys for symmetric key encryptions, or private keys for digital signatures. Those secrete credentials are stored in devices or chips attached to devices (e.g., smart cards). However, such an authentication method still cannot defend against all aforementioned attacks. For example, when devices are compromised, those credentials will be revealed by attackers, by hacking the devices or injecting malicious codes. It again shows the distinction between M2M authentication and person-based authentication where entities (i.e., persons) usually are assumed uncompromising.

Therefore, the entity authentication in M2M context must be reconsidered and reinspected. We also need to explore the tailored authentication methods in M2M context, to guarantee a stronger authentication (that will be formally defined later), in case the devices are compromised and credentials are exposed. Besides, the formal models for authentication are appealing, as the formal models can guarantee the security strength and clarify the core part out from various application details. Unfortunately, such problem has not been explored thoroughly until now, to the best of our knowledge.

Currently, although several related works start to concentrate on M2M security problems [4–8], the strong authentication methods in M2M have not been thoroughly explored yet [9–13]. In this paper, we make the first attempt to figure out the abstract models for M2M context. We adapt a formal and rigorous method used in modern or theoretic cryptography, to strictly state, present, and analyze the security of authentication. More specifically, we firstly formulate attack models regarding to device compromising in M2M context by using interactive Turing machine. We next categorize the classifications in M2M authentication and their security specification. Finally, we propose several abstract authentication models to address different attacking patterns and proof their security. All our presentations strictly follow the formal expressions for better clarity and rigorous generality.

The contributions of the paper are listed as follows: (1) we strictly formulate the possible attacks and adversaries in M2M, which facilities to clearly locate the security fragile point. For example, we point out credential compromising attack, function compromising attack, and ghost compromising attack; (2) we formulate the general and abstract authentication models with provable security in M2M context, which figures out the fundamental characteristics of all possible authentication methods in M2M to guide the further design and security analysis in practices; (3) we point out several concrete attacking methods and propose corresponding authentication approaches to illustrate our models.

The rest of the paper is organized as follows. In Section 2, we discuss the basic assumption and models used throughout the paper. Section 3 provides the detailed description of our proposed models and analysis. Section 4 gives an overview on relevant prior work. Finally, Section 5 concludes the paper.

2. Problem Formulation

2.1. Network Model

In most M2M communications, there exists two major entities: devices, denoted as Dev, and a central server.

Dev is defined to equip following components.

• (1)

Functional module, denoted as Dev.FM. It consists of software and hardware for generating sensing data, computing meta information, sending reports, receiving instructions, and acting accordingly. It usually has three folders in terms of functionality: (i) a communication module, usually enabling wide area communications (e.g., GRPS/CDMA/TD-LTE) to report data to a central server; (ii) a computing program processing the data; (iii) a storage system storing relevant code and the data.

(2)

Credential module, denoted as Dev.CM. It consists of software and hardware for identification and credentials. One typical credential module is subscriber identification module (SIM) card, which stores unique identification and secretes credentials such as keys.

In this paper, we focus on above typical fashion in M2M communications—from devices to central servers. It is without loss of generality, because communications between devices and devices far away in M2M are usually relayed by a central server. As the devices are equipped with wide area communication capabilities, multihop M2M relay within remote devices rarely happen. The relay is usually unnecessary, as the devices can upload reports directly to central servers.

Even though multihop relay between devices happens, it is usually local area wireless communication such as wireless personal area network (WPAN), for example, Zigbee, or wireless local area network. That is, the reasonable architecture has two tiers: the communication between devices and gateways is WPAN, but the communication between gateways and a central server is M2M. In this case, the authentication of devices in the former tier has been explored in WSN communities and previous solutions can be migrated; the authentication of gateways in the latter tier is our focus. That is, in this scenario, we look on gateways as devices in our discussion.

In addition, no matter in which kind of authentication scenarios, we always assume the peer who authenticates (i.e., verifier) is trusted or secure. It is a baseline for the further meaningful discussion. We thus focus on the peer being authenticated (i.e., prover), which is a device in M2M scenarios. That is, how to authenticate a device in M2M.

2.2. Attack Model

It is required to consider the situation that devices may be compromised, as the devices may be always located in unattended environments. From the viewpoint of security strength, such assumption for the existence of stronger adversary will result in stronger security guarantee, which is mandatory for certain critical applications, such as gas emission monitoring and back-bone smart grid. According to the modeling of networks and devices, we classify the attack models into four folders as follows.

• (1)

Channel eavesdropping attack, denoted as Attack_ce. It is a straightforward attack that adversaries sniff communication channels and try to subvert authentication methods, for example, revealing credentials.

(2)

Credential Compromising Attack, denoted as Attack_cc. In this attack, the credential module is hacked, exposed, modified, cloned, or replaced by adversaries.

(3)

Function compromising attack, denoted as Attack_fc. In this attack, the functional module is hacked, exposed, modified, cloned, or replaced by adversaries.

(4)

Ghost compromising attack, denoted as Attack_gc. In this attack, the whole device can be hacked, exposed, modified, cloned, or replaced by adversaries. It can be looked as the combination of Attack_cc and Attack_fc.

Note that, the Attack_cc and Attack_fc may not be concurrent. For example, when tamper-proof hardware is applied for credential module, adversary's malicious code can only compromise function module, not credential module.

2.3. Security Definition

Roughly speaking, the secure authentication in this paper is defined as the interactive proof between two probabilistic polynomial interactive Turing machine (ITM) [14].

The ITM being authenticated is called Prover (denoted as 𝒫); the ITM authenticating Prover is called Verifier (denoted as 𝒱). The 𝒫 and 𝒱 both have one outgoing communication tape, one incoming communication tape, one input computing tape, one output computing tape, and one inner working tape. They also have other auxiliary tapes for interaction and security: one identity tape, one security parameter tape, one random tape, and one-bit activation tape. In this paper, the outgoing communication tape of 𝒫 is the same with the incoming communication tape of 𝒱. For simplicity, this tape is called interaction tape, denoted as ${𝒯}_i$ .

The adversary (denoted as A) is also modeled as an ITM. In different attack models, adversaries have different corresponding capabilities. We list them from weaker one to stronger one incrementally. The stronger one inherently has the capability of the weaker one.

• (1)

In Attack_ce, the adversary is denoted as A_ce, which can read and write the interaction tape.

(2)

In Attack_cc and not in Attack_fc, the adversary is denoted as A_cc, which can read and write the work tape. We assume it inherently has the capability of A_ce.

(3)

In Attack_fc and not in Attack_cc, the adversary is denoted as ${𝒜}_{\text{fc}}$ , which can also read and write input tape and output tape. We assume it inherently has the capability of A_ce.

(4)

In Attack_gc, the adversary is denoted as ${𝒜}_{\text{gc}}$ , which can also read and write all tapes.

As we have already stated, 𝒱 needs to be secure (or honest) in authentication semantics.

Environmental ITM (denoted as 𝒵) exists. 𝒵 can read and write input tapes of 𝒫 and 𝒱. The protocol result is the output of 𝒵.

The one interaction between 𝒫 and 𝒱 can be modeled as follows.

• (1)

𝒫 writes outgoing communication tape ${𝒯}_i$ ;

(2)

𝒱 reads incoming communication tape ${𝒯}_i$ .

The sequence can be interchangeable. The times of interaction may be more than once.

Next, we state the definition of authentication and its security as follows:

Definition 1 (Authentication).

From the transcripts on tape ${𝒯}_i$ by 𝒱, 𝒱 can believe the data is indeed from 𝒫 (and data is not modified). More specifically, from $\text{tag}$ in the transcripts $\{\text{id},\text{data},\text{tag}\}$ on tape ${𝒯}_i$ , 𝒱 can believe $\text{data}$ is indeed from the device 𝒫 with the $\text{id}$ without any change.

Definition 2.

Security of Authentication of Protocol Π in the presence of adversary 𝒜. From $\text{ta}{\text{g}}^{\prime }$ in $\{\text{id},{\text{data}}^{\prime },\text{ta}{\text{g}}^{\prime }\}$ in the protocol Π's transcripts that $\text{data}$ are tampered to ${\text{data}}^{\prime }$ by adversary 𝒜, the probability that the adversary can fool 𝒱 to believe $\text{dat}{\text{a}}^{\prime }$ is from the device 𝒫 with $\text{id}$ without any change is negligible.

Define attack experiment ${\text{AuthFool}}_{𝒜,\Pi }(n)$ as follows:

• (1)

run protocol Π in the presence of adversary 𝒜, where 𝒫 and 𝒱 are both ITM with security parameter n;

(2)

𝒱 witnesses 𝒜 tampered transcripts on tape ${𝒯}_i-\{\text{id},{\text{data}}^{\prime },\text{ta}{\text{g}}^{\prime }\}$ , 𝒱 output 1. That is, 𝒱 believes that ${\text{data}}^{\prime }$ come from the device 𝒫 with $\text{id}$ without any change. Otherwise, output 0;

(3)

if and only if 𝒱 output 1, the experiment output 1.

Definition 3.

Authentication protocol Π is secure, if for any ITM adversary 𝒜, it exists a negligible function $\text{negl}$ satisfying

$$\begin{array}{cc}& \text{Pr}\left[{\mathsf{A}\mathsf{u}\mathsf{t}\mathsf{h}\mathsf{F}\mathsf{o}\mathsf{o}\mathsf{l}}_{𝒜,\Pi }\left(n\right)=\mathrm{1}\right]\le \mathsf{n}\mathsf{e}\mathsf{g}\mathsf{l}\left(n\right).\end{array}$$

(1)

Indeed, authentication can be further divided into two types: entity authentication and message authentication. Entity authentication is the concentration in this paper. Message authentication is however usually required also in communication context and can be attained with entity authentication together. We thus later do not explicitly split those two.

Definition 4 (Entity Authentication (Message Source Authentication)).

From $\text{tag}$ in the transcripts $\{\text{id},\text{data},\text{tag}\}$ on tape ${𝒯}_i$ , 𝒱 can believe $\text{data}$ is from the device 𝒫 with $\text{id}$ .

Definition 5 (Message Authentication (Message Integrity Authentication)).

From $\text{tag}$ in the transcripts $\{\text{id},\text{data},\text{tag}\}$ on tape ${𝒯}_i$ , 𝒱 can believe $\text{data}$ is transferred without any change.

We can similarly define the attack experiment and corresponding security for entity authentication and message authentication.

3. Proposed Authentication Models

In this section, we propose a family of models to solve the authentication problem in M2M context.

We list all major notations used in the remainder of the paper in Table 1.

Table 1

Notation.

𝒫	Prover
𝒱	Verifier
$\text{cred}$	Credential
$\text{id}$	Device identity
$\text{data}$	Reporting data
negl $(n)$	Negligible function with parameter n

3.1. Defending Channel Eavesdropping Attack: Credential-Based Model (CBM)

To defend Attack_ce, the simplest authentication model is credential-based model, where the authentication relies on the knowledge or possession of certain credentials, for example, secrete keys. The credential-based model is described as follows:

$$\begin{array}{ll}& {\mathsf{M}\mathsf{S}\mathsf{G}}_{\text{cbm}}:𝒫\to 𝒱:\left\{\text{id},\text{data},\text{tag}=f\left(\text{cred}\parallel \text{id}\parallel \text{data}\right)\right\},\\ \phantom{{\text{MSG}}_{\text{cbm}}:𝒫}𝒱:\text{Verify}(\text{id},\text{data},\text{tag})\stackrel{?}{=}\mathrm{1},\end{array}$$

(2)

where the $\text{Verify}()$ is a tag verification function $\text{Verify}(\text{tag})$ ; MSG_cbm is a message from 𝒫 to 𝒱; $\text{cred}$ is a credential such as a secret key; $f()$ is a function with following properties.

(1) One-wayness. From $f(\text{cred}\parallel \text{id}\parallel \text{data})$ , it is computationally infeasible to compute $\text{cred}$ , even if $\text{id}$ , $\text{data}$ and $f()$ are public. By using a formal notation, that is

$$\begin{array}{ll}& \left|\text{Pr}\left\{\text{cred}\hspace{0.17em}|\hspace{0.17em}f\left(\text{cred}\parallel \text{id}\parallel \text{data}\right),\text{id},\text{data},f\left(\right)\right\}-\text{Pr}\left\{\text{cred}\right\}\right|\\ \hspace{1em}\hspace{1em}\le \mathsf{n}\mathsf{e}\mathsf{g}\mathsf{l}\left(n\right),\end{array}$$

(3)

where $\text{negl}(n)$ is a negligible function with parameter n. $\text{Pr}\{A\hspace{0.17em}|\hspace{0.17em}B\}$ means given B the probability of event A (i.e., guessing right A). That is, any polynomial probabilistic Turing machine (PPTM) with parameter n cannot guess $\text{cred}$ with noneligible probability, no matter whether $f(\text{cred}\parallel \text{id}\parallel \text{data}),\text{id},\text{data},f()$ are given or not.

(2) Second-Preimage Resistance. Without $\text{cred}$ , it is computationally infeasible to find another ${\text{id}}^{\prime }$ $({\text{id}}^{\prime }\ne \text{id})$ such that $f(\text{cred}\parallel \text{i}{\text{d}}^{\prime }\parallel \text{data})=f(\text{cred}\parallel \text{id}\parallel \text{data})$ , even if $\text{data}$ , $\text{id}$ and $f()$ are public. Similarly, without $\text{cred}$ , it is computationally infeasible to find another $\text{dat}{\text{a}}^{\prime }$ $(\text{dat}{\text{a}}^{\prime }\ne \text{data}$ satisfying $f(\text{cred}\parallel \text{id}\parallel \text{data})=f(\text{cred}\parallel \text{id}\parallel \text{dat}{\text{a}}^{\prime })$ , even if $\text{data}$ , $\text{id}$ and $f()$ are public. That is,

$$\begin{array}{ll}& \text{Pr}\{\text{i}{\text{d}}^{\prime }\ne \text{id},f\left(\text{cred}\parallel \text{i}{\text{d}}^{\prime }\parallel \text{data}\right)\\ \hspace{1em}\hspace{0.5em}=f\left(\text{cred}\parallel \text{id}\parallel \text{data}\right)\hspace{0.17em}|\hspace{0.17em}\text{data},\text{id},f\left(\right)\phantom{\text{i}{\text{d}}^{\prime }\ne \text{id},f\left(\text{cred}\parallel \text{i}{\text{d}}^{\prime }\parallel \text{data}\right)}\}\le \mathsf{n}\mathsf{e}\mathsf{g}\mathsf{l}\left(n\right),\\ \text{Pr}\{\text{dat}{\text{a}}^{\prime }\ne \text{data},f\left(c\text{red}\parallel \text{id}\parallel \text{dat}{\text{a}}^{\prime }\right)\\ \hspace{1em}\hspace{0.5em}=f\left(\text{cred}\parallel \text{id}\parallel \text{data}\right)\hspace{0.17em}|\hspace{0.17em}\text{data},\text{id},f\left(\right)\phantom{\text{dat}{\text{a}}^{\prime }}\}\le \mathsf{n}\mathsf{e}\mathsf{g}\mathsf{l}\left(n\right).\end{array}$$

(4)

Certainly, $f(\text{cred}\parallel \text{id}\parallel \text{data})$ can be easily computed if $\text{cred},\text{id},\hspace{0.17em}\hspace{0.17em}\text{and}\hspace{0.17em}\hspace{0.17em}\text{data}$ are available, especially for resource constraint devices in M2M context. $f()$ can be instantiated with cryptographic primitives such as one-way function with second-preimage resistance, pseudorandom function, and trapdoor permutation.

Credential-based model can be further divided into two folders: one credential-based model and multicredential-based model. As it is named, multicredential-based model use multiple credentials in each MSG_cbm message or distinct credential in multiple MSG_cbm messages.

For only guaranteeing the entity authentication, MSG_cbm can be changed to ${\text{MSG}}_{\text{cbm}}^{\prime }:𝒫\to 𝒱:\{\text{id},\text{data},\text{tag}=f(\text{cred}\parallel \text{id})\}$ ; Similarly, for only guaranteeing the message authentication, MSG_cbm can be changed to ${\text{MSG}}_{\text{cbm}}^{\mathrm{\prime \prime }}:𝒫\to 𝒱:\{\text{id},\text{data},\text{tag}=f(\text{cred}\parallel \text{data})\}$ .

Analysis

Definition 6 (Soundness).

The designed protocol can guarantee the required security. That is, the designed protocol is the sufficient condition of the required security.

Definition 7 (Completeness).

The required security needs the designed protocol to guarantee. That is, the designed protocol is the necessary condition of the required security.

Proposition 8.

Credential-based model ${\Pi }_{cbm}$ is secure in ${\text{Attack}}_{ce}$ . That is,

$$\begin{array}{cc}& \text{Pr}[{\mathsf{A}\mathsf{u}\mathsf{t}\mathsf{h}\mathsf{F}\mathsf{o}\mathsf{o}\mathsf{l}}_{{𝒜}_{ce},{\Pi }_{cbm}}\left(n\right)=\mathrm{1}]\le \mathsf{n}\mathsf{e}\mathsf{g}\mathsf{l}\left(n\right).\end{array}$$

(5)

Proof.

It can be proofed by similar methods in Universally Composable security [14]; hereby only sketch is given. The security of the proposed model is guaranteed by the security of $f()$ . The rationale is from the Turing Test. There exist a reality model and an ideal model. From the viewpoint of environmental machine, if the reality model and ideal model are indistinguishable, the reality model will reach the security of the ideal model. In reality model, there exist adversary, prover, and verifier running protocol; In ideal model, there exist ideal function that emulates the protocol, dummy prover and dummy verifier, and simulated adversary that emulates all possible interactions and attacks. Ideal function is always secure (it is regarded as an imaged trusted third party). If the ideal model and reality model are indistinguishable from the viewpoint of environmental machine, the security of protocol will be guaranteed.

In other words, if environmental machine can distinguish the reality model and the ideal model, a new adversary can be created to subvert a certain security assumption by revoking the environmental machine as a subfunction. In the ideal function, $f()$ is perfectly secure. In the reality model, $f()$ is assumed to satisfy certain security requirements (e.g., one-wayness and preimage resistance). If the ideal model is indistinguishable with reality model by environmental machine, the adversary will subvert the assumption by consulting the environmental machine. Finally, the proposition proofs the soundness of credential-based model.

Proposition 9.

Credential-based model has completeness for defending Channel Eavesdropping Attack.

Proof.

The proof has two folders: the credential is required; the credential is presented properly. On the one hand, as devices need to distinguish themselves with others, they need to show their secretly possessed knowledge—credential—to proof their identity. Thus, there must exist a credential in the tuples in MSG_cbm on the transcripts $T_i$ . On the other hand, the credential must be secretly and properly presented, as the interaction tape $T_i$ can be tampered by eavesdropping adversary ${𝒜}_{\text{ce}}$ . Thus, the presence of credential relies on $f()$ that has one-wayness and second-preimage resistance.

Besides, multicredential-based model is securer than one credential-based model. That is, the exposure of one credential by eavesdropping adversary ${𝒜}_{\text{ce}}$ will only result in subverting the authentication security guaranteed by that credential. If 𝒫 has multiple credentials, the exposure of credentials will become more difficult. It is natural to extend the security discussion to following statement.

Definition 10 (Forward Authentication Security).

That is, if current credential is exposed by eavesdropping adversary ${𝒜}_{\text{ce}}$ , the authentication security before exposure is still guaranteed.

Proposition 11.

In ${\text{Attack}}_{ce}$ , multiple credentials that derive from one-way function can guarantee forward authentication security.

Proof.

By using one-way function f, $\text{cre}{\text{d}}_i=f(\text{cre}{\text{d}}_{i-\mathrm{1}})$ ,   $(\mathrm{1}\le i\le n)$ , where $\text{cre}{\text{d}}_{\mathrm{0}}=\text{cred}$ . The sequence of using $\text{cred}$ is from $\text{cre}{\text{d}}_n$ to $\text{cre}{\text{d}}_{\mathrm{0}}$ . Due to the one-wayness of $f()$ , it can guarantee the confidentiality of previous credentials, even if current used credential is revealed by ${𝒜}_{\text{ce}}$ .

Proposition 12.

Credential-based model ${\Pi }_{cbm}$ is not secure in ${\text{Attack}}_{ce}$ . That is,

$$\begin{array}{cc}& \text{Pr}\left[{\mathsf{A}\mathsf{u}\mathsf{t}\mathsf{h}\mathsf{F}\mathsf{o}\mathsf{o}\mathsf{l}}_{{𝒜}_{cc},{\Pi }_{cbm}}\left(n\right)=\mathrm{1}\right]>\mathsf{n}\mathsf{e}\mathsf{g}\mathsf{l}\left(n\right).\end{array}$$

(6)

Proof (Straightforward).

The authentication security of credential-based model relies on the secrecy of credentials. The presence of ${𝒜}_{\text{cc}}$ will reveal all credentials. Thus, the authentication security is broken.

3.2. Defending Credential Compromising Attack: Machine-Metrics Based Model (MBM)

If the attack model is strengthened to Attack_cc, the credential-based model will not be able to guarantee the security of authentication, as it is proofed in previous proposition.

For simple illustration of Attack_cc, we first point out an attack method called relocation attack.

Definition 13 (Credential Relocation Attack).

It is an attack that the credentials are relocated to anther device. Although the received $\{\text{id}\parallel \text{data}\parallel \text{tag}\}$ is verified valid at 𝒱, the data do not come from the device with claimed $\text{id}$ ; indeed, the data come from another device with different $\text{id}$ .

To tackle the Attack_cc, we propose a machine-metric based model (MBM). In this MBM model, the physical characteristics of devices are collected as the identification of devices. Suppose the physical characteristic space is S, which consists of n characteristics. That is, $S=\{\text{cha}{\text{r}}_{\mathrm{1}},\text{cha}{\text{r}}_{\mathrm{2}},\dots ,\text{cha}{\text{r}}_n\}$ . Software program $\text{prg}{\text{m}}_i()$ returns $\text{cha}{\text{r}}_i\in S,(i=\mathrm{1},\dots ,n)$ . The machine-metrics based model is described as follows:

$$\begin{array}{ll}& {\mathsf{M}\mathsf{S}\mathsf{G}}_{\text{mbm}}:𝒫\to 𝒱:\left\{\text{id},\text{data},i,\text{tag}=f\left(\text{prg}{\text{m}}_i\left(\right)\parallel \text{id}\parallel \text{data}\right)\right\},\\ \phantom{{\&\text{MSG}}_{\text{mbm}}:𝒫}𝒱:\text{Verify}\left(\text{id},\text{data},\text{tag}\right)\stackrel{?}{=}\mathrm{1},\end{array}$$

(7)

where $\text{Verify}()$ is a tag verification function (we assume 𝒱 securely possesses a table $\text{Tbl}=〈i,\text{cha}{\text{r}}_i〉$ , $(i=\mathrm{1},\dots ,n)$ , and fetches $\text{cha}{\text{r}}_i$ according to index i to verify received tag); MSG_mbm is a message from device 𝒫 to 𝒱; $\text{prg}{\text{m}}_i()$ is securely computed at functional module in 𝒫 and it returns a characteristic $\text{cha}{\text{r}}_i$ as a credential of 𝒫; $f()$ is a function with one-wayness and second-preimage resistance; note that $f()$ can be securely computed by functional module.

If we look $\text{cha}{\text{r}}_i$ as a credential in CBM model, we will have similar discussion as follows. $\text{prg}{\text{m}}_i()$ and $f(\text{prg}{\text{m}}_i()\parallel \text{id}\parallel \text{data})$ ,   $(i=\mathrm{1},\dots ,n)$ can be easily computed, especially for resource constraint devices in M2M context. $f()$ can be instantiated with cryptographic primitives such as one-way function with second-preimage resistance, pseudorandom function, and trapdoor permutation.

Machine-metrics based model can be further divided into two folders: one Machine-Metrics based model and multiple Machine-Metrics based model. As it is named, multiple Machine-Metrics based model use multiple $\text{prg}{\text{m}}_i()$ in each MSG_mbm message or distinct $\text{prg}{\text{m}}_i()$ in multiple MSG_mbm messages.

For only guaranteeing the entity authentication, MSG_mbm can be changed to ${\text{MSG}}_{\text{mbm}}^{\prime }:𝒫\to 𝒱:\{\text{id},\text{data},i,\text{tag}=f(\text{prg}{\text{m}}_i()\parallel \text{id})\}$ ; Similarly, for only guaranteeing the message authentication, MSG_mbm can be changed to ${\text{MSG}}_{\text{mbm}}^{\mathrm{\prime \prime }}:𝒫\to 𝒱:\{\text{id},\text{data},i,\text{tag}=f(\text{prg}{\text{m}}_i()\parallel \text{data})\}$ .

Analysis

Proposition 14.

Machine-Metrics based model ${\Pi }_{mbm}$ is secure in ${\text{Attack}}_{cc}$ . That is, $\text{Pr}[{\text{AuthFool}}_{{𝒜}_{cc},{\Pi }_{mbm}}(n)=\mathrm{1}]\le \text{negl}(n)$ .

Proof.

As the function module is secure, adversary cannot compute $\text{prg}{\text{m}}_i()$ , ( $i=\mathrm{1},\dots ,n$ ). It can be looked as a computed credential to guarantee the authentication security. The proof thus is reduced to the proof of the Proposition 8. It proofs the soundness of Machine-Metrics based model.

Proposition 15.

Machine-Metrics based Model has completeness for defending Credential Compromising Attack.

Proof.

The proof can be reduced to the proof of Proposition 9. Concretely, the proof has two folders: a new credential is required; the new credential is presented properly. On the one hand, as devices need to distinguish themselves with others, they need to show their secretly possessed knowledge—credential—to proof their identity. As the credential module can be compromised, the credential must come from the functional module. Thus, there must exist a credential in the tuples in MSG_mbm on the transcripts $T_i$ . On the other hand, the credential must be secretly and properly presented, as the interaction tape $T_i$ can be tampered by eavesdropping adversary ${𝒜}_{\text{ce}}$ . Thus, the presentation of credential relies on f that has one-wayness and second-preimage resistance. Besides, if the credential is online computed (not stored) by functional module, the security will be enhanced, which is similar to the case of multiple credentials.

Similarly, multiple Machine-Metrics based model is securer than one Machine-Metrics based model. The discussion is similar to the one in the previous section. In summary, Machine-Metrics based model can be looked as an analog of biometric-based authentication for human.

Proposition 16.

Machine-Metrics based model ${\Pi }_{mbm}$ is not secure in ${\text{Attack}}_{fc}$ . That is,

$$\begin{array}{cc}& \text{Pr}\left[{\mathsf{A}\mathsf{u}\mathsf{t}\mathsf{h}\mathsf{F}\mathsf{o}\mathsf{o}\mathsf{l}}_{{𝒜}_{fc},{\Pi }_{mbm}}\left(n\right)=\mathrm{1}\right]>\mathsf{n}\mathsf{e}\mathsf{g}\mathsf{l}\left(n\right).\end{array}$$

(8)

Proof (Straightforward).

The authentication security of Machine-Metrics based model relies on the secure computation of $\text{prg}{\text{m}}_i()$ , $(i=\mathrm{1},\dots ,n)$ . The presence of ${𝒜}_{\text{fc}}$ will reveal all $\text{prg}{\text{m}}_i()$ , $(i=\mathrm{1},\dots ,n)$ . Thus, the authentication security is broken.

We give three special illustrations on Machine-Metrics based model for defending Attack_cc (e.g., Credential Relocation Attack).

Definition 17 (Computation-Based Authentication).

Each time 𝒱 sends a one-time random computational puzzle, 𝒫 counts the computation duration time in microsecond or Central Process Unit (CPU) cycles as the result of $\text{prg}{\text{m}}_i()$ .

Example 18.

𝒱 sends a computational puzzle $g^n\hspace{0.17em}\hspace{0.17em}\mathrm{mod}\hspace{0.17em}\hspace{0.17em}p$ , where p is a prime number; $2<g<p$ is an integer; $n<p$ is a positive integer. 𝒫 counts the computation duration time in microsecond as the computation characteristic, in other words, the returning result of $\text{prg}{\text{m}}_i()$ .

Definition 19 (Location-Based Authentication).

𝒱 sends an one-time random location puzzle. 𝒫 returns computed location values. 𝒱 verifies the location characteristic of 𝒫. That is, $\text{prg}{\text{m}}_i()$ returns location values of 𝒫.

Example 20.

𝒱 sends an one-time random location puzzle: the distance from 𝒫 to a randomly chosen point. 𝒫 computes the distance value according to its location values such as global positions and latitudes, as the location characteristic, in other words, the returning result of $\text{prg}{\text{m}}_i()$ .

Similarly, we can further define authentication methods by requesting other physical characteristics such as memory size, hardware fingerprints. Note that such kind of requesting must be fresh and generated at real time.

3.3. Defending Function Compromising Attack: Reference-Based Model (RBM)

If the attack model is strengthened to Attack_fc, the Machine-Metrics based model will not be able to guarantee the security of authentication, which is proofed in previous proposition.

To illustrate Attack_fc, we first point out two concrete attack methods called Characteristic Replication Attack and Data Pollution Attack.

Definition 21 (Characteristic Replication Attack).

The set $S=\{\text{cha}{\text{r}}_i,\dots ,\text{cha}{\text{r}}_n\}$ is replicated to another device by attackers, and they will choose corresponding $\text{cha}{\text{r}}_i$ by elements upon revoking of $\text{prg}{\text{m}}_i()$ .

Definition 22 (Data Pollution Attack).

Data is polluted by attackers, although the credential is valid to make the data being authenticated. That is, $𝒫\to 𝒱:\{\text{id},\text{dat}{\text{a}}^{\prime },\text{tag}=f(\text{cred}\parallel \text{id},\parallel \text{dat}{\text{a}}^{\prime })\}$ , where $\text{data}$ is changed to ${\text{data}}^{\prime }$ by adversary Attack_fc after functional module is compromised.

To tackle the Attack_fc, we propose a reference-based model (RBM). In RBM model, the reference behavior of 𝒫 (e.g., from previous data or other devices) will be checked for the trustworthiness of $\text{data}$ .

The reference-based model is described as follows:

$$\begin{array}{ll}& {\mathsf{M}\mathsf{S}\mathsf{G}}_{\text{rbm}}:𝒫\to 𝒱:\left\{\text{id},\text{data},\text{tag}=f\left(\text{cred}\parallel \text{id}\parallel \text{data}\right)\right\},\\ \phantom{{\text{MSG}}_{rbm}:𝒫}𝒱:\text{Verify}\left(\right)\stackrel{?}{=}\mathrm{1},\end{array}$$

(9)

where the $\text{Verify}()$ includes a tag verification function $\text{Verify}(\text{tag})$ and especially, an extra verification function for data, called $\text{Verify}(\text{data})$ .

We give two special illustration on reference-based model in the following.

Definition 23 (History-Based Authentication).

The authenticator 𝒱 verifies the history behaviors (e.g., data) to authenticate the trustworthiness of current behavior of 𝒫, for example, the trustworthiness of $\text{data}$ . Concretely, the data filter method can be applied at 𝒱, where data come from the history.

Example 24.

Suppose the history set is S, which consists of n values. That is, $S=\{v_{\mathrm{1}},v_{\mathrm{2}},\dots ,v_n\}$ . Suppose the history set is trustworthy, the detection of abnormal $\text{data}$ can be done by the following verification function:

$$\begin{array}{cc}& \text{Verify}\left(\text{data}\right)=\text{iff}\left(\frac{{\left(\text{data}-\stackrel{-}{v}\right)}^{\mathrm{2}}}{{\sum }_{i=\mathrm{1}}^{n-\mathrm{1}}{\left(v_i-\stackrel{-}{v}\right)}^{\mathrm{2}}}<\text{th},\mathrm{1,0}\right),\end{array}$$

(10)

where $\text{th}$ is an alert threshold.

Definition 25 (Neighbor-Based Authentication).

The authenticator 𝒱 verifies the other 𝒫's behaviors (e.g., neighbors' reporting data) to authenticate the trustworthiness of current behavior of 𝒫, for example, the trustworthiness of $\text{data}$ . Concretely, the data filter method can be applied at 𝒱, where the data come from neighbors.

Example 26.

Similar to above example, suppose the neighbor set is S, which consists of n values. That is, $S=\{v_{\mathrm{1}},v_{\mathrm{2}},\dots ,v_n\}$ . Suppose the neighbor set is trustworthy, the detection of abnormal $\text{data}$ can be done by the following verification function:

$$\begin{array}{cc}& \text{Verify}\left(\text{data}\right)=\text{iff}\left(\frac{{\left(\text{data}-\stackrel{-}{v}\right)}^{\mathrm{2}}}{{\sum }_{i=\mathrm{1}}^{n-\mathrm{1}}{\left(v_i-\stackrel{-}{v}\right)}^{\mathrm{2}}}<\text{th},\mathrm{1,0}\right),\end{array}$$

(11)

where $\text{th}$ is an alert threshold.

In the neighbor-based authentication, the reference set S may not be always trustworthy. That is, the values in S may come from other 𝒫s that are untrustworthy. To deal with this issue, we propose extra two methods in the following.

Definition 27 (Trustworthy Stunt Authentication).

The S is from other trustworthy 𝒫s that are predeployed. That is, the authenticator 𝒱 verifies the trusted stunt's report (e.g., data) to authenticate the trustworthiness of current behavior of 𝒫, for example, the trustworthiness of $\text{data}$ . The verification function in this situation is similar to history-based Authentication.

Definition 28 (Threshold Stunt Authentication).

Suppose there exists at least α nodes in S that are trustworthy (i.e., not compromised) in neighbor-based authentication. Simply speaking, the verification function can be designed as follows: select the median $S-\alpha$ values in S and then use verification function similarly.

Analysis  

Proposition 29.

Reference-based model ${\Pi }_{rbm}$ is secure in ${\text{Attack}}_{fc}$ . That is,

$$\begin{array}{cc}& \text{Pr}\left[{\mathsf{A}\mathsf{u}\mathsf{t}\mathsf{h}\mathsf{F}\mathsf{o}\mathsf{o}\mathsf{l}}_{{𝒜}_{fc},{\Pi }_{rbm}}\left(n\right)=\mathrm{1}\right]\le \mathsf{n}\mathsf{e}\mathsf{g}\mathsf{l}\left(n\right).\end{array}$$

(12)

Proof.

The message source authentication is guaranteed by Proposition 8. The message integrity authentication is roughly guaranteed by history-based authentication and neighbor-based authentication in reference-based model. It proofs the soundness of reference-based model.

Proposition 30.

Reference-based Model has completeness for defending Function Compromising Attack.

Proof.

As functional module can be compromised by ${𝒜}_{\text{gc}}$ , computational credential (namely, $\text{prg}{\text{m}}_i()$ or $\text{cha}{\text{r}}_i$ ) may be revealed, which is so-called characteristic replication attack. Besides, even though credentials in credential module can grantee that data cannot be modified by adversaries in the channel, the data can still be modified at the devices after the functional module is compromised, which is so-called data pollution attack. Thus, credentials in credential module defend against the former one; history-based authentication and neighbor-based authentication defend against the latter one.

Proposition 31.

Reference-based model ${\Pi }_{rbm}$ is not secure in ${\text{Attack}}_{gc}$ . That is,

$$\begin{array}{cc}& \text{Pr}\left[{\mathsf{A}\mathsf{u}\mathsf{t}\mathsf{h}\mathsf{F}\mathsf{o}\mathsf{o}\mathsf{l}}_{{𝒜}_{gc},{\Pi }_{rbm}}\left(n\right)=\mathrm{1}\right]>\mathsf{n}\mathsf{e}\mathsf{g}\mathsf{l}\left(n\right).\end{array}$$

(13)

Proof (Straightforward).

As the credential module can be compromised in ${𝒜}_{\text{gc}}$ , the authentication security is broken.

3.4. Defending Ghost Compromising Attack: Witness-Based Model (WBM)

If the adversary has the most powerful strength, namely, the Attack_gc. We point out it cannot be defended against by any authentication enhancement method only from 𝒫.

Proposition 32.

  ${\text{Attack}}_{gc}$ cannot be defended only by 𝒫 itself.

Proof (Straightforward).

As the credential module and functional module can both be compromised, any security enhancement will be also compromised. Thus, Attack_gc cannot be defended only by 𝒫 itself merely.

To tackle the Attack_gc, we propose a witness-based model (WBM). In WBM model, environmental characteristics and device characteristics are both collected for the final authentication decision.

Suppose environmental characteristics consist of n components. That is, $S_e=\{\text{env}{\text{r}}_{\mathrm{1}},\text{env}{\text{r}}_{\mathrm{2}},\dots ,\text{env}{\text{r}}_n\}$ . There exists at least one program $\text{wtn}{\text{s}}_i()$ that can return $\text{env}{\text{r}}_i\in S_e,(i=\mathrm{1},\dots ,n)$ . In addition, suppose the device characteristics space is $S_d$ , which consists of n characteristics. That is, $S_d=\{\text{cha}{\text{r}}_{\mathrm{1}},\text{cha}{\text{r}}_{\mathrm{2}},\dots ,\text{cha}{\text{r}}_n\}$ . There exists at least one program $\text{prg}{\text{m}}_i()$ that can return $\text{cha}{\text{r}}_i\in S_d,(i=\mathrm{1},\dots ,n)$ . The witness-based model is described as follows:

$$\begin{array}{ll}& {\mathsf{M}\mathsf{S}\mathsf{G}}_{\text{wbm}}:𝒫\to 𝒱:\{\text{id},\text{data},\text{tag}\\ \phantom{{\hspace{1em}\text{MSG}}_{\text{wbm}}:𝒫\to 𝒱:}=f\left(\text{cred}\hspace{0.17em}|\hspace{0.17em}\hspace{0.17em}|\hspace{0.17em}\text{prg}{\text{m}}_i\left(\right)\parallel \text{id}\parallel \text{data}\right)\},\\ \phantom{{\text{MSG}}_{wbm}:𝒫}𝒱:\text{Verify}\left(\text{id},\text{data},\text{tag}\right)\stackrel{?}{=}\mathrm{1},\end{array}$$

(14)

where the $\text{Verify}()$ includes a tag verification function $\text{Verify}(\text{tag})$ , a data verification function $\text{Verify}(\text{data})$ , and an environment verification function $\text{Verify}(\text{envr})$ .

We give an illustration for the witness-based authentication in the following.

Definition 33 (Contamination-Based Authentication).

The authentication is provided by witness from other trustworthy peers in different channels.

Example 34.

The authenticator 𝒱 verifies whether 𝒫 is touched or moved via the observation of protection lock or surveillance video camera. For example, $\text{wtn}{\text{s}}_{\mathrm{1}}()$ returns lock status (suppose locked status is 1); $\text{wtn}{\text{s}}_{\mathrm{2}}()$ returns whether camera picture is in static status (suppose static status is 1 means the monitored device is untouched). The $\text{Verify}(\text{envr})=\text{wtn}{\text{s}}_{\mathrm{1}}()\hspace{0.17em}.\text{AND}.\hspace{0.17em}\hspace{0.17em}\text{wtn}{\text{s}}_{\mathrm{2}}()$ .

Analysis

Proposition 35.

Witness-based model ${\Pi }_{wbm}$ is secure in ${\text{Attack}}_{gc}$ . That is,

$$\begin{array}{cc}& \text{Pr}[{\mathsf{A}\mathsf{u}\mathsf{t}\mathsf{h}\mathsf{F}\mathsf{o}\mathsf{o}\mathsf{l}}_{{𝒜}_{gc},{\Pi }_{wbm}}\left(n\right)=\mathrm{1}]\le \mathsf{n}\mathsf{e}\mathsf{g}\mathsf{l}\left(n\right).\end{array}$$

(15)

Proof (Sketch).

As the proof of authentication relies on the witness from others who are not compromised, the authentication security can be guaranteed. It proofs the soundness of witness-based model.

Proposition 36.

Witness-based Model has completeness for defending Ghost Compromising Attack.

Proof (Sketch).

As the 𝒫 can be totally compromised, the security enhancement for authentication must come from other trustworthy entities.

Comparison. The security comparison of proposed models is compared and summarized in Tables 2 and 3.

Table 2

Comparison of attack models and authentication models.

Authentication model	Attack model
(Authentication illustration)	(Attack illustration)
Credential-based model	Channel eavesdropping attack
Machine-metrics-based model	Credential compromising attack
(Computation-based authentication)	(Credential relocation attack)
(Location-based authentication)
Reference-based model	Function compromising attack
(History-based authentication)	(Characteristic replication attack)
(Neighbor-based authentication)	(Data pollution attack)
(Trustworthy stunt authentication)
(Threshold stunt authentication)
Witness-based model	Ghost compromising attack
(Contamination-based authentication)

Table 3

Security comparison of models.

Authentication model	Authentication security
CBM	$\text{Pr}[$ AuthFool ${}_{{𝒜}_{\text{ce}},{\hspace{0.17em}\mathrm{\Pi }}_{\text{cbm}}}(n)=\mathrm{1}]\le$   negl $(n)$
	$\text{Pr}[$ AuthFool ${}_{{𝒜}_{\text{cc}},{\hspace{0.17em}\mathrm{\Pi }}_{\text{cbm}}}(n)=\mathrm{1}]>$   negl $(n)$
MBM	$\text{Pr}[$ AuthFool ${}_{{𝒜}_{\text{cc}},{\hspace{0.17em}\mathrm{\Pi }}_{\text{mbm}}}(n)=\mathrm{1}]\le$   negl $(n)$
	$\text{Pr}[$ AuthFool ${}_{{𝒜}_{\text{fc}},{\hspace{0.17em}\mathrm{\Pi }}_{\text{mbm}}}(n)=\mathrm{1}]>$   negl $(n)$
RBM	$\text{Pr}[$ AuthFool ${}_{{𝒜}_{\text{fc}},{\hspace{0.17em}\mathrm{\Pi }}_{\text{rbm}}}(n)=\mathrm{1}]\le$   negl $(n)$
	$\text{Pr}[$ AuthFool ${}_{{𝒜}_{\text{gc}},{\hspace{0.17em}\mathrm{\Pi }}_{\text{rbm}}}(n)=\mathrm{1}]>$   negl $(n)$
WBM	$\text{Pr}[$ AuthFool ${}_{{𝒜}_{\text{gc}},{\hspace{0.17em}\mathrm{\Pi }}_{\text{wbm}}}(n)=\mathrm{1}]\le$   negl $(n)$

4. Related Work

Security of M2M communications starts to attract more and more attentions [4, 5, 7, 8], but solutions for authentication in M2M context have not been thoroughly explored. Especially, the formal authentication models for M2M have been rarely discussed. In this paper, we made the first attempt in this regard. Zhang et al. [12] provided a practical group-based authentication for Machine Type Communication (MTC) scenario. Each device shares a secret key with home environment, and a group secret key with other devices in the same group. Their discussion focused on roaming cellular networks and human may be involved. He [10] proposed to use machine's fingerprint and encryption technique to conduct remote register authentication of software to prevent unauthorized use. It focused on software copyright safeguard. Lu et al. [5] first pointed out the reliability and security requirements in M2M communications. Many other works addressed security problems in smart grid scenarios, which may be related to M2M communications. For example, Fadlullah et al. [15] studied the detection of malicious activities in smart grid communication and proposed an early warning system. Bartoli et al. [16] studied secure aggregation in smart grid M2M networks. They included the security design in the physical layer and MAC layer. Saied et al. [8] proposed a key establishment solution for heterogeneous M2M communications. Other works explored the security in a broader domain—IoT, which is relevant to M2M. For example, Alam et al. [17] studied the interoperability in security attributes between different administrative domains in IoT. They proposed a layered architecture of IoT framework. As the M2M is still undergoing development, several works studied M2M standards [6, 18–20]. For example, Bartoli et al. [6] reviewed the current undergoing standards for M2M communications.

5. Conclusions

In this paper, we made the first attempt to propose a family of formal models to authenticate devices in M2M context. We first modeled four attacking adversaries that can include all possible attacks in M2M. Next, we proposed four models to tackle corresponding adversaries. We also illustrated several concrete attacking methods and authentication approaches. We proofed the authentication security for all proposed models and compared them for clarity. Our models presented soundness and completeness with respect to necessary and sufficient conditions for authentication security, which can guide the design and analysis of concrete authentication protocols. Especially, we constructed a uniform authentication framework for possible various authentication approaches. Our model also pointed out all possible authentication mechanisms or sufficient solutions for authentications in M2M.