International Association
for Cryptologic Research

Two years ago, at RWC 2023 in Tokyo, we presented attacks on Mega—an end-to-end encrypted (E2EE) cloud storage provider with over 300 million users—and challenges on the path to designing a secure cloud storage protocol with end-to-end guarantees. Now, it is time for an update. In the past two years, analyses of multiple E2EE cloud storage providers revealed serious flaws in most systems, showing that the entire ecosystem is largely broken. At the same time, Google and Apple launched optional client-side encryption for Google Drive and iCloud, thereby making E2EE cloud storage available to their users (albeit with limited functionality). This is great news for privacy-minded users, but given the vulnerabilities that were discovered in most of the smaller providers, one may ask: how do we know if they are secure? Moreover, the vast majority of cloud storage providers still only use server-side encryption, which provides no protection against server compromise. Why is this the case? And what can we do about it? In this talk, we present the first cryptographic model for secure cloud storage in the malicious server threat model, formalizing E2EE cloud storage. Our model and security notions are motivated by our study of real-world E2EE cloud storage providers. We begin by briefly recapping our insights from analyzing MEGA and Nextcloud, identifying the main challenges that they struggled with. We then give a formal syntax for the core functionality of a cloud storage system, focusing on how we tailored the model to capture the real-world complexity of such systems. We continue by showing how we define the expected end-to-end security guarantees against a potentially compromised or malicious cloud server. Finally, we present the first provably secure E2EE cloud storage protocol. Along the way, we hope to inspire a discussion between academia and industry on the remaining challenges of bringing provably secure E2EE cloud storage to practice.

Most applications that deduplicate data first split said data in smaller blocks, called chunks, using content-defined chunking (CDC). CDC cuts the chunks based on a local context window in the data: this means that chunks boundaries are preserved when the data is changed, and enables significant deduplication efficiency gains across applications dealing with large redundant dataset such as backup solutions, software patching systems, and file hosting platforms like IPFS and HuggingFace. However, CDC also introduces a subtle leakage: the length of each chunk leaks information about the data being chunked. This enables fingerprinting attacks, where adversaries exploit chunk length patterns to infer the presence or structure of specific data. Such attacks threaten confidentiality in scenarios ranging from encrypted backups on untrusted cloud servers to data transmitted over encrypted channels. To address these risks, many systems - mainly in the cloud backup setting - have developed bespoke mitigations by mixing a cryptographic key inside the chunking process. We demonstrate the ineffectiveness of these mitigations by presenting efficient key recovery attacks that rely solely on a known plaintext assumption. These attacks entirely circumvent all folklore mitigations except one, re-enabling fingerprinting attacks. To address this, we introduce a formal treatment for Keyed Content-Defined Chunking (KCDC) schemes and propose a provably secure construction that fulfills a strong notion of security. In doing so, we take a step towards making these real-world systems more resilient against leakage.