N Renugadevi

C Mala
email: mala@nitt.edu

Key Agreement with Modified Batch Rekeying for Distributed Group in Cognitive Radio Networks

Keywords: Distributed group, Ternary key tree, One way function, Batch rekeying, Cognitive radio networks

published or not. The documents may come

Introduction

The group oriented applications are in the rise due to rapid developments in internet technology and mobile computing technology. The distributed collaborative applications such as video conferencing, online games and pay-per-view have received special interest in recent years [START_REF] Daghighi | Toward secure group communication in wireless mobile environments: Issues, solutions, and challenges[END_REF]. The unlicensed frequency spectrums are heavily congested due to rapid proliferation of wireless mobile devices working in these spectrum bands.

Cognitive Radio (CR) [START_REF] Mitola | Cognitive radio: making software radios more personal[END_REF] can resolve the spectrum scarcity problem present in the existing wireless networks through dynamic operations such as spectrum sensing, spectrum mobility, etc. The concepts such as Dynamic Spectrum Access [START_REF] Grandblaise | Dynamic spectrum allocation (DSA) and reconfigurability[END_REF] and Secondary Spectrum Access [START_REF] Wyglinski | Cognitive radio communications and networks: principles and practice[END_REF] used in CR Networks (CRNs) allow the unlicensed or CR Users (CRUs) to access the free portions of licensed spectrum bands without disturbing the operations of licensed or Primary Users (PUs).

To ensure privacy [START_REF] Armando | Mobile App Security Analysis with the MAVeriC Static Analysis Module[END_REF] and data confidentiality in distributed and collaborative groups in CRNs, a secure group communication should be provided by establishing the common group key for all the CRUs or members. Group Key Management (GKM) is a building block for providing security in group oriented applications. The distributed GKM or key agreement protocol is suitable for providing security in group communication of distributed and dynamic networks [START_REF] Kiyomoto | Design of categorization mechanism for disaster-information-gathering system[END_REF][START_REF] Pokri | Augmented Reality Enabled IoT Services for Environmental Monitoring Utilising Serious Gaming Concept[END_REF] such as CRNs rather than centralized and decentralized GKM techniques [START_REF] Zou | Secure group communications over data networks[END_REF].

Batch Rekeying (BR) approach reduces the total rekeying cost than Individual Rekeying (IR) as it performs rekeying operations for a batch of join and leave requests at a time to compute the new group key [START_REF] Lee | Distributed collaborative key agreement and authentication protocols for dynamic peer groups[END_REF]. The tree based GKM protocols also help in minimizing both computation and communication cost during rekeying [START_REF] Kim | Simple and fault-tolerance key agreement for dynamic collaborative groups[END_REF].

An alternative method of developing key agreement protocols is to employ an One Way Function (OWF) [START_REF] Diffie | New directions in cryptography[END_REF] rather than a standard Diffie-Hellman primitive to get the group key. OWF helps to achieve computational savings by eliminating the expensive modular exponentiations [START_REF] Boyd | Protocols for authentication and key establishment[END_REF] and therefore OWF is a best candidate for smaller and portable mobile devices in CRNs. Hence, this paper proposes a Ternary Key Tree based OFT (TKTOFT) protocol which integrates OWF, tree based distributed GKM and BR approach to improve the efficiency of both computation and communication involved in tree based GKM protocols.

The rest of the paper is organized as follows. Section 2 explains briefly about the existing OWF based research work. The proposed TKTOFT protocol is discussed in Section 3. Section 4 concludes this paper.

Literature review

This section discusses about available OWF based research work and GKM protocols which can be adopted for CRNs.

An efficient authentication algorithm [START_REF] Rif-Pous | Authenticating hard decision sensing reports in cognitive radio networks[END_REF] based on OWF and symmetric key cryptography was proposed for authenticating local sensing reports in cooperative spectrum sensing in CRNs. In sensing assignment phase, each user generates two one-way chains both for empty decision and occupied decision for each channel.

Sherman and McGrew presented a novel centralized algorithm based on OWF tree namely OFT [START_REF] Sherman | Key establishment in large dynamic groups using one-way function trees[END_REF] for dynamic large groups. The bottom-up construction of key tree halves the number of bits to be broadcast during rekeying.

A key distribution protocol which uses parametric OWF and Euler's totient function [START_REF] Vijayakumar | An effective key distribution protocol for secure multicast communication[END_REF] for achieving high level of security with reduced computation time was developed for secure multicast communication. This paper uses an N-ary tree to minimize the number of multiplications performed during leave operation in the group which in trun reduces the computation complexity.

Zhou et al. proposed a multicast key management technique called Threshold based OFT (TOFT) [START_REF] Zhou | Multicast key management scheme based on TOFT[END_REF]. In this paper, threshold-key mechanism and quad tree were employed to improve the security of algorithm and to reduce the storage as well as rekeying cost.

An efficient centralized GKM was proposed which integrates key trees with one-way key derivation in order to reduce the communication complexity during rekeying operations [START_REF] Lin | Efficient group key management protocol with one-way key derivation[END_REF]. The member itself can derive the key by itself and hence, the total number of keys to be transmitted by the server, i.e., bandwidth of rekeying message was reduced.

A Hash-chain based Authentication Protocol (HAP) [START_REF] Sulaiman | Improving scalability in vehicular communication using one-way hash chain method[END_REF] was designed for vehicular communication in which vehicle can be verified by combining its public key and its hash code. A new GKM for dynamic access control in a large leaf class hierarchy was proposed [START_REF] Odelu | A secure effective key management scheme for dynamic access control in a large leaf class hierarchy[END_REF] which improves previous related research works by using symmetric key cryptography and OWF with less computational and storage overheads.

An image based group key agreement protocol [START_REF] Mao | An image-based key agreement protocol using the morphing technique[END_REF] was designed which employs OWF as an image morphing operation to hide the secret information of each member in the morphed image. An Extended Chaotic Map and password based three Party Authenticated Key Exchange (ECM-3PAKE) [START_REF] Islam | Design and analysis of a three party password-based authenticated key exchange protocol using extended chaotic maps[END_REF] was developed which provides both implicit and explicit key confirmation.

Li et al. proposed a secure BR scheme which employs two algorithms namely, Distributed BR Marking (DBRM) and Secure Distributed BR (SDBR) [START_REF] Li | Secure distributed batch rekeying algorithm for dynamic group[END_REF] for marking the key tree and re-computing the group key respectively.

3 Proposed TKTOFT Protocol Subsection 3.1 explains briefly about OWF and Subsection 3.2 discusses about BR scheme used in the existing SDBR algorithm [START_REF] Li | Secure distributed batch rekeying algorithm for dynamic group[END_REF]. The proposed protocol which uses an improved BR scheme is described in Subsection 3.3.

One Way Function (OWF)

An n-bit hash (h) is a map from a binary string of any arbitrary length to n-bit binary string and the properties of OWF are as follows [START_REF] Rogaway | Cryptographic hash-function basics: Definitions, implications, and separations for preimage resistance, second-preimage resistance, and collision resistance[END_REF]. 1. Preimage resistance: It is easy to compute y for the given x, such that y=h(x). But it is not possible to find x given h(x). 2. Second Preimage resistance: Given an input x, it is not possible to find different y, such that h(y)=h(x).

Collision resistance:

It is not possible to find any two different x and y, such that h(x)=h(y). The security of proposed TKTOFT protocol is based on one way property of hash function.

Existing SDBR and DBRM Algorithms

The SDBR algorithm [START_REF] Li | Secure distributed batch rekeying algorithm for dynamic group[END_REF] uses a combination of binary key tree and OWF for generating the group key in a distributed dynamic collaborative group. It avoids a renewed node to be rekeyed more than once. In DBRM marking algorithm, four cases of join and leave possibilities are discussed.

The distributed OWF based key tree (OFT) used in SDBR is shown in Fig. 1. The leaf nodes in the key tree store individual members' keys as they represent group members. An unique secret key 'k i ' of the member 'i' is generated using the pseudo random number generator and OWF is used to compute its corresponding Blinded Key, BK i , such that BK i = f (k i ), where f is an OWF. The secret key of parent node is computed from the blinded keys of its children, i.e., parent's secret key = F (BK 2i+1 , BK 2i+2 ), where F is a mixing function.

Each member in the key tree maintains the secret keys of nodes in its keypath Fig. 1:

Distributed OFT and also blinded keys of sibling of nodes in its keypath in order to compute the group key. The four cases of DBRM algorithm are discussed as follows.

Case 1. J = L : Join members replace all the leave members. The algorithm marks nodes in the path from sibling nodes of all the leave members to root node as UPDATE.

Case 2. J < L : The locations of J number of leave members with minimum height are selected to replace them with join members. The nodes associated with the remaining leave members are removed from the key tree. The nodes in the path from sibling nodes of replaced and remaining nodes to the root are marked as UPDATE.

Case 3. J > L & L = 0 : Create a key tree 'STB' for new joining members and a new root node. Connect the existing key tree 'STA' as left child of newly created root node and STB as its right child. The root of STA and nodes in the path from sponsor of STB to its root are marked as UPDATE.

Case 4. J > L & L > 0 : All the leave members are replaced by join members. Then, Case 3 is applied for remaining J-L joining members.

The DBRM algorithm has some limitations. In Case 3, insertion of STB as a right child of new root node increases the height of key tree which is shown in Fig. 2. Whenever the system has J > L & L = 0, this algorithm repeats the Fig. 2: OFT after inserting joining members same operation which causes the increase in height of key tree. This step may significantly degrade the performance of BR algorithm when the system has only less number of joining members.

