Journal of Computer Science and Technology ›› 2021, Vol. 36 ›› Issue (4): 877-895.doi: 10.1007/s11390-020-0060-y

Special Issue: Theory and Algorithms

• Regular Paper • Previous Articles     Next Articles

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

Yuan Li1, Xing-Chen Wang1, Lin Huang1, and Yun-Lei Zhao1,2,3,*, Member, CCF        

  1. 1 School of Computer Science, Fudan University, Shanghai 201203, China;
    2 State Key Laboratory of Integrated Services Networks, Xidian University, Xi'an 710071, China;
    3 State Key Laboratory of Cryptology, Beijing 100878, China
  • Received:2019-12-13 Revised:2020-12-29 Online:2021-07-05 Published:2021-07-30
  • Contact: Yun-Lei Zhao E-mail:ylzhao@fudan.edu.cn
  • About author:Yuan Li received his M.S. degree in computer science from Sun Yat-sen University, Guangzhou, in 2015. He is currently pursuing his Ph.D. degree in computer science at Fudan University, Shanghai. His research interests mainly include cloud security and database security and privacy.
  • Supported by:
    This work is supported in part by the National Key Research and Development Program of China under Grant No. 2017YFB-0802000, the National Natural Science Foundation of China under Grant Nos. 61472084 and U1536205, Shanghai Innovation Action Project under Grant No. 16DZ1100200, Shanghai Science and Technology Development Funds under Grant No. 16JC1400801, and Shandong Provincial Key Research and Development Program of China under Grant Nos. 2017CXG0701 and 2018CXGC0701.

PDF (PC)

83

Supplement

1

Order-preserving encryption (OPE) and order-revealing encryption (ORE) are among the core ingredients for encrypted databases (EDBs). 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. Our FIAs only exploit the ideal leakage of OPE/ORE (in particular, no need of data denseness or frequency). We also improve their efficiency with the frequency statistics using a hierarchical idea such that the high-frequency values will be recovered more quickly. We conduct some experiments on real datasets to test the performance, and the results show that our FIAs can cause an extreme hazard on most of the existing OPEs and OREs with high efficiency and 100% recovery rate. We then formulate forward security of ORE, and propose a practical compilation framework for achieving forward secure ORE to resist the perniciousness of FIA. The compilation framework can transform most of the existing OPEs/OREs into forward secure OREs, 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. The proposed compilation is highly efficient and forward secure.

Key words: order-revealing encryption; order-preserving encryption; file-injection attack; forward security;

[1] Popa R A, Redfield C M S, Zeldovich N, Balakrishnan H. CryptDB:Protecting confidentiality with encrypted query processing. In Proc. the 23rd ACM Symp. Operating Systems Principles, October 2011, pp.85-100. DOI:10.1145/2043556.2043566.
[2] Agrawal R, Kiernan J, Srikant R, Xu Y. Order preserving encryption for numeric data. In Proc. the ACM SIGMOD Int. Conference on Management of Data, June 2004, pp.563-574. DOI:10.1145/1007568.1007632.
[3] Boneh D, Lewi K, Raykova M, Sahai A, Zhandry M, Zimmerman J. Semantically secure order-revealing encryption:Multi-input functional encryption without obfuscation. In Proc. the 34th Annual Int. Conference on the Theory and Applications of Cryptographic Techniques, April 2015, pp.563-594. DOI:10.1007/978-3-662-46803-619.
[4] Boldyreva A, Chenette N, Lee Y, O'Neill A. Orderpreserving symmetric encryption. In Proc. the 28th Annual Int. Conference on the Theory and Applications of Cryptographic Techniques, April 2009, pp.224-241. DOI:10.1007/978-3-642-01001-913.
[5] Chenette N, Lewi K, Weis S A, Wu D J. Practical orderrevealing encryption with limited leakage. In Proc. the 23rd International Conference on Fast Software Encryption, March 2016, pp.474-493. DOI:10.1007/978-3-66252993-524.
[6] Kerschbaum F. Frequency-hiding order-preserving encryption. In Proc. the 22nd ACM Conference on Computer and Communications Security, October 2015, pp.656-667. DOI:10.1145/2810103.2813629.
[7] Roche D, Apon D, Choi S G, Yerukhimovich A. POPE:Partial order-preserving encoding. In Proc. the 23rd ACM Conference on Computer and Communications Security, October 2016, pp.1131-1142. DOI:10.1145/2976749.2978345.
[8] Islam M S, Kuzu M, Kantarcioglu M. Inference attack against encrypted range queries on outsourced databases. In Proc. the 4th ACM Conference on Data and Application Security and Privacy, March 2014, pp.235-246. DOI:10.1145/2557547.2557561.
[9] Naveed M, Kamara S, Wright C V. Inference attacks on property-preserving encrypted databases. In Proc. the 22nd ACM Conference on Computer and Communications Security, October 2015, pp.644-655. DOI:10.1145/2810103.2813651.
[10] Durak F B, DuBuisson T M, Cash D. What else is revealed by order-revealing encryption. In Proc. the 23rd ACM Conference on Computer and Communications Security, October 2016, pp.1155-1166. DOI:10.1145/2976749.2978379.
[11] Grubbs P, Sekniqi K, Bindschaedler V, Naveed M, Ristenpart T. Leakage-abuse attacks against order-revealing encryption. In Proc. the 2017 IEEE Symp. Security and Privacy, May 2017, pp.655-672. DOI:10.1109/SP.2017.44.
[12] Wang X, Zhao Y. Order-revealing encryption:File-injection attack and forward security. In Proc. the 23rd European Symposium on Research in Computer Security, September 2018, pp.101-121. DOI:10.1007/978-3-319-98989-16.
[13] Boldyreva A, Chenette N, O'Neill A. Order-preserving encryption revisited:Improved security analysis and alternative solutions. In Proc. the 31st Int. Cryptology Conference, August 2011, pp.578-595. DOI:10.1007/978-3-642-22792933.
[14] Popa R A, Li F H, Zeldovich N. An ideal-security protocol for order-preserving encoding. In Proc. the 2013 IEEE Symp. Security and Privacy, May 2013, pp.463-477. DOI:10.1109/SP.2013.38.
[15] Cash D, Liu F H, O'Neill A, Zhang C. Reducing the leakage in practical order-revealing encryption. http://eprint.iacr.org/2016/661, April 2020.
[16] Zhang Y, Katz J, Papamanthou C. All your queries are belong to us:The power of file-injection attacks on searchable encryption. In Proc. the 25th USENIX Security Symposium, August 2016, pp.707-720.
[17] Cash D, Grubbs P, Perry J, Ristenpart T. Leakage-abuse attacks against searchable encryption. In Proc. the 22nd ACM Conference on Computer and Communications Security, October 2015, pp.668-679. DOI:10.1145/2810103.2813700.
[18] Islam M S, Kuzu M, Kantarcioglu M. Access pattern disclosure on searchable encryption:Ramification, attack and mitigation. In Proc. the 19th Annual Network and Distributed System Security Symposium, February 2012.
[19] He W, Akhawe D, Jain S, Shi E, Song D. ShadowCrypt:Encrypted web applications for everyone. In Proc. the 21st ACM SIGSAC Conference on Computer and Communications Security, November 2014, pp.1028-1039. DOI:10.1145/2660267.2660326.
[20] Lau B, Chung S, Song C, Jang Y, Lee W, Boldyreva A. Mimesis aegis:A mimicry privacy shield-A system's approach to data privacy on public cloud. In Proc. the 23rd USENIX Conference on Security Symp., August 2014, pp.33-48.
[21] Goldreich O. Fondations of Cryptography-Basic Techinigues. Cambridge, 2004.
[22] Cilibrasi R, Vitányi P. The google similarity distance. IEEE Trans. Knowledge and Data Engineering, 2007, 19(3):370-383. DOI:10.1109/TKDE.2007.48.
[23] Stefanov E, Papamanthou C, Shi E. Practical dynamic searchable encryption with small leakage. In Proc. the 21st Annual Network and Distributed System Security Symp., February 2014. DOI:10.14722/ndss.2014.23298.
[24] Garg S, Mohassel P, Papamanthou C. TWORAM:Efficient oblivious RAM in two rounds with applications to searchable encryption. In Proc. the 36th Int. Cryptology Conference, August 2016, pp.563-592. DOI:10.1007/978-3-66253015-320.
[25] Goldreich O, Ostrovsky R. Software protection and simulation on oblivious RAMs. Journal of the ACM, 1996, 43(3):431-473. DOI:10.1145/233551.233553.
[26] Naveed M. The fallacy of composition of oblivious RAM and searchable encryption. http://eprint.iacr.org/2015/668, April 2020.
[27] Lewi K, Wu D J. Order-revealing encryption:New constructions, applications, and lower bounds. In Proc. the 23rd ACM SIGSAC Conference on Computer and Communications Security, October 2016, pp.1167-1178. DOI:10.1145/2976749.2978376.
[1] Santi Marti nez, Magda Valls, Concepcio Roig, Josep M. Miret, and Francesc Gine. A Secure Elliptic Curve-Based RFID Protocol [J]. , 2009, 24(2): 309-318.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] Li Wanxue;. Almost Optimal Dynamic 2-3 Trees[J]. , 1986, 1(2): 60 -71 .
[2] C.Y.Chung; H.R.Hwa;. A Chinese Information Processing System[J]. , 1986, 1(2): 15 -24 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Zhang Cui; Zhao Qinping; Xu Jiafu;. Kernel Language KLND[J]. , 1986, 1(3): 65 -79 .
[5] Zheng Guoliang; Li Hui;. The Design and Implementation of the Syntax-Directed Editor Generator(SEG)[J]. , 1986, 1(4): 39 -48 .
[6] Huang Xuedong; Cai Lianhong; Fang Ditang; Chi Bianjin; Zhou Li; Jiang Li;. A Computer System for Chinese Character Speech Input[J]. , 1986, 1(4): 75 -83 .
[7] Shi Zhongzhi;. Knowledge-Based Decision Support System[J]. , 1987, 2(1): 22 -29 .
[8] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[9] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[10] Xia Peisu; Fang Xinwo; Wang Yuxiang; Yan Kaiming; Zhang Tingjun; Liu Yulan; Zhao Chunying; Sun Jizhong;. Design of Array Processor Systems[J]. , 1987, 2(3): 163 -173 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

 Home
Editorial Board
Author Guidelines
Subscription		 Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved