Repository navigation
Look into the "create NULL values with JOIN using count(*)" difference attack #164
Description
Cristian raised the following difference attack:
I was under the impression this attack was already described in another discussion. But to be more explicit:
We have 2 tables: purchases, with columns product_id and client_id, and clients, with columns id and ssn.
Column ssn is labeled as the AID. Assume the following data is present:
Clients:
| id | ssn |
|---|---|
| 1 | a |
| 2 | b |
| 3 | c |
| 4 | d |
| 5 | e |
| 6 | f |
Purchases:
| product_id | client_id |
|---|---|
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
| 4 | 4 |
| 5 | 5 |
| 1 | 6 |
| 2 | 6 |
| 3 | 6 |
| 4 | 6 |
| 5 | 6 |
If we issue a query like:
select count(*) from purchases join clients on client_id = clients.idwe get the following input to the count aggregator:
| count | ssn |
|---|---|
| 1 | a |
| 1 | b |
| 1 | c |
| 1 | d |
| 1 | e |
| 5 | f |
If Ne=1 and Nt = 2, this results in a flattening of 4. The output will be 10 - 4 + noise(1) = 6 + noise(1).
For the query:
select count(*) from purchases left join clients on client_id = clients.id and ssn <> 'f'we get the following input to the count aggregator:
| count | ssn |
|---|---|
| 1 | a |
| 1 | b |
| 1 | c |
| 1 | d |
| 1 | e |
| 5 | NULL |
The last row is put aside as unaccounted.
If Ne=1 and Nt = 2, this results in a flattening of 0 for accounted rows. The output will be 5 - 0 + 5 - 0 + noise(1) = 10 + noise(1).
The difference in the results is large enough to dominate the noise, allowing us to know the entity with ssn = 'f' is an outlier and to detect other attributes of it by conditional inclusion/exclusion in queries.
Activity
sebastian commentedon May 26, 2021
The last row is not put aside as unaccounted for. The unaccounted for business only applies if there is another AID for us to attach the information to, which in this case there is not.
The result, in this example, would be: 5 + noise(1).
Presumably there would additionally be a noise layer associated with the negative condition excluding ssn
f, or LED compensating for the low effect exclusion of AID values.If you can exclude a victim, then this is clearly not safe...
I think a premise for this attack to work would be if we have a query that meets the following criteria:
Let's alter the above example such that both tables have an AID to make this attack work. TL;DR: The difference is now between
6 + noise(2)in the first query, and10 + noise(2)(and presumably extra noise layers?) in the second query.The tables would be as in the original example, only with
product_idbeing an AID as well.Clients:
Purchases:
Now the query
select count(*) from purchases join clients on client_id = clients.idwould yield:Anonymized based on
ssn:i.e. a count of
10 - 4 + noise(1) = 6 + noise(1)Anonymized based on
product_id:i.e. a count of
10 - 0 + noise(2) = 10 + noise(2)The final anonymized result would be:
6 + noise(2)For query
select count(*) from purchases left join clients on client_id = clients.id and ssn <> 'f'would produce:Anonymized based on
ssn:i.e. a count of
5 + 5 + noise(1) = 10 + noise(1)Anonymized based on
product_id:i.e. a count of
10 + noise(2)The final anonymized result would therefore be
10 + noise(2)cristianberneanu commentedon May 26, 2021
The example with a single AID was for illustrative purposes.
In many joins, there would be 2 or more AIDs, with the ones on the left side being non-null.
Plus, if we have an algorithm for handling null AID values, why wouldn't we use it consistently in all cases?
I don't think LED can compensate for not flattening outliers.
yoid2000 commentedon May 27, 2021
The design I've settled on will adjust for one AID, and this adjustment takes place before noise and flattening are computed. In fact it happens within the selectable containing the isolating condition.
So in the case of this attack, LED would insert the rows with
ssn = fback into the computation, and there would be difference in the underlying data for both queries.Can I suggest that we revisit this attack after LED is implemented in the reference implementation?