Secure provable data possession scheme with replication support in the cloud using Tweaks

The advent of emerging computing technologies such as service-oriented architecture and cloud computing has enabled us to perform business services more efficiently and effectively. Cloud storage enables users to remotely store their data and enjoy the on-demand high quality cloud applications without the burden of local hardware and software management. A cloud storage system is considered as a large-scale distributed storage system that consists of many independent storage servers. Cloud computing is a concept that treats the resources on the Internet as a unified entity, a cloud. Users just use services without being concerned about how computation is done and storage is managed. The cloud supports redundant, self recovering and scalable programming models that allows workloads to recover from many hardware and software failures.

Hence organizations and enterprises are showing huge interest in migrating their sensitive and important data to the cloud. More than half of all businesses utilize cloud services, with 95% of the general public using cloud in at least one form, according to a recent study from Soliant Consulting [20]. Cloud usage is expected to become even more widespread in 2017, with Soliant estimating that 36% of all data will be stored in the cloud by the end of 2017.

Cloud service (storage) providers such as Microsoft Azure, Amazon S3 invite data owners to store sensitive data on their storage servers. These providers attracts the data owners by offering various storage and security facilities. Currently, Microsoft’s virtual private storage service [21], Amazon’s virtual private cloud [22] etc., offers virtual private storage space for data storage. The data or the information that are stored in these types of cloud server’s by the data owner is referred as data outsourcing and they are managed by the respective cloud service providers. So when the data or application is being outsourced by an enterprise to the cloud service providers, their privacy becomes a very challenging task because the data owners (the cloud computing clients) have to trust the cloud providers on many fronts, especially on the availability of cloud service as well as data security. Therefore the Service Level Agreements (SLAs) forms an integral part of a data owner’s first line of defense. Further security defenses are hosted along with the other user data on the cloud and are controlled by the service-providers. Thus other than the SLAs user can’t hold a complete control over data security over his own critical data [15].

Data replication is a technique used by organizations to improve the availability of data. The explosive growth of data generated by organizations emphasizes the need for creating a new and advanced approach for data recovery and replication. Organizations need high speed data replication solution for enabling efficient backup and to reduce recovery time. However, because data capacity requirements are growing so rapidly, organizations are migrating to cloud based storage solution for their sensitive data backup and replication. Cloud data replication services provide cost savings and performance improvements. The cloud based data replication systems does not provide any evidence regarding the storage of multiple copies of data. The CSP can collude a single copy of data to make it look like they are storing many copies of the data, whereas in reality they only store a single copy.

Considering all the issues mentioned above we propose our model called “Secure Provable Data Possession scheme with Replication support in the Cloud using Tweaks (SPDPR-Tweaks)” that has the following propertiesThe rest of this paper is organized as follows. In Sect. 2, we present literature survey. Section 3 presents our system model. Section 4 illustrates our integrity preserving storage model and Sect. 5 illustrates our new tweak based PDP-R scheme. In Sect. 6 detailed algorithms for dynamic data support are given. Section 7 explores the challenge–response paradigm and in Sect. 8 we conclude the paper.

Provable Data Possession (PDP) schemes were introduced by Ateniese et al. [3]. PDP is a technique that allows users, and the data owner, to check the integrity of their data without retrieving it. Ateniese et al. [3] have proposed a provable data possession (PDP) scheme that supports data appending operation which allows users to add new blocks at the end of the file. In their scheme the data owner before uploading the data to the cloud will split the File F into equal size blocks {b1,b2,b3,\({\ldots }\),bn}, where n is the total number of blocks. The data owner will generate a unique tag for every outsourced block and store these tags in their trusted storage space. The data blocks are then outsourced in the cloud. During auditing phase the data owner send challenge message that contains the set of data blocks to be verified. The data owner will request the cloud service provider to generate tags for the specified data blocks. The data owner can then verify the response by using tags stored in the trusted storage space. If the returned tags match the stored ones, the data file F is not tampered. The absence of dynamic operations is the major pitfall in this method. To overcome this Erway et al. [9] proposed a scheme that supports dynamic operations on the outsourced blocks using rank-based authenticated skip lists which supports provable updates. This scheme is not efficient due to the use of authenticated skip list.

