research-article

ShieldDB: An Encrypted Document Database With Padding Countermeasures

Authors:

Xingliang Yuan,

Cong WangAuthors Info & Claims

IEEE Transactions on Knowledge and Data Engineering, Volume 35, Issue 4

Pages 4236 - 4252

https://doi.org/10.1109/TKDE.2021.3126607

Published: 01 April 2023 Publication History

Abstract

Cloud storage systems have seen a growing number of clients due to the fact that more and more businesses and governments are shifting away from in-house data servers and seeking cost-effective and ease-of-access solutions. However, the security of cloud storage is underestimated in current practice, which resulted in many large-scale data breaches. To change the status quo, this paper presents the design of ShieldDB, an encrypted document database. ShieldDB adapts the searchable encryption technique to preserve the search functionality over encrypted documents without having much impact on its scalability. However, merely realising such a theoretical primitive suffers from real-world threats, where a knowledgeable adversary can exploit the leakage (aka access pattern to the database) to break the claimed protection on data confidentiality. To address this challenge in practical deployment, ShieldDB is designed with tailored padding countermeasures. Unlike prior works, we target a more realistic adversarial model, where the database gets updated continuously, and the adversary can monitor it at an (or multiple) arbitrary time interval(s). ShieldDB’s padding strategies ensure that the access pattern to the database is obfuscated all the time. We present a full-fledged implementation of ShieldDB and conduct intensive evaluations on Azure Cloud.

References

[1]

Information is Beautiful, “World’s biggest data breaches,” 2020. [Online]. Available: http://www.informationisbeautiful.net/visualizations/worlds-biggest-data-breaches-hacks/

[2]

IBM, “2017 ponemon cost of data breach study - australia-specific report,” 2019. [Online]. Available: https://www-03.ibm.com/security/au/en/data-breach/

[3]

Verizon, “2020 data breach investigations report,” 2020. [Online]. Available: https://enterprise.verizon.com/en-au/resources/reports/dbir/

[4]

C. Liuet al., “Authorized public auditing of dynamic big data storage on cloud with efficient verifiable fine-grained updates,” IEEE Trans. Parallel Distrib. Syst., vol. 25, no. 9, pp. 2234–2244, Sep. 2014.

[5]

D. Fadolalkarim, E. Bertino, and A. Sallam, “An anomaly detection system for the protection of relational database systems against data leakage by application programs,” in Proc. IEEE Int. Conf. Data Eng., 2020, pp. 265–276.

[6]

Y. Ji, C. Xu, J. Xu, and H. Hu, “VABS: Towards verifiable attribute-based search over shared cloud data,” in Proc. IEEE Int. Conf. Data Eng., 2019, pp. 2028–2031.

[7]

X. Yi, R. Paulet, E. Bertino, and V. Varadharajan, “Practical approximate k nearest neighbor queries with location and query privacy,” IEEE Trans. Knowl. Data Eng., vol. 28, no. 6, pp. 1546–1559, Jun. 2016.

Digital Library

[8]

R. A. Popa, C. Redfield, N. Zeldovich, and H. Balakrishnan, “CryptDB: Protecting confidentiality with encrypted query processing,” in Proc. ACM Symp. Oper. Syst. Princ., 2011, pp. 85–100.

[9]

Microsoft SQL Server 2016, “Always encrypted (database engine),” 2016. [Online]. Available: https://msdn.microsoft.com/en-us/library/mt163865.aspx/

[10]

V. Pappas, B. Vo, F. Krell, S. Choi, V. Kolesv, A. Keromytis, and T. Malkin, “Blind seer: A scalable private DBMS,” in Proc. IEEE Symp. Secur. Privacy, 2014, pp. 359–374.

[11]

A. Papadimitriouet al., “Big data analytics over encrypted datasets with seabed,” in Proc. USENIX Conf. Operating Syst. Des. Implementation, 2016, pp. 587–602.

[12]

R. Poddar, T. Boelter, and R. A. Popa, “Arx: A strongly encrypted database system,” VLDB Endowment, vol. 12, no. 11, pp. 1664–1678, 2019.

Digital Library

[13]

X. Yuan, Y. Guo, X. Wang, C. Wang, B. Li, and X. Jia, “EncKV: An encrypted key-value store with rich queries,” in Proc. ACM Asia Conf. Comput. Commun. Secur., 2017, pp. 423–435.

[14]

H. Zhang, X. Liu, D. G. Andersen, M. Kaminsky, K. Keeton, and A. Pavlo, “Order-preserving key compression for in-memory search trees,” in Proc. ACM SIGMOD Int. Conf. Manage. Data, 2020, pp. 1601–1615.

[15]

X. Meng, H. Zhu, and G. Kollios, “Top-k query processing on encrypted databases with strong security guarantees,” in Proc. IEEE 34th Int. Conf. Data Eng., 2018, pp. 353–364.

[16]

M. Naveed, S. Kamara, and C. V. Wright, “Inference attacks on property-preserving encrypted databases,” in Proc. ACM SIGSAC Conf. Comput. Commun. Secur., 2015, pp. 644–655.

[17]

V. Bindschaedler, P. Grubbs, D. Cash, T. Ristenpart, and V. Shmatikov, “The Tao of inference in privacy-protected databases,” VLDB Endowment, vol. 11, no. 11, pp. 1715–1728, 2018.

Digital Library

[18]

D. Song, D. Wagner, and A. Perrig, “Practical techniques for searches on encrypted data,” in Proc. IEEE Symp. Secur. Privacy, 2000, pp. 44–55.

[19]

R. Curtmola, J. Garay, S. Kamara, and R. Ostrovsky, “Searchable symmetric encryption: Improved definitions and efficient constructions,” in Proc. ACM Conf. Comput. Commun. Secur., 2006, pp. 79–88.

[20]

M. Islam, M. Kuzu, and M. Kantarcioglu, “Access pattern disclosure on searchable encryption: Ramification, attack and mitigation,” in Proc. 19th Annu. Netw. Distrib. Syst. Secur. Symp., 2012, pp. 1–15.

[21]

D. Cash, P. Grubbs, J. Perry, and T. Ristenpart, “Leakage-abuse attacks against searchable encryption,” in Proc. ACM Conf. Comput. Commun. Secur., 2015, pp. 668–679.

[22]

Y. Zhang, J. Katz, and C. Papamanthou, “All your queries are belong to us: The power of file-injection attacks on searchable encryption,” in Proc. USENIX Conf. Secur. Symp., 2016, pp. 707–720.

[23]

P. Grubbs, T. Ristenpart, and V. Shmatikov, “Why your encrypted database is not secure,” in Proc. ACM 16th Workshop Hot Top. Operating Syst., 2017, pp. 162–168.

[24]

S. Eskandarian and M. Zaharia, “ObliDB: Oblivious query processing for secure databases,” VLDB Endowment, vol. 13, no. 2, pp. 169–186, 2019.

Digital Library

[25]

Z. Liu, B. Li, Y. Huang, J. Li, Y. Xiang, and W. Pedrycz, “NewMCOS: Towards a practical multi-cloud oblivious storage scheme,” IEEE Trans. Knowl. Data Eng., vol. 32, no. 4, Apr. 2020.

[26]

M. Naveed, “The fallacy of composition of oblivious ram and searchable encryption,” IACR Cryptol. ePrint Archive, vol. 2015, 2015, Art. no. [Online]. Available: https://eprint.iacr.org/2015/668

[27]

D. Cash, P. Grubbs, J. Perry, and T. Ristenpart, “Leakage-abuse attacks against searchable encryption,” in Proc. ACM SIGSAC Conf. Comput. Commun. Secur., 2015, pp. 668–679.

[28]

P. Mishra, R. Poddar, J. Chen, A. Chiesa, and R. A. Popa, “Oblix: An efficient oblivious search index,” in Proc. IEEE Symp. Secur. Privacy, 2018, pp. 279–296.

[29]

R. Bost and P.-A. Fouque, “Thrawting leakage abuse attacks againts searchable encryption a formal approach and applications to database padding,” Cryptol. ePrint Archive, Tech. Rep. 2017/1060, 2017.

[30]

S. Kamara, C. Papamanthou, and T. Roeder, “Dynamic searchable symmetric encryption,” in Proc. ACM Conf. Comput. Commun. Secur., 2012, pp. 965–976.

[31]

D. Cash, J. Jaeger, S. Jarecki, and C. Jutla, “Dynamic searchable encryption in very-large databases: Data structures and implementation,” in Proc. 21st Annu. Netw. Distrib. Syst. Secur. Symp., 2014, pp. 1–16.

[32]

X. Song, C. Dong, D. Yuan, I. Xu, and M. Zhao, “Forward private searchable symmetric encryption with optimized I/O efficiency,” IEEE Trans. Dependable Secure Comput., vol. 17, no. 5, pp. 912–927, Sep./Oct. 2018.

[33]

R. Bost, “Sophos - Forward secure searchable encryption,” in Proc. ACM Conf. Comput. Commun. Secur., 2016, pp. 1143–1154.

[34]

S.-F. Sun, J. K. Liu, A. Sakzad, R. Steinfeld, and T. H. Yuen, “An efficient non-interactive multi-client searchable encryption with support for boolean queries,” in Proc. Eur. Symp. Res. Comput. Secur., 2016, pp. 154–172.

[35]

S. Jarecki, C. Jutla, H. Krawczyk, M. Rosu, and M. Steiner, “Outsourced symmetric private information retrieval,” in Proc. ACM Conf. Comput. Commun. Secur., 2013, pp. 875–888.

[36]

R. Bost, B. Minaud, and O. Ohrimenko, “Forward and backward private searchable encryption from constrained cryptographic primitives,” in Proc. ACM Conf. Comput. Commun. Secur., 2017.

[37]

S.-F. Sunet al., “Practical backward-secure searchable encryption from symmetric puncturable encryption,” in Proc. ACM Conf. Comput. Commun. Secur., 2018, pp. 763–780.

[38]

V. Vo, S. Lai, X. Yuan, S.-F. Sun, S. Nepal, and J. K. Liu, “Accelerating forward and backward private searchable encryption using trusted execution,” in Proc. Int. Conf. Appl. Cryptogr. Netw. Secur., 2020, pp. 83–103.

[39]

L. Blackstone, S. Kamara, and T. Moataz, “Revisiting leakage abuse attacks,” in Proc. Netw. Distrib. Syst. Secur. Symp., 2020, pp. 1–18.

[40]

Z. Zhang, Statistical Implications of Turing’s Formula. Hoboken, NJ, USA: Wiley, 2017.

[41]

Y. Zhang, K. Tangwongsan, and S. Tirthapura, “Streaming k-means clustering with fast queries,” in Proc. IEEE 33rd Int. Conf. Data Eng., 2017, pp. 449–460.

[42]

H. M. Gomes, J. Read, A. Bifet, J. P. Barddal, and J. A. Gama, “Machine learning for streaming data: State of the art, challenges, and opportunities,” SIGKDD Explorations Newslett., vol. 21, pp. 6–22, 2019.

Digital Library

[43]

M. Chase and S. Kamara, “Structured encryption and controlled disclosure,” in Proc. Annu. Int. Conf. Theory Appl. Cryptol. Informat. Secur., Advances in Cryptology -ASIACRYPT 2010, Singapore: Springer, 2010, pp. 577–594.

[44]

D. Cash, S. Jarecki, C. Jutla, H. Krawczyk, M.-C. Roşu, and M. Steiner, “Highly-scalable searchable symmetric encryption with support for boolean queries,” in Proc. Annu. Cryptol. Conf., 2013, pp. 353–373.

[45]

V. Vo, S. Lai, X. Yuan, S. Nepal, and J. K. Liu, “Towards efficient and strong backward private searchable encryption with secure enclaves,” in Proc. Int. Conf. Appl. Cryptography Netw. Secur., 2021, pp. 50–75.

[46]

I. Demertzis and C. Papamanthou, “Fast searchable encryption with tunable locality,” in Proc. ACM Int. Conf. Manage. Data, 2017, pp. 1053–1067.

[47]

I. Demertzis, R. Talapatra, and C. Papamanthou, “Efficient searchable encryption through compression,” Proc. VLDB Endowment, vol. 11, no. 11, pp. 1729–1741, 2018.

[48]

E. Stefanov, E. Shi, and D. Song, “Towards practical oblivious RAM,” in Proc. Netw. Distrib. Syst. Secur. Symp., 2012, pp. 1–19.

[49]

E. Stefanovet al., “Path ORAM: An extremely simple oblivious RAM protocol,” in Proc. 2013 ACM SIGSAC conf. Comput. & communications security, Association for Computing Machinery, New York, NY, USA, 2013., pp. 299–310.

[50]

L. Xu, X. Yuan, C. Wang, Q. Wang, and C. Xu, “Hardening database padding for searchable encryption,” in Proc. IEEE Conf. Comput. Commun., 2019, pp. 2503–2511.

[51]

S. Kamara and T. Moataz, “Computationally volume-hiding structured encryption,” in Advances in Cryptology – EUROCRYPT19. Berlin, Germany: Springer, 2019.

[52]

S. Patel, G. Persiano, K. Yeo, and M. Yung, “Mitigating leakage in secure cloud-hosted data structures: Volume-hiding for multi-maps via hashing,” in Proc. ACM Conf. Comput. Commun. Secur., 2019, pp. 79–93.

[53]

Z. Chang, L. Zou, and F. Li, “Privacy preserving subgraph matching on large graphs in cloud,” in Proc. Int. Conf. Manage. Data, 2016, pp. 199–213.

[54]

P. Antonopouloset al., “Azure SQL database always encrypted,” in Proc. Int. Conf. Manage. Data, 2020, pp. 1511–1525.

[55]

X. Lei, A. X. Liu, R. Li, and G. Tu, “SecEQP: A secure and efficient scheme for SkNN query problem over encrypted geodata on cloud,” in Proc. IEEE 35th Int. Conf. Data Eng., 2019, pp. 662–673.

[56]

G. Kellaris, G. Kollios, K. Nissim, and A. O’Neill, “Generic attacks on secure outsourced databases,” in Proc. ACM Conf. Comput. Commun. Secur., 2016, pp. 1329–1340.

Cited By

Liu FXue KYang JZhang JHuang ZLi JWei D(2024)Volume-Hiding Range Searchable Symmetric Encryption for Large-Scale DatasetsIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2023.333530421:4(3597-3609)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1109/TDSC.2023.3335304
Senouci MBenkhaddra ISenouci ALi F(2024)A sustainable certificateless authenticated searchable encryption with multi-trapdoor indistinguishabilityTelecommunications Systems10.1007/s11235-024-01121-w86:1(213-227)Online publication date: 1-May-2024
https://dl.acm.org/doi/10.1007/s11235-024-01121-w
Xu LZheng LXu CYuan XWang CMeng WJensen CCremers CKirda E(2023)Leakage-Abuse Attacks Against Forward and Backward Private Searchable Symmetric EncryptionProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security10.1145/3576915.3623085(3003-3017)Online publication date: 15-Nov-2023
https://dl.acm.org/doi/10.1145/3576915.3623085

Recommendations

Universal Padding Schemes for RSA
CRYPTO '02: Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology

A common practice to encrypt with RSA is to first apply a padding scheme to the message and then to exponentiate the result with the public exponent; an example of this is OAEP. Similarly, the usual way of signing with RSA is to apply some padding ...
Practical padding oracle attacks
WOOT'10: Proceedings of the 4th USENIX conference on Offensive technologies

At Eurocrypt 2002, Vaudenay introduced a powerful side-channel attack, which is called padding oracle attack, against CBC-mode encryption with PKCS#5 padding (See [6]). If there is an oracle which on receipt of a ciphertext, decrypts it and then replies ...
Efficient certificate-based verifiable encrypted signature scheme

Certificate-based public key cryptographic is a novel cryptographic primitive solving the heavy management problem in the conventional public key cryptographic. Verifiable encrypted signature is useful for many cryptographic protocols and often is used ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Knowledge and Data Engineering

IEEE Transactions on Knowledge and Data Engineering Volume 35, Issue 4

April 2023

1091 pages

ISSN:1041-4347

Issue’s Table of Contents

1041-4347 © 2021 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See https://www.ieee.org/publications/rights/index.html for more information.

Publisher

IEEE Educational Activities Department

United States

Publication History

Published: 01 April 2023

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Liu FXue KYang JZhang JHuang ZLi JWei D(2024)Volume-Hiding Range Searchable Symmetric Encryption for Large-Scale DatasetsIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2023.333530421:4(3597-3609)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1109/TDSC.2023.3335304
Senouci MBenkhaddra ISenouci ALi F(2024)A sustainable certificateless authenticated searchable encryption with multi-trapdoor indistinguishabilityTelecommunications Systems10.1007/s11235-024-01121-w86:1(213-227)Online publication date: 1-May-2024
https://dl.acm.org/doi/10.1007/s11235-024-01121-w
Xu LZheng LXu CYuan XWang CMeng WJensen CCremers CKirda E(2023)Leakage-Abuse Attacks Against Forward and Backward Private Searchable Symmetric EncryptionProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security10.1145/3576915.3623085(3003-3017)Online publication date: 15-Nov-2023
https://dl.acm.org/doi/10.1145/3576915.3623085

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents