Diffix Vulnerability #4

Back to Overview

Discovered	January 2018
Demonstrated	January 2018
Announced	July 2018
Severity	Very High
Patched Version	18.3
Patched Date	July 2018

This attack was discovered by Aircloak in January 2018. It was independently discovered by Andrea Gadotti, Florimond Houssiau, Luc Rocher, Ben Livshits, and Yves-Alexandre de Montjoye (attack authors). The attack is documented at https://www.usenix.org/system/files/sec19-gadotti_0.pdf and https://arxiv.org/abs/1804.06752v1. Aircloak internally demonstrated the attack in January 2018. The attack was patched in version 18.3, released in July 2018.

The attack authors have not attempted the attack on any Aircloak system. Rather, they demonstrated the attack on a simplified version of Diffix that they themselves built, based on a public description of Diffix from June 2018.

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 only know a few attributes of the victim user, where these attributes are enough to uniquely identify the user with high probability.

Attack:
The attack is a difference attack composed of two queries, whereby one query definitely excludes the victim user, and the other query may or may not exclude the victim user depending on whether the user has an unknown attribute being tested for. Both queries contain a large number of “dummy” conditions: negative conditions such as “age != 1000” that have no effect on the users selected by the query. Each such dummy condition produces a user-dependent noise layer, which, when taken together, amounts to a substantial amount of noise. When one of the queries contains the user, and the other does not, then these noise layers produce different noise values, resulting in noisy counts that are much further apart than expected.

Effectiveness:
The attack is 100% effective (on the earlier unpatched version). The attack does not work on the patched version as of July 2018.

Patch:
The Aircloak system first detects the 200 most common values in each column. Aircloak determines that a conditions may be a dummy condition when it does not match one of these values. No dummy conditions are allowed.