Similarity-Aware Defense Scheme for Online Brute-Force Attacks in Encrypted Deduplication

Encrypted deduplication is appealing to cloud storage systems, as it provides both storage savings and data confidentiality. Unfortunately, it is vulnerable to brute-force attacks (BFAs), which poses a severe security threat. Server-aided message-locked encryption (MLE) was proposed to mitigate BFAs by deploying a key server to perform rate limiting for key generation requests. However, the existing rate-limiting strategy has several limitations: (1) Vulnerable to Sybil BFAs; (2) Improper rate-limiting thresholds; (3) Inability to identify requests for duplicate data. To address these limitations, we present a similarity-aware rate-limiting strategy based on the following observations: (i) the candidate data used for online BFAs are generally similar; (ii) there won't be a lot of similar data in a short time period in real-world datasets. Then, we propose two similarity-aware defense schemes, SADS-I and SADS-II. SADS-I incorporates data similarity into the key generation and rate limiting using a partially oblivious pseudorandom function (POPRF) but leaks data similarity. SADS-II leverages Intel SGX to protect data similarity and improve performance. Through evaluation using real-world datasets, we demonstrate that our schemes exhibit high data upload performance and provide stronger security protection against online BFAs compared to the existing server-aided MLE.