Improved cloud storage auditing scheme with deduplication

1.   Introduction

1.1.   Background

Nowadays, a large amount of data is generated every day. Securely storing and processing such a large amount of data is a significant challenge ^[1,2,3]. Cloud computing ^[4], artificial intelligence ^[5,6,7,8], and big data techniques ^[9] are promising ways to address this challenge. Among them, cloud storage is essential because it provides a basic way of storing such a vast amount of data. Cloud storage services are becoming increasingly popular, and many people have outsourced their data, including files, movies, and photos, to the cloud. On the one hand, this service is very convenient for users since they do not need to maintain their data locally. Furthermore, they can access it via their mobile devices at any time and from anywhere. For some users, perhaps the most valuable aspect of cloud storage is the assurance that their outsourced data is almost never lost. On the other hand, the security of these outsourced files, movies, and photos cannot be guaranteed by the cloud storage service providers themselves. We need mechanisms to ensure their security, such as encryption, secure search, deduplication, and auditing techniques.

1.2.   Motivation

Due to limited local storage, many data owners want to outsource their files to a cloud server, such as movies, pictures, or music. Before outsourcing the file to the cloud server, the data owners encrypt their files using convergent encryption. Then they outsource the encrypted files to the cloud server. If many data owners (more than the predefined threshold) outsource the same encrypted files to the cloud server, these encrypted files will be the same and denoted as "popular." They will then be deduplicated, and the cloud server will only store one copy for all the data owners. However, if only a few data owners (less than the predefined threshold) outsource the encrypted files to the cloud server, these encrypted files will be denoted as "unpopular, " and they will not be deduplicated. In this way, the cloud server can save on storage costs. The technique of deduplication has been used by many cloud service providers, such as Amazon.

In this paper, we focus on a recently proposed scheme for cloud storage auditing ^[10] with deduplication. It supports different security levels and first introduces the concept of different security levels in this context. In this scheme, the outsourced data is categorized as popular or unpopular. If many data users have outsourced the same file to the cloud, this file can be considered popular. Otherwise, if the outsourced file has not been outsourced by many users, it can be categorized as unpopular. For popular files, Hou et al. suggest using convergent encryption to encrypt them, which is better for deduplication. In this way, cloud service providers can greatly reduce storage space. But for unpopular files, they suggest using probabilistic encryption to achieve semantic security, which is more secure than convergent encryption. Due to the unpopularity of these files, deduplication is no longer necessary. Generally speaking, this proposal is very interesting and valuable. However, we will show that it is not as secure as claimed, as there are some flaws in the scheme that invalidate its protocol's security. We also propose an improved scheme to achieve the security goal.

1.3.   Our contribution

Our contribution can be summarized is two-fold. First, we focus on and demonstrate that the scheme proposed in ^[10] is not secure. Although it is the first relevant work on introducing data popularity to cloud auditing, this scheme is not entirely secure. We also analyze why their scheme has this security flaw and show how to avoid it. Then, we present an improved scheme building on the ideas proposed in ^[10], and provide a thorough analysis of its security. Our scheme addresses the security flaw present in the original proposal, and we explain in detail why it is more resistant to attacks.

1.4.   Organization

In section 1, we provide the background, paper contribution, and organization. In section 2, we discuss related work. In section 3, we review the scheme proposed by Hou et al. In section 4, we present the attack. In section 5, we provide an improved proposal and briefly analyze its security. Finally, in section 6, we conclude the paper.

2.   Related work

There is a large body of research in this context, and we have included the most relevant works to the one presented in this paper. This includes related work on encryption and deduplication techniques, as well as auditing schemes.

1. Encryption and deduplication are important techniques for ensuring the confidentiality and efficient management of outsourced data. While traditional encryption techniques, such as probabilistic public key encryption or symmetric encryption like AES, can achieve semantic security, they are not suitable for implementing functionality such as searching and deduplication. Therefore, novel encryption techniques have been developed specifically for use in cloud computing, including encryption with keyword search ^{[11,12,13,14]}, encryption with access control ^[15,16], convergent encryption with deduplication ^[17,18], and others ^[19].

