# Hierarchical Group Based Mutual Authentication and Key Agreement for Machine Type Communication in LTE and Future 5G Networks

Authors: Probidita Roychoudhury; Basav Roychoudhury; Dilip Kumar Saikia
Journal: Security and Communication Networks
 (2017)

---

## Abstract

In view of the exponential growth in the volume of wireless data communication among heterogeneous devices ranging from smart phones to tiny sensors across a wide range of applications, 3GPP LTE-A has standardized Machine Type Communication (MTC) which allows communication between entities without any human intervention. The future 5G cellular networks also envisage massive deployment of MTC Devices (MTCDs) which will increase the total number of connected devices hundredfold. This poses a huge challenge to the traditional cellular system processes, especially the traditional Mutual Authentication and Key Agreement (AKA) mechanism currently used in LTE systems, as the signaling load caused by the increasingly large number of devices may have an adverse effect on the regular Human to Human (H2H) traffic. A solution in the literature has been the use of group based architecture which, while addressing the authentication traffic, has their share of issues. This paper introduces Hierarchical Group based Mutual Authentication and Key Agreement (HGMAKA) protocol to address those issues and also enables the small cell heterogeneous architecture in line with 5G networks to support MTC services. The aggregate Message Authentication Code based approach has been shown to be lightweight and significantly efficient in terms of resource usage compared to the existing protocols, while being robust to authentication message failures, and scalable to heterogeneous network architectures.


---

## Body

## 1. Introduction

The market for cellular data is growing at a tremendous pace with the birth of a new generation of cellular system at almost every decade. This has been largely triggered by the explosive growth in mobile traffic coupled with advancements in wireless communication technologies. As per the Cisco Visual Networking Index 2014–19 [1], machine to machine (M2M) also termed as Machine Type Communication (MTC) connections are expected to grow to 10.5 billion by 2019. M2M or MTC communication refers to communication between entities without any human intervention, intended to support applications like home automation, security and surveillance, healthcare, traffic management, and many others. The communicating entities are termed Machine Type Communication Devices (MTCDs). Standardization organizations, like Third Generation Partnership Project (3GPP), European Telecommunications Standards Organization (ETSI), and so forth, have already come up with standards on MTC architecture and security architecture under 3GPP Long Term Evolution Advanced (LTE-A) [2]. Under the 7th Framework Programme for Research (7FP) [3], the European Union has initiated several programs to promote research in technologies to build wired and wireless communication networks of the future. A key project, Mobile and wireless communication Enablers for Twenty-twenty Information Society (METIS) [4], the flagship program of the European Union on Fifth Generation Cellular Network (5G), has attempted to prepare the groundwork for 5G network before any standardization activities are carried out. The scenarios and use cases analyzed by METIS [5] indicate a massive deployment of MTCDs in future cellular networks. The existing cellular network is ill-equipped to handle the surge in traffic from such massive MTC deployment. The traffic generated from the authentication procedure, executed for security reasons by each MTCD before they can attach to the network, becomes a serious concern in such scenarios. A sizable number of MTCDs trying to attach to the network simultaneously with each having to undergo the Mutual Authentication and Key Agreement (AKA) procedure result in massive signaling overload at both access network and core network.The existing literature on MTC authentication has tried to find different approaches to reduce the signaling traffic needed for the AKA procedure by grouping the MTCDs based on different criteria like belonging to the same application, appearing in the same location, and so forth. The schemes exploiting the group based approach use one of the following methods for reducing the AKA signaling load:(1)
First MTCD performs a full AKA with the core network and also authenticates the group by fetching the authentication data for the entire group to the serving network; the rest of the group members authenticates locally at the serving network using the prefetched authentication data.(2)
Each MTCD sends its authentication message to a MTCD selected from among the group to be a group leader who in turn aggregates the same and transmits it to the core network.The main drawback of the first approach is that while it reduces the signaling load between the home network and the serving network, the load at the access network remains unchanged. The latter approach successfully reduces the load at the access network but a single corrupt authentication message in the aggregate will result in the rejection of the authentication of the entire group. Furthermore, the group leader based approach also includes the complexity and consequent delay of group leader selection and, in the event of group leader failure/exit, reselection of the new incumbent. Hence, a natural corollary to these contributions would be one that addresses these limitations.In this paper, the authors propose the Hierarchical Group based Mutual Authentication and Key Agreement (HGMAKA) protocol for MTC which will be suitable for both current LTE-A and future 5G networks. The main contributions of this paper are the following:(1)
Introduction of a hierarchical approach, as against the existing first MTCD based or group leader based approach, for implementation of group based AKA between a group of MTCDs and the Core Network.(2)
Adoption of hierarchical small cell architecture, in line with 5G architecture, for reduction in signaling load due to authentication as against macrocell architecture in existing literature.(3)
Introduction of en route integrity verification of authentication messages to avoid batch reauthentication due to failures.(4)
Performance comparison with ten other group based schemes in the literature.The proposed group based hierarchical protocol uses the support of network elements instead of a group leader, thereby eliminating the additional complexity related to group leader management. In view of resource constrained devices used in most M2M applications, it uses the lightweight symmetric key based aggregate Message Authentication Code (MAC) approach with integrity verification of authentication messages at each level of the hierarchy. This eliminates the chance of group authentication failure at the core network which can otherwise be caused, in the existing group based schemes using aggregate MAC, by even a single corrupt MAC appearing in the aggregate authentication message.Furthermore, the use of small cells helps in offloading traffic from the macrocells to small cells resulting in further reduction in signaling load at the access network level. This is also in line with the architectures of future cellular networks as proposed by several projects like METIS, iJOIN [6], TROPIC [7], and so forth advocating the use of small cells. Depending on applications, MTCDs may be deployed in low coverage areas like underground parking or remote inaccessible locations where connectivity to cellular networks may not be feasible. The proposed HGMAKA scheme takes into consideration such cases through the use of small cells and capillary network of devices. Being hierarchical in nature, it allows larger group sizes through multilevel aggregation resulting in lesser number of groups for a given number of MTCDs. Moreover, highly mobile MTCDs like those in public vehicles will need frequent handovers resulting in high overhead. The proposed protocol uses mobile femtocells to address this issue.The rest of the paper is organized as follows: Section2 provides an overview of MTC under LTE-A, the mutual AKA protocol, and the importance of heterogeneous cellular network architecture; Section 3 spells out the motivation behind the proposed protocol; Section 4 reviews some related works from the literature on group based mutual AKA protocols and highlights the issues therein; Sections 5 and 6 present the proposed system architecture along with the proposed protocol; Section 7 presents the security analysis of the protocol; Section 8 provides performance analysis of the proposed protocol vis-à-vis existing group based protocols; and Section 9 concludes the paper.


## 2. Machine Type Communication and Small Cell Architecture

### 2.1. Machine Type Communication

Machine Type Communication (MTC) [8] also known as M2M communication refers to the communication between entities without any human intervention. This communication mainly entails collection of data by the MTCD and transmitting to an MTC Server which processes the data and initiates some action. There can also be scenarios where the MTC Server triggers the MTCD to perform some action. A third scenario may involve two MTCDs communicating among themselves with or without involving any MTC Server. Standardization organizations, like 3GPP, have published specifications to enable optimization of 3G and LTE cellular networks for MTC traffic. The MTCD connects to the LTE core network, also known as Evolved Packet Core (EPC), via the evolved Node B (eNodeB/eNB) which is the base station in the Radio Access Network (RAN), named Evolved Universal Terrestrial RAN (eUTRAN) in case of LTE. LTE also supports other non-3GPP RAN which can be either trusted or untrusted, depending on the operator’s policies. The RAN, and thereby, the base station, can differ in case of trusted/untrusted 3GPP/non-3GPP networks. Before the MTCD can communicate over the LTE network, it has to perform a mutual authentication with the core network. The Mobility Management Entity (MME) represents the network in this authentication procedure. In case of trusted non-3GPP access networks, the Authentication, Authorization, and Accounting (AAA) Server, and for untrusted non-3GPP networks, the evolved Packet Data Gateway (ePDG), performs the authentication with the MTCD. The Home Subscriber Server (HSS) is the central database of all authentication information and assists the MME/AAA/ePDG in the authentication procedure. The Packet Data Gateway (PDG) entity provides connectivity to external packet data networks.In case of indoor traffic, a smaller and less powerful base station, named Home eNodeB (HeNB) [9], can be used, which improves the coverage in indoor locations with higher data rates. The HeNB is a small, less expensive base station that is located at the customer site and connects to the EPC via the customer’s existing broadband access line like DSL or broadband cable. Multiple HeNBs can be managed by an optional element of the EPC called the Home eNodeB Gateway (HeNB-GW). It multiplexes connections from multiple HeNBs into a single stream in order to alleviate the load on the MME. The HeNB-GW is transparent to the MME as well as to the HeNBs. Figure 1 gives the network architecture of LTE.Figure 1
LTE-A network architecture.A Mutual Authentication and Key Agreement procedure is carried out between the MME/AAA/ePGD and the MTCD. The authentication procedure used is the Evolved Packet System-Authentication and Key Agreement (EPS-AKA) [10] for 3GPP and Extensible Authentication Protocol-AKA (EAP-AKA) [11] for non-3GPP networks. On successful completion of the authentication procedure, both parties share a secret session key to be used for confidentiality and integrity protection or for deriving next level keys to be used for the same purpose. Figure 2 shows the steps involved in the EPS-AKA protocol.Figure 2
EPS-AKA protocol.


### 2.2. Small Cell Architecture and HetNets

As mentioned in the previous section, the growing number of MTC connection is a concern for the current cellular network which will face tremendous challenges in providing the desired level of user satisfaction to both M2M and Human to Human (H2H) communications. One of the possible approaches to handle hyper densification of cells is to offload traffic into smaller cells served by low powered base stations like micro and pico eNodeBs (eNB), Home eNodeBs (HeNB), Relay Nodes (RN), and even Remote Radio Heads (RRH) (radio elements which have a wired connection to an existing macro eNB). As the deployment of additional macrocells is not practically possible due to paucity of space and prohibitive costs, a network of macro as well as small cells, termed as Heterogeneous Network or HetNet [12], will assist in a long way in handling the massive numbers of users. Small cells bring in the advantages of load balancing between cells, improved coverage leading to improved user satisfaction, and reduced latency and lower power consumption as the base stations are closer to the users. A HetNet in LTE-A can consist of macrocells, microcells, picocells, and femtocell, in the decreasing order of the base station power. While femtocells cater to only indoor traffic, the others mostly cater to outdoor traffic. Another small cell termed mobile femtocell (MFemtocell) [13] combines the concepts of femtocell with mobile relay. It consists of dedicated relay nodes mounted outside public vehicles like buses, trains, and so forth. The users inside the vehicle form a femtocell which uses the mobile relay node to communicate with the macro base station. The base station views the MFemtocell and all its users as a single entity and at the same time, the users are unaware of the existence of the mobile relay node. The deployment of MFemtocell will prove to be beneficial for high mobility scenarios and also improve network coverage.In addition to the above which operate in the licensed spectrum, the network can also incorporate Capillary Networks of MTCDs where the devices also use some local communication technologies like Bluetooth, ZigBee, WiFi, and so forth in the unlicensed spectrum. The devices in the network communicate with MTC Servers via a MTC Gateway Device that acts as the intermediary between the cellular network and the capillary network of devices. The MTC Gateway Device is equipped with dual communication capabilities like cellular and some local access technology [14].The small cells have their share of challenges to overcome. These include cost effective deployment and efficient operation and management of small cells by operators, intercell interference management, technologies for backhauling traffic from small cells to core networks, security, and many more. The authors in [15] have listed some of the issues related to use of capillary M2M networks, which includes interference and low data rates for applications with high end-to-end reliability requirement.Considering the fact that small cells are expected to be an integral component of future mobile cellular networks, the proposed hierarchical group based authentication protocol uses an architecture which brings together a macrocells network with an overlay of small cells and capillary networks.


