Response to "Breaking web applications built on top of encrypted data" (CCS 2016) by P. Grubbs, R. McPherson, M. Naveed, T. Ristenpart and V. Shmatikov

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.

• Attacks 1 and 2.

  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.

• Attack 3.

  The attack works as follows:

  1. The attacker compromises the server.
  2. The attacker creates a principal P, and chooses a victim user V.
  3. The attacker gives V access to P.
  4. V's client automatically generates a delta D (for Mylar's searchable encryption scheme) from V to P, and gives it to the server.
  5. V searches for word W, by supplying an encrypted search token for W to the server.
  6. The attacker converts this token using D into an encryption of W with the key of P.
  7. The attacker uses P's key to mount a dictionary attack to compute the plaintext word W.

  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.

Response to the document "Mylar: The Guide for the Perplexed" by Grubbs et al.

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.

• The claims that we "retroactively rewrite a published paper and erase evidence of previously made claims" and "heavily revised" it are incorrect. In our revised Crypto ePrint paper, the subtitle states that the document is an updated version, provides the date of last change (2016-08-29), includes an explicit update log describing what changed from the NSDI paper, and cites the NSDI paper. In particular, as the change log makes clear, the updated paper did not change the technical design of Mylar. Both the original and revised papers are available from our web site, and we have exchanged emails with Grubbs et al. informing them about the updated paper, prior to them publishing their Q&A.

• The accusations regarding our web site changes are unfounded. The content with which we updated the Mylar web site is based on our own research: our Mylar publications, the follow-up Verena publication, and our follow-up investigation on integrity and searchable encryption. This research existed prior to and independently of the paper by Grubbs et al. Moreover, we discussed these changes to our web site with the authors of Grubbs et al. prior to their Q&A being released.

• Grubbs et al. argue that Mylar's allow_search countermeasure is broken because a user can give access to data to a compromised user. We find this argument incorrect: by this argument, most discretionary access control systems are also broken, because a user can set the permissions incorrectly. We also find that Grubbs et al. misrepresent how developers should use allow_search. Finally, despite statements by Grubbs et al. to the contrary, we believe that their attack 3 is technically the same attack as was already described in the original Mylar paper. Grubbs et al. choose different words to describe it, but the attack consists of the same 7 technical steps described above.