TL;DR
This paper critically analyzes Mylar, a web application framework designed to protect user data from untrusted servers using multi-key searchable encryption (MKSE). The authors demonstrate that Mylar's underlying security model is flawed, making it vulnerable to both passive and active attacks that can reveal sensitive user data and queries, even when the data is encrypted.
What Problem Does This Paper Address?
Modern web applications often store sensitive user data on servers. While client-side encryption can protect data at rest, it often sacrifices the server's ability to perform useful operations, leading to a trade-off between security and functionality. "Building on Property-revealing Encryption" (BoPETs) aim to bridge this gap by encrypting data such that servers can still perform specific operations on it without decrypting the sensitive content. Mylar is a prominent example of a BoPET that uses Multi-Key Searchable Encryption (MKSE) to enable secure search and sharing of encrypted data. However, the paper questions whether Mylar truly delivers on its promise of security, particularly against actively malicious servers, and whether the formal security models used to justify its design are sufficient in practice.
Methods
The authors introduce a systematic approach to analyzing BoPETs by defining a taxonomy of server threats: snapshot passive (one-time server compromise), persistent passive (continuous observation), and active attacks (arbitrary malicious behavior). They then apply this framework to Mylar.
Key methodological contributions include:
- Formal Security Model Critique: They show that the Popa-Zeldovich security definitions for MKSE, which Mylar relies on, do not imply meaningful security. They construct a counterexample scheme that meets these definitions but trivially leaks keywords.
- Practical Attack Demonstrations: They implement and test attacks against Mylar and four real-world applications (kChat, MDaisy, OpenDNA, MeteorShop) ported to use Mylar. These attacks exploit both metadata leakage and the core MKSE implementation.
- Threat Model Expansion: They argue that existing BoPET security models often exclude crucial attack vectors like access patterns and metadata, which are vital for a realistic security assessment.
Datasets
- Ubuntu IRC logs: Used for simulating brute-force attacks on chat data.
- English word dictionary: Used in conjunction with IRC logs for keyword recovery.
The paper does not introduce new benchmarks but rather uses existing datasets to evaluate the practical implications of Mylar's security vulnerabilities.
Key Insights and Ideas
- Formal Models Aren't Enough: The formal security proofs for MKSE (and by extension, Mylar) are insufficient to guarantee real-world security. The gap between theoretical definitions and practical attacks is significant.
- Metadata is a Goldmine for Attackers: Even with encrypted data, unencrypted metadata (like object names, sizes, and access graphs) can reveal a surprising amount of sensitive information to attackers, even those with only a one-time snapshot of the server.
- Mylar's Design Flaw: Mylar's reliance on the untrusted server to convert search tokens is a critical design flaw. This allows a malicious server to perform powerful dictionary attacks on user queries, recovering keywords even if they don't appear in adversary-controlled documents.
- Access Patterns Leak Secrets: The paper emphasizes that BoPETs often leak access patterns, which persistent passive attackers can exploit to infer sensitive information about user behavior and data relationships.
- The "Active Adversary" Problem is Hard: Securing systems against actively malicious servers is significantly more challenging than against passive ones. It requires careful partitioning of functionality and robust verification mechanisms, which Mylar and similar systems struggle with.
Key Results
- Mylar is Not Secure Against Active Attacks: The paper demonstrates that Mylar fails to protect user data and queries against actively malicious servers, contradicting its claimed security.
- Metadata Leakage: Snapshot passive attackers can infer sensitive information from Mylar's access graphs and object names (e.g., inferring medical conditions from appointment relationships).
- Query Recovery: Persistent passive attackers can infer user queries by observing access patterns.
- Brute-Force Query Attack: The core MKSE flaw allows a malicious server to recover a significant percentage (up to 65-69% in simulations) of user queries and their order, even without knowing specific documents.
- Application-Specific Vulnerabilities: All four case-study applications (kChat, MDaisy, OpenDNA, MeteorShop) were found to be vulnerable to one or more attacks, revealing sensitive information like medical conditions, genetic predispositions, and shopping cart contents.
Limitations and Future Work
- Limitations of Formal Models: The authors highlight that the Popa-Zeldovich MKSE model is insufficient and does not capture the full threat landscape. They suggest the need for more comprehensive, simulation-based security models that account for active adversaries and dynamic access graphs.
- Dynamic Access Graphs: Mylar's security model assumes a static access graph, which is unrealistic for collaborative applications. Future work needs to address security in dynamic environments.
- Access Pattern Hiding: The paper acknowledges that hiding access patterns is crucial for persistent passive security but is difficult to achieve without sacrificing BoPET functionality.
- Server-Side Operations Verification: For active attack resistance, essential server operations need to be verified by the client, which is a significant re-engineering challenge for existing applications.
- Open Research Problems: The paper concludes by outlining open research problems, including developing realistic threat models and formal definitions for BoPETs, and finding ways to hide access patterns and verify server operations without incurring prohibitive performance overheads.
Summary updated