## 2.1. Machine Type Communication

Machine Type Communication (MTC) [8] also known as M2M communication refers to the communication between entities without any human intervention. This communication mainly entails collection of data by the MTCD and transmitting to an MTC Server which processes the data and initiates some action. There can also be scenarios where the MTC Server triggers the MTCD to perform some action. A third scenario may involve two MTCDs communicating among themselves with or without involving any MTC Server. Standardization organizations, like 3GPP, have published specifications to enable optimization of 3G and LTE cellular networks for MTC traffic. The MTCD connects to the LTE core network, also known as Evolved Packet Core (EPC), via the evolved Node B (eNodeB/eNB) which is the base station in the Radio Access Network (RAN), named Evolved Universal Terrestrial RAN (eUTRAN) in case of LTE. LTE also supports other non-3GPP RAN which can be either trusted or untrusted, depending on the operator’s policies. The RAN, and thereby, the base station, can differ in case of trusted/untrusted 3GPP/non-3GPP networks. Before the MTCD can communicate over the LTE network, it has to perform a mutual authentication with the core network. The Mobility Management Entity (MME) represents the network in this authentication procedure. In case of trusted non-3GPP access networks, the Authentication, Authorization, and Accounting (AAA) Server, and for untrusted non-3GPP networks, the evolved Packet Data Gateway (ePDG), performs the authentication with the MTCD. The Home Subscriber Server (HSS) is the central database of all authentication information and assists the MME/AAA/ePDG in the authentication procedure. The Packet Data Gateway (PDG) entity provides connectivity to external packet data networks.In case of indoor traffic, a smaller and less powerful base station, named Home eNodeB (HeNB) [9], can be used, which improves the coverage in indoor locations with higher data rates. The HeNB is a small, less expensive base station that is located at the customer site and connects to the EPC via the customer’s existing broadband access line like DSL or broadband cable. Multiple HeNBs can be managed by an optional element of the EPC called the Home eNodeB Gateway (HeNB-GW). It multiplexes connections from multiple HeNBs into a single stream in order to alleviate the load on the MME. The HeNB-GW is transparent to the MME as well as to the HeNBs. Figure 1 gives the network architecture of LTE.Figure 1
LTE-A network architecture.A Mutual Authentication and Key Agreement procedure is carried out between the MME/AAA/ePGD and the MTCD. The authentication procedure used is the Evolved Packet System-Authentication and Key Agreement (EPS-AKA) [10] for 3GPP and Extensible Authentication Protocol-AKA (EAP-AKA) [11] for non-3GPP networks. On successful completion of the authentication procedure, both parties share a secret session key to be used for confidentiality and integrity protection or for deriving next level keys to be used for the same purpose. Figure 2 shows the steps involved in the EPS-AKA protocol.Figure 2
EPS-AKA protocol.


## 2.2. Small Cell Architecture and HetNets

As mentioned in the previous section, the growing number of MTC connection is a concern for the current cellular network which will face tremendous challenges in providing the desired level of user satisfaction to both M2M and Human to Human (H2H) communications. One of the possible approaches to handle hyper densification of cells is to offload traffic into smaller cells served by low powered base stations like micro and pico eNodeBs (eNB), Home eNodeBs (HeNB), Relay Nodes (RN), and even Remote Radio Heads (RRH) (radio elements which have a wired connection to an existing macro eNB). As the deployment of additional macrocells is not practically possible due to paucity of space and prohibitive costs, a network of macro as well as small cells, termed as Heterogeneous Network or HetNet [12], will assist in a long way in handling the massive numbers of users. Small cells bring in the advantages of load balancing between cells, improved coverage leading to improved user satisfaction, and reduced latency and lower power consumption as the base stations are closer to the users. A HetNet in LTE-A can consist of macrocells, microcells, picocells, and femtocell, in the decreasing order of the base station power. While femtocells cater to only indoor traffic, the others mostly cater to outdoor traffic. Another small cell termed mobile femtocell (MFemtocell) [13] combines the concepts of femtocell with mobile relay. It consists of dedicated relay nodes mounted outside public vehicles like buses, trains, and so forth. The users inside the vehicle form a femtocell which uses the mobile relay node to communicate with the macro base station. The base station views the MFemtocell and all its users as a single entity and at the same time, the users are unaware of the existence of the mobile relay node. The deployment of MFemtocell will prove to be beneficial for high mobility scenarios and also improve network coverage.In addition to the above which operate in the licensed spectrum, the network can also incorporate Capillary Networks of MTCDs where the devices also use some local communication technologies like Bluetooth, ZigBee, WiFi, and so forth in the unlicensed spectrum. The devices in the network communicate with MTC Servers via a MTC Gateway Device that acts as the intermediary between the cellular network and the capillary network of devices. The MTC Gateway Device is equipped with dual communication capabilities like cellular and some local access technology [14].The small cells have their share of challenges to overcome. These include cost effective deployment and efficient operation and management of small cells by operators, intercell interference management, technologies for backhauling traffic from small cells to core networks, security, and many more. The authors in [15] have listed some of the issues related to use of capillary M2M networks, which includes interference and low data rates for applications with high end-to-end reliability requirement.Considering the fact that small cells are expected to be an integral component of future mobile cellular networks, the proposed hierarchical group based authentication protocol uses an architecture which brings together a macrocells network with an overlay of small cells and capillary networks.


## 3. Motivation

While MTC applications span across a wide domain, each with distinct features and requirements, the common feature distinguishing them from the regular H2H communication is the presence of massive number of devices. As these devices have to execute EPS-AKA to connect to the EPC for access authentication, a large number of these trying to connect at the same time will create substantial signaling overload in the access network. In a roaming scenario, where the devices are away from their home network (HN), the serving network (SN) will have to fetch the authentication data from the HN leading to an increased signaling load. Consequently, this necessitates the design of Mutual Authentication and Key Agreement protocols for MTC aimed at minimizing the signaling overhead.In addition, the MTCDs are usually low powered devices lacking high computational capabilities. This calls for an authentication protocol of lower computational complexity. Furthermore, an additional issue with cellular MTC is the presence of the devices at cell edges and in indoor spaces like inside underground parking lots, shopping malls, hospitals, and so forth, where network connectivity may be poor. Likewise, some of the devices may not exhibit any form of mobility (e.g., security camera) while others may be highly mobile (e.g., devices in trains or buses). Thus, the authentication procedure needs to take into consideration the following factors:(i)
Massive deployment of MTCDs causing signaling overload(ii)
Deployment environment of the MTCDs (i.e., indoor/outdoor)(iii)
Mobility behavior of the MTCDs (i.e., stationary/mobile)(iv)
Computational and storage capabilities of MTCDsThis paper thus proposes an Authentication and Key Agreement protocol to reduce the signaling load, while addressing the aforementioned factors. The first three factors are accounted for in the deployment architecture while the last factor is handled by the use of symmetric cryptography in the proposed algorithm.


## 4. Related Works

A number of group based mutual authentication schemes exist in the literature. The schemes can be categorized into three types:(i)
Schemes consist of one device of the group performing a full AKA with the core network and thereafter the authentication records for all members of the group are retrieved from the HN and sent to the SN. For the second group member onwards, the HN remains offline with the authentication being performed locally at the SN with the prefetched data. Some of the schemes following this approach are SE-AKA [16] by Lai et al., MTC-AKA [17] also by Lai et al., DGBAKA [18] by Zhang et al., and GAKA [19] by Chen et al. with some minor variations.While these schemes successfully reduce the signaling traffic between the home network and the serving network, the load at the access network remains unchanged.(ii)
Schemes use aggregation of messages where a selected group leader from among the MTCDs receives individual messages from all group members, aggregates them into a single message along with an aggregate signature or an aggregate MAC, and forwards the same to the core network. The core network element verifies the aggregate signature or aggregate MAC to authenticate the group. Schemes like Cao et al. in [20, 21] uses the aggregate signature concept and those [22] by Lai et al., [23] by Choi et al., and GLARM [24] by Lai et al. are based on the aggregate MAC concept. While the scheme [20] is based on the concept of aggregate signature proposed by Boneh et al. [25], the scheme [21] uses the Nyberg Rueppel signature scheme [26].The aggregate MAC approach for group authentication is a lightweight one, significantly reducing the signaling overhead at the access network level as compared to aggregate signature schemes. Most existing schemes use a group leader to aggregate the MACs received from the individual MTCDs in a group. However, this can cause a bottleneck at the group leader and also involves the additional complexity and delay associated with group leader selection and management. Another drawback of the aggregation approach is that a single bad (message, MAC) pair or a single invalid signature in the aggregate can cause the entire authentication to fail resulting in repeating the entire authentication process. An attacker only needs to change a single bit in a message or MAC across the group to ensure a failure. So, the cost of this endeavor from the attacker’s point of view is very low, making the system susceptible to Denial of Service attacks.(iii)
Schemes follow a batch processing approach whereby authentication requests from multiple devices are processed at once as a batch, like ABAKA [27] by Huang et al.These schemes are also hounded by the issue of a single invalid signature requiring the rerun of the entire authentication process.


## 5. HGMAKA Protocol: System Architecture

The proposed system architecture consists of macrocells, femtocells, mobile femtocells, and also capillary network of devices, thereby forming a HetNet. The architectural elements are classified into three tiers, each consisting of heterogeneous devices performing distinct activities:(i)
The first tier, Tier 1, consists of the data generating/consuming MTCDs, for example, smart meters and medical equipment. They generate data periodically or on being triggered and send the data to some MTC Server. The MTCDs may be static (e.g., surveillance camera) or may be mobile (devices inside train, bus, etc.). They need to be authenticated before they can use the network for sending data to the MTC Servers. Thus, they generate authentication request messages which are sent to the Tier 2 elements.(ii)
The second tier, Tier 2, comprises aggregating elements, those which aggregate the multiple streams of data received from elements in the first tier into a single stream and forward it to the elements in the next tier. Additionally, they verify the MACs of the received messages to verify their integrity and ensure that no tampered messages are included in the aggregate. These elements can be HeNBs, mobile femtocells, MTC Gateway devices, and so forth.(iii)
The third tier, Tier 3, elements provide the last mile connectivity to the core network. They accept the multiple incoming aggregated streams from Tier 2 elements and forward them to the core network either as individual streams or as an aggregate stream as per the requirements. They are also the second level aggregator and verifier. Like the Tier 2 elements, they also verify the integrity of the incoming messages from Tier 2 using MAC before including them in the aggregate. These elements include Home eNodeB Gateway, if HeNBs were the Tier 2 elements, and eNodeB if the corresponding Tier 2 elements were MFemtocells or MTC Gateway devices.The proposed protocol thus not only performs the aggregation of multiple streams from a lower tier into a single stream at a higher tier, but also eliminates the possibility, due to presence of tampered messages in the aggregate, of authentication failure of the entire group. The Tiers 2 and 3 elements take up the role of aggregation from the group leaders of aggregate based schemes in the literature, thus eliminating the requirement of group leader and the associated computational overheads. Moreover, the limited communication range of group leader due to the use of local access technology at the group level restricts the group sizes. The use of hierarchical architecture also removes this limitation, thereby allowing larger groups of MTCDs to spread across a macrocell. Figure3 shows the network architecture while Figure 4 illustrates the advantage of hierarchical architecture in terms of group sizes. Table 1 lists the classification of the architectural elements.Table 1
Network elements.
Tier Description Devices Tier 1 The end-device in the communication scenario which generates the authentication requests MTCD Tier 2 Level 1 aggregator and integrity verifier of authentication requests from Tier 1 HeNB, MTC-GW, mobile femtocell Tier 3 Last mile connecting device and Level 2 aggregator and integrity verifier of Tier 2 messages HeNB-GW, eNodeBFigure 3
Proposed MTC network architecture.Figure 4
Larger groups enabled by hierarchical architecture.


## 6. HGMAKA Protocol: Algorithm

The aggregation of authentication message at various hierarchies in HGMAKA protocol is followed by a key agreement phase resulting in a unique secret session key being shared among an individual MTCD and the corresponding SN.The grouping of MTCDs in this protocol may be predetermined or may be done on the fly. For example, a group of MTCDs belonging to the same MTC owner or using the same MTC application may be grouped together by the operator and assigned a group key. Alternately, a group can also be created on the fly based on, say, the current location of the MTCDs, like group of MTCDs inside a vehicle/train/bus and so forth. In this scenario, a group key agreement protocol must be used to generate a group key for all group members with the HSS involved in the process. The group key can also be changed dynamically as changes in membership occur in the group. While there are various group key management protocols available in the literature [28–30] and so forth, the same is beyond the scope of the paper and hence not discussed here. The group key is shared among the MTCDs, HSS, the Tier 1, the Tier 2, and the Tier 3 elements. Notations explain the symbols used in the protocol. The proposed protocol consists of two phases:(i)
Aggregate generation phase, where the authentication request messages and MACs, sent by Tier 1 elements, are aggregated at higher levels, first by Tier 2 elements and followed by Tier 3 elements. Integrity verification of the incoming messages is performed at each level prior to the aggregate generation.(ii)
Group based Mutual Authentication and Key Agreement phase, where the HSS authenticates all group members simultaneously from the aggregate MAC and the MTCDs authenticate the MME and HSS through a random challenge response protocol terminating with the derivation of unique shared secret keys between the MME and each MTCD.


### 6.1. Aggregate Generation Phase

(1)
Consider a groupGi where the jth MTCD MTCDGi-j, identified by its Unique International Mobile Subscriber Identity IMSIGi-j, shares a secret key KGi-j with the HSS. In this phase, MTCDGi-j generates the authentication request message (MGi-j1) containing the IMSI (IMSIGi-j), Group Identifier (GIDGi), random number (RGi-j), and a MAC (MACGi-j) computed on the same using the secret key KGi-j and sends it to the Tier 2 element. Also included in this communication is another MAC (MACGi-j1) computed on MGi-j1 and MACGi-j using the group key GKGi. While the former is used for authentication of the MTCD by the HSS, the latter is used for verifying the integrity of the message by the Tier 2 element. The detailed steps are listed below:
(a)
Each MTCDj of group Gi generates an authentication message MGi-j1 which contains MTCD identity (IMSIGi-i), group identifier (GIDGi), a random number RGi-i generated by the MTCDGi-j, and a MAC, MACGi-j. This MAC, later aggregated by the Tier 2 elements, is used by the HSS to authenticate the MTCD.(1)MGi-j1=IMSIGi-j∥RGi-j∥GIDGi∥MACGi-j, whereMACGi-j=f2(KGi-j,IMSIGi-j∥RGi-j∥GIDGi). (b)
The MTCD computes a second MAC onMGi-j1 with the group key GKGi, to be used for integrity verification of these Tier 1 messages at the Tier 2 element,(2)MACGi-j1=f2GKGi,MGi-j1. (c)
M T C D G i - j sends MGi-j1∥MACGi-j1 to the Tier 2 element. (2)
On receiving the messageMGi-j1∥MACGi-j1, the Tier 2 element of group Gi first verifies the integrity of the received message from MACGi-j1 using the shared group key GKGi. On successful verification, it proceeds to compute the aggregate MAC (aggMACGik2) and aggregate message (aggMGik2) for all Tier 1 elements under it. Finally, the Tier 2 element computes a MAC, MACGik2, on aggMGik2∥aggMACGik2 to be later used for the integrity verification of the message at the Tier 3 element. The steps are listed below:
(a)
For each Tier 1 elementj of group Gi under the Tier 2 element k, the Tier 2 element verifies MACGi-j1 in the received message MGi-j1∥MACGi-j1 using (2). Successful verification assures that the message MGi-j1 has not been tampered with. (b)
The Tier 2 element then computes aggregate MAC,aggMACGik2, by performing XOR operation on the individual MACs received from the Tier 1 elements(3)aggMACGik2=aggMACGik2⊕MACGi-j. (c)
Aggregate messageaggMGik2 is compiled by concatenating individual messages received from Tier 1 elements (4)MGi-j1=removeMGi-j1,MACGi-j. The remove function excluded the MAC field from individual messages.(5)aggMGik2=aggMGik2∥MGi-j1. (d)
M A C G i k 2 is then computed for integrity verification of message at the next higher Tier element(6)MACGik2=f2GKGi,aggMGik2∥aggMACGik2. (e)
Finally, the first level aggregate messageaggMGik2∥aggMACGik2∥MACGik2 is sent to Tier 3 element. (3)
The Tier 3 element performs integrity verification of the message received from Tier 2 and then the second level aggregation is as follows:
(a)
For each Tier 2 element of groupGi under the Tier 3 element, the Tier 3 element verifies MACGik2 in the received aggregate message aggMGik2∥aggMACGik2∥MACGik2 using (6). (b)
On successful verification, an aggregate MAC,aggMACGi, is computed from the first level aggregate MACs, to be used by the HSS for authenticating the entire group Gi(7)aggMACGi=aggMACGi⊕aggMACGik2. (c)
The aggregate messageaggMGi is compiled by concatenating the level one aggregate messages of group Gi: (8)aggMGi-jk2=removeaggMGi-jk2,aggMACGik2aggMGi=aggMGi∥aggMGik2. (d)
The second level aggregate messageaggMGi∥aggMACGi is then sent to MME.


### 6.2. Group Authentication and Key Agreement Phase

(1)
On receiving the aggregate authentication request and aggregate MAC, that is,aggMGi∥aggMACGi from the Tier 3 element, the MME forwards this, along with its Serving Network Identity (SN_ID), that is, aggMGi∥aggMACGi∥SN_ID, to the HSS. (2)
The HSS receives this aggregate message authentication request for groupGi from the MME and authenticates the entire group from the aggregate MAC:
(a)
The HSS verifies the aggregate MAC,aggMACGi (see (7)). (b)
The HSS uses a random numberRHSS to compute a Temporary Group Key, TGKGi, (9)TGKGi=f1GKGi,RHSS∥SN_ID and generates an authentication tokenAUTHHSS, to be used by the MTCD for authenticating the HSS, as(10)MACHSSGi=f2TGKGi,RHSS∥GIDGi(11)AUTHHSS=RHSS∥MACHSSGi. (c)
Next, the HSS generates individual session keys(KASMEGi-j) for each MTCD in the group as well as the expected response XRES to the random challenge that the HSS sends to the MTCDs for authentication purposes via MME.
For eachn member j of group Gi Forj=1 to n
A K G i - j = f 5 ( K G i - j , R H S S ) C K G i - j = f 3 ( K G i - j , R H S S ) I K G i - j = f 4 ( K G i - j , R H S S ) K A S M E G i - j = K D F ( S Q N ⊕ A K G i - j , C K G i - j , I K G i - j , S N _ I D ) X R E S G i - j = f 6 ( K G i - j , R H S S ) End For The HSS compiles the authentication information together with the computedKASME and XRES for all members of the group in the form of a table called Group Key Index (GKI). The GKI for group Gi is constructed as seen in Table 2. (d)
The HSS sends the GKI andAUTHHSS (from (11)) to the MME. (2)
The MME receives these from the HSS and saves the GKI. It forwardsAUTHHSS to each MTCD of group GIDGi. (3)
At each MTCD, on receiving the authentication challenge, one has the following:
(a)
The MTCDs authenticate the HSS from this challenge by verifyingMACHSSGi after computing TGKGi (using (9), (10)). (b)
Each MTCDj in the group also computes a response (RESGi-j) to the challenge given by the HSS(12)RESGi-j=f6KGi-j,RHSS. The group members send their response to the Tier 2 element who aggregates the response in the same way as for MAC. The aggregate RES is sent to the Tier 3 element that again aggregates the response and sends it as an aggregate responseaggRESGi for the group. The procedure is the same as aggregate MAC generation. (4)
The MME receives the aggregate response(aggRESGi) and performs the authentication as follows:
(a)
The MME verifies ifaggRESGi == XRESGi-1 xor XRESGi-2 xor …… (b)
If the verification is successful, the MTCDs in the group are authenticated. The MTCDs generate their individualKASMEs as(13)KASMEGi-j=KDFSQN⊕AKGi-j,CKGi-j,IKGi-j,SN_ID. Thus, at the end of the Authentication and Key Agreement phase, a shared secret keyKASMEGi is shared between each MTCD and the MME. Figure 5 shows a working example of the aggregate generation phase and Figure 6 shows the message sequence in the group Authentication and Key Agreement phase.Table 2
Group Key Index.
Group identifier Group member IMSI K A S M E XRES G I D G i I M S I G i - 1 K A S M E G i - 1 X R E S G i - 1 I M S I G i - 2 K A S M E G i - 2 X R E S G i - 2 ⋮ ⋮ ⋮ I M S I G i - n K A S M E G i - n X R E S G i - nFigure 5
Example working of proposed protocol (aggregate generation).Figure 6
Message exchanges in group Authentication and Key Agreement phase.


## 6.1. Aggregate Generation Phase

(1)
Consider a groupGi where the jth MTCD MTCDGi-j, identified by its Unique International Mobile Subscriber Identity IMSIGi-j, shares a secret key KGi-j with the HSS. In this phase, MTCDGi-j generates the authentication request message (MGi-j1) containing the IMSI (IMSIGi-j), Group Identifier (GIDGi), random number (RGi-j), and a MAC (MACGi-j) computed on the same using the secret key KGi-j and sends it to the Tier 2 element. Also included in this communication is another MAC (MACGi-j1) computed on MGi-j1 and MACGi-j using the group key GKGi. While the former is used for authentication of the MTCD by the HSS, the latter is used for verifying the integrity of the message by the Tier 2 element. The detailed steps are listed below:
(a)
Each MTCDj of group Gi generates an authentication message MGi-j1 which contains MTCD identity (IMSIGi-i), group identifier (GIDGi), a random number RGi-i generated by the MTCDGi-j, and a MAC, MACGi-j. This MAC, later aggregated by the Tier 2 elements, is used by the HSS to authenticate the MTCD.(1)MGi-j1=IMSIGi-j∥RGi-j∥GIDGi∥MACGi-j, whereMACGi-j=f2(KGi-j,IMSIGi-j∥RGi-j∥GIDGi). (b)
The MTCD computes a second MAC onMGi-j1 with the group key GKGi, to be used for integrity verification of these Tier 1 messages at the Tier 2 element,(2)MACGi-j1=f2GKGi,MGi-j1. (c)
M T C D G i - j sends MGi-j1∥MACGi-j1 to the Tier 2 element. (2)
On receiving the messageMGi-j1∥MACGi-j1, the Tier 2 element of group Gi first verifies the integrity of the received message from MACGi-j1 using the shared group key GKGi. On successful verification, it proceeds to compute the aggregate MAC (aggMACGik2) and aggregate message (aggMGik2) for all Tier 1 elements under it. Finally, the Tier 2 element computes a MAC, MACGik2, on aggMGik2∥aggMACGik2 to be later used for the integrity verification of the message at the Tier 3 element. The steps are listed below:
(a)
For each Tier 1 elementj of group Gi under the Tier 2 element k, the Tier 2 element verifies MACGi-j1 in the received message MGi-j1∥MACGi-j1 using (2). Successful verification assures that the message MGi-j1 has not been tampered with. (b)
The Tier 2 element then computes aggregate MAC,aggMACGik2, by performing XOR operation on the individual MACs received from the Tier 1 elements(3)aggMACGik2=aggMACGik2⊕MACGi-j. (c)
Aggregate messageaggMGik2 is compiled by concatenating individual messages received from Tier 1 elements (4)MGi-j1=removeMGi-j1,MACGi-j. The remove function excluded the MAC field from individual messages.(5)aggMGik2=aggMGik2∥MGi-j1. (d)
M A C G i k 2 is then computed for integrity verification of message at the next higher Tier element(6)MACGik2=f2GKGi,aggMGik2∥aggMACGik2. (e)
Finally, the first level aggregate messageaggMGik2∥aggMACGik2∥MACGik2 is sent to Tier 3 element. (3)
The Tier 3 element performs integrity verification of the message received from Tier 2 and then the second level aggregation is as follows:
(a)
For each Tier 2 element of groupGi under the Tier 3 element, the Tier 3 element verifies MACGik2 in the received aggregate message aggMGik2∥aggMACGik2∥MACGik2 using (6). (b)
On successful verification, an aggregate MAC,aggMACGi, is computed from the first level aggregate MACs, to be used by the HSS for authenticating the entire group Gi(7)aggMACGi=aggMACGi⊕aggMACGik2. (c)
The aggregate messageaggMGi is compiled by concatenating the level one aggregate messages of group Gi: (8)aggMGi-jk2=removeaggMGi-jk2,aggMACGik2aggMGi=aggMGi∥aggMGik2. (d)
The second level aggregate messageaggMGi∥aggMACGi is then sent to MME.


## 6.2. Group Authentication and Key Agreement Phase

(1)
On receiving the aggregate authentication request and aggregate MAC, that is,aggMGi∥aggMACGi from the Tier 3 element, the MME forwards this, along with its Serving Network Identity (SN_ID), that is, aggMGi∥aggMACGi∥SN_ID, to the HSS. (2)
The HSS receives this aggregate message authentication request for groupGi from the MME and authenticates the entire group from the aggregate MAC:
(a)
The HSS verifies the aggregate MAC,aggMACGi (see (7)). (b)
The HSS uses a random numberRHSS to compute a Temporary Group Key, TGKGi, (9)TGKGi=f1GKGi,RHSS∥SN_ID and generates an authentication tokenAUTHHSS, to be used by the MTCD for authenticating the HSS, as(10)MACHSSGi=f2TGKGi,RHSS∥GIDGi(11)AUTHHSS=RHSS∥MACHSSGi. (c)
Next, the HSS generates individual session keys(KASMEGi-j) for each MTCD in the group as well as the expected response XRES to the random challenge that the HSS sends to the MTCDs for authentication purposes via MME.
For eachn member j of group Gi Forj=1 to n
A K G i - j = f 5 ( K G i - j , R H S S ) C K G i - j = f 3 ( K G i - j , R H S S ) I K G i - j = f 4 ( K G i - j , R H S S ) K A S M E G i - j = K D F ( S Q N ⊕ A K G i - j , C K G i - j , I K G i - j , S N _ I D ) X R E S G i - j = f 6 ( K G i - j , R H S S ) End For The HSS compiles the authentication information together with the computedKASME and XRES for all members of the group in the form of a table called Group Key Index (GKI). The GKI for group Gi is constructed as seen in Table 2. (d)
The HSS sends the GKI andAUTHHSS (from (11)) to the MME. (2)
The MME receives these from the HSS and saves the GKI. It forwardsAUTHHSS to each MTCD of group GIDGi. (3)
At each MTCD, on receiving the authentication challenge, one has the following:
(a)
The MTCDs authenticate the HSS from this challenge by verifyingMACHSSGi after computing TGKGi (using (9), (10)). (b)
Each MTCDj in the group also computes a response (RESGi-j) to the challenge given by the HSS(12)RESGi-j=f6KGi-j,RHSS. The group members send their response to the Tier 2 element who aggregates the response in the same way as for MAC. The aggregate RES is sent to the Tier 3 element that again aggregates the response and sends it as an aggregate responseaggRESGi for the group. The procedure is the same as aggregate MAC generation. (4)
The MME receives the aggregate response(aggRESGi) and performs the authentication as follows:
(a)
The MME verifies ifaggRESGi == XRESGi-1 xor XRESGi-2 xor …… (b)
If the verification is successful, the MTCDs in the group are authenticated. The MTCDs generate their individualKASMEs as(13)KASMEGi-j=KDFSQN⊕AKGi-j,CKGi-j,IKGi-j,SN_ID. Thus, at the end of the Authentication and Key Agreement phase, a shared secret keyKASMEGi is shared between each MTCD and the MME. Figure 5 shows a working example of the aggregate generation phase and Figure 6 shows the message sequence in the group Authentication and Key Agreement phase.Table 2
Group Key Index.
Group identifier Group member IMSI K A S M E XRES G I D G i I M S I G i - 1 K A S M E G i - 1 X R E S G i - 1 I M S I G i - 2 K A S M E G i - 2 X R E S G i - 2 ⋮ ⋮ ⋮ I M S I G i - n K A S M E G i - n X R E S G i - nFigure 5
Example working of proposed protocol (aggregate generation).Figure 6
Message exchanges in group Authentication and Key Agreement phase.


## 7. Security Analysis

To illustrate that the proposed protocol is secure, the authors have followed a three-pronged approach to security analysis. First, an informal security analysis of the protocol has been performed to demonstrate the resilience of the protocol against different protocol attacks. Second, the automated formal verification tool AVISPA has been used to verify if the security goals of mutual authentication and secure key agreement have been met. And third, a provable security approach has been used to formally prove that no feasible polynomial time adversary exists which can break the security of the scheme.


### 7.1. Mutual Authentication

The proposed protocol is based on the aggregate MAC concept. An aggregate MAC(aggMACGi) is generated at two levels, Level 1 by Tier 2 elements and Level 2 by Tier 3, from the individual MACs sent by the MTCDs in the group. This is sent to the MME which forwards it to the HSS. The HSS verifies this aggregate MAC and generates a random challenge and forwards it to the MME in the form of an authentication token (AUTHHSS) along with the expected response (XRES) for each MTCD in the group. The MME broadcasts the same to all MTCDs. All MTCDs authenticate the HSS from AUTHHSS. The MTCD computes their individual response to the random challenge and sends it via the Tier 2 and Tier 3 elements after going through two levels of aggregation to arrive at the aggregate response (aggRESGi). The MME then completes the mutual authentication by comparing the received aggregate response to the precomputed responses stored at the MME. Thus, the MME and MTCDs perform a mutual authentication.


### 7.2. Secured Key Agreement

Once mutual authentication is successful, both parties, that is, MME and MTCD, have a session key shared between them. The key(KASMEGi-j) is generated at both ends after mutual authentication and is never transmitted over any channel. Also, the respective keys are generated at both ends as KDF(SQN⊕AKGi-j,CKGi-j,IKGi-j,SN_ID), where AKGi-j,  CKGi-j, and IKGi-j are computed from RHSS and the shared secret key KGi-j only after mutual authentication is successful.


### 7.3. Man-in-the-Middle Attack

Despite the fact that the entire communication, both within the capillary network/femtocell and between the MTC-GW and the network, occurs in plaintext, an intruder cannot determine the session keys (TGKGi and KASMEGi-j) as these require the knowledge of long term secret keys shared between the MTCD and the HSS as well as the random numbers and sequence numbers.


### 7.4. Replay Attack

Replay attacks can be thwarted by the use of the random numbers generated by the MTCDs and HSS in the authentication procedure. Even if an attacker captures the messages, the same random number cannot be used for another round of authentication as fresh numbers are required for a fresh round of authentication.


### 7.5. Key Compromise Impersonation (KCI)

A key agreement protocol is KCI-resilient if no adversary can masquerade as an honest user and establish a session key with another user whose long term key has been compromised by the adversary. The proposed protocol is KCI-resilient as proved formally in the next section.


### 7.6. Forward Secrecy

Forward secrecy implies that if the long term key of the entity is compromised then the secrecy of the earlier session keys generated is not affected. In case of HGMAKA, the session keyKASMEGi-j is computed as a function of the long term secret key KGi-j as well as RHSS and SQN, both of which changes for each session. Thus, even if KGi-j is compromised, it will be difficult for the attacker to correlate both the correct RHSS and SQN to be used for generating a past session key. Hence, the protocol has forward key secrecy.


### 7.7. Formal Verification Using AVISPA

