A paper by Grubbs et al. (CCS 2016) investigates the security of Mylar. The paper proposes three leakage/attack scenarios: the first two are outside of the scope of Mylar (and Grubbs et al. acknowledge this fact) and the third, an attack on search, was already described in the Mylar paper and does not work against Mylar. We elaborate on these points below.
The first two scenarios show that there is some information leakage from access control metadata (knowing who has access to what, but not the actual data content) and from access patterns (what data item a user accesses, but not its contents). Mylar's goal is to provide end-to-end encryption for fields marked as sensitive by the developer; Mylar's goal does not include hiding the metadata that is the focus of these two attacks. For example, Grubbs et al. say that if two medical patients access the same encrypted procedure information, an attacker can infer that both are undergoing the same procedure. Note that the attacker does not see the actual procedure or medical profile of the patients, which are encrypted by Mylar with end-to-end encryption.
These leakages are hence outside of the scope of Mylar's security guarantees, and Grubbs et al. acknowledge this. In fact, practical encrypted systems today do not prevent against access patterns leakage because the currently known techniques (e.g., ORAM) are still too slow.
The attack works as follows:
Once the attacker knows W, if W appears in any of the victim's documents, the attacker will know that the document contains W.
This attack was already described in the Mylar NSDI'14 paper (see the last paragraph of Section 5), including the optimization of precomputing a dictionary file.
Mylar's API was designed to prevent this attack. Specifically, Mylar does not automatically generate the delta D in the attack scenario above. Instead, Mylar requires the application developer to explicitly use the allow_search() function (shown in the API table in Figure 2 of our NSDI'14 paper) to indicate that it is safe to compute the delta D. It is the developer's responsibility to ensure that this function is called only for trusted principals. For example, the application could ask the user if the user trusts principal P and would be OK with P seeing all of the search queries made by the user. As long as the developer uses the Mylar API correctly, the user's client would not generate the delta D, and thereby prevent the above attack.
Grubbs et al. also discuss Mylar's search model (which is described in detail in ePrint report 2013/508). The original definition described security in terms of two games, one focused on hiding data, and the other focused on hiding search tokens. They point out that Mylar's security definition for search could be stronger if it combined the two security games into one. We agree, and thank them for the observation. Nevertheless, we expect that Mylar's search scheme remains secure under a combined security definition (we have not yet proven this formally). Finally, we thank Grubbs et al. for pointing out that some high-level statements in the Mylar paper were unclear. We clarified these in the updated Mylar paper, posted on Crypto ePrint.
In the updated paper,
we also took the opportunity to describe in more detail the security
guarantees of Mylar.
After we posted our technical response above, Grubbs et al. produced and distributed a Q&A called "Mylar: The Guide for the Perplexed". Their Q&A is inaccurate in several ways. Below, we address the major points.