Xu et al. [12] proposed a new concept to prove the server data possession. In their algorithm, the client creates tags as polynomials and considers the file blocks as coefficients to polynomials. The proof procedure is based on polynomial commitment and uses evaluation in the exponential instead of bilinear maps. This idea is based on Lagrangian interpolation.

Replication is a method adopted in distributed environments like cloud in which data are stored across multiple sites in a network to enhance the availability and minimize the bandwidth consumption. The advantage of data replication is speeding up data access, reducing access latency and increasing data availability (Berl et al. [6], Long et al. [13]). Static replication strategies follow deterministic policies; therefore, the number of replicas and the host node is well defined and predetermined (Long et al. [13], Ghemawat et al. [10]) have proposed a Google File System (GFS) method to grab data replication. They have proposed a static method for replication which provides fast response, high availability, and high efficiency. The limitation of this algorithm is that a fixed replica number is used for all files which may not be the best solution for data.

Cidon et al. [8] have proposed a MinCopysets method which is a simple general purpose scalable replication scheme. MinCopysets has decoupled the mechanisms used for data distribution and durability. MinCopyset method incurs significant overhead on storage operations. Zeng and Veeravalli [19] have presented an optimal load balancing technique for large-scale cloud data centers that are composed of numerous Raw Data Server and many Meta Data Servers connected by arbitrary networks. In their algorithm the number of replicas of each object is based on the demand rate for the object.

Dynamic strategies for data replication in cloud environments is proposed by, Bai et al. [5] they have used Response Time-Based Replica Management (RTRM) to create a replica for automatically enhancing the number of replicas based on the average response time. The major drawback of this method is low reliability, low load balancing and high replication cost. Boru et al. [7] have presented an energy-efficient data replication method in cloud data centers. In this replication approach, every data object is permanently stored at the Central Data Base (CentralDB) and depending on the access pattern, it is replicated in data center DB and Rack DBs.The problem with their approach is the cost of replication is high and updation of replica is very time consuming process. Gill and Singh [11] have presented an algorithm named Dynamic Cost-aware Re-replication and Re-balancing Strategy with the concept of knapsack problem to optimize the cost of replication. This algorithm has less consistency rate and response time.

Multiple-Replica PDP (MR-PDP) technique was proposed by Curtmola [14] which allows the data owner to verify the replicas of the outsourced file available with the CSP.It is the enhanced version of the method that was originally proposed by Ateniese et al. [3]. Pseudo-Random Function (PRF) was used to introduce some randomness in the replicas. Different PRF keys are used to generate multiple data copies. RSA signatures are used for tag generation. The disadvantages are the data is not encrypted, the size of RSA signatures is huge and finally it deals only with static data.

Barsoum et al. [4] proposed a scheme to support multiple replicas and data encryption. The data blocks in each copy are appended to file blocks before encryption. AES encryption scheme is used for data encryption and BLS signatures are used for tag generation. Dynamic data operations are supported with the help of Merkle Hash Trees. The disadvantage of this scheme is if a file has huge number of blocks, then number of nodes in MHT will be huge. The computation and communication overhead is the bottle neck problem to this algorithm performance. Considering all these limitations we present our SPDPR-Tweaks model in the following sections.

Our proposed system model is presented in Fig. 1 and it consists of the following communication parties.

To outsource a file to cloud service provider, the data owner encodes file F using some encoding technique such as erasure code to obtain file blocks Fi \(=i \,0,1,2,{\ldots },n-1\). Thus only a fraction of blocks Fi’s can recover the original file F using the decoding algorithm of the erasure code.

The data owner creates specific number of replicas for a block before doing encryption operation. Tweaks (discussed in Sect. 5) are used to generate unique replicas for every data block. Each replicated block is encrypted with a secret key. The encrypted replicas are outsourced to the storage nodes managed by the cloud service provider S. These storage nodes are maintained in a hierarchical tree based structure by the S and these storage nodes may be located at different locations.

Asymmetric key algorithms are used for encryption. All the authorized users are shared with the valid decryption key. In order to access the data blocks the authorized users request the CSP and download the encrypted blocks from the cloud and decrypt it using the decryption key. The data owner can verify the integrity of the replicas or request a trusted third party auditor to do it. To do so, the data owner can challenge the CSP to verify the integrity of the outsourced replicas for this operation we present a challenge–response scheme in Sect. 7 which is used to verify the integrity of the replicas.

We use the Merkle hash tree (MHT) based storage model for providing security and preserving integrity for all replicas of the outsourced data blocks. MHTs are used to authenticate a set of n replicas with a constant size storage space [1, 2]. A MHT for a set of “n” replicas R1,...,Rn, is a binary tree that has R1,\(\ldots \),Rn as leaves. An interior node of the tree with children C\(_{\mathrm{L}}\) and C\(_{\mathrm{R}}\) is the hash of the concatenation of its children (i.e., h\((\mathrm{C}_{\mathrm{L}} {\vert }{\vert }\mathrm{C}_{\mathrm{R}}\)), for h a collision-resistant hash function. The value stored in the root of the tree thus depends on all the values stored in the leaves of the tree and can be used to authenticate all the leaf values. If the value of the root of the tree is stored by the data owner, then all the leaves of the tree can be authenticated by reading O(log(n)) hashes from the tree. We give example of a MHT that can store a maximum of eight replicas.

The binary tree structured merkle tree model shown in the Fig. 2 has many limitations. If the number of blocks in the file increases then the number of nodes in the MHT will also increase. This problem will become severe when replication of data blocks is essentially needed. The communication, computation overheads will increase and it reduce the performance of the system. To overcome this issue we propose a modified MHT structure, in which we replace the binary tree structure of the MHT to B+ tree structure. B+ Trees are special case of binary trees. It stores all the blocks in the leaf nodes. In a B+ tree there is an intermediary layer with nodes. They do not have actual blocks stored instead they are connected to the leaf node. Only the leaf node contains the blocks in some sorted order. In our approach Leaf nodes are connected through pointers to form a kind of linked list. This linkage helps in efficient traversal of the data blocks. In our approach the new block is always attached to the right hand side of the B+ tree. The B+ tree based MHT structure proposed in our approach has the following advantages.In the Fig. 3 h(bi,R) represents the hashed value for all replicas for the block “i” .The root node contains the hash value for the entire file. It may be noted that a File F is represented as a set of blocks {b\(_{0}\),b\(_{1}\),\({\ldots }\),b\(_{\mathrm{n}}\)}. Figure 4 represents the data access time when replication of data block is done. Comparison is done for the three variations of the MHT namely binary tree, general tree and the B+ tree for the same number of data blocks.

From the graph presented in Fig. 4 it is obvious that B+ tree based MHT approach performs better than the other two approaches. Similarly we have also studied the performance of B+ tree based MHT approach without replication support. Figure 5 shows the access time for data blocks without replication.

We carried out our experiments on text files. The file is divided into a set of data blocks and they are represented as a storage nodes in B+ tree based MHT. We plot the upload and download time for text files in Fig. 6. The block size was typically set as 2 kB for the files. The graph represents the upload and download time for a single data block.

The tweak based PDP-R scheme is used to enhance the security of the storage model discussed in the previous section and to generate unique replicas for a given data block. The tweak based Secure PDP-R algorithm is a three tuple algorithm that consists of three methods namely(a) ASYMKeyGen()

It is an asymmetric key generation algorithm that generates two keys namely public (K\(_{\mathrm{U}})\) and private key (K\(_{\mathrm{R}})\). Private key is kept secret and the public key is shared with all trusted users in the system. This algorithm is executed by the data owner. We use elgammal based public key cryptosystem to generate private, public key pairs [16]. This cryptosystem is based on discrete logarithmic problem. The security of this cryptographic technique depends on difficulty in computing discrete logs in a large prime modules. The key generation part of the elgammal cryptosystem is illustrated as follows:(b) Tweak and replica generation

Tweaks are generated to produce unique replicas for a given block. Tweaks provide strong evidence to ensure that the CSP is possessing all the replicated data copies as agreed upon the SLA and also all the replicated copies are intact. In addition tweaks enhance the security and produce good diffusion. Hence when different tweaks are used with the same plain text and the same key they produce different cipher text. To generate tweaks the data owner generates “n” random numbers by using a pseudo random number generator (PRNG). Let { r\(_{1}\), r\(_{2,}\)r\(_{3}\ldots \ldots \ldots \),r\(_{\mathrm{n}}\)} \(\in \) Z\(_{\mathrm{N}}^{*}\) be the random numbers generated, these “n” random numbers are used for creating “n” replicas for a data block (“n” stands for the agreed number of replicas to be stored by the cloud). Each random number corresponds to creation of one replica for the given data block. Figure 7 presents the diagrammatic representation of tweak generation.

The following algorithm generates tweaks that are attached with the replicated blocks before encryption.

This algorithm is run by the data owner to generate multiple replicas for the given data block. Before generating the replicas the entire file is preprocessed to produce a tag. For all the “m” blocks for a given file F a unique SEED is generated. SEED value will be computed only once i.e at the time of outsourcing the file F to the CSP. SEED is generated as follows:

Once SEED is generated “n” replicas for all the “m” blocks for a given file can be generated by the following algorithm.

Once replicas are generated, they are encrypted and outsourced to the cloud. An asymmetric key encryption algorithm is used for encryption and decryption. Encryption is done with the private key K\(_{\mathrm{R}}\) and the decryption is done with the public key K\(_{U.}\) The encryption algorithm needs the public key K\(_{\mathrm{U}}\) and the message block b\(_{\mathrm{i}}\) as input.The encrypted data blocks are uploaded to the CSP.

These algorithms are run by the data owner to perform any operation on the outsourced data blocks. The data owner sends the Update request to the cloud service provider with the parameters <FileId,BlockId>. The output of this algorithm would be the updated version of the block in the file.

Insertion operation Modification operation Deletion operation

When one block is deleted, indices of all subsequent blocks are moved one step forward thus maintaining the B+ tree structure.

To study the performance of the dynamic data operations on the outsourced blocks we conducted experiments on multiple blocks. These experiments are executed from the data owner side. The update operation includes block insert, modify operations in addition to creation of tweaks. We ran the experiments for block update on a 1 MB file with a file block size of 128 bytes. The experiments are run by inserting and modifying 2 to 50% number of file blocks. The results are depicted in Fig. 10.

Challenge–response is a protocol used by the data owner to verify the integrity of the outsourced blocks in the cloud [17, 18]. Data owner has two options for such verification namely (a) Deterministic (b) probabilistic. In the first approach the data owner challenge the CSP to verify the integrity of the entire outsourced block including the replicas. In later case only a few blocks from all the copies are used for verification. In our approach we use the second method of integrity verification. In probabilistic approach we use only a fraction of outsourced blocks for integrity verification and it accounts for the entire block verification. To choose the blocks for integrity verification we use a pseudo random number generator which generates random number that corresponds to the block number for which the integrity to be verified. The challenge–response protocol has a set up phase in which public parameters are shared between the data owner and CSP these parameters are used during integrity verification. During this phase the data owner computes tweaks T\(_{\mathrm{j}}\) for each block using the tweak generation process.

During the challenge phase the data owner generate a random number that corresponds to the block number for which the integrity has to be verified. In our algorithm the data owner generate a set of random co efficient to challenge the CSP, this property ensures that CSP cannot cheat the data owner by simply sending the response (the same challenge message) without doing any computation on the data stored in CSP side. The challenge and verification between the data owner and the CSP is based on the quadratic residues over the multiplicative cyclic group over modulo N with a generator g. Thus s \(\in _{\mathrm{R}}\) Z\(_{\mathrm{N}}\) is kept secret and the generator g and r are kept public. In Table 1 we present the challenge–response mechanism in detail.

SetupWe present the performance of our challenge–response scheme with other PDP schemes in the Table 2. The performance comparison is made for a file which is split into “m” number of blocks and with “n” number of challenges

Cloud computing is a technology that is continuously growing, and it is expected to successfully change the way we utilize information and communication technology resources. It also raises the demand for trust and security in cloud enabled technologies. Hence security will become more important and will be a decision criterion for enterprises moving services into cloud computing technology. In this paper we listed various security concerns that may arise because of migrating the sensitive data to the cloud by organizations. Generally a data owner may request the cloud service provider to replicate some or all of their sensitive data to increase the availability and to enhance the performance. In the current scenario sufficient protocols are not there to ensure that the cloud service provider is maintaining the required number of replicas based on the SLAs. To overcome such issues we have proposed our “Secure Provable Data Possession scheme with Replication support using Tweaks” scheme. The tweaks generated in our approach helps to generate unique replicas for a block. The proposed encryption method strengthens our approach. We have also suggested a probabilistic challenge–response scheme to verify the integrity of the blocks. Extensive analysis shows that our scheme is provable secure, and the performance evaluation shows that our scheme is better than the existing protocols.