The main goal of the proposed protocol is to provide mutual authentication between the MTCD and the MME/HSS and secured key agreement between the entities. The formal verification of the proposed protocol is tested onAutomated Validation of Internet Security Protocols and Applications (AVISPA) [31]. AVISPA is a tool for automatic security analysis of protocols represented inHigh Level Protocol Specification Language (HLPSL) and evaluated using automatic deduction techniques. We have modeled three roles, MTCD, Gateway, and MME, using HLPSL. As the MME and HSS have a secured channel between them, so we have integrated the roles of MME and HSS into a single role. The On-the-Fly Model Checker has been used to test our protocol. The goals of the protocol are given in Algorithm 1 and the output is given in Algorithm 2. The HLPSL roles for MTCD and MME are given in Appendix A as Algorithms 3 and 4.Algorithm 1:Goal specification of proposed protocol.
goal secrecy_of kasme secrecy_of gtkg1 authentication_on mtcd_mme_rg11 authentication_on mtcd_mme_rhss end goalAlgorithm 2:Results from OFMC.
% OFMC % Version of 2006/02/13 SUMMARY SAFE DETAILS BOUNDED_NUMBER_OF_SESSIONS PROTOCOL /home/span/span/testsuite/results/Proposed.if GOAL as_specified BACKEND OFMC COMMENTS STATISTICS parseTime: 0.00s searchTime: 0.21s visitedNodes: 8 nodes depth: 3 pliesAlgorithm 3:Role of MTCD in HLPSL.
role mtcd(MTCD,GW,MME: agent, Kg1_1,Gkg1: symmetric_key, IMSIg1_1, GIDg1:text, HMAC: function, F1,F2,F3,F4,F5,F6,KDF:function, SQN:text, SND,RCV,SNDG,RCVG:channel(dy)) played_by MTCD def= local State:nat, Rg1_1:text, MACg1_1:text, GMACg1_1:text, Authhss,Rmme,Rhss,Macmme:text, SNID:text init State:=0 transition ( 1 )    State=0 ∧ RCV(start)=|> State':=3∧ Rg1_1':=new() ∧ MACg1_1':= HMAC(IMSIg1_1.Rg1_1')_Gkg1 ∧ GMACg1_1':= H M A C(IMSIg1_1.Rg1_1'.MACg1_1'.GIDg1)_Gkg1 ∧ SNDG(IMSIg1_1.Rg1_1'.MACg1_1'.GIDg1.GMACg1_1') ∧ witness(MME,MTCD,mme_mtcd_rg11,Rg1_1') ( 2 )    State=3 ∧ RCV(Rhss'.(HMAC(Rhss'.GIDg1)_(F1(Rhss'.SNID)_Gkg1)).Rmme'.(F2(Rmme'.(Rhss'.(HMAC(Rhss'.GIDg1)_ (F1(Rhss'.SNID)_Gkg1))))_(F1(Rhss'.SNID)_Gkg1))) =|> State':=6∧ SNDG(F6(Rhss'.Rg1_1)_Kg1_1) ∧ request(MTCD,MME,mtcd_mme_rhss,Rhss') ∧ request(MTCD,MME,mtcd_mme_rmme,Rmme') end roleAlgorithm 4:Role of MME in HLPSL.
role mme(MTCD,GW,MME: agent, Kg1_1, Gkg1: symmetric_key, IMSIg1_1, GIDg1:text, HMAC: function, F1,F2,F3,F4,F5,F6,KDF:function, SQN:text, SND,RCV:channel(dy)) played_by MME def= local State:nat, SNID,Aggmacg1,Aggres,Rhss, Macg1:text, GTKg1,Kasmeg1_1:symmetric_key, Authhss:text, Akg1_1,Ckg1_1,Ikg1_1,Xresg1_1, Rmme,Rg1_1,Macmme:text, init State:=3 transition ( 1 )       State=3 ∧ RCV(IMSIg1_1.Rg1_1'.GIDg1.(xor(Aggmacg1,HMAC(IMSIg1_1.Rg1_1')_Gkg1)).SNID) =|> State':=5∧ Rhss':=new() ∧ GTKg1':=F1(Rhss'.SNID)_Gkg1 ∧ secret(GTKg1',gtkg1,MME,MTCD) ∧ Macg1':=HMAC(Rhss'.GIDg1)_GTKg1' ∧ Authhss':= Rhss'.Macg1' ∧ Akg1_1':= F5(Rhss')_Kg1_1 ∧ Ckg1_1':= F 3(Rhss')_Kg1_1 ∧ Ikg1_1':= F4(Rhss')_Kg1_1 ∧ Kasmeg1_1':=KDF(xor(SQN,Akg1_1'),Ckg1_1',Ikg1_1',SNID) ∧ secret(Kasmeg1_1',kasme,MTCD,MME) ∧ Xresg1_1':= F6(Rhss'.Rg1_1')_Kg1_1 ∧ Rmme':= new() ∧ Macmme':= H M A C(Rmme'.Authhss')_GTKg1' ∧ SND(Authhss'.Rmme'.Macmme') ∧ witness(MME,MTCD,mtcd_mme_rmme,Rmme) ∧ witness(MME,MTCD,mtcd_mme_rhss,Rhss) ( 2 )      State=5 ∧ RCV(xor(Aggres,F6(Rhss.Rg1_1')_Kg1_1)) =|> State':=6∧ request(MTCD,MME,mme_mtcd_rg11,Rg1_1') end role


### 7.8. Formal Protocol Analysis

The foundation of the security proof of the proposed protocol lies in Shoup’s formal security model [32] for secure Mutual Authentication and Key Agreement using the simulation based technique. In [33] Zhang suitably modified Shoup’s model to fit the mobile communication scenario. Further, Huang et al. in [34, 35] also used Zhang’s model to present a provably secure AKA protocol for UMTS. The authors have based their security proof on Zhang’s model. In Zhang’s simulation based model, the proof of security is arrived at by comparing the performance of an adversary in a real protocol execution (real world) and an ideal scenario (ideal world) which is assumed to be secure by definition. The protocol is said to be provably secure if it is not possible to distinguish between the actions of the attacker in the real world and the ideal world.As per Shoup’s model, the MTC scenario involves two types of communication channels: a secure (assumed) channel between network entities and an insecure wireless channel between the MTCD entities and the network entities. The latter is under the full control of the adversary who can read, modify, and replay the messages transmitted over the channel. The adversary can set up and initiate multiple sessions between MTCD and network and also acquire session keys and apply it on some mathematical function. The activities of the adversary are captured under two scenarios: ideal world and real world. The security of the proposed protocol is proved by comparing the actions of the adversary in the two worlds and proving that the adversary cannot do any more harm in the real world than it would do in the ideal world. AppendixB contains the descriptions of the ideal and real world as well as certain preliminary definitions.Security Proof. Each entity in the proposed protocol possesses a random number generator which produces random numbers, RGi-j (for all i and j) and RHSS, for the entity instances. Let all random numbers be selected randomly in A and E1 is the event that TA is collision-free; we get(14)Pr⁡E1-≤ni222-RGi-j+2-RHSS,where ni is the count of instances created by A and |RGi-j| and |RHSS| are lengths of the respective random numbers and are polynomial in k, and then Pr⁡E1- is negligible.Lemma 1.
For real world adversaryA with collision-free (assumed) transcript TA and independent function family f2 assumed to be collision resistant in TA, the probability of the event E2- (E2 is the event that TA is authentic) is given by(15)Pr⁡E2-≤ni2×Advf2macp,n,where p=O(t) and n=O(ni) and t is the execution time of A.Proof.
ForTA to be nonauthentic, we must have at best one instance that has accepted based on a stimulus sent by a noncompatible instance. To prove this we show that upper bound on the probability of TA being nonauthentic is given by (15) and the proof proceeds as follows.
Case 1. Say, the network entity instance Ii′j′ accepted on receipt of aggregate message aggMGi∥aggMACGi. We try to prove that the stimulus was sent by a compatible MTCD entity. If Ii′j′ has accepted, that means that the MAC verification has been successful. However, the identity IMSIGi-j of each MTCD entity instance in the group is used in the computation of MAC. Since the IMSI contains the HN identity embedded in it, if Ii′j′ accepts then it could only be on stimulus sent by a compatible MTCD instance. Let F be the adversary for Message Authentication Code f2 with oracle access to f2K where K is a randomly selected key. Let PIDi′j′=IMSIi′j′ of user U and U might be initialized by F. F starts its execution by picking keys for all users other than U and proceeds as in the real world. If F needs access to the MAC function f2K under the key of U, the same is provided by the corresponding oracles. Further, the evaluation of functions f1,  f3,  f4,  f5,  f6, and KDF with U’s key is realized through returning a constant or random number by F. Say, Ii′j′ accepts at some point and F outputs aggMACGi and the message aggMGi and stops else F stops with a null string as output.
LetSucc(F,f2) be the event that F outputs aggMAC and a message which has not been given to the oracle f2K as a query. Let the event that Ii′j′ has accepted on stimulus by noncompatible instance be represented by Ei′j′. If Ei′j′=1 then the adversary has been successful in forging the MAC for the given message. Thus, (16)Pr⁡Ei′j′=1≤Pr⁡SuccF,f2=1(17)hence,Pr⁡Ei′j′=1≤Advf2macp,n,where p=O(t) and n=O(ni).
Case 2. Say, MTCD instance Iij accepted on stimulus AUTHHSS. Let the event that Iij accepted on stimulus from a nonnetwork entity be denoted by Eij and let the event that Iij accepted on stimulus from a noncompatible network entity Ii′j′ be denoted by Eij′. If Eij′ has occurred then Ii′j′ must have received aggMGi∥aggMACGi before sending AUTHHSS. As TA is collision-free RGi-j could be generated only by Iij which implies that the adversary has successfully forged one or more MACs in aggMAC. Thus,(18)Pr⁡Eij′=1≤Advf2macp,n.If Eij has occurred then the adversary was successful in forging the MAC for the message RHSS. An execution of A results in an adversary F′ for f2 such that the event of Iij accepting results in F′ ends with output MACHSSGi and RHSS. Thus in (18), we have Pr⁡Eij=1≤Pr⁡(SuccF′,f2=1). Hence,(19)Pr⁡Eij=1≤Advf2macp,n.Therefore, the upper bound on the probability that MTCD instance Iij accepted on a stimulus from a network instance noncompatible with it is given by (20)Pr⁡Eij=1+Pr⁡Eij′=1≤2×Advf2macp,n.Case 3. Let the network instance that accepted on stimulus aggRESGi be denoted by Ii′′j′′ and Ii′′j′′ had earlier sent RHSS. If aggRESGi was not sent by a MTCD instance then the adversary was successful in forging MACHSSGi and it can be proved similar to (17) that the upper bound on this event is Advf2macp,n. Further, say, aggRESGi was output by noncompatible MTCD instance Ii1j1. In this case Ii1j1 received AUTHHSS (which contains RHSS) prior to generating the stimulus. With TA being collision-free, it is not possible for a network entity, other than Ii′′j′′, to output AUTHHSS pointing to an adversary having forged MACHSSGi. Similar to (19) we have an upper bound on this event as Advf2macp,n. Thus, the upper bound on the probability that the stimulus on Ii′′j′′ was from a noncompatible MTCD instance is 2×Advf2macp,n.
We can therefore conclude that the probability of the eventE2- is (21)Pr⁡E2-≤ni2×Advf2macp,n.Lemma 2.
Letf1,  f3,  f4,  f5,  f6, and KDF, represented by H, be a family of pseudorandom functions and H is independent of f2 and collision resistant in the real world adversary A’s authentic and collision-free transcript TA. The algorithm D that distinguishes between the transcript of the real world adversary A and the ideal world adversary A∗ has(22)AdvTA,TA∗distD≤nMTCDAdvHprfp,n,where A initializes nMTCD MTCD entities and ni instances. p=O(t) and n=O(ni).Proof.
A simulator with a real world adversaryA creates an ideal world adversary A∗ and converts the transcript in the real world (TA) into a transcript in the ideal world (TA∗) so that the two are almost identical. The conversion is carried out in the following manner:(i)
An implementation record inTA is copied to TA∗ through an implementation operation.(ii)
A (start session,i,j) record in TA is connection assignment with the ring master replacing the session key KASMEij with idealized random session key Kij.(iii)
An (abort session,i,j) is copied to TA∗ with TA∗ executing (abort session, i,j) operation.(iv)
In case of an application action inTA, all necessary evaluation is made by the ring master using the session key of the ideal world.The main difference between TA and TA∗ lies in the application records. We prove that the assignments made by A∗ are legal and TA and TA∗ are indistinguishable.
Case 1. Let us assume that an MTCD instance Iab receives AUTHHSS and accepts. This message cannot be sent by a noncompatible network entity as TA is authentic. Let the stimulus on Iab be sent by compatible MTCD entity instance Ia′b′. The connection assignment (create, a′, b′) is made by adversary A∗. This connection assignment has not been made earlier as AUTHHSS contains RHSS which the MTCD can verify as not being repeated. Thus, the ring master can substitute the session key KASMEab with an idealized (random) session key Kab.
Case 2. Say Ip′q′, a network instance, receives aggMGi∥aggMACGi. Ipq is an MTCD instance whose individual MAC is included in aggMACGi and Ip′q′ accepts on this stimulus. The connection assignment made by A∗ is (create, p,q). The random session key Kpq is assigned by the ring master instead of KASMEp′q′. Since f2 is collision resistant in TA, hence the received message could be the stimulus only on Ip′q′. Thus, the connection assignment (create, p,q) has not be made earlier. This can be proved similarly for all MTCD instances included in the group MAC construction.
Case 3. Let Ix′y′ be the network instance that receives aggRESGi from a group Gi and let Ixy be a MTCD instance of an MTCD belonging to this group. Assume Ix′y′ has accepted on this stimulus. Since f2 is collision resistant and TA is collision-free, as in Case 2, we can prove that Ixy has accepted on receiving stimulus provided by Ix′y′. Thus, the adversary A∗ has made a valid connection assignment (connect, x,y) with the ring master setting the session key KASMEx′y′ to Kxy.
Each start session record inTA∗ has a connection assignment as seen from the analysis. The main difference between TA and TA∗ now lies only in the application records. For a single MTCD entity initialized by A and algorithm D that distinguishes between TA and TA∗, an adversary D′ for H is such that AdvTA,TA∗distD=AdvHprf(D′). Hence, AdvTA,TA∗distD≤AdvHprfp,n, where p=O(t) and n=O(ni).
FornMTCD MTCD entities with keys KGi-1,KGi-2,…,KGi-nMTCD, D and D′ have access to oracles GKGi-1,GKGi-2,…,GKGi-nMTCD′. Thus,(23)AdvTA,TA∗distD≤nMTCDAdvHprfp,n.H can be replaced by any of f1, f3, f4, f5, f6, or KDF.Theorem 3.
Assume f1, f3, f4, f5, f6, and KDF, represented byH, are pseudorandom function families and f2 is a secure MAC and all functions are independent of each other. Then, HGMAKA is a secure AKA protocol.Proof.
For real world adversaryA with transcript TA, the probability that f2 is collision resistant is negligible as f2 is a secure Message Authentication Code. From Lemma 2, we have a distinguishing algorithm D for ideal world adversary A∗ such that(24)PrDTA=1∣E1∧E2-Pr⁡DTA∗=1∣E1∧E2≤nMTCDAdvHprfp,n.Therefore,(25)AdvTA,TA∗distD=Pr⁡DTA=1-PrDTA∗=1=Pr⁡DTA∣E1∧E2-Pr⁡DTA∗=1∣E1∧E2Pr⁡E1∧E2+PrDTA∣E1-∨E2--Pr⁡DTA∗=1∣E1-∨E2-Pr⁡E1-∨E2-≤PrDTA=1∣E1∧E2-PrDTA∗=1∣E1∧E2+Pr⁡E2-+Pr⁡E1-≤nMTCDAdvHprfp,n+Pr⁡E2-+Pr⁡E1-.Again,(26)Pr⁡E2-=Pr⁡E2-∣E1Pr⁡E1+Pr⁡E2-∣E1-Pr⁡E1-≤Pr⁡E2-∣E2+Pr⁡E1-.Hence,(27)AdvTA,TA∗distD≤nMTCDAdvHprfp,n+Pr⁡E2-∣E1+2Pr⁡E1-.The probabilities Pr⁡E1- and Pr⁡E2-∣E1 are negligible in k (from (14) and Lemma 1); hence AdvTA,TA∗distD is also negligible. Hence it is proved that HGMAKA is a secure AKA protocol.Theorem 4.
HGMAKA is KCI-resilient.Proof.
We consider the case when the long term secret key of a MTCD has been compromised by an adversary. LetI denote a MTCD entity instance who tries to execute the Authentication and Key Agreement protocol with a compatible network entity instance I′. I′ accepts with session key KASMEGi-j on the stimulus aggMGi∥aggMACGi. Now, the adversary corrupts MTCDGi-j and I′ responds with message AUTHHSS. This is intercepted by the adversary and replaced by message AUTHHSS′. Next, I accepts and generates session key KASMEGi-j′ which is the same as the one generated by the adversary and different from KASMEGi-j generated by I′. In the ideal world, the session key generated by I′ was prior to the adversary corrupting the MTCD entity instance. Hence, the only connection assignment possible iscreate. Further, in case of I since it was corrupted by the adversary, the only possible connection assignment iscompromise. However, I cannot be compromised without invalidating the rules of the ideal world as PIDI=IDI′. Also,connect is not possible without KASMEGi-j=KASMEGi-j′. Thus, the real world transcript will be different from the ideal world transcript causing the simulation to be impossible. Therefore, we can conclude that HGMAKA is KCI-resilient.


## 7.1. Mutual Authentication

The proposed protocol is based on the aggregate MAC concept. An aggregate MAC(aggMACGi) is generated at two levels, Level 1 by Tier 2 elements and Level 2 by Tier 3, from the individual MACs sent by the MTCDs in the group. This is sent to the MME which forwards it to the HSS. The HSS verifies this aggregate MAC and generates a random challenge and forwards it to the MME in the form of an authentication token (AUTHHSS) along with the expected response (XRES) for each MTCD in the group. The MME broadcasts the same to all MTCDs. All MTCDs authenticate the HSS from AUTHHSS. The MTCD computes their individual response to the random challenge and sends it via the Tier 2 and Tier 3 elements after going through two levels of aggregation to arrive at the aggregate response (aggRESGi). The MME then completes the mutual authentication by comparing the received aggregate response to the precomputed responses stored at the MME. Thus, the MME and MTCDs perform a mutual authentication.


## 7.2. Secured Key Agreement

Once mutual authentication is successful, both parties, that is, MME and MTCD, have a session key shared between them. The key(KASMEGi-j) is generated at both ends after mutual authentication and is never transmitted over any channel. Also, the respective keys are generated at both ends as KDF(SQN⊕AKGi-j,CKGi-j,IKGi-j,SN_ID), where AKGi-j,  CKGi-j, and IKGi-j are computed from RHSS and the shared secret key KGi-j only after mutual authentication is successful.


## 7.3. Man-in-the-Middle Attack

Despite the fact that the entire communication, both within the capillary network/femtocell and between the MTC-GW and the network, occurs in plaintext, an intruder cannot determine the session keys (TGKGi and KASMEGi-j) as these require the knowledge of long term secret keys shared between the MTCD and the HSS as well as the random numbers and sequence numbers.


## 7.4. Replay Attack

Replay attacks can be thwarted by the use of the random numbers generated by the MTCDs and HSS in the authentication procedure. Even if an attacker captures the messages, the same random number cannot be used for another round of authentication as fresh numbers are required for a fresh round of authentication.


## 7.5. Key Compromise Impersonation (KCI)

A key agreement protocol is KCI-resilient if no adversary can masquerade as an honest user and establish a session key with another user whose long term key has been compromised by the adversary. The proposed protocol is KCI-resilient as proved formally in the next section.


## 7.6. Forward Secrecy

Forward secrecy implies that if the long term key of the entity is compromised then the secrecy of the earlier session keys generated is not affected. In case of HGMAKA, the session keyKASMEGi-j is computed as a function of the long term secret key KGi-j as well as RHSS and SQN, both of which changes for each session. Thus, even if KGi-j is compromised, it will be difficult for the attacker to correlate both the correct RHSS and SQN to be used for generating a past session key. Hence, the protocol has forward key secrecy.


## 7.7. Formal Verification Using AVISPA

The main goal of the proposed protocol is to provide mutual authentication between the MTCD and the MME/HSS and secured key agreement between the entities. The formal verification of the proposed protocol is tested onAutomated Validation of Internet Security Protocols and Applications (AVISPA) [31]. AVISPA is a tool for automatic security analysis of protocols represented inHigh Level Protocol Specification Language (HLPSL) and evaluated using automatic deduction techniques. We have modeled three roles, MTCD, Gateway, and MME, using HLPSL. As the MME and HSS have a secured channel between them, so we have integrated the roles of MME and HSS into a single role. The On-the-Fly Model Checker has been used to test our protocol. The goals of the protocol are given in Algorithm 1 and the output is given in Algorithm 2. The HLPSL roles for MTCD and MME are given in Appendix A as Algorithms 3 and 4.Algorithm 1:Goal specification of proposed protocol.
goal secrecy_of kasme secrecy_of gtkg1 authentication_on mtcd_mme_rg11 authentication_on mtcd_mme_rhss end goalAlgorithm 2:Results from OFMC.
% OFMC % Version of 2006/02/13 SUMMARY SAFE DETAILS BOUNDED_NUMBER_OF_SESSIONS PROTOCOL /home/span/span/testsuite/results/Proposed.if GOAL as_specified BACKEND OFMC COMMENTS STATISTICS parseTime: 0.00s searchTime: 0.21s visitedNodes: 8 nodes depth: 3 pliesAlgorithm 3:Role of MTCD in HLPSL.
role mtcd(MTCD,GW,MME: agent, Kg1_1,Gkg1: symmetric_key, IMSIg1_1, GIDg1:text, HMAC: function, F1,F2,F3,F4,F5,F6,KDF:function, SQN:text, SND,RCV,SNDG,RCVG:channel(dy)) played_by MTCD def= local State:nat, Rg1_1:text, MACg1_1:text, GMACg1_1:text, Authhss,Rmme,Rhss,Macmme:text, SNID:text init State:=0 transition ( 1 )    State=0 ∧ RCV(start)=|> State':=3∧ Rg1_1':=new() ∧ MACg1_1':= HMAC(IMSIg1_1.Rg1_1')_Gkg1 ∧ GMACg1_1':= H M A C(IMSIg1_1.Rg1_1'.MACg1_1'.GIDg1)_Gkg1 ∧ SNDG(IMSIg1_1.Rg1_1'.MACg1_1'.GIDg1.GMACg1_1') ∧ witness(MME,MTCD,mme_mtcd_rg11,Rg1_1') ( 2 )    State=3 ∧ RCV(Rhss'.(HMAC(Rhss'.GIDg1)_(F1(Rhss'.SNID)_Gkg1)).Rmme'.(F2(Rmme'.(Rhss'.(HMAC(Rhss'.GIDg1)_ (F1(Rhss'.SNID)_Gkg1))))_(F1(Rhss'.SNID)_Gkg1))) =|> State':=6∧ SNDG(F6(Rhss'.Rg1_1)_Kg1_1) ∧ request(MTCD,MME,mtcd_mme_rhss,Rhss') ∧ request(MTCD,MME,mtcd_mme_rmme,Rmme') end roleAlgorithm 4:Role of MME in HLPSL.
role mme(MTCD,GW,MME: agent, Kg1_1, Gkg1: symmetric_key, IMSIg1_1, GIDg1:text, HMAC: function, F1,F2,F3,F4,F5,F6,KDF:function, SQN:text, SND,RCV:channel(dy)) played_by MME def= local State:nat, SNID,Aggmacg1,Aggres,Rhss, Macg1:text, GTKg1,Kasmeg1_1:symmetric_key, Authhss:text, Akg1_1,Ckg1_1,Ikg1_1,Xresg1_1, Rmme,Rg1_1,Macmme:text, init State:=3 transition ( 1 )       State=3 ∧ RCV(IMSIg1_1.Rg1_1'.GIDg1.(xor(Aggmacg1,HMAC(IMSIg1_1.Rg1_1')_Gkg1)).SNID) =|> State':=5∧ Rhss':=new() ∧ GTKg1':=F1(Rhss'.SNID)_Gkg1 ∧ secret(GTKg1',gtkg1,MME,MTCD) ∧ Macg1':=HMAC(Rhss'.GIDg1)_GTKg1' ∧ Authhss':= Rhss'.Macg1' ∧ Akg1_1':= F5(Rhss')_Kg1_1 ∧ Ckg1_1':= F 3(Rhss')_Kg1_1 ∧ Ikg1_1':= F4(Rhss')_Kg1_1 ∧ Kasmeg1_1':=KDF(xor(SQN,Akg1_1'),Ckg1_1',Ikg1_1',SNID) ∧ secret(Kasmeg1_1',kasme,MTCD,MME) ∧ Xresg1_1':= F6(Rhss'.Rg1_1')_Kg1_1 ∧ Rmme':= new() ∧ Macmme':= H M A C(Rmme'.Authhss')_GTKg1' ∧ SND(Authhss'.Rmme'.Macmme') ∧ witness(MME,MTCD,mtcd_mme_rmme,Rmme) ∧ witness(MME,MTCD,mtcd_mme_rhss,Rhss) ( 2 )      State=5 ∧ RCV(xor(Aggres,F6(Rhss.Rg1_1')_Kg1_1)) =|> State':=6∧ request(MTCD,MME,mme_mtcd_rg11,Rg1_1') end role


## 7.8. Formal Protocol Analysis

The foundation of the security proof of the proposed protocol lies in Shoup’s formal security model [32] for secure Mutual Authentication and Key Agreement using the simulation based technique. In [33] Zhang suitably modified Shoup’s model to fit the mobile communication scenario. Further, Huang et al. in [34, 35] also used Zhang’s model to present a provably secure AKA protocol for UMTS. The authors have based their security proof on Zhang’s model. In Zhang’s simulation based model, the proof of security is arrived at by comparing the performance of an adversary in a real protocol execution (real world) and an ideal scenario (ideal world) which is assumed to be secure by definition. The protocol is said to be provably secure if it is not possible to distinguish between the actions of the attacker in the real world and the ideal world.As per Shoup’s model, the MTC scenario involves two types of communication channels: a secure (assumed) channel between network entities and an insecure wireless channel between the MTCD entities and the network entities. The latter is under the full control of the adversary who can read, modify, and replay the messages transmitted over the channel. The adversary can set up and initiate multiple sessions between MTCD and network and also acquire session keys and apply it on some mathematical function. The activities of the adversary are captured under two scenarios: ideal world and real world. The security of the proposed protocol is proved by comparing the actions of the adversary in the two worlds and proving that the adversary cannot do any more harm in the real world than it would do in the ideal world. AppendixB contains the descriptions of the ideal and real world as well as certain preliminary definitions.Security Proof. Each entity in the proposed protocol possesses a random number generator which produces random numbers, RGi-j (for all i and j) and RHSS, for the entity instances. Let all random numbers be selected randomly in A and E1 is the event that TA is collision-free; we get(14)Pr⁡E1-≤ni222-RGi-j+2-RHSS,where ni is the count of instances created by A and |RGi-j| and |RHSS| are lengths of the respective random numbers and are polynomial in k, and then Pr⁡E1- is negligible.Lemma 1.
For real world adversaryA with collision-free (assumed) transcript TA and independent function family f2 assumed to be collision resistant in TA, the probability of the event E2- (E2 is the event that TA is authentic) is given by(15)Pr⁡E2-≤ni2×Advf2macp,n,where p=O(t) and n=O(ni) and t is the execution time of A.Proof.
ForTA to be nonauthentic, we must have at best one instance that has accepted based on a stimulus sent by a noncompatible instance. To prove this we show that upper bound on the probability of TA being nonauthentic is given by (15) and the proof proceeds as follows.
Case 1. Say, the network entity instance Ii′j′ accepted on receipt of aggregate message aggMGi∥aggMACGi. We try to prove that the stimulus was sent by a compatible MTCD entity. If Ii′j′ has accepted, that means that the MAC verification has been successful. However, the identity IMSIGi-j of each MTCD entity instance in the group is used in the computation of MAC. Since the IMSI contains the HN identity embedded in it, if Ii′j′ accepts then it could only be on stimulus sent by a compatible MTCD instance. Let F be the adversary for Message Authentication Code f2 with oracle access to f2K where K is a randomly selected key. Let PIDi′j′=IMSIi′j′ of user U and U might be initialized by F. F starts its execution by picking keys for all users other than U and proceeds as in the real world. If F needs access to the MAC function f2K under the key of U, the same is provided by the corresponding oracles. Further, the evaluation of functions f1,  f3,  f4,  f5,  f6, and KDF with U’s key is realized through returning a constant or random number by F. Say, Ii′j′ accepts at some point and F outputs aggMACGi and the message aggMGi and stops else F stops with a null string as output.
LetSucc(F,f2) be the event that F outputs aggMAC and a message which has not been given to the oracle f2K as a query. Let the event that Ii′j′ has accepted on stimulus by noncompatible instance be represented by Ei′j′. If Ei′j′=1 then the adversary has been successful in forging the MAC for the given message. Thus, (16)Pr⁡Ei′j′=1≤Pr⁡SuccF,f2=1(17)hence,Pr⁡Ei′j′=1≤Advf2macp,n,where p=O(t) and n=O(ni).
Case 2. Say, MTCD instance Iij accepted on stimulus AUTHHSS. Let the event that Iij accepted on stimulus from a nonnetwork entity be denoted by Eij and let the event that Iij accepted on stimulus from a noncompatible network entity Ii′j′ be denoted by Eij′. If Eij′ has occurred then Ii′j′ must have received aggMGi∥aggMACGi before sending AUTHHSS. As TA is collision-free RGi-j could be generated only by Iij which implies that the adversary has successfully forged one or more MACs in aggMAC. Thus,(18)Pr⁡Eij′=1≤Advf2macp,n.If Eij has occurred then the adversary was successful in forging the MAC for the message RHSS. An execution of A results in an adversary F′ for f2 such that the event of Iij accepting results in F′ ends with output MACHSSGi and RHSS. Thus in (18), we have Pr⁡Eij=1≤Pr⁡(SuccF′,f2=1). Hence,(19)Pr⁡Eij=1≤Advf2macp,n.Therefore, the upper bound on the probability that MTCD instance Iij accepted on a stimulus from a network instance noncompatible with it is given by (20)Pr⁡Eij=1+Pr⁡Eij′=1≤2×Advf2macp,n.Case 3. Let the network instance that accepted on stimulus aggRESGi be denoted by Ii′′j′′ and Ii′′j′′ had earlier sent RHSS. If aggRESGi was not sent by a MTCD instance then the adversary was successful in forging MACHSSGi and it can be proved similar to (17) that the upper bound on this event is Advf2macp,n. Further, say, aggRESGi was output by noncompatible MTCD instance Ii1j1. In this case Ii1j1 received AUTHHSS (which contains RHSS) prior to generating the stimulus. With TA being collision-free, it is not possible for a network entity, other than Ii′′j′′, to output AUTHHSS pointing to an adversary having forged MACHSSGi. Similar to (19) we have an upper bound on this event as Advf2macp,n. Thus, the upper bound on the probability that the stimulus on Ii′′j′′ was from a noncompatible MTCD instance is 2×Advf2macp,n.
We can therefore conclude that the probability of the eventE2- is (21)Pr⁡E2-≤ni2×Advf2macp,n.Lemma 2.
Letf1,  f3,  f4,  f5,  f6, and KDF, represented by H, be a family of pseudorandom functions and H is independent of f2 and collision resistant in the real world adversary A’s authentic and collision-free transcript TA. The algorithm D that distinguishes between the transcript of the real world adversary A and the ideal world adversary A∗ has(22)AdvTA,TA∗distD≤nMTCDAdvHprfp,n,where A initializes nMTCD MTCD entities and ni instances. p=O(t) and n=O(ni).Proof.
A simulator with a real world adversaryA creates an ideal world adversary A∗ and converts the transcript in the real world (TA) into a transcript in the ideal world (TA∗) so that the two are almost identical. The conversion is carried out in the following manner:(i)
An implementation record inTA is copied to TA∗ through an implementation operation.(ii)
A (start session,i,j) record in TA is connection assignment with the ring master replacing the session key KASMEij with idealized random session key Kij.(iii)
An (abort session,i,j) is copied to TA∗ with TA∗ executing (abort session, i,j) operation.(iv)
In case of an application action inTA, all necessary evaluation is made by the ring master using the session key of the ideal world.The main difference between TA and TA∗ lies in the application records. We prove that the assignments made by A∗ are legal and TA and TA∗ are indistinguishable.
Case 1. Let us assume that an MTCD instance Iab receives AUTHHSS and accepts. This message cannot be sent by a noncompatible network entity as TA is authentic. Let the stimulus on Iab be sent by compatible MTCD entity instance Ia′b′. The connection assignment (create, a′, b′) is made by adversary A∗. This connection assignment has not been made earlier as AUTHHSS contains RHSS which the MTCD can verify as not being repeated. Thus, the ring master can substitute the session key KASMEab with an idealized (random) session key Kab.
Case 2. Say Ip′q′, a network instance, receives aggMGi∥aggMACGi. Ipq is an MTCD instance whose individual MAC is included in aggMACGi and Ip′q′ accepts on this stimulus. The connection assignment made by A∗ is (create, p,q). The random session key Kpq is assigned by the ring master instead of KASMEp′q′. Since f2 is collision resistant in TA, hence the received message could be the stimulus only on Ip′q′. Thus, the connection assignment (create, p,q) has not be made earlier. This can be proved similarly for all MTCD instances included in the group MAC construction.
Case 3. Let Ix′y′ be the network instance that receives aggRESGi from a group Gi and let Ixy be a MTCD instance of an MTCD belonging to this group. Assume Ix′y′ has accepted on this stimulus. Since f2 is collision resistant and TA is collision-free, as in Case 2, we can prove that Ixy has accepted on receiving stimulus provided by Ix′y′. Thus, the adversary A∗ has made a valid connection assignment (connect, x,y) with the ring master setting the session key KASMEx′y′ to Kxy.
Each start session record inTA∗ has a connection assignment as seen from the analysis. The main difference between TA and TA∗ now lies only in the application records. For a single MTCD entity initialized by A and algorithm D that distinguishes between TA and TA∗, an adversary D′ for H is such that AdvTA,TA∗distD=AdvHprf(D′). Hence, AdvTA,TA∗distD≤AdvHprfp,n, where p=O(t) and n=O(ni).
FornMTCD MTCD entities with keys KGi-1,KGi-2,…,KGi-nMTCD, D and D′ have access to oracles GKGi-1,GKGi-2,…,GKGi-nMTCD′. Thus,(23)AdvTA,TA∗distD≤nMTCDAdvHprfp,n.H can be replaced by any of f1, f3, f4, f5, f6, or KDF.Theorem 3.
Assume f1, f3, f4, f5, f6, and KDF, represented byH, are pseudorandom function families and f2 is a secure MAC and all functions are independent of each other. Then, HGMAKA is a secure AKA protocol.Proof.
For real world adversaryA with transcript TA, the probability that f2 is collision resistant is negligible as f2 is a secure Message Authentication Code. From Lemma 2, we have a distinguishing algorithm D for ideal world adversary A∗ such that(24)PrDTA=1∣E1∧E2-Pr⁡DTA∗=1∣E1∧E2≤nMTCDAdvHprfp,n.Therefore,(25)AdvTA,TA∗distD=Pr⁡DTA=1-PrDTA∗=1=Pr⁡DTA∣E1∧E2-Pr⁡DTA∗=1∣E1∧E2Pr⁡E1∧E2+PrDTA∣E1-∨E2--Pr⁡DTA∗=1∣E1-∨E2-Pr⁡E1-∨E2-≤PrDTA=1∣E1∧E2-PrDTA∗=1∣E1∧E2+Pr⁡E2-+Pr⁡E1-≤nMTCDAdvHprfp,n+Pr⁡E2-+Pr⁡E1-.Again,(26)Pr⁡E2-=Pr⁡E2-∣E1Pr⁡E1+Pr⁡E2-∣E1-Pr⁡E1-≤Pr⁡E2-∣E2+Pr⁡E1-.Hence,(27)AdvTA,TA∗distD≤nMTCDAdvHprfp,n+Pr⁡E2-∣E1+2Pr⁡E1-.The probabilities Pr⁡E1- and Pr⁡E2-∣E1 are negligible in k (from (14) and Lemma 1); hence AdvTA,TA∗distD is also negligible. Hence it is proved that HGMAKA is a secure AKA protocol.Theorem 4.
HGMAKA is KCI-resilient.Proof.
We consider the case when the long term secret key of a MTCD has been compromised by an adversary. LetI denote a MTCD entity instance who tries to execute the Authentication and Key Agreement protocol with a compatible network entity instance I′. I′ accepts with session key KASMEGi-j on the stimulus aggMGi∥aggMACGi. Now, the adversary corrupts MTCDGi-j and I′ responds with message AUTHHSS. This is intercepted by the adversary and replaced by message AUTHHSS′. Next, I accepts and generates session key KASMEGi-j′ which is the same as the one generated by the adversary and different from KASMEGi-j generated by I′. In the ideal world, the session key generated by I′ was prior to the adversary corrupting the MTCD entity instance. Hence, the only connection assignment possible iscreate. Further, in case of I since it was corrupted by the adversary, the only possible connection assignment iscompromise. However, I cannot be compromised without invalidating the rules of the ideal world as PIDI=IDI′. Also,connect is not possible without KASMEGi-j=KASMEGi-j′. Thus, the real world transcript will be different from the ideal world transcript causing the simulation to be impossible. Therefore, we can conclude that HGMAKA is KCI-resilient.


## 8. Performance Analysis

A comparative analysis of the proposed HGMAKA protocol vis-à-vis ten others discussed in Section4 was performed with respect to three different metrics: (a) number of signaling messages exchanged in executing the protocol; (b) communication cost, that is, the amount of data (in number of bits) transferred in executing the protocols; and (c) computational complexity, that is, the time (in milliseconds) taken for executing the cryptographic operations involved in the protocols, by both the MTCD and the network.An example scenario is given in the annexure. A total population,n, of 10000 MTCDs was considered which may be divided into groups of varying sizes. It is assumed that 1% of this population can generate corrupt authentication requests, represented by nc; that is, 100 corrupt messages can exist. The presence of even a single corrupt message can cause authentication failure resulting in a reauthentication requirement for the entire group. For a group size of nb,the probability that exactly i invalid requests out of nc are present in the group nb follows the hypergeometric distribution as(28)Pr⁡X=i=n-ncnb-incinnbi=0,1,2,…,100.If A represents the event that reverification of the entire group is required, then probability of A is(29)PrA=Pr⁡i=1+Pr⁡i=2+⋯+Pr⁡i=100.This computation has been applied for different group sizes that isnb and the corresponding probabilities are shown in Table 3.Table 3
Probability of authentication failure and success.
Group size 100 200 300 400 500 600 700 800 900 1000 Number of groups 100 50 33 25 20 16 14 12 11 10 P r ( A ) 0.6358 0.8687 0.9532 0.9835 0.9942 0.9980 0.9993 0.9998 0.9999 0.9999 1 - P r ( A ) 0.3642 0.1313 0.0468 0.0165 0.0058 0.0020 0.0007 0.0002 7.63E−05 2.51E−05Thus for a group size of 100, there are 0.6358 probabilities that group reauthentication will be required and 0.3642 that group reauthentication will not be required. As the number of groups decreases resulting in increase in the number of MTCDs in each individual group, the probability of reauthentication (due to failure) increases.These probabilities are taken into account in the performance analysis for the proposed protocol vis-à-vis the existing protocols. Each of the aforementioned metrics was computed for different protocols using the following formula: Quantity of metric required forg groups for successful authentication = y·Pr⁡A·t+x·1-Pr⁡A·t, where t is the number of authentication runs, x is the quantity of metric required for authentication of g groups, and y is the quantity of metric required for reauthentication of g groups.A total oft=10 runs of the authentication protocol have been considered. For each metric, comparison of the various protocols has been performed considering the probabilities mentioned in Table 3.


### 8.1. Number of Signaling Messages

The number of message exchanges that takes place fort rounds of authentication for different number of groups across existing group based protocols vis-à-vis proposed HGMAKA protocol was considered. Only group based protocols are considered as the advantages of group based as against nongroup based schemes have already been shown in existing literature. As the HGMAKA protocol allows group sizes to be large due to the hierarchical nature of the aggregation, two variants of this were compared: one with a single large group with the entire population of 10000 MTCDs as members and the other consisting of multiple smaller groups.The HGMAKA protocol requires the lowest number of signaling messages as compared to the existing protocols as seen in Figure7. Furthermore, the reduction in signaling messages with increasing number of groups is far more significant in the single group variation as compared to the multiple group version, the reason being that even though the probability of reauthentication increases with larger group size, the proposed protocol does not require the entire group to be reauthenticated in case of failure.Figure 7
Comparison of signaling messages per MTCD with increasing number of groups.


### 8.2. Communication Cost

The communication costs of the protocols are computed as the sum of the sizes of the individual messages that are exchanged for a full round of AKA. The parameters used are placed in the annexure for reference; for example, the size of the messages exchanged between Tier 1 and Tier 2 elements, Tier 2 and Tier 3 elements, and Tier 3 and core networks in HGMAKA is added to arrive at its communication cost. The plot in Figure8 compares the communication costs.Figure 8
Comparison of communication cost (in bits) per MTCD with increasing number of groups.HGMAKA protocol, with a single group, requires the least communication cost which is significantly lower as compared to others. When considered in multiple smaller group, it still exhibits a low communication cost, with only Choi-AKA and SE-AKA performing a little better.


### 8.3. Computational Cost

For calculation of the computational complexity of the protocols, only significant cryptographic operations like hash, point multiplication, map-to-point, pairing, and so forth were considered. A table has been included in the annexure that lists the execution times of these operations using Crypto++ library on a Celeron 1.1 GHz processor as MTCD and Dual Core 2.6 GHz processor as a network element (MME/HSS) as reported in [16].The plots in Figure9 show that the computation cost exhibited by HGMAKA protocol is low, sharing the same with only three other protocols: MTC-AKA, Choi-AKA, and GAKA.Figure 9
Comparison of computation cost per MTCD at the MTCD and at the network with increasing number of groups.While the main motivation was to reduce the signaling load on the network, HGMAKA is seen to be light even in terms of communication and computation costs.


## 8.1. Number of Signaling Messages

The number of message exchanges that takes place fort rounds of authentication for different number of groups across existing group based protocols vis-à-vis proposed HGMAKA protocol was considered. Only group based protocols are considered as the advantages of group based as against nongroup based schemes have already been shown in existing literature. As the HGMAKA protocol allows group sizes to be large due to the hierarchical nature of the aggregation, two variants of this were compared: one with a single large group with the entire population of 10000 MTCDs as members and the other consisting of multiple smaller groups.The HGMAKA protocol requires the lowest number of signaling messages as compared to the existing protocols as seen in Figure7. Furthermore, the reduction in signaling messages with increasing number of groups is far more significant in the single group variation as compared to the multiple group version, the reason being that even though the probability of reauthentication increases with larger group size, the proposed protocol does not require the entire group to be reauthenticated in case of failure.Figure 7
Comparison of signaling messages per MTCD with increasing number of groups.


## 8.2. Communication Cost

The communication costs of the protocols are computed as the sum of the sizes of the individual messages that are exchanged for a full round of AKA. The parameters used are placed in the annexure for reference; for example, the size of the messages exchanged between Tier 1 and Tier 2 elements, Tier 2 and Tier 3 elements, and Tier 3 and core networks in HGMAKA is added to arrive at its communication cost. The plot in Figure8 compares the communication costs.Figure 8
Comparison of communication cost (in bits) per MTCD with increasing number of groups.HGMAKA protocol, with a single group, requires the least communication cost which is significantly lower as compared to others. When considered in multiple smaller group, it still exhibits a low communication cost, with only Choi-AKA and SE-AKA performing a little better.


## 8.3. Computational Cost

For calculation of the computational complexity of the protocols, only significant cryptographic operations like hash, point multiplication, map-to-point, pairing, and so forth were considered. A table has been included in the annexure that lists the execution times of these operations using Crypto++ library on a Celeron 1.1 GHz processor as MTCD and Dual Core 2.6 GHz processor as a network element (MME/HSS) as reported in [16].The plots in Figure9 show that the computation cost exhibited by HGMAKA protocol is low, sharing the same with only three other protocols: MTC-AKA, Choi-AKA, and GAKA.Figure 9
Comparison of computation cost per MTCD at the MTCD and at the network with increasing number of groups.While the main motivation was to reduce the signaling load on the network, HGMAKA is seen to be light even in terms of communication and computation costs.


## 9. Conclusion

This paper presents a hierarchical group based mutual authentication scheme, HGMAKA, for Machine Type Communication over LTE network. The proposed lightweight symmetric key based HGMAKA protocol introduces an architectural model that utilizes a heterogeneous network of femtocells, mobile femtocell, and capillary network of MTCDs in line with the future 5G networks. The HGMAKA protocol contributes by reducing the overall signaling load on the access network eNBs and offloads the same to the smaller cells. It also significantly reduces the number of signaling message exchanges and the size of the exchanged messages by using a single aggregate MAC in place of individual MACs for each MTCD. The scheme also addresses the important issue with aggregate MACs: single corrupt MAC-message pair invalidating the aggregate MAC, through the use of hierarchical en route filtering of MACs. HGMAKA has been shown to perform significantly better compared to other group based protocols. Moreover, this also releases the overhead of group leader management, which includes selection of group leader, its failure, and so forth, which plagues many of the group based protocols.



---

*Source: 1701243-2017-01-19.xml*