There may be a situation in which the system may have only join members without any leave members. If this happens repeatedly, then after a few rekeying operations, the key tree will become either skewed or unbalanced. The high rekeying cost will be the consequence, irrespective of the relationship between join and leave members in future rekey operation.

Though the system may have one or more leave members in Case 4, after replacing the leave memebrs with L join members, again it will have only join members, i.e., J > L & L = 0. This will make the system to follow Case 3 which will result in further performance degradation.

An Efficient Distributed Key Agreement Scheme (EDKAS) [START_REF] Zhang | EDKAS: A Efficient Distributed Key Agreement Scheme Using One Way Function Trees for Dynamic Collaborative Groups[END_REF] also uses a binary key tree and SDBR outperforms well than EDKAS by modifying all blinded keys which are known to leaving members. The efficiency of BR algorithm depends on the structure of key tree being used. An unbalanced key tree leads to increased number of operations which in turn increases the total rekey-ing cost. The limitations of DBRM algorithm explained above are overcome in the proposed algorithm and is explained in the next subsection.

Proposed TKTOFT Protocol

The efficiency of BR method in this type of tree based GKA depends on the structure of key tree [START_REF] Kim | Simple and fault-tolerance key agreement for dynamic collaborative groups[END_REF]. An efficient BR algorithm should maintain the balanced key tree in order to reduce the rekeying cost. Li et al. proved that the optimal key tree to provide a minimal rekeying cost in the group with unrestricted size during batch update is a ternary key tree [START_REF] Li | Approximately optimal trees for group key management with batch updates[END_REF]. Therefore, the proposed TKTOFT uses the ternary key tree to organize the members in the group which is depicted in Fig. 3. SKT is created for new joining members. Case 3 searches for an appropriate IL and inserts SKT, where the height of KT is not increased. First, it checks the links of root node. If the root has null links, then SKT is inserted as a subtree to the root. If the root is full, i.e., if it has three children, then TKTOFT BP() searches the IN which is closest to root node (CIN).

If CINs in key tree have null links, then CIN with minimum ID is selected as an IL. Else, CIN with minimum height is selected at which SKT can be inserted into KT. After selecting IL, unlike exisiting methods, TKTOFT BP() checks whether the insertion of SKT into KT at this IL will increase the height of KT or not. It will be merged with KT only when there is no increase in height. Otherwise, the root node will be selected as IL.

Algorithm 1 TKTOFT BP(KT, J, L)

This algorithm modifies only Cases 3 & 4 discussed in subsection 3.2

Begin

Step 1 % Modified Case 3 In Case 4, the location of leave member which is closest to root node is selected first as an IL. If the insertion of SKT at this IL increases the height of KT, then an appropriate IL is chosen using Case 3. Else, SKT is inserted at this selected IL. In Fig. 3, when the system has 3 leave members (M3,M8,M12) and 6 join members, it results in a key tree shown in Fig. 4. The location of M8 is selected as an IL, where the SKT created for 6 join members is inserted without increase in height of KT.

If (J > L & L = 0) then Begin Case Create a SKT 5: If (LK(RN ) = φ) then IL=LK(RN) Else If (LK(CIN ) = φ) then IL ← CINMinID Else IL ← CINMinHt Endif If (Ht(N KT ) > Ht(KT )) then IL ← RN Endif Endif End Case Endif Step 2 % Modified Case 4 If (J > L & L > 0) then
Thus, the proposed BR algorithm always chooses the correct IL in order to maintain the balanced key tree. It will select the root of KT as IL only after checking all the possibilities for inserting SKT into KT without increasing the height of KT. Thus, the number of operations to generate the group key tree will be reduced.

If selected IL has null link, then SKT is inserted as its child node. Else, a new Fig. 4: Merging SKT with KT IN is generated. The member stored at IL is connected as a left child and root of SKT is connected as a middle child of newly created IN. In all the cases of algorithm, the sponsor nodes are selected based on the group operations (i.e., join and leave) and positions of both join and leave members in the key tree. All the sponsors in the key tree recompute the group key by updating their secret key.

The remaining members will compute the new group key after receiving the broadcast message from the sponsor.

Results and Discussion

The performance of proposed TKTOFT protocol is analysed and compared with the existing SDBR protocol. The computation complexity is decided based on a) time to generate initial group key and b) number of secret key computation of parent node. The communication complexity is determined based on the number of renewed nodes generated in the key tree [START_REF] Kiyomoto | Design of categorization mechanism for disaster-information-gathering system[END_REF][START_REF] Li | Secure distributed batch rekeying algorithm for dynamic group[END_REF] which are non-leaf nodes whose keys are modified during BR operation.

A group with size 3 5 (243 members) was considered for generating the initial group key. In Figs. 5 and6, x-axis represents the group size. Fig. 5 compares the time to compute the initial group key which is represented in y-axis between SDBR and TKTOFT. From the figure it is inferred that TKTOFT takes less time to generate the group key than SDBR for the same group size.

Fig. 6 depicts the performance analysis between the existing and proposed protocols based on the number of secret key computation of parent node in the key tree. As the number of internal nodes in the ternary key tree is less than binary key tree for the same group size, TKTOFT performs less number of key computations when compared to SDBR protocol.

It is clearly seen from Figs.5 and 6 that, initially there is no big difference between SDBR and proposed TKTOFT. But, when the group is increased, both key generation time and the number of secret key computation in SDBR are also increased. As SDBR uses a binary key tree, the height of key tree is increased even for a small change in group size. The increase in height leads to performance degradation in SDBR.

As proposed TKTOFT uses ternary key tree, its key tree height is minimum when compared to SDBR for the same group size. This reduced height of the key tree helps in minimizing the group key generation time and number of key computation of parent nodes in the key tree. The difference in values of y axis both in SDBR and TKTOFT is more prominent when the group has more number of members. From Figs. 5 and6, it is concluded that the proposed TKTOFT protocol has reduced computation complexity than SDBR protocol. As ternary key tree is being used in this paper, a group with 243 (3 5 ) members was considered during each iteration of batch rekeying. The values for number of join and leave members in the group were varied between 0 and 81 for measuring the total number of renewed nodes which indicates the communication complexity. In Fig. 7, the total number of join members (J) and total number of leave members (L) are represented in x and y-axis respectively. The total number of renewed nodes created in the key tree are mentioned in z-axis of Fig. 7. From the graph, it is understood that TKTOFT has generated less number of renewed nodes than SDBR. The reasons are, a) the height of key tree is minimum, b) maintaining the same key tree height even when J is large with no leave members by choosing the correct insertion location for the sub key tree and c) pruning the leave members and choosing the appropriate location for merging. These prevent increase in key tree height which in turn minimizes the number of nodes to be renewed in the key tree. In this figure also, the significant difference in total renewed nodes can be clearly seen when J and L are large. Because, SDBR replaces the leave members with join members which result in the same key tree height instead of pruning them.

In Case 3 of SDBR, SKT is inserted at the root node without checking the status of KT. This leads to an unbalanced key tree with increased height. These limitations have been overcome in the proposed TKTOFT BP algorithm which gives an improved performance. TKTOFT protocol reduces the number of renewed nodes by choosing the appropriate insertion location to merge the key tree created for joining members and by pruning the leave members when J > L & L > 0.

From the experimental analysis, it is concluded that the modified Cases 3 and 4 of the proposed protocol improves the performance in terms of both computation and communication complexities. Hence, this proposed TKTOFT can be adopted for a distributed group with highly dynamic scenarios in CRNs.

Conclusion

Cognitive radio network can help in providing a quick communication as its nodes solve spectrum scarcity problem prevalent in the present wireless systems. An improved distributed group key agreement called TKTOFT has been proposed in this paper which integrates ternary key tree, one way function and modified batch rekeying algorithm. The experimental results show that TK-TOFT improves the efficiency of both computation and communication. Hence, this proposed protcol is suited for providing quick and secure group communication among cognitive radio devices in distributed collaborative applications in cognitive radio networks.

Fig. 3 :

 3 Fig. 3: Ternary OFTThe leaf nodes indicate CRUs in distributed dynamic group in CRNs, i.e., members in the group. As ternary key tree is being used in the proposed protocol, each set of maximum of three CRUs can form a subgroup which corresponds to a subtree in the key tree.The Subgroup Key (SK) is stored in the intermediate nodes whereas the root node has key for the entire group of CRUs. The rightmost nodes both in subtrees and entire key tree act as sponsors. The subgroup sponsor generates the sub group key and the sponsor of entire group establishes the Group key (G). This paper uses the terms 'members' and 'CRUs' alternatively to mean the group members.An algorithm for Batch Process (BP) operation of the proposed protocol called TKTOFT BP is given in Alg.1. It considers each specific case with the appropriate number of join and leave requests. This BP algorithm improves the Cases 3 and 4 and the remaining Cases are same as in DBRM. The abbreviations used in TKTOFT BP are Key Tree (KT), Sub Key Tree (SKT), Root Node (RN), Link (LK), Internal Node (IN), Closest IN (CIN), Insertion Location (IL), Height (Ht), Minimum Height (MinHt), Node ID (NID), Minimum ID (MinID), New KT (NKT), Leave Members (LMs) and First ID (FID).SKT is created for new joining members. Case 3 searches for an appropriate IL and inserts SKT, where the height of KT is not increased. First, it checks the links of root node. If the root has null links, then SKT is inserted as a subtree to the root. If the root is full, i.e., if it has three children, then TKTOFT BP() searches the IN which is closest to root node (CIN).If CINs in key tree have null links, then CIN with minimum ID is selected as an IL. Else, CIN with minimum height is selected at which SKT can be inserted into KT. After selecting IL, unlike exisiting methods, TKTOFT BP() checks whether the insertion of SKT into KT at this IL will increase the height of KT or not. It will be merged with KT only when there is no increase in height. Otherwise, the root node will be selected as IL.

