Diffix Vulnerability #2

Back to Overview

Discovered

April 2018

Demonstrated

—–

Announced

April 2018

Severity

Very Low

Expected Patch Date

Q4 2019

This attack was discovered by Andrea Gadotti, Florimond Houssiau, Luc Rocher, and Yves-Alexandre de Montjoye of Imperial College London. The attack is documented at https://arxiv.org/abs/1804.06752. The attack has never been demonstrated to work in practice. The attack has been implemented by researchers at the Max Planck Institute for Software Systems (MPI-SWS), but has so far failed to work.

Goal:
The attack is a singling out attack, whereby the attacker makes a claim of the sort “There is a single user with the following attributes.”

Prerequisites:
The attacker must know the complete contents of roughly N=5 columns. The attacker is trying to learn an unknown value in an N+1th column. Within the N known columns, there must be a set of values whereby all N values uniquely identify a user, but where any N-1 values in combination with the unknown value identify enough users to avoid Low Count Filtering in the Aircloak system. (The conditions are rare. In measurements carried out by MPI-SWS, roughly 1 in 75 million rows satisfied the conditions.)

Attack:
The attack generates a small set of queries whereby each answer has a different set of users (those defined by any N-1 values), and therefore a different noise sample. One set of queries does not contain the victim user, and the other set of queries either contains or does not contain the victim user, depending on whether the victim has or does not have the unknown column value. Because each query has a different noise value, the attack can take the average of each set to improve the confidence in the exact value. By taking the difference in counts between the set without the victim, and the set that may or may not contain the victim, the attacker can deduce whether the victim is in the second set, and therefore whether the victim has the unknown value or not.

Effectiveness:
The attack appears to be ineffective. The authors of the attack have never demonstrated it. An implementation of the attack by MPI-SWS has so far failed to demonstrate a single correct claim.

Patch:
Future planned improvements in anonymization will make the attack impossible. These improvements will detect when any given condition pertains to only a few users or less, and ignore the condition.