SARAs: Substitution and Replay Attacks in the Maintenance Mode of Encrypted Databases

Encrypted databases (EDBs) have become the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">de facto</i> technique to ensure data confidentiality in database outsourcing scenarios. Among them, HEDB is a state-of-the-art EDB system that balances full-SQL functionality, efficient maintainability, and rigorous security. However, we identify a critical vulnerability in its maintenance mode and design the first attack of its kind against EDB systems. Specifically, we introduce substitution and replay attacks (SARAs) launched by database administrators (DBAs) against the HEDB system. Subsequently, we craft an automatic attack tool, <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Auto SARAs</i>, to demonstrate the real-life impact of this attack. The experimental results on the TPC-H benchmark show that SARAs can successfully compromise 1,449,125 records in HEDB within only 167.06 seconds. As for defenses, we prove that authentication mechanisms, whether pre-query authentication or post-query authentication, are insufficient to defend against SARAs, which represent an inherent vulnerability within HEDB systems.