2. Auditing is an important way to ensure the integrity of the outsourced data. In 2007, Ateneo et al. ^[20] proposed the concept of provable data possession, which aims to allow the cloud servers to provide proof that they have stored the outsourced data well to the cloud users. Furthermore, the proof is very compact and the probability of cheating by the cloud servers is very low. This interesting primitive is actually a new auditing method for cloud storage. Since then, many cloud auditing schemes following this paradigm have been proposed, such as dynamic provable data possession ^[21], proof of retrievability ^[22,23], compact proof of retrievability ^[24], publicly verifiable auditing ^[25,26].

3. In 2016, Yu proposed a cloud data integrity checking scheme with an identity-based auditing mechanism from RSA ^[27]. Later, they proposed identity-based ^[28], attribute-based ^[29], and blockchain-based ^[30] cloud auditing schemes with different properties, and these are very interesting results in this field. Sometimes, the cloud service provider needs to use both auditing and deduplication techniques simultaneously. This way, the cloud service provider can reduce its costs when many users are outsourcing the same file, like popular movies, popular music, etc., and at the same time, the cloud users can ensure that their outsourced data, like files and photos, have not been lost or tampered with.

3.   Description of Hou et al.'s scheme

The system model of Hou et al.'s cloud auditing scheme with deduplication ^[10] is shown in Figure 1. There are three roles in the system: the data owners, the cloud server, and the TPA (third-party auditor). The system operates as follows:

1. To check the integrity of the outsourced files, the data owners, cloud server, and TPA (third party auditor) run the auditing scheme proposed by Hou et al. In this scheme, the data owners compute the authenticators for the data blocks of the files and outsource both the files and the authenticators to the cloud server. When the data owners want to check the integrity of the outsourced files, they delegate this task to the TPA. The TPA launches a challenge-proof game with the cloud server. First, the TPA sends a challenge to the cloud server requesting the server to return the aggregated data blocks and the corresponding aggregated authenticators as proof for the integrity of the outsourced file. Then, the cloud server returns the proof to the TPA, who checks the correctness of the proof using verification equations.

2. However, in the auditing process described above, the cloud server may be malicious. In an effort to reduce storage space, it may delete or modify some outsourced files without being detected by the data owners or the TPA. This means that the malicious cloud server has a strong incentive to delete the outsourced files. In the following section, we will demonstrate an attack on Hou et al's auditing scheme. In this attack, the malicious cloud server is able to forge the authenticator for any data block, which in turn invalidates their auditing scheme.

We will now review Hou et al.'s scheme ^[10]. The core data flow between the data owner and cloud storage server, between the IS and cloud storage server, and between the TPA and cloud storage server can be seen in Figures 2, 3, and 4.

$\mathtt{Notations:}$ Assume the file outsourced to the cloud by the data owner is $F = \{m_1, m_2, \cdots, m_n \}$. Each $m_i = \{m_{i1}, m_{i2}, \cdots, m_{is}\}$, here $1 \leq i \leq n$. The file has its unique file identifier, it is signed with signature $SSig$ to prevent the attackers to modify it. The user (data owner) keeps his secret key for generating $SSig$ and publish the public key for signature.

1. $\mathtt{Setup:}$ With parameter $k$ as the input,

(a) Running $IG(1^k)$ to generate $G_1$ and $G_2$, which are two cyclic multiplicative groups of large prime order $p$. There exists a $e: G_1 \times G_1 \rightarrow G_2$ which is a bilinear pairing.

(b) We denote $h:\{0, 1\}^*\rightarrow \{0, 1\}^*$ as an indexing function, $\phi: Z_p^*\times Z_p^* \rightarrow Z_p^*$ and $\pi: Z_p^* \times \{1, 2, \cdots, n\}$ as a PRF and a PRP, denote $H_1:\{0, 1\}^* \rightarrow G_1$, $H_2:G_2\rightarrow \{0, 1\}^l$, $H_3:\{0, 1\}^*\rightarrow G_1$ as three cryptographic hash functions.

(c) Run $\varepsilon_{\mu}. Setup(k, n, t)\rightarrow (pk, sk, S)$ where $pk = \{p, G_1, G_2, e, H_1, H_2, H_3, h, g, g_{pub}\}$, $n$ key shares $\{x_i\}_{i = 0}^{n-1}$ also generated.

2. $\mathtt{Join:}$ this algorithm is not directly related with the attack.