Fig. 5 :

 5 Fig. 5: Group size Vs Initial group key generation time

Fig. 7 :

 7 Fig. 7: No. of Join & Leave operations Vs Renewed nodes


Nan Guo
email: guonan@mail.neu.edu.cn

Fangting Peng
email: pengft@mail.neu.edu.cn

Tianhan Gao

Secure mobility management for MIPv6 with identity-based cryptography

Keywords: Mobile IPv6, IPSec, IBC, Mobility Management

Mobile IPv6 is an improvement of the original IPv6 protocol, and provides mobility support for IPv6 nodes. However, the security of mobility management is one of the most important issues for MIPv6. Traditional MIPv6 uses IPSec to protect the mobility management, while the dependence on the mechanism of the pre-shared key or certificate limits its applicability. This paper proposes an improved scheme for the original method based on IBC, to protect the mobility management signaling for MIPv6.

Introduction

The development of IPv6[11] has leaded to the rapid popularization of Mobile IPv6 (MIPv6). MIPv6 is a protocol to provide mobile support for IPv6, and it was standardized by IETF in 2004. The security problem has been exposed at the devising of MIPv6. The primary threat comes from fake binding update messages, replay attack and route attack which mainly manifest in the mobility management procedure [START_REF] Tian | Identity-based hierarchical access authentication in mobile IPv6 networks[C]. Communications[END_REF][START_REF] Andersson | Rethinking IP Mobility Management[END_REF]. The main reason derives from no efficient authentication approach between the communication entities. In this paper, we propose a novel encryption and authentication scheme to guarantee the security of MIPv6 mobility management.

In the literatures, [START_REF] Elgoarany | Security in Mobile IPv6: A survey[END_REF] shows that MIPv6 adopts IPSecurity(IPSec) protocol and Internet Key Exchange(IKE) protocol to protect mobile management signaling between mobile node and home agent. However, the method is not efficient as required. [START_REF] Aura | Designing the Mobile IPv6 Security Protocol[J][END_REF] shows that pre-shared key or certificate adopted by the first stage of IKE is not suitable under the mobile environment. It is not realistic to build the infrastructure to satisfy IKE. Besides, using IPSec with IKE would add extra burden for mobile nodes. To solve the problem, [START_REF] Choi | Mobile multi-layered IPsec[END_REF] utilizes multilevel IPSec in MIPv6 to protect mobility management procedure; [START_REF] Yebin | Optimized Method of Constructing IPSec SA between MN and HA in MobileIPv6[END_REF] suggests that a secure association between mobile node and home agent should be built in advance. However, this will bring more cost of security management. Thus, the efficiency of the above schemes still need to be improved.

In traditional public key cryptography, the public key is a string of random characters without any practical information. The Certificate Authority(CA) in PKI infrastructure takes the responsibility of publishing certificates. As a result, the expense of release, storage, verification and revocation is enormous. To solve the problem, the Identity-Based Cryptography(IBC) uses IP address, Email address or any other string that represents the users identity as public keys. Shamir first proposed Identity-Based Encryption(IBE) in 1984. Then in 2001, Boneh and Franklin proposed BF-IBE scheme [START_REF] Boneh | Identity-Based Encryption from the Weil Pairing[J[END_REF]. Later, Identity-Based Signature(IBS) was proposed. In IBS, every communication entity owns a pair of public key and private key. Public key is the identity of the entity and private key is generated and allocated by the trusted third party, Private Key Generator(PKG). Certificate is not necessary during communication, which relieves the computation and storage cost in encryption and authentication. IBC is thus suitable for the security of mobile network [START_REF] Sun | Flow Mobility Management in PMIPv6-based D-MM (Distributed Mobility Management) Networks[J][END_REF].

In this paper, we discuss the typical security protocols in MIPv6 and propose a novel identity-based security scheme for MIPv6 mobility management. The scheme can protect the mobility management signaling among mobile node, home agent and correspondent node in an efficient way.

Preliminaries

MIPv6 Protocol

According to the standardization document RFC3775, MIPv6 protocol is the mobility extension solution for IPv6. It is composed of four entities, Mobile Node(MN), Home Agent(HA), Correspondent Node(CN) and Access Router(AR). MN is allocated a permanent address, i.e. Home of Address(HoA) at the home network, and will get a temporary address, i.e. Care-of Address(CoA), from AR and register it to HA when moving to a foreign network [START_REF] Conta | Generic Packet Tunneling in IPv6 Specification, RFC 2473[END_REF].

IPSec Protocol

IPSec protocol provides confidentiality, data integrity, data authentication and anti-replay services at IP layer. It is an open framework applied widely in a variety of operating environments including mobile network. IPSec supports IKE protocol, which means that key negotiation can be implemented. Besides, encryption and authentication in IPSec guarantee the security of IP data packet. As shown in Fig. 1, IPSec owns a set of approaches for data security such as Authentication Header(AH), Encapsulating Security Payload(ESP), as well as the related cryptography algorithms.

Identity-Based Cryptography

An IBE scheme is generally defined as follows.

IBE.Setup: given a security parameter k as input, output PKG's public key mpk and private key msk.

IBE.Extract: given msk and user's id as input, output user's private key usk. IBS.Sign: given usk and message m as input, output the signature σ on m. IBS.Verify: given mpk, id, m and σ as input, output 1 σ is valid or 0 otherwise.

Our Solution

In this chapter, we propose a secure mobility MIPv6 management scheme based on BF-IBE scheme [START_REF] Boneh | Identity-Based Encryption from the Weil Pairing[J[END_REF] and BF-IBS Scheme [START_REF] Barreto | Efficient algorithms for pairing-based cryptosystems[M[END_REF]. The network architecture and intra-domain security management solution are given in detail.

Network Architecture

In our scheme, the security of the mobility management signaling among MN, CN and HA is guaranteed by IBC. NAI acts as the identifier for every entity. The format of NAI is as user@domain, which would be kept fixed even when the location of MN has changed.

As shown in Fig. 2, the proposed network architecture can be divided into several domains according to the trajectories of MN's roaming. The architecture is composed of CA, PKG, MN, HA and CN. CA is in charge of issuing certificates for PKGs and providing identity authentication service for the communication among them. PKG takes the responsibility of security management in each domain. It maintains public parameters and generates private keys for entities in its domain.

In order to simplify the descriptions of the relevant protocol, Table 1. shows the notations and explanations used in our scheme. The source of message Destination

The final destination of message P ayload

The load of message T ime The message's generation time and allowable maximum delay

Secure Mobility Management Scheme

There are two states in our scheme in terms of MN's location: When MN is at home domain, the scheme is on the initial state, and when MN moves to foreign domain, the scheme is on the mobile state.

As shown in Fig. 3. MN and HA execute Diffie-Hellman key exchange to negotiate the shared symmetric key, which is the same as IKE key agreement that can provide encryption key for IPSec.

At the initial state, key negotiation is relatively simple and there are only two messages because MN and HA are both at the home domain.

(

Conclusion and Future Work

In this paper, we first analyze a series of threats on MIPv6, then propose a secure mobility management scheme based on IBC to protect the signaling among MN, HA and CN. The details of the scheme are explained.

For the next step, we plan to discuss inter-domain secure mobile management scheme and add a new method Return Routability to guarantee the security of MIPv6. Further security analysis is also required to demonstrate the robustness of our scheme.

Fig. 1 .

 1 Fig. 1. The architecture of IPSec

Fig. 2 .

 2 Fig. 2. Network Architecture

  )MN → HA: Key Exchange Request Message format in detail: Code||M N ||HA||Enc(Sig(g m , S M N,0 ), ID HA )||T ime Key Exchange Request is generated by MN and sent to HA. Code is the message type. MN is Source and HA is Destination. g m is the parameter of Diffie-Hellman key exchange in the Payload, where g is public parameter in the home domain and m is the secret value chosen by MN. After sending the message, MN expects to get reply within Time.

Fig. 3 .

 3 Fig. 3. Intra-domain Secure Mobile Management Scheme

Table 1 .

 1 Notations and Explanations

	Notations	Explanations
	M sg1||M sg2	M sg1 connects to M sg2
	Sx,y	Entity X's private key generated by P KGY
	SKx,y	Symmetric key between entity X and entity Y
	IDx	Entity X's ID
	Enc(M sg, IDx) M sg is encrypted by Entity X's public key IDx by BF-IBE
	Sig(M sg, Sx,y)	M sg is signed by Entity X's private key Sx,y by BF-IBS
	Code	Global unique message type for message handling
	Source

  11. Antonio J. Jara, Latif Ladid, and Antonio Skarmeta. The Internet of Everything through IPv6: An Analysis of Challenges, Solutions and Opportunities[J]. Journal of Wireless Mobile Networks, Ubiquitous Computing, and Dependable Applications (JoWUA), Vol. 4, No. 3, pp. 97-118, September 2013.

Acknowledgments This work was supported by National Natural Science Foundation of China under [Grant Number 61402095] and [Grant Number 61300196], China Fundamental Research Funds for the Central Universities under [Grant Number N120404010] and [Grant Number N130817002].


Yana Bekeneva

Konstantin Borisenko
email: borisenkoforleti@mail.ru

Andrey Shorov

Igor Kotenko

Investigation of DDoS Attacks by Hybrid Simulation

Keywords: network security, DDoS attacks, simulation, Flooding

At present protection against distributed attacks of the type "denial of service" (DDoS) is one of the important tasks. The paper considers a simulation environment for DDoS attacks of different types using the combination of a simulation approach and real software-hardware testbeds. In the paper we briefly describe the system architecture and a series of experiments for DDoS attack simulation on transport and application levels. The experimental results are provided, and the analysis of these results is performed.

Introduction

The main goal of DDoS attacks is to make a network resource unavailable to its users. Every year there is an increase in the number DDoS attacks, their power and complexity and hence the harm they can do. According to the report of the Arbor Network [1], more than 60% of companies that have been questioned detected more than 10 DDoS attacks per month in 2014. By the year 2015 the main victims of such attacks are not only servers of different companies and Internet providers, but also their clients. New types of DDoS attacks appear and one of destroyable type of attacks is so called Reflection attacks. These attacks use servers to reflect and amplify the malicious traffic. Nowadays Network Time Protocol (NTP) Reflection attacks using NTP servers became very popular. This means that it is necessary to develop new efficient protection mechanisms against DDoS attacks. Development of new protection systems and testing of real networks for stability to DDoS attacks requires significant hardware, temporal, and financial costs. For this reason in order to perform such experiments we suggest using computer simulation techniques. As against of our previous papers [START_REF] Konovalov | Simulation-Based Study of Botnets and Defense Mechanisms against Them[END_REF][START_REF] Kotenko | Agent-based Modeling and Simulation of Botnets and Botnet Defense[END_REF] we would like to present the system, having included the possibility of using real nodes connected to a virtual network. Such an approach has made it possible to significantly increase the adequacy of DDoS attack simulation on transport and application levels. The system has been verified for a real network. The paper is devoted to the experiments for simulating different types of DDoS attacks in the developed environment. The authors have conducted the experiments of simulating DDoS attacks on transport and application levels. We have simulated the attacks using the protocols of TCP (for SYN-flooding) and UDP (for Chargen and Echo attacks). Attack simulation on an application level has been performed. Section 2 discusses related work. Section 3 specifies formal models of main components. In section 4 we briefly represent the architecture and implementation. Sections 5 and 6 consider examples of experiments. Section 7 and Conclusion outline application of the developed system, main results and further research.

Relevant works

Nowadays a large number of researches and companies are looking for the most efficient ways of service protection against DDoS attacks [START_REF] Kotenko | Agent-based Modeling and Simulation of Botnets and Botnet Defense[END_REF]. In [START_REF] Wang | Advanced DDoS Attacks Traffic Simulation with a Test Center Platform[END_REF] one can get acquainted with a system that uses Spirent Test Center [START_REF]Spirent TestCenter[END_REF] as a device generating traffic. This work contains templates for setting IP-address configurations and attack scenarios. In order to deal with similar tasks it is also possible to use the environment produced in 2014 by the company MazeBolt's Team [START_REF]MazeBolt developer[END_REF]. Using this environment we can generate different types of DDoS attacks of the power up to 20 000 Mbit/sec. [START_REF] Butler | Interop network squares off against controlled 70G bit/sec DDoS attack[END_REF] considers a system developed by Ixia [START_REF]About Ixia[END_REF]. The authors point out that the system makes it possible to provide protection against DDoS attacks of the power of 70 Gbits/sec. in real time. ViSe [START_REF] Årnes | Using a virtual security testbed for digital forensic reconstruction[END_REF] is a system for simulating the main most widespread attacks (40 different scenarios). In [START_REF] Konovalov | Simulation-Based Study of Botnets and Defense Mechanisms against Them[END_REF] we can read about a DDoS attack simulation system, which allows us to simulate a network with different behavior of clients inside it.

The system introduced in our paper allows us to construct virtual networks with a high degree of adequacy. Furthermore, the system makes it possible to introduce any known protection mechanism or the one created by the user. Protection mechanisms can be architecture-dependent, which also allows us to conduct experiments in the way most close to a real network. An important advantage is the possibility of connecting real nodes to a virtual network, which will make it possible to improve the accuracy of the experiments and also to test various settings and types of servers.

Specification of simulation components

In order to understand the structure of the developed simulation components, it is necessary to specify the parameters of their models. The formal model of the network is defined as follows:

1 where NetPar -router's parameters obtained during initialization of Netconf; NPcap -the number of modules to account the traffic flow; Def -a protection algorithm running on the router, this algorithm is implemented in software, the router may use any number of algorithms; ExtDevN -the number of interfaces connected to the external network, required for routers which contain an external host in their local network; DelConf -configuration of packets delay, it is used that the virtual network would have the characteristics of the real network. Model of virtual clients where VictimPath -a path to the victim server (to empower attacks against several servers); Atype -type of the attack against the server: 1 -HTTP Flooding, 2-7different variants of TCP Flooding (SYN, SYN-ACK, RST, UDP, etc.); Lvl -the percent of clients involved in the attack;; Dport -destination port, it is defined in a random manner; DeltaT -the time between packets (in the case of HTTP Flooding it is the time between sessions); AStart, AEnd -start and end time of the attack; various conditions for this interval can be set; MaxP -the maximum number of packet sendings (in the case of HTTP attacks -sessions); SpecialP -specific attack parameters, i.e. for HTTP it is a string of the HTTP query, for TCP -the type of the sender's IP address spoofing. The developed models allow connecting any number of external servers to the virtual network. In the router it is also possible to configure the attack scenarios and the DDoS protection methods.

Architecture and implementation of a simulation system

The architecture of the developed system can be represented as a set of several components (Fig. 1). On the first level of the component hierarchy we can find a discreteevent simulation system OMNeT++ [START_REF]OMNeT++ Discrete Event System Simulator[END_REF]. The second level of hierarchy is represented by a model of a computer network. In order to adjust the network and set package switching the INET library is used [START_REF]INET Framework[END_REF]. The library ReaSE [START_REF] Rease | developer web-site[END_REF] has been completed for topology settings. The authors ceased to support it in 2011 and therefore it was renewed for working with the version OMNeT++ 4.5. The third level contains the models of hosts and routers that are included in the network. The server model is related to both this level and the next one. The fourth level contains the following models developed: an application for performing attacks according to the given scenario; traffic accounting modules; a container for protection algorithms, which can be installed at different network nodes. The models and architecture that have been created were used for developing a hybrid simulation system. In order to provide virtualization of operating systems and computational resources, VirtualBox и Vmware [START_REF]VirtualBox[END_REF][START_REF]developer site[END_REF] have been applied. The possibilities for risk analysis [START_REF] Kotenko | Evaluation of Computer Network Security based on Attack Graphs and Security Event Processing[END_REF][START_REF] Fedorchenko | Integrated repository of security information for network security evaluation[END_REF] can be added.

Examples of settings for created components are shown below. Fig. 2 depicts an example of the topology which includes models Network, NetConf, NetPar. This topology contains a Web-server, routers, gateways and hosts. Every node can be configured by user any time. Example of settings for NetConf is shown in Fig. 3. It should be noted that the range of addresses, the real IP address of the server belongs to, must not overlap with IP addresses of virtual PC. This is to ensure that the server's responses are forwarded to computer of the virtual network. For the experiments we used a computer with the following characteristics: processor is Intel Core i7-3770, 3,4 Ghz, 8 cores; RAM is 15,6 GB DDR3 1600 Mhz; Operating system is Ubuntu 14.04 64-bit. The developed system can also be deployed on the Windows computers. The system currently operates in a single-threaded simulation mode. More than 200 virtual desktops are used, they can attack with the delay of 10 ms. During attack simulations the capacity of the core is 50%.

Experiments with attacks on transport level

The authors have conducted a series of 10 experiments devoted to simulating an attack of the type SYN-Flooding In order to successfully perform a SYN-flooding attack, SYN cookies were switched off on a server. The attack involves 200 hosts generating packages with a frequency of 2 packages per second. 3 hosts are attacking throughout the whole experimental time; the rest are included in an attack in a distributed way from the 10th to the 35th second of the experiment and stop package generation in the interval from the 50th to the 70th seconds. Fig. 4 shows SYN packages sent to a server from a virtual network; the line shows the mean value for 10 experiments and errors are also demonstrated. Server responses are represented in a similar way without repeated sending of SYN-ACK for semiopen connections that have already been established. Only 3 clients applied to the server prior to the 10th second. At the beginning of an attack, on the 10th second, the number of server applications increases because more and more virtual clients are beginning to take part in the attack. Till the 14th second the server manages to process all messages and after that the TCP-stack is overfilled and the server is unable to deal with an increasing flow of applications. Then, beginning from the 50th second and ending with the 70th second virtual clients are leaving the attack. 3 clients are applying to the server again from the 70th on the 88th second. Simulation was stopped at the 88th second. In the period from the 14th second till the 68th second the server did not respond to SYN-packages.

The experiments devoted to attack simulation and based on the UDP-protocol used the network consisting of 100 computers. The attacking packages were sent at a rate of 2 packages per second. The nodes started generation of malicious packages from the 1st to the 20th seconds and terminated the attack from the 40th to the 60th seconds. The Chargen attack is performed by sending a large number of packages to the UDP-port of the 19th victim computer. This causes the server to generate responses consisting of a random set of symbols. Thus, it is possible to reboot the server and reduce its efficiency. The solid line in Fig. 5 shows malicious traffic arriving at an attacking server. Prior to the 20th second we can notice traffic rise, which remains invariable till the 40th second. Then, the number of malicious packages starts to de-crease. The dashed line shows server responses (chargen). After sending some number of responses the server becomes inactive and instead of UDP-packages generates ICMP-messages about the server unavailability. ICMP-messages are shown in the plot by the dot-and-dash line. Traffic resending is reached when a server being attacked has to send return packages to the UDP-port of the 19th sender, which generates return chargen packages to the server. Attack Echo is carried out by sending a large number of packets on the UDP port 7 of a victim computer. This causes the server to generate responses that mimic the incoming packet. As Chargen, this attack leads to overload of the server, and reduces its productivity. Fig. 7 outlines by the solid line the malicious traffic directed to the target server. The traffic increases up to 20 second, then it remains unchanged up to 40 second, and further the number of malicious packets is reduced. The dashed line shows the server's response (echo). After sending a certain number of responses the server becomes inactive and generates ICMP packets (instead of UDP ones) that the service is not available. The graph demonstrates the ICMP packets by the dotted line. Bounced traffic is generated when the attacked server needs to send response packets to the UDP port 7 of the sender, which in turn generates echo response packets to the server. However, the implementation of such an attack cannot achieve infinite loop, as the server, as in the previous case, at some time becomes inactive and does not respond to incoming traffic.

Experiments with attacks on application level

An HTTP-Flooding attack is reached by sending a large number of GET queries to the port 80 and as a result the server becomes incapable of processing other queries. A series of 10 experiments has been conducted and 200 hosts are involved in the attack.

Each host initiates a TCP-connection with an HTTP-query at a rate of 2 packages per second. The queries are processed by the server using the PHP script, which increases the server load. Due to increasing load the server response time increases with the increase of the number of hosts. The host studied is participating in the attack during the whole experiment; other hosts are included in the attack in a distributed way from the 10th to the 40th seconds and stop package generation from the 70th to the 90th second. The plot (Fig. 9) shows the dependence of session duration from its number.

The line shows the mean value for 10 experiments and the errors are also indicated.

As can be seen from the plot, the server load increases during an attack, which makes the query processing time longer. Next NTP Reflection Attack was simulated. It is based on an NTP vulnerability consisting in the fact that if the packet with the request on the latest hosts, which asked for his time, was sent, the NTP-server will send the list of these hosts.

Attack of the type NTP Reflection Attack is implemented the following way. The attacking nodes send the queries get_monlist to an NTP-server; at the same time the source address is replaced with the address of a victim computer. In response to this command the server sends a package containing 600 IP-addresses applying to it earlier. We can gain 500 times attack increase. Consider a scenario when 30% of computers included in a network are participating in the attack (Fig. 10). Each of the attacking nodes generated 2 packages per second. One of the packages was a legitimate query to an NTP-server, i.e. a query for time synchronization. Ad-dress substitution has not been used. The second package contained the command get_monlist, and the IP-address of the source was replaced with the IP-address of a server being attacked. The nodes started sending packages in a distributed way from the 1st to the 20th seconds and terminated the attack from the 40th to the 60th seconds. The plot (Fig. 10) shows time dependencies of the number of queries and responses. The curves of legitimate queries and NTP responses and also get_monlist queries coincide completely and are shown by the solid line. Server responses to the command get_monlist are shown by the dashed line.

Discussion

There are many systems that can simulate DDoS attacks [3, 4, 5, 6, 7, 8, 9, etc.], including systems that generate real traffic for malicious attacks against legitimate sites. But they all have drawbacks that make it difficult to use them. The system presented in [START_REF]Spirent TestCenter[END_REF] cannot be applied to create defense mechanisms. The systems [START_REF]MazeBolt developer[END_REF][START_REF]About Ixia[END_REF] can provide protection against the attacks with limited power; moreover, these systems are very expensive. ViSe [START_REF] Årnes | Using a virtual security testbed for digital forensic reconstruction[END_REF] requires a lot of hard disc space as well as a rather large number of settings for starting and repeating the tests. Our system can be considered not only as a packets generator for various types of DDoS attacks, but also as a research laboratory to investigate existing DDoS attacks and methods of protection against them. The main advantage of the developed system is that it allows creating and testing new distributed architecture specific defense mechanisms against DDoS attacks. This is achieved by the fact that by using this laboratory it is possible to create a large-scale computer networks consisting of thousands of nodes, generating as attacks as well as the legitimate traffic. The ability to use real hosts allows to work not only with the web server, but with any network services without the need for simulation, for example, with cloud computing systems.

The ability to use not emulated, but real software is very important to simulate DDoS attacks with the highest power, as different software can react differently to events taking place in its environment. For example, if the attacked host is an actual web server, it can have different hardware configurations, settings, software installed on it, so that the reaction of one attacked host may differ significantly from others. The virtual (simulated) part of the system also gives the possibilities to configure parameters of network interfaces for clients and routers (connection speed, performance of routers, etc.). Experiments have shown that the developed system allows quite accurate simulation of the behavior of attacked web servers. For example, in the experiments on SYN Flooding the server stops processing all SYN packets from clients. This corresponds to the official CERT document describing SYN Flooding [START_REF]TCP SYN Flooding and IP Spoofing Attacks[END_REF].

Conclusion

In the present paper we have introduced the experiments devoted to simulation of different types of DDoS-attacks. The experiments were conducted in the modeling environment developed by the authors with the possibility of connecting real nodes.

In the paper we have provided the experiments for attack simulation at transport and application levels. The experiments have shown that the developed system performs adequate simulation of the processes occurring in computer networks. The behavior of a server being attacked when it is overloaded corresponds to a real server. All the results and plots obtained during simulation in the developed environment are almost identical to the results that could have been achieved in a real network. The developed system can be used in the field of computer security for creating and testing protection mechanisms against DDoS attacks. In future we plan to use this environment for developing new protection techniques against DDoS attacks.

Fig. 1 .Fig. 2 .Fig. 3 .

 123 Fig. 1. Common architecture of modeling system

Fig. 4 .

 4 Fig. 4. Plot of the traffic log for SYN Flooding against the server

Fig. 5 .

 5 Fig. 5. Server traffic for a Chargen attack

Fig. 6

 6 Fig. 6 shows server traffic during an attack with resending. The solid line indicates incoming malicious packages coming from different UDP-ports except the 19th one. The dot line shows incoming UDP-packages sent from the 19th port of attacking nodes, i.e. obtained during resending. The dashed line (short dashes) shows chargen server responses. The curve of chargen responses almost completely coincides with the curve of resent packages. The line with long dashes shows ICMP-messages of the server telling us that the server is currently unavailable.

Fig. 6 .

 6 Fig. 6. Server traffic for a Chargen attack with resending

Fig. 7 .

 7 Fig. 7. Server traffic under an Echo attack

Fig. 8

 8 Fig. 8 depicts by solid line the incoming UDP packets to the server, including bounced traffic. The dotted line shows Echo responses of the server. It can be seen that when the server responds to Echo requests the incoming traffic includes balanced Echo messages from attacking hosts. Dotted line represents the ICMP packets, indicating that the server is currently inactive.

Fig. 8 .

 8 Fig. 8. Server traffic under an Echo attack with bounced traffic

Fig. 9 .

 9 Fig. 9. Traffic log plot for HTTP Flooding against the server

Fig. 10 .

 10 Fig. 10. Server traffic for an NTP-attack (30% of network computers are in an attack)

Acknowledgements. This research is being supported by grants of RFBR (projects 13-01-00843, 13-07-13159, 14-07-00697 and 14-07-00417), state project "Organization of scientific research" of the main part of the state plan of the Board of Education of Russia, project part of the state plan of the Board of Education of Russia (task # 2.136.2014/K) as well as by Government of the Russian Federation, Grant 074-U01.


Chi-Yao Weng

Sheng-Jie Wang
email: sjwang@mail.cpu.edu.tw

Shiuh-Jeng Wang

A lossless data hiding strategy based on two-dimensional side-match predictions

Keywords: Reversible data hiding (RDH) scheme, Two dimensional histogram distribution, Side-match predictor

The histogram-based reversible data hiding scheme (RDH) generated a one-dimensional (1D) histogram distribution. In this article, based on twodimensional (2D) histogram distribution, a framework of reversible data hiding is proposed by using two side-match predictors, called as Forward side-match (FSM) and Backward side-match (BSM). First, by considering each predicted pixel value, we use two side-match predictors to obtain two prediction error distributions. A slope meter is computed by the differencing of two distributions. Then, a two dimensional histogram is generated by composing of BSM distribution and slope meter. Based on the 2D, more specified spaces can be found to enhance the performance. The experimental results demonstrated that our proposed scheme can achieve better performance in terms of both marked image quality and embedding capacity than that of conventional works.

Introduction

Data hiding is an advanced technology for protecting the message with integrity and security from data transmission in a public network [START_REF] Bender | Techniques for data hiding[END_REF]. The secret information is capable of being hidden into some media, such as an image, audio or video data, using the well-known data hiding scheme. In general, for different target, the data hiding scheme can be classified into two categories. One is non-reversible data hiding scheme [START_REF] Chan | Hiding data in images by simple LSB substitution[END_REF][START_REF] Sun | Data embedding in image-media using weightfunction on modulo operation[END_REF][START_REF] Maleki | Adaptive and non-adaptive data hiding methods for grayscale images based on modulus function[END_REF]. The non-reversible data hiding scheme aims to protect the hidden data for secret communication. The conventional LSBs (least signification bit substitution) is a simple and easy technology of non-reversible data hiding scheme. For example of 1-bit LSBs method, a secret bit is to be embedded into 1-rightmost bit of the cover pixel. The other is reversible data hiding (RDH) scheme [START_REF] Ni | Reversible data hiding[END_REF][START_REF] Tai | Reversible data hiding based on histogram modification of pixel differences[END_REF][START_REF] Tsai | Reversible image hiding scheme using predictive coding and histogram shifting[END_REF][START_REF] Tain | Reversible data embedding using a difference expansion[END_REF][START_REF] Kim | A novel difference expansion transform for reversible data embedding[END_REF][START_REF] Alattar | Reversible watermark using the difference expansion of a generalized integer transform[END_REF][START_REF] Sachnev | Reversible watermarking algorithm using sorting and prediction[END_REF][START_REF] Wu | A high capacity reversible data hiding scheme with edge prediction and difference expansion[END_REF][START_REF] Dragoi | Local-prediction-based difference expansion reversible watermarking[END_REF][START_REF] Li | Efficient reversible watermarking based on adaptive predictionerror expansion and pixel selection[END_REF][START_REF] Yang | Improving histogram-based reversible data hiding by interleaving predictions[END_REF][START_REF] Wang | Reversible data hiding based on two-dimensional prediction errors[END_REF]. The goal of RDH algorithm is to obtain both cover media and hidden data that can be recovered and extracted from stego media. It indicates that the distortion of cover media is intolera-ble when secret message is extracted. RDH can be widely applied into some applications, such as military, medical, or legal document. Many RDH techniques have been developed in present. It can be divided into three categories, namely, histogram-based [START_REF] Ni | Reversible data hiding[END_REF][START_REF] Tai | Reversible data hiding based on histogram modification of pixel differences[END_REF][START_REF] Tsai | Reversible image hiding scheme using predictive coding and histogram shifting[END_REF][START_REF] Tain | Reversible data embedding using a difference expansion[END_REF], difference expansion [START_REF] Kim | A novel difference expansion transform for reversible data embedding[END_REF][START_REF] Alattar | Reversible watermark using the difference expansion of a generalized integer transform[END_REF][START_REF] Sachnev | Reversible watermarking algorithm using sorting and prediction[END_REF][START_REF] Wu | A high capacity reversible data hiding scheme with edge prediction and difference expansion[END_REF], and prediction error [START_REF] Dragoi | Local-prediction-based difference expansion reversible watermarking[END_REF][START_REF] Li | Efficient reversible watermarking based on adaptive predictionerror expansion and pixel selection[END_REF][START_REF] Yang | Improving histogram-based reversible data hiding by interleaving predictions[END_REF][START_REF] Wang | Reversible data hiding based on two-dimensional prediction errors[END_REF]. Ni et al. first proposed a reversible data hiding based on histogram shifting in 2006 [START_REF] Ni | Reversible data hiding[END_REF]. In their method, the histogram distribution is fist generated from an input image. After that, shift and conceal the secret bits into the selected range from histogram distribution. Ni's approach performed a good quality in the stego image because pixel shifting and data concealing are only shifted by one unit. Although histogram-based approach is simplicity and provides high image quality, the number of embedding capacity is limited in the height of peak point. Later on, more efficient algorithms have been invented for improving the embedding capacity limitation [START_REF] Tai | Reversible data hiding based on histogram modification of pixel differences[END_REF][START_REF] Tsai | Reversible image hiding scheme using predictive coding and histogram shifting[END_REF][START_REF] Tain | Reversible data embedding using a difference expansion[END_REF].

The second category is difference expansion. In 2003, Tian proposed a reversible data hiding scheme based difference expansion (DE) [START_REF] Kim | A novel difference expansion transform for reversible data embedding[END_REF]. Tain's method expands the two pixel differencing for data concealing. The maximal embedding ratio based on DE is near to 0.5 bpp (bit per pixel) for one layer embedding. Some researchers are focused on investigation and developing high-fidelity reversible data hiding scheme [START_REF] Alattar | Reversible watermark using the difference expansion of a generalized integer transform[END_REF][START_REF] Sachnev | Reversible watermarking algorithm using sorting and prediction[END_REF][START_REF] Wu | A high capacity reversible data hiding scheme with edge prediction and difference expansion[END_REF].

The histogram-based approach and difference expansion method can perform lossless data hiding, but their performance might be limited within the media context. A basic idea is to review their drawback and develop suitable strategy for promoting the performance in terms of embedding capacity and image quality. The prediction error is a good strategy for both histogram-based approach and difference expansion method to devise a new method of improving the performance. A local prediction reversible data hiding combined prediction error and difference expansion is proposed by Drago and Coltur in 2014 [START_REF] Dragoi | Local-prediction-based difference expansion reversible watermarking[END_REF]. Drago and Colutr's approach utilized least square predictor to obtain the prediction error, then, expend the prediction error for data hiding. This approach has better performance than that of DE method. Later on, more researchers are developed the efficient approaches for obtaining higher performance [START_REF] Li | Efficient reversible watermarking based on adaptive predictionerror expansion and pixel selection[END_REF][START_REF] Yang | Improving histogram-based reversible data hiding by interleaving predictions[END_REF][START_REF] Wang | Reversible data hiding based on two-dimensional prediction errors[END_REF].

In reviewing above-mention reversible data hiding scheme, a framework of reversible data hiding is proposed. Our main contribution is to build 2D histogram distribution based on two side-match predictors and slope meter. 2D histogram distribution can collect more information and find out more spaces for date embedding, resulting in high embedding capacity. Our proposed can be extended into multi-dimensional framework in future.

The rest of the paper is organized as follows. The related works about histogram shifting scheme are briefly introduced in Section 2. Section 3 presents our proposed scheme in detail. The experimental result is illustrated in Section 4. Finally, the conclusion is concludes in Section 5.

Related works

In this subsection, we will review the reversible data hiding scheme based on histogram shifting. Step 1: Generate a histogram distribution H(x) from an inputted image. Where, Figure 1 is an example of histogram distribution using Lena image.

Step 2: Find out a pair-data (P, Z) from the histogram distribution. Notable, P indicates the maximum number of pixels in this distribution. Z means no pixel or minimum pixel in this distribution. Step 3: Shift all the pixels x within the range of peak point and zero point by one unit. Note, the Figure 2 shows the result after pixel shifting operation. The shifting function is given as following.

(1) Figure 2. The example of pixel shifting using Figure 1.

Step 4: Scan all pixels in the cover image, once the pixel value meets the P value, and then, check the secret bits. If the secret bit is "0", the pixel value remains unchanged. If the secret bit is "1", the pixels value is changed by one unit according to following data concealing function [START_REF] Chan | Hiding data in images by simple LSB substitution[END_REF] Finally, output all the scanned pixel as the stego pixel (stego image). Notably, the stego pixel can be performed the processes of data extracting and pixel recovering since a pair-data (P, Z) is received. For the data extracting, the secret bit will be extracted when the inputted pixel meets the value of P or P+1. In other words, the hidden bits can be successfully retrieved. For the concept of pixel recovering, each inputted pixel can run the inverse of shifting operation to recover the pixel value as an original pixel.

Our proposed method

In this section, we introduce our reversible data hiding scheme based on 2D histogram modification in detail. The 1D histogram-based approach applied one factor, such as pixel value or prediction error, to generate a factor histogram distribution. Then, modify the highest value in the factor distribution for data concealing. For receiving more efficiency, our proposed scheme uses two prediction error to produce a 2D histogram distribution. More specified cases are to be considered for pursuing more spaces for promoting the embedding capacity. The detail of our data embedding algorithm is shown as below.

Input: Cover image CI with size M N, CI=Ii,j,, i= 0 to M-1, j= to N-1, secret message SMsg=b1b2b3 …bn, bi . Output: Marked-image MI, two pair information (PP0, PZ0) and (NP0, NZ0).

Step 1: Scan the cover image and run two side-match predictor methods, Forward side-match (FSM) and Backward side-match (BSM), to predict the pixel vale in the image.

Step 1.1: The FSM prediction algorithm is shown the subsection, and then, compute the prediction error PE_FSMi,j = PIi,j -Ii,j.

Step 1.1.a: If i = 0 and j = 0, then PIi,j = Ii,j -128.

Step 1.1.b: If i = 0, then PIi,j = Ii,j -Ii,j-1.

Step 1.1.c: If j = 0, then PIi,j = Ii,j -Ii-1,j.

Step 1.1.d: Else, PIi,j = Ii,j -int (average (Ii-1,j +Ii-1,j-1+ Ii,j-1)).

Step 1.2: The Backward side-match (BSM) prediction algorithm is shown the subsection, and calculate the prediction error PE_BSMi,j = PIi,j -Ii,j.

Step 1.2.a: If i = 0 and j = M-1, then PIi,j = Ii,j -128.

Step 1.2.b: If i = 0, then PIi,j = Ii,j -Ii,j+1.

Step 1.2.c: If j = 0 and j ≠ 0 , then PIi,j = Ii,j -Ii-1,j.

Step 1.2.d: Else, PIi,j = Ii,j -int (average (Ii-1,j + Ii,j-1)).

Step 1.3: Obtain each slope meter SM from computing the difference of PE_BSMi,j and PE_FSMi,j, where SMi,j = PE_FSMi,j ─ PE_BSMi,j.

Step 2: Let (SMi,j, PE_FSMi,j) denotes a 2D value, and collect all 2D values to generate a 2D histogram distribution, H(SMi,j, PE_FSMi,j).

Step 3: Find two pair information (PP0, PZ0) and (NP0, NZ0) from 2D histogram distribution. Where a pair information (PP0, PZ0) is selected in the positive regions of 2D histogram distribution. In the same way, a pair information (NP0, NZ0) is picked by the negative positive regions of 2D histogram distribution.

Step 4: Shift all the prediction error PE_FSMi,j by 1 unit according to following function.

(3)

Step 5: Scan all the PE_FSMi,j and fetch each secret bits from secret message SMsg, and then, conceal the secret bitstring into PE_FSMi,j value while SMi,j precisely equals to "0" and the PE_FSMi,j equals to the peak values, PP0 and NP0. The data concealing function is listing as below.

(4)

Step 6: Recover the marked prediction error value (PE_FSMi,j) to be a stegopixel (SPI) according the inverse of Forward side-match (FSM) predictor, where the inverse algorithm is given as below.

Step 6.1: If i = 0 and j = 0, then SPIi,j = PE_FSMi,j + 128.

Step 6.2: If i = 0, then SPIi,j = PE_FSMi,j + Ii,j-1.

Step 6.3: If j = 0, then SPIi,j = PE_FSMi,j + Ii-1,j.

Step 6.4: Else, SPIi,j = PE_FSMi,j + int (average (Ii-1,j +Ii-1,j-1+ Ii,j-1)). All the marked prediction error values are fully to be recovered, the marked image (MI) is therefore outputted.

The data extracting procedure is similar with the data embedding procedure. Two prediction methods, FSM and BSM, are also used in the extracting process. The extracting process is the inverse of the data embedding procedure.

After running the data extracting procedure, the secret message is completely obtained and the image is successfully recovered.

Experiment results

In section, we demonstrate the simulations of our proposed scheme. Five 512×512 images, including Lena, Airplane, Pepper, Boat, and Goldhill (See Figure 3) are used in our simulations. The secret bitstring in our simulation is generated by the random number generator. We also employ the commonly measure function peak-signal-to-noise-ratio (PSNR) and MSE as a evaluate tool for comparing the visual quality between the cover image and marked image. The measure functions are given as following.

(

) ( 8
) 9
where W and H are defined as the width and height of the image. I(x, y) and I'(x, y) indicates the values of cover image and marked image, respectively. The Max means the maximum value of cover image. Here, our cover image is gray level image, thus, the Max value in gray level is 255(=2 8 ). To obtain a better knowledge of how different cover image impact the performance of the proposed RDH scheme, we compare our experimental results with the recent RDH scheme, the comparison result is illustrated in Table 1. From this comparison, our scheme has better performance in terms of high embedding capacity and good image quality than that of existing RDH methods. The side match predictor applied the neighbor pixels to predict the predic-tion value. Generally speaking, in a nature image, the current pixel is very similar with its neighbor pixels. Assume that we use side match manner to predict the value, we can obtain an accuracy prediction. It leads that more and more prediction errors are falling into zero space. This is a reason that our side match predictor explores the advantage of prediction error to create more space for data concealing.

Conclusion

In this paper, based on two side match predictors and two peaks histogram embedding, an efficient reversible data hiding scheme is proposed. The key point is to build 2D histogram based on two side match predictors and slope meter. The slope meter is used to estimate the differencing of two prediction errors. Based on accurate prediction and selecting two peak points, our proposed scheme provides more spaces for enhancing embedding capacity, the evidence can be seen in the performance evaluation. From the experimental result, it shows that our proposed approach is superior over some histogrambased works.

  The histogram shifting scheme, named as histogram-based, is introduced in 2006. Ni et al.'s approach found out that each cover image has its pixel distribution. Firstly, they applied the statistic function to account each pixel number, the histogram distribution is thus generated. Next, find out the range of peak point and zero point from this distribution. In the end, shift and conceal the data into the range of peak point and zero point. The detail algorithm of histogram-based is shown as below. Input: Cover image CI, each pixel value x , secret message SM=b1b2b3 …bn, bi . Output: Stego image SI, a pair information (peak point, zero point).

Figure 1 .

 1 Figure 1. The example of pixel distribution using Lena as cover image

Figure 3 .

 3 Figure 3. The five cover images. (a)Lean; (b)Airplane; (c)Pepper; (d)Boat; (e)Goldhill

Table 1 .

 1 The performance comparison with various approaches

		Ni et al.'s [5]	Tsai et	Li et al.'s	Our approach
			al.'s[7]	[14]
	Lean	0.02	0.18	0.23	0.25
	Airplane	0.07	0.25	0.30	0.29
	Pepper	0.02	0.18	0.24	0.23
	Boat	0.04	0.17	0.19	0.22
	Goldhill	0.02	0.13	0.19	0.17
	Avag. Capacity	0.034	0.182	0.230	0.232
	(bpp)
	Avag. PSNR	48.30	48.7+	48.47	49.32
	(db)

Acknowledgment

This work was supported in part by the Ministry of Science and Technology, Taiwan, under Contract MOST 103-2221-E-015-002-and MOST 104-2221-E-015-001-.


Dirmanto Jap

Jakub Breier
email: jbreier@ntu.edu.sg

Differential Fault Attack on LEA

Keywords: LEA, Fault Attack, DFA

LEA is a symmetric block cipher proposed in 2014. It uses ARX design and its main advantage is the possibility of a fast software implementation on common computing platforms.

In this paper we propose a Differential Fault Analysis attack on LEA. By injecting random bit faults in the last round and in the penultimate round, we were able to recover the secret key by using 258 faulty encryptions in average. If the position of faults is known, then only 62 faulty encryptions are needed in order to recover the key which surpasses the results achieved so far.

Introduction

Today's applications require efficient ciphers that can run on small devices with constrained computing power. Recent trends show an increasing number of services intended for Internet of Things [START_REF] Robles | An IoT based reference architecture for smart water management processes[END_REF]5] requiring both high level of security and fast running speed on embedded devices. For such applications, lightweight cryptography is an ideal choice.

LEA [START_REF] Hong | Lea: A 128-bit block cipher for fast encryption on common processors[END_REF] is a symmetric block cipher, using the ARX design (modular Addition, bitwise Rotation, and bitwise XOR). It offers fast software encryption, comparable to lightweight ciphers, and comes in the same key size variants as AES. There is an exhaustive security analysis report published by Bogdanov et al. [2], stating that the cipher is secure against known cryptanalysis attacks. So far, there was only one attempt to break the cipher using fault analysis method, which requires 300 chosen fault injections for recovering the 128-bit secret key.

In this paper we present a Differential Fault Analysis attack on LEA. We exploit properties of a non-linearity of modular addition operation used in a round function. To recover the key, our attack requires two different positions of fault injections -in the last round and in the penultimate round. By using a random bit-flip model, we were able to recover a 128-bit secret key by using ≈258 faulty ciphertexts in average. If the precise fault position is known, our attack requires only ≈62 faulty ciphertexts in average. Thus, our method overcomes the fault attack on LEA published so far. This paper is organized as follows. First, we provide an overview of related work in Section 2. LEA cipher is described in details in Section 3. Section 4 provides methodology of our fault attack, following by Section 5 which summarizes our simulation results. Finally, Section 6 concludes this work and provides motivation for further work.

Related Work

Since the first publication proposing a fault analysis as a method to retrieve the secret information from the encryption process proposed by Boneh, DeMillo, and Lipton in 1997 [3], this technique became very popular and testing of implementations against information leakage from fault attack has become a standard procedure.

Differential Fault Analysis technique was first introduced by Biham and Shamir [1], using this powerful technique for revealing the DES secret key. Many other techniques using fault injection have been proposed so far, e.g. Collision Fault Analysis (CFA), Ineffective Fault Analysis (IFA), and Safe-Error Analysis (SEA) [4].

There is only one fault attack on LEA published so far, using the Differential Fault Analysis technique. Myungseo and Jongsun [START_REF] Myungseo | Differential Fault Analysis of the Block Cipher LEA[END_REF] used 300 chosen fault injections in order to recover 128-bit secret key. They inject faults into three out of four words in the intermediate state at round 24.

From the attack methodology point of view, the closest attack proposal to this paper is the attak proposed by Tupsamudre et al. [START_REF] Tupsamudre | Differential fault analysis on the families of simon and speck ciphers[END_REF], aiming at SPECK cipher. Since SPECK uses the ARX structure as well, authors aimed at the only non-linear operation, at the modular addition. They were able to recover the n-bit secret key by using n/3 bit faults on average.

LEA Cipher

In this section we will describe a symmetric block cipher LEA, introduced by Hong et al. [START_REF] Hong | Lea: A 128-bit block cipher for fast encryption on common processors[END_REF]. According to security evaluation report [2], LEA is secure against state-of-the-art cryptographic attacks.

The block size of this cipher is 128 bits, key sizes can be 128, 192, or 256 bits. Number of rounds for each key size is 24, 28, and 32, respectively. It is a pure ARX cipher, consisting of modular Addition, bitwise Rotation, and bitwise XOR operations on 32-bit words. We will further describe the design of the 128-bit key size version of the cipher.

Encryption Procedure

First, the 128-bit intermediate value X 0 is set to the plaintext P . Then, a key schedule process creates r round keys. The 128-bit output X i+1 = (X i+1 [0], . . . , X i+1 [3]) of i-th round is computed as:

X i+1 [0] ← ROL 9 ((X i [0] ⊕ RK i [0]) (X i [1] ⊕ RK i [1])) X i+1 [1] ← ROR 5 ((X i [1] ⊕ RK i [2]) (X i [2] ⊕ RK i [3])) X i+1 [2] ← ROR 3 ((X i [2] ⊕ RK i [4]) (X i [3] ⊕ RK i [5])) X i+1 [3] ← X i [0]
The resulting ciphertext is then obtained after r rounds in the following way:

C[0] ← X r [0], C[1] ← X r [1], C[2] ← X r [2], C[3] ← X r [3].
The whole process is depicted in Figure 1.

Key Schedule

Let K = (K[0], K[1], K[2], K[3]) be a 128-bit key. We set T [i] = K[i] for 0 ≤ i < 4. Round keys RK i = (RK i [0], . . . , RK i [5]
) for 0 ≤ i < 24 are then computed as follows:

T [0] ← ROL 1 (T [0] ROL i (δ[i mod 4]), T [1] ← ROL 3 (T [1] ROL i+1 (δ[i mod 4]), T [2] ← ROL 6 (T [2] ROL i+2 (δ[i mod 4]), T [3] ← ROL 1 1(T [3] ROL i+3 (δ[i mod 4]), RK i ← (T [0], T [1], T [2], T [1], T [3], T [1]),
where δ[i] for 0 ≤ i < 8 are key generating constants, obtained from a hexadecimal expression of √ 766995, where 76, 69, and 95 are ASCII codes of 'L,' 'E,' and 'A.'

Attack Methodology

To perform a differential fault attack on LEA, we propose using two single bit flip faults, at X 22 [0] and at X 23 [2]. The propagation of the faults can be observed in Figure 2. We then retrieve the key by exploiting the modular addition operation.

To describe the proposed method, we first show how it works on a normal modular addition. First, let us assume that the operation is done on 32-bit values, A and B. The modular addition could then be expressed as:

D = (A B), D j = (A j ⊕ B j ⊕ c j ),
where j ∈ {0, ..., 31}, and c j is a carry bit from the previous addition with c 0 = 0. The idea is, that the fault could be injected at A, and by observing (A ⊕ A * ) and the pair of correct-faulty outputs (D, D * ), the attacker could retrieve the value of A and B. Here, A * denotes the faulty value of A, where A * k = A k for k ∈ {j, j + 1, ..., j + n} and n ≥ 0. The value k denotes the position of fault(s). If n = 0, then it is a single bit fault, otherwise, it is a multiple consecutive bit fault.

From the output value D and D * , the attacker could also observe D ⊕ D * . The attacker then checks how many N bit difference(s) are in D ⊕ D * . First, we consider the case with only 1 bit difference in (A ⊕ A * ), more specifically, at bit j. Starting from the location of fault j, the attacker calculates N . If the value of N = 1, it can be concluded that the carry bit at bit j + 1 is not flipped and hence, from the left part of the Table 1, we can conclude that the value of B j = c j (highlighted with red color). However, if N 1 > 1, it can be concluded that the carry bit at j + 1 is flipped, and thus, B j = c j . Note that this attack requires that the carry bit c j is known and thus, it relies on the assumption that the 0-th bit could be faulted in the process (since c 0 = 0 is the only known carry from the beginning). Once the values of B j , c j and D j are known, the value A j could be determined (A j = D j ⊕ B j ⊕ c j ), as well as the value c j+1 (by observing the carry bit of A j + B j + c j ).

Next, we consider the case when there are multiple consecutive bit differences at (A ⊕ A * ), in bits j, ..., j + n. First, the attacker needs to determine if the carry bit at the bit j + i (i ∈ {0, ..., n}) is flipped or not. The attacker observes

(D ⊕ D * ) j+i . (D ⊕ D * ) j+i = (A j+i ⊕ B j+i ⊕ c j+i ) ⊕ (A * j+1 ⊕ B j+1 ⊕ c * j+1 ) (D ⊕ D * ) j+i = 1 ⊕ c j+i ⊕ c * j+i
* ) j+i = 1) ⇒ (c j+i = c * j+i ).
Then, the attacker determines the value of the carry bit in the next bit (j + i + 1) using similar approach. The Table 1 summarizes the scenario when the carry values for the current bit and the consecutive bit are flipped or not. To highlight, if the value of the current bit is not flipped and if the value in the next carry bit is not flipped as well, then B j+i = c j+i (left part, highlighted with red color). If the value of the current bit is not flipped and if the value in the next carry bit is flipped, then B j+i = c j+i (left part). On the contrary, if the value of the current carry bit is flipped, and also the value in the next carry bit is flipped, then A j+i = c j+i (right part). If the value of the current bit is flipped and if the value in the next carry bit is not flipped then A j+i = c j+i (right part, highlighted with yellow color). Once the value of either A j+i , or B j+i is known, the other value and the next carry bit c j+i+1 could be determined.

Table 1: Changes of values in modular addition after a bit flip.

First faulty bit

Aj A * j Bj cj cj+1 c * j+1 0 1 0 0 0 0 0 1 0 1 0 1 0 1 1 0 1 0 0 1 1 1 1 1 1 0 0 0 0 0 1 0 0 1 1 0 1 0 1 0 0 1 1 0 1 1 1 1 Consecutive faulty bit Aj A * j Bj cj c * j cj+1 c * j+1 0 1 0 0 1 0 1 0 1 0 1 0 0 0 0 1 1 0 1 0 1 0 1 1 1 0 1 1 1 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 1 0 1 1 1 1 0 1 1 0 1 0

Experiments

We tested the proposed method by conducting an experiment using simulated faults. Here, the attacker uses one fixed plaintext, measured multiple times, and injects fault at different bit locations. Then, he collects all the faulty ciphertexts.

As mentioned earlier, the attacker has to inject faults at two different positions of different rounds. The main target is LEA-128, due to its key structure. Each of the round keys can be segmented into 6 parts, each part consists of 32 bits. In LEA-128, the second, the fourth and the last part (RK i [1], RK i [3], and RK i [5]) are identical, based on the key scheduling. In previous section, it is shown that the attack exploits the modular addition D = (A B).

Phase 1

First, the attacker injects single bit flip fault at X 22 [0], and the fault will propagate to X 24 [0], X 24 [2] and X 24 [3]. The fault propagation will not be affected by the XOR operation with the round keys.

1. The attacker first exploits the difference (

X 24 [3]⊕X * 24 [3]) = (X 23 [0]⊕X * 23 [0]
). Then, he can pinpoint the location of initial fault injected by taking the last bit difference in ROR 9 (X 23 [0]) ⊕ ROR 9 (X * 23 [0]), since the attacker knows that the fault is a single bit flip and the locations of faults have been changed due to a rotation.

Observations

One observation regarding the attack is that the last bit (MSB) could not be obtained because the next carry bit cannot be determined. This condition holds for each part of the key and hence, in total, 4 bits of the key could not be determined. Thus, these remaining key bits have to be brute-forced. Another problem could also occur due to the rotation of the bits. Due to rota- tion ROL 9 , the resulting bit difference might not be consecutive, for example, ROL 9 (0 . . . 01 . . . 1) (110 . . . 01 . . . 1). To mitigate this problem, it could be considered as separate multiple consecutive faults. From the example, the fault can be considered as (110 . . . 0) and (0 . . . 01 . . . 1). Since the attack only considers bits of D and D * which coincide with the faulty bits in A * , the previous method still works.

In Figure 3, we show the number of faults required to retrieve the value of the input of the modular addition. In the case where each bit could be flipped precisely, around 30 faults are required. However, if the bit could be flipped only randomly, more faults are required.

Based on the experiment, if the attacker cannot determine the location of a single bit flip fault, and hence, could only inject faults randomly at single bit, it requires ≈ 130 and ≈ 128 for the first and the second fault respectively in order to determine the last round key, minus the 4 bits mentioned earlier.

However, if the attacker could determine the precise location of a single bit flip, it requires only ≈ 31 and ≈ 31 faults for the first and the second fault respectively. This is because each fault reveals one bit of the key and in each attack, 2 parts of the last round key could be determined. For the previous attack model, more faults are required in order to obtain the value of each bit, similar to the coupon collector problem (Θ(nlogn)). These results were verified by simulating 500 independent experiments on different scenarios.

Conclusions

In this paper we have proposed a differential fault attack on LEA. We used a random bit flip model, aiming at the last two rounds of the cipher. Using this model, we were able to retrieve the secret key with around 258 faulty encryptions in average. However, if the attacker can determine the position of faults, number of faults can be reduced to only 62 faulty encryptions in average. This result overcomes the only known fault attack on LEA published so far which needs 300 chosen faulty encryptions in order to reveal the key.

In the future, we would like to aquire practical results for our fault model, using the software implementation of LEA on a microcontroller, with the laser fault injection technique.

Fig. 1 :

 1 Fig. 1: i -th round function.

Fig. 2 :

 2 Fig. 2: Fault propagation in rounds 23 and 24.

  Known position of faulty bits.

  Unknown position of faulty bits.

Fig. 3 :

 3 Fig. 3: Number of key bits retrieved.