How (Not) to Index Order Revealing Encrypted Databases

Order Reveling Encryption (ORE) enables efficient range queries on encrypted databases, but may leak information that could be exploited by inference attacks. State-of-the-art ORE schemes claim different security guarantees depending on the adversary attack surface. Intuitively, online adversaries who access the database server at runtime may access information leakage; offline adversaries who access only a snapshot of the database data should not be able to gain useful information. We focus on offline security of the ORE scheme proposed by Lewi and Wu (LW-ORE, CCS 2016), which guarantees semantic security of ciphertexts stored in the database, but requires that ciphertexts are maintained sorted with regard to the corresponding plaintexts to support sublinear time queries. The design of LW-ORE does not discuss how to build indexing data structures to maintain sorting. The risk is that practitioners consider indexes as a technicality whose design does not affect security. We show that indexes can affect offline security of LW-ORE because they may leak duplicate plaintext values, and statistical information on plaintexts distribution and on transactions history. As a real-world demonstration, we found two open source implementations related to academic research (JISA 2018, VLDB 2019), and both adopt standard search trees which may introduce such vulnerabilities. We discuss necessary conditions for indexing data structures to be secure for ORE databases, and we outline practical solutions. Our analyses could represent an insightful lesson in the context of security failures due to gaps between theoretical modeling and actual implementation, and may also apply to other cryptographic techniques for securing outsourced databases.