Side-Channel Attacks on Query-Based Data Anonymization

A longstanding problem in computer privacy is that of data anonymization. One common approach is to present a query interface to analysts, and anonymize on a query-by-query basis. In practice, this approach often uses a standard database back end, and presents the query semantics of the database to the analyst. This paper presents a class of novel side-channel attacks that work against any query-based anonymization system that uses a standard database back end. The attacks exploit the implicit conditional logic of database runtime optimizations. They manipulate this logic to trigger timing and exception-throwing side-channels based on the contents of the data. We demonstrate the attacks on the implementation of the CHORUS Differential Privacy system released by Uber as an open source project. We obtain perfect reconstruction of millions of data values even with a Differential Privacy budget smaller than epsilon = 1.0 and no prior knowledge. The paper also presents the design of a general defense to the runtime-optimization attacks, and a concrete implementation of the defense in the latest version of Diffix. The defense works without modifications to the back end database, and operates by modifying SQL to eliminate the runtime optimization or disable the side-channels. In addition, two other attacks that exploit specific flaws in Diffix and CHORUS are reported. These have been fixed in the respective implementations.