Database Reconstruction from Noisy Volumes: A Cache Side-Channel Attack on SQLite

Authors: 

Aria Shahverdi, University of Maryland; Mahammad Shirinov, Bilkent University; Dana Dachman-Soled, University of Maryland

Abstract: 

We demonstrate the feasibility of database reconstruction under a cache side-channel attack on SQLite. Specifically, we present a Flush+Reload attack on SQLite that obtains approximate (or "noisy") volumes of range queries made to a private database. We then present several algorithms that, taken together, reconstruct nearly the exact database in varied experimental conditions, given these approximate volumes. Our reconstruction algorithms employ novel techniques for the approximate/noisy setting, including a noise-tolerant clique-finding algorithm, a "Match & Extend" algorithm for extrapolating volumes that are omitted from the clique, and a "Noise Reduction Step" that makes use of the closest vector problem (CVP) solver to improve the overall accuracy of the reconstructed database. The time complexity of our attacks grows quickly with the size of the range of the queried attribute, but scales well to large databases. Experimental results show that we can reconstruct databases of size 100,000 and ranges of size 12 with an error percentage of 0.11% in under 12 hours on a personal laptop.

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

BibTeX
@inproceedings {274715,
author = {Aria Shahverdi and Mahammad Shirinov and Dana Dachman-Soled},
title = {Database Reconstruction from Noisy Volumes: A Cache Side-Channel Attack on SQLite},
booktitle = {30th {USENIX} Security Symposium ({USENIX} Security 21)},
year = {2021},
isbn = {978-1-939133-24-3},
pages = {1019--1035},
url = {https://www.usenix.org/conference/usenixsecurity21/presentation/shahverdi},
publisher = {{USENIX} Association},
month = aug,
}

Presentation Video