back to list

A Practical Evaluation of Countermeasures against Leakage Attacks on Encrypted Keyword Search

Master Thesis

Motivation

Motivated by calls for privacy and data breaches of cloud services, efforts to broadly deploy Encrypted Search Algorithms (ESAs) are moving forward. ESAs allow search on encrypted data and can be found in research as well as industry. They are built using various techniques, which represent complex tradeoffs between efficiency, expressiveness, and security. As all practical solutions leak some information, security is determined by the success of leakage attacks that try to use the leakage in conjunction with some auxiliary information to recover the underlying keywords of the encrypted search tokens. Unfortunately, their practical implications are unclear due to closed-source implementations, empirical evaluations conducted on small and/or unrealistic data, and reliance on very strong assumptions that can significantly affect accuracy. So while practitioners can formulate precise requirements for the dimensions of efficiency and expressiveness, the practical aspects of the dimension of security has remained ambiguous. Recently, [KKM+21] re-implemented and re-evaluated known-data attacks, where the adversary knows a subset of the data under attack, in more realistic scenarios without strong assumptions. However, they did not include evaluations of countermeasures against such attacks that modify the leakage, leaving open how effective these are in more realistic scenarios than previously considered. Furthermore, recent sampled-data attacks, where the adversary knows a related but distinct auxiliary dataset, have not been implemented.

Goal

The goal of this thesis is to implement recent sampled-data keyword leakage attacks [DHP21,GPP21,IKK12,OK21a,OK21b,PW16,RPH21] in the LEAKER framework [KKM+21], including the possibility to evaluate attacks in both a known-data and sampled-data setting. A new suitable real-world dataset should be uncovered that represents a practical sampled-data attack scenario. Then, attack countermeasures [CLRZ18,DPPS20,GKL+20,PPYM19,SOPK21] should be added to LEAKER as well. The thesis should then evaluate known-data and sampled-data attacks against the corresponding countermeasures on the new and existing [KKM+21] data to provide a more practical empirical foundation for how effective current countermeasures are in protecting against these attacks.

References

  • [CLRZ18] Guoxing Chen, Ten-Hwang Lai, Michael K. Reiter, and Yinqian Zhang. Differentially private access patterns for searchable symmetric encryption. In IEEE Conference on Computer Communications (INFOCOM), 2018.
  • [DHP21] Marc Damie, Florian Hahn, and Andreas Peter. A Highly Accurate Query-Recovery Attack against Searchable Encryption using Non-Indexed Documents. In USENIX Security Symposium (USENIX Security), 2021.
  • [DPPS20] Ioannis Demertzis, Dimitrios Papadopoulos, Charalampos Papamanthou, and Saurabh Shintre. SEAL: Attack Mitigation for Encrypted Databases via Adjustable Leakage. In USENIX Security Symposium (USENIX Security), 2020.
  • [GKL+20] Paul Grubbs, Anurag Khandelwal, Marie-Sarah Lacharité, Lloyd Brown, Lucy Li, Rachit Agarwal, and Thomas Ristenpart. Pancake: Frequency smoothing for encrypted data stores. In USENIX Security Symposium (USENIX Security), 2020.
  • [GPP21] Zichen Gui, Kenneth G Paterson, and Sikhar Patranabis. Leakage Perturbation is Not Enough: Breaking Structured Encryption Using Simulated Annealing. In IACR ePrint, 879, 2021
  • [IKK12] Mohammad Saiful Islam, Mehmet Kuzu, and Murat Kantarcioglu. Access pattern disclosure on searchable encryption: Ramification, attack and mitigation. In Network and Distributed System Security Symposium (NDSS), 2012.
  • [KKM+21] Seny Kamara, Abdelkarim Kati, Tarik Moataz, Thomas Schneider, Amos Treiber, and Michael Yonli. Cryptanalysis of encrypted search with LEAKER – a framework for LEakage AttacK Evaluation on Real-world data. In IACR ePrint, 1035, 2021
  • [OK21a] Simon Oya and Florian Kerschbaum. Hiding the access pattern is not enough: Exploiting search pattern leakage in searchable encryption. In USENIX Security Symposium (USENIX Security), 2021.
  • [OK21b] Simon Oya and Florian Kerschbaum. IHOP: Improved Statistical Query Recovery against Searchable Symmetric Encryption through Quadratic Optimization. In arXiv 2110.04180, 2021.
  • [PPYM19] Sarvar Patel, Giuseppe Persiano, Kevin Yeo, and Moti Yung. Mitigating leakage in secure cloud-hosted data structures: Volume-hiding for multi-maps via hashing. In ACM SIGSAC Conference on Computer and Communications Security (CCS), 2019.
  • [PW16] David Pouliot and Charles V Wright. The shadow nemesis: Inference attacks on efficiently deployable, efficiently searchable encryption. In ACM SIGSAC Conference on Computer and Communications Security (CCS), 2016.
  • [RPH21] Ruben Groot Roessink, Andreas Peter, and Florian Hahn. Experimental review of the IKK query recovery attack: Assumptions, recovery rate and improvements. In International Conference on Applied Cryptography and Network Security (ACNS), 2021.
  • [SOPK21] Zhiwei Shang, Simon Oya, Andreas Peter, and Florian Kerschbaum. Obfuscated Access and Search Patterns in Searchable Encryption. In Network and Distributed System Security Symposium (NDSS), 2021.

Supervisors