Within this project we research a new attack technique that allows extraction of selected database content relying only on the attackers ability to perform database transactions (INSERTs or UPDATEs) that are usually available to any anonymous database user. Our attack technique uses a side-channel timing attack in the realm of database indexing algorithms and data structures.
We prove that by exploiting the inherent characteristics of the most commonly used indexing data structures and algorithms in todays commercial database management systems it is possible to extract privacy-sensitive data from a database. Explicitly, we are able to argument that implementations of storage systems, that use B-trees for indexing, take more time to make an INSERT operation when a new page is written; and we give evidence on how can an attacker that is only allowed to make INSERTS and time them, be able to use this to construct a divide-and-conquer search for (supposedly) private indexed keys.
Further, we have successfully implemented this attack technique against MySQL and MS SQL.
Ariel Futoransky came up with the idea and started researching it with Damian Saura. Ariel Waissbein participated in some of the initial discussions and joined the team to make the attack work against MySQL. Pedro Varangot and Waissbein worked on the MS SQL attack.