Response to "Inference attacks on property preserving encrypted databases"

CryptDB Team


This note is in response to the paper "Inference attacks on property preserving encrypted databases" of Naveed, Kamara and Wright, and to the blog post (as of Sept 7, 2015) of one of the authors.

This paper represents an unsafe usage of CryptDB, violating CryptDB's security guidelines. In CryptDB, the administrator of a database application must annotate sensitive fields with 'sensitive' -- then, CryptDB encrypts these fields with strong encryption schemes that prevent all the attacks of Naveed et al. The authors violated CryptDB's security guidelines by not annotating the fields they considered sensitive. Hence, the conclusions drawn by this paper with regard to CryptDB's guarantees for medical applications are incorrect: had the guidelines been followed, none of the claimed attacks would have been possible. Our tech report elaborates on this as well as on CryptDB's behavior for OpenEMR:

Read our technical report.

Response to inaccurate claims

Unfortunately, we also found that Naveed et al. made statements about CryptDB that are false. In addition to the discussion in our tech report, we explain two of the main incorrect claims below.

Claim: In the blog post, the authors claim that fields annotated as 'sensitive' would be encrypted only with RND ("encrypted with standard encryption schemes") and that "these fields then cannot be queried at all -- ever" resulting in "an EDB system that only works over non-sensitive data". "you effectively have to cripple them until you have to use regular plain encryption" meaning RND.

Response: These statements are false. For a 'sensitive' field, CryptDB still uses a set of non-standard encryption schemes that offer functionality, and can support a wealth of queries on these encrypted fields.

Section 5 of the tech report elaborates on this. To summarize here, for a sensitive field, in addition to RND, CryptDB uses non-standard encryption schemes such as a homomorphic encryption scheme for addition (Paillier), a homomorphic encryption scheme for multiplication (ElGamal), SEARCH (searchable encryption which performs exact match), and, if the data items are unique, DET. Using these encryption schemes together with efficient systems techniques, CryptDB can support a wealth of queries. Some SQL examples are: SELECT, UPDATE, DELETE, COUNT, INSERT, SUM, +, multiply, =, !=, <>, IN, NOT IN, various functions applied to the result set (e.g., FORMAT, SUBSTRING, SIN), and ORDER BY.

We emphasize that, despite claims by Naveed et al., for the functionality above, the proxy does not download the entire database or an entire column: the proxy receives from the server only rows in the result set, as it should.

Claim: In an Ars technica article, one author stated that the table in Fig 9 of CryptDB shows how CryptDB recommends to run OpenEMR including how many sensitive fields it recommends to encrypt with OPE and how many with DET.

Response: The author's interpretation of Fig. 9 is false. As a quick proof, in the same row with OpenEMR in Fig. 9, there are 7 fields whose queries CryptDB cannot run at the server with any encryption scheme at all -- so clearly CryptDB does not say one should run an application in a way it cannot be run!

Instead, the table in Fig. 9 shows what encryption schemes support all queries on a field if these queries were to run completely at the server in the most efficient way possible -- this table does not say that a sensitive field should be encrypted this way. In fact, for sensitive fields that are not supported directly at the server, the CryptDB publications discuss ways of supporting them with a combination of in-proxy and server-side processing that reveal only strong encryption schemes at the server. Some of these techniques are almost as efficient as the direct server computation. For example, the CryptDB paper states that even if there is a sensitive-marked field on which an order is performed, CryptDB will not expose the order-preserving encryption (OPE) on this field to the server. Our tech report above explains how such queries can be supported.

Talking to the authors

Unfortunately, the authors did not contact us to inform us of their paper. They contacted journalists asking them to write about their paper (reporters forwarded their emails to us). We only learned about their paper late after the camera-ready deadline from a reporter. A lot of the issues above could have been avoided in an academic way, had the authors contacted us before their camera-ready deadline.