3. $\mathtt{Upload:}$ this algorithm is not directly related with the attack.

4. $\mathtt{AuthGen:}$ With a ciphertext of file $C = \{c_1, c_2, \cdots, c_n\}$ (specially $C$ is $C_{\epsilon_{\mu}}$ or $C_{\epsilon}$) and a secret key $k_{tag}\leftarrow Z_p^*$, the key $v \leftarrow g^{k_{tag}}$ is computed and published by the user. For each ciphertext block $c_i (1 \leq i \leq n)$, the authenticator $T_i$ is generated by $Ui$ and uploaded to the cloud.

(a) $u_1, u_2, \cdots, u_s$ are $s$ generators of $G_1$, which are chosen by $Ui$, $r\leftarrow Z_p^*$ is also randomly chosen by $Ui$.

(b) Denote ${\tau_0 = name||n||v^r||u_1||u_2||\cdots||u_s}$. Let $ssk\leftarrow Z_p^*$ be signing key and $P_{ssk}\leftarrow g^{ssk}$ the corresponding verification key. These are randomly generated by the user. The file tag is $\tau\leftarrow \tau_0||SSig_{ssk}(\tau_0)$.

(c) For each data block the authenticator is computed by $Ui$ as

(d)

are computed by $Ui$ and sent to $IS$.

(e) The file tag and $\{T_i\}_{1\leq i \leq n}$ are sent by $Ui$ to the cloud.

5. $\mathtt{PopulartityChange:}$ For the popularity threshold $t$, the algorithm is executed whenever the users' number that are submitting the same index is higer than it. The file $F$ is not needed to upload to cloud again by the user $Ui$. $IS$ sends the set $index$ to the cloud, and $Ui$ sends it to the cloud. For all those users with file index in the set $index$, the storage cloud collects decryption shares of them. Then the ciphertext $C_{\epsilon_{\mu}}$ uploaded by these users can be decrypted by the storage cloud. Then, the ciphertext $F_C$ encrypted by the convergent encryption can be obtained by the storage cloud. Thus, as the ciphertext $F_C$ coincides with that for file $F$, the deduplication can be achieved. Finally, $\left\{u_1^{k_{tag}(r(C_{\epsilon_{\mu}})_{i, 1}-(C_{\epsilon})_{i, 1})}, u_2^{k_{tag}(r(C_{\epsilon_{\mu}})_{i, 2}-(C_{\epsilon})_{i, 2})}, \cdots, u_s^{k_{tag}(r(C_{\epsilon_{\mu}})_{i, s}-(C_{\epsilon})_{i, s})}\right\}$ are sent to the cloud by the $IS$. The new data block authenticator^*

^* In ^[10], $T_i' = T_i \cdot \prod_{j = 1}^s u_j^{k_{tag}(rc_{\epsilon {\mu}_{i_j}}-c_{{\epsilon}_{i_j}})}$, but we think it should be $T_i' = T_i \cdot \prod_{j = 1}^s u_j^{k_{tag}(r(C_{\epsilon_{\mu}})_{i, j}-(C_{\epsilon})_{i, j})}$.

for each user are created by the clouds.

6. $\mathtt{ProofGen:}$ With the $\{c_i\}_{1\leq i \leq n}$, $\{T_i\}_{1\leq i \leq n}$ as the input,

● The auditing challenge is generated by $TPA$ as the following:

(a) The file tag gained by the TPA from the cloud and using the key $Pssk$ it checks whether the correctness of signature on $\tau_0$. TPA rejects and halts if the signature is not correct.

(b) Otherwise, filename $name$, $n$, $v^r$ and $\{u_1, u_2, \cdots, u_s \}$ are recovered by the TPA. Then $c$, with $1 \leq c \leq n$ is chosen by him.

(c) Parameters $k_1\leftarrow Z_p^*$, $k_2\leftarrow Z_p^*$ are randomly selected by the TPA.

(d) The challenge $chal = (c, k_1, k_2)$ is sent by the TPA to the cloud.

● The cloud yields $l_t = \pi_{k_1}(t)$ and $a_t = \phi_{k_2}(t)$ wherein $1\leq t\leq c$ after receiving $chal$ from the TPA. And then the proof $T = \prod_{t = 1}^{c} T_{l_t}^{a_t}$, $\eta_{j} = \sum_{t = 1}^{c}a_t\cdot c_{l_t, j}, 1\leq j \leq s$ is computed.

