Cryptology ePrint Archive: Report 2017/1086

Order-Revealing Encryption: File-Injection Attack and Forward Security

Xingchen Wang and Yunlei Zhao

Abstract: Order-preserving encryption (OPE) and order-revealing encryption (ORE) are among the core ingredients for encrypted database (EDB) systems as secure cloud storage. In this work, we study the leakage of OPE and ORE and their forward security. We propose generic yet powerful file-injection attacks (FIAs) on OPE/ORE, aimed at the situations of possessing order by and range queries. The FIA schemes only exploit the ideal leakage of OPE/ORE (in particular, no need of data denseness or frequency). We also improve its efficiency with the frequency statistics using a hierarchical idea such that the high-frequency values will be recovered more quickly. Compared with other attacks against OPE/ORE proposed in recent years, our FIA attacks rely upon less demanding conditions and are more effective for attacking the systems with the function of data sharing or transferring like encrypted email system. We executed some experiments on real datasets to test the performance, and the results show that our FIA attacks can cause an extreme hazard on most of the existing OPE and ORE schemes with high efficiency and 100% recovery rate. In order to resist the perniciousness of FIA, we propose a practical compilation framework for achieving forward secure ORE. The compilation framework only uses some simple cryptographical tools like pseudo-random function, hash function and trapdoor permutation. It can transform most of the existing OPE/ORE schemes into forward secure ORE schemes, with the goal of minimizing the extra burden incurred on computation and storage. We also present its security proof and execute some experiments to analyze its performance.

Category / Keywords: Order-revealing Encryption; Order-preserving Encryption; File-injection Attack; Forward Security

Original Publication (with major differences): ESORICS 2018

Date: received 9 Nov 2017, last revised 11 Nov 2018

Contact author: xingchenwang16 at fudan edu cn

Available format(s): PDF | BibTeX Citation

Version: 20181112:052718 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]