Information Leakage in Encrypted Deduplication via Frequency Analysis: Attacks and Defenses
This addresses a security vulnerability in storage systems for users relying on encrypted deduplication, offering both attack insights and practical defenses, though it is incremental as it builds on existing encrypted deduplication frameworks.
The paper tackles the problem of information leakage in encrypted deduplication systems due to deterministic encryption revealing frequency distributions, enabling inference attacks that infer a significant fraction of plaintext chunks in backup workloads. It proposes attacks exploiting chunk locality and defenses like MinHash encryption and scrambling, which effectively mitigate attacks while maintaining storage efficiency with limited overhead.
Encrypted deduplication combines encryption and deduplication to simultaneously achieve both data security and storage efficiency. State-of-the-art encrypted deduplication systems mainly build on deterministic encryption to preserve deduplication effectiveness. However, such deterministic encryption reveals the underlying frequency distribution of the original plaintext chunks. This allows an adversary to launch frequency analysis against the ciphertext chunks and infer the content of the original plaintext chunks. In this paper, we study how frequency analysis affects information leakage in encrypted deduplication storage, from both attack and defense perspectives. Specifically, we target backup workloads, and propose a new inference attack that exploits chunk locality to increase the coverage of inferred chunks. We further combine the new inference attack with the knowledge of chunk sizes and show its attack effectiveness against variable-size chunks. We conduct trace-driven evaluation on both real-world and synthetic datasets and show that our proposed attacks infer a significant fraction of plaintext chunks under backup workloads. To defend against frequency analysis, we present two defense approaches, namely MinHash encryption and scrambling. Our trace-driven evaluation shows that our combined MinHash encryption and scrambling scheme effectively mitigates the severity of the inference attacks, while maintaining high storage efficiency and incurring limited metadata access overhead.