7. $\mathtt{ProofVerify:}$ With the proof $P = (T, \eta)$ and the challenge massage $chal = (c, k_1, k_2)$, TPA computes $l_t = \pi_{k_1}(t)$ together with $a_t = \phi_{k_2}(t)$ wherein $1 \leq t \leq c$. Subsequently, the below verification equations are checked

If one of them passed, the proof is valid.

4.   Attack on the generation and updating of authenticators

The attack is executed according to the following steps:

1. The attacker can be the IS or the cloud. Note here the IS or the cloud can obtain

from $Ui$ by running algorithm $\mathtt{AuthGen}$. Concretely the IS or the cloud can obtain

2. Let $A_1 = u_1^{r k_{tag}}$, $B_1 = u_1^{k_{tag}}$, $A_2 = u_2^{r k_{tag}}$, $B_2 = u_2^{k_{tag}}$, $\cdots, \cdots, \cdots$, $A_s = u_s^{r k_{tag}}$, $B_s = u_s^{k_{tag}}$ then

can be rewritten as

3. With

the attacker can compute $A_1$, $B_1$, $\cdots, \cdots, \cdots$, $A_s$, $B_s$ as following. First let $X_1 = A_1^{(C_{\epsilon_{\mu}})_{1, 1}}B_1^{(C_{\epsilon})_{1, 1}}, X_2 = A_2^{(C_{\epsilon_{\mu}})_{1, 2}}B_2^{(C_{\epsilon})_{1, 2}}, \cdots, X_s = A_s^{(C_{\epsilon_{\mu}})_{1, s}}B_s^{(C_{\epsilon})_{1, s}}$, $Y_1 = A_1^{(C_{\epsilon_{\mu}})_{2, 1}}B_1^{(C_{\epsilon})_{2, 1}}, Y_2 = A_2^{(C_{\epsilon_{\mu}})_{2, 2}}B_2^{(C_{\epsilon})_{2, 2}}, \cdots, Y_s = A_s^{(C_{\epsilon_{\mu}})_{2, s}}B_s^{(C_{\epsilon})_{2, s}}$ then the above can be rewritten as

4. With $X_1$, $Y_1$, the adversary can compute $A_1, B_1$ as following:

then

5.Due to the group order $p$ is publicly known and thus the following holds. Let $Z_1 = \frac{ X_1^{(C_{\epsilon_{\mu}})_{2, 1}} }{ Y_1^{(C_{\epsilon_{\mu}})_{1, 1}} }$ then $B_1 = Z_1^{ \left({(C_{\epsilon})_{1, 1}(C_{\epsilon_{\mu}})_{2, 1} }-{{(C_{\epsilon})_{2, 1}(C_{\epsilon_{\mu}})_{1, 1}} } \right)^{-1}\bmod p}$.

6. Similarly

then

7. Due to the group order $p$ is publicly known and thus the following holds. Let

then

8. By using the above same method, the adversary can compute $A_2$, $B_2$, $\cdots$, $\cdots$, $A_s$, $B_s$.

With $A_1$, $B_1$, $A_2$, $B_2$, $\cdots$, $\cdots$, $A_s$, $B_s$, the adversary can forge any data block's authenticator as the following.

1. First the adversary (the IS or the cloud) can obtain

Note here $c_{ij}$ is public known to all.

2. With

and $A_1$, $B_1$, $A_2$, $B_2$, $\cdots$, $\cdots$, $A_s$, $B_s$, the adversary can compute

Then it forges any data block's authenticator as following

3. Let $\widehat{c_{ij}}$ be the forged encrypted $j$-th sector of the $i$-th data block, then the adversary compute the following:

which is a valid authenticator for the any forged encrypted sector.

4. This means that the cloud can modify the outsouced encrypted data block and its corresponding authenticator to be any other one, which obviously breaks the security of cloud auditing protocols.

5.   The improved cloud auditing scheme with secure generation and updating of the authenticators

First, we will review the core idea for updating the authenticator in ^[10]. Next, we will analyze why this core idea is not secure. Finally, we will present an improved method.

● Now we review the core idea in ^[10]. In the original proposal, $(H(i)\cdot u^{C_i})^x$ is the authenticator. Assume $\sigma_i = (H(i) \cdot u^{C_i})^x$ is the original authenticator and $\sigma_i = (H(i) \cdot u^{C_i'})^x$ is the new corresponding authenticator. Denote $\vartriangle i = \sigma_i'/\sigma_i = \frac{(H(i)\cdot u^{C_i'})^x}{ (H(i)\cdot u^{C_i})^x} = (u^{(C_i'-C_i)})^x = (u^x)^{(C_i'-C_i)}$. Thus, $\sigma_i \cdot (u^x)^{(C_i'-C_i)} = \sigma_i'$. The cloud can compute $\sigma_i'$ given $\sigma_i$ and $(u^x)^{(C_i'-C_i)}$. However, the inverse of $(C_i' - C_i)$ can be calculated by the adversary and thus it is not secure. For example, for $C_i^*$, the corresponding authenticator $\sigma_i^* = \sigma_i \cdot (u^x)^{(C_i'-C_i)(C_i'-C_i)^{-1}\cdot (C_i^* -C_i)} = \sigma_i (u^x)^{(C_i^* -C_i)}$ can be forged. For safety, a blind factor $r$ is introduced. $(u^x)^{(r\cdot C_i'-C_i)}$ is first computed and then uploaded by the user to the storage cloud. New authenticator $\sigma_i' = \sigma_i \cdot (u^x)^{(r\cdot C_i'-C_i)}$ whenever there are changes regarding the data popularity.

● However, the attack above shows that their idea of using $(u^x)^{(r\cdot C_i'-C_i)}$ instead of $(u^x)^{(C_i'-C_i)}$ is still not secure. The reason is the following: if the cloud knows $(u^x)^{(r\cdot C_i'-C_i)}$ for many such $1\leq i\leq n$, it can compute $(u^x)^r$ and $(u^x)$ easily. And thus it can forge any authenticator updates $(u^x)^{(r\cdot C_{any}'-C_{any})}$ easily. Furthermore, it also can forge authenticator $\sigma_i = (H(i) \cdot u^{C_{any}})^x$ easily for any block $C_{any}$, thus their core idea is not secure.

● We improve their core idea by modifying $(u^x)^{(r\cdot C_i'-C_i)}$ to be $((u^x)^{(r_i\cdot C_i'-C_i)}, u^{r_i})$ for many such $1\leq i\leq n$, in this way, the cloud can not compute $(u^x)^{r_i}(1\leq i \leq n)$ and $(u^x)$ easily. And thus it can not forge authenticators any more.

Building upon the improved core idea, we have developed an improved cloud auditing scheme which is outlined below:

1. $\mathtt{Setup:}$ For the sake of comparison, it is worth noting that this algorithm is identical to the corresponding algorithm presented in ^[10].

2. $\mathtt{Join:}$ This algorithm is the same as the corresponding algorithm in ^[10].

3. $\mathtt{Upload:}$ This algorithm is the same as the corresponding algorithm in ^[10].

4. $\mathtt{AuthGen:}$ With a ciphertext of file $C = \{c_1, c_2, \cdots, c_n\}$ (specially $C$ is $C_{\epsilon_{\mu}}$ or $C_{\epsilon}$) and a secret key $k_{tag}\leftarrow Z_p^*$, the key $v \leftarrow g^{k_{tag}}$ is computed and published by the user. For each ciphertext block $c_i (1 \leq i \leq n)$, the authenticator $T_i$ is generated by $Ui$ and uploaded to the cloud.

(a) $u_1, u_2, \cdots, u_s$ are $s$ generators of $G_1$, which are chosen by $Ui$, ${r_1, r_2, \cdots, r_n} \leftarrow Z_p^*$ are also randomly chosen by $Ui$.

(b) Let ${\tau_0 = name||n||v^{r_1}||v^{r_2}||\cdots||v^{r_n} ||u_1||u_2||\cdots||u_s}$. A signing key $ssk\leftarrow Z_p^*$ and the corresponding verification key $P_{ssk}\leftarrow g^{ssk}$ are randomly generated by the user. The file tag is $\tau\leftarrow \tau_0||SSig_{ssk}(\tau_0)$.

(c) For each data block the authenticator is computed by $Ui$ as

(d)

are computed by $Ui$ and sent to $IS$, we denote them as $Upd$.

(e) The file tag and $\{T_i\}_{1\leq i \leq n}$ are sent by $Ui$ to the cloud.

5. $\mathtt{PopulartityChange:}$ This algorithm is the same as the corresponding algorithm in ^[10] except

Note here we use $r_i$ instead of $r$ in the exponentiation.

6. $\mathtt{ProofGen:}$ With the $\{c_i\}_{1\leq i \leq n}$, $\{T_i\}_{1\leq i \leq n}$ as the input,

● the auditing challenge is generated by $TPA$ as the following:

(a) The file tag gained by the TPA from the cloud and using the key $Pssk$ it checks whether the correctness of signature on $\tau_0$. TPA rejects and halts if the signature is not correct.

(b) Otherwise, filename $name$, $n$, ${v^{r_1}, v^{r_2}, \cdots, \cdots, v^{r_n}}$ and $\{u_1, u_2, \cdots, u_s \}$ are recovered by the TPA. Then $c(1 \leq c \leq n)$ is chosen by him, which is the number of the challenged blocks.

(c) $k_1\leftarrow Z_p^*$, $k_1\leftarrow Z_p^*$ are randomly picked by the TPA.

(d) The challenge $chal = (c, k_1, k_2)$ is sent by the TPA to the cloud.

● The cloud computes $l_t = \pi_{k_1}(t), a_t = \phi_{k_2}(t)(1\leq t\leq c)$ after receiving $chal$ from the TPA. And then the proof $T = \prod_{t = 1}^{c} T_{l_t}^{a_t}$, $\eta_{j} = \sum_{t = 1}^{c}a_t\cdot c_{l_t, j}, 1\leq j \leq s$ is computed.

● $\mathtt{ProofVerify:}$ With the proof $P = (T, \eta)$ and the challenge massage $chal = (c, k_1, k_2)$, TPA computes $l_t = \pi_{k_1}(t), a_t = \phi_{k_2}(t)(1 \leq t \leq c)$. Then the below verification equations are checked

If one of them passed, the proof is valid.

The reasons why this improved proposal can resist the attack above is explained as follows: From the $Upd$,

the adversary can not obtain the below values anymore

it can only obtain

from these values, the adversary can not compute $u_1^{r_1 k_{tag}}$, $u_1^{k_{tag}}$, $u_2^{r_2 k_{tag}}$, $u_2^{k_{tag}}$, $\cdots, \cdots, \cdots$, $u_n^{r_n k_{tag}}$, $B_s = u_2^{k_{tag}}$ anymore. Thus the above attack can not work anymore.

6.   Conclusion

In 2019, Hou et al. proposed an auditing scheme. However, in this paper, we demonstrate that their proposal is not secure. The main reason for this is that the core idea of their updated authenticator algorithm is vulnerable. Specifically, if the cloud storage server obtains many values of $(u^x)^{(r\cdot C_i'-C_i)}$ for $1\leq i\leq n$, it can easily compute $(u^x)^r$ and $(u^x)$, which allows it to forge an authenticator $\sigma_i = (H(i) \cdot u^{C_{any}})^x$ for any block $C_{any}$. This attack is a generalization of attacks on many cloud storage auditing protocols based on the discrete logarithm hard problem, as shown in ^[31,32]. It highlights the need for caution when designing cloud storage auditing protocols using cryptographic techniques, as these schemes have rich algebraic structure that may result in vulnerabilities.

To address these shortcomings, we have developed an improved cloud storage auditing scheme based on Hou et al.'s proposal. Our updated authenticator algorithm now uses $(u^x)^{(r_i\cdot C_i'-C_i)}$ for $1\leq i\leq n$, which makes it impossible for the adversary to compute $(u^x)^r$ and $(u^x)$. We have also analyzed why our improved scheme is secure. We hope that our work will help future researchers avoid similar shortcomings in their own cloud storage auditing schemes.

Acknowledgments

This work is supported by the Key Research and Development Program of Xianyang City(No. L2022ZDYFSF061), Scientific Research Funding of Xianyang Vocational & Technical College on "Research on Key Technologies for Secure Outsouced Cloud Storage"(Grant No.2021KJB03).

Conflict of interest

The authors declare there is no conflict of interest.