1

Imaginary example, simplified to better explain the question. Let's say I have a form with the following fields :

  • user email
  • who did you vote for in 2012
  • who did you vote for in 2016

When submitted, I fill the following PostgreSQL (v.11) DB tables :

"UserList" table

  • Serial (auto-increment INT)
  • Email (text)

"UserData" table

  • Unique_Random (INT)
  • Vote_2012 (text)
  • Vote_2016 (text)

The entries are (as far as I can tell) unlinkable across tables because there is no relation between the Serial and the Unique Random ints.

Threat model : attacker gains full control of the postgreSQL DB server (both hardware and software)

If I am correct, UserData entries are not inserted in any specific position when created, so it should not be possible to tell which was added last.

Is there anything else (logs, data position on disk, memory, ...) that can reveal which entries were created or updated at the same time (and thus are linked) ?

If so, what can be done to prevent this ?

2
  • Define "at the same time". While this phrase seems clear in every day English, it is not at all for the technical purpose. In the same transaction? In transactions started in at the same time / within a given time frame? Also (always!) declare the Postgres version in use. May 14, 2019 at 22:14
  • Not sure yet about how it will be implemented, either same transaction or immediatly after (if one method can more easily solve the issue, I will adapt accordingly, this is why I left it as an open "detail"). You are right about the version, I will edit to precise "v11".
    – Jane1386
    May 14, 2019 at 22:19

2 Answers 2

0

Like mustaccio provided, CLUSTER is good way to remove physical traces of insert order. But rows do not necessarily remain in physical order: Other commands like VACUUM or various write operations are also free to move tuples around as Postgres sees fit. The physical order of rows is unreliable.

That aside, there is a simpler, more reliable way to identify rows inserted in the same transaction with the transaction ID in xmin:

Your evil attacker can simply join on xmin:

SELECT *
FROM   "UserList" ul
JOIN   "UserData" ud ON ud.xmin = ul.xmin

What's worse (or better, depends on who's asking): since Postgres 9.5, you can also keep track of commit timestamps with the track_commit_timestamp setting and thereby identify rows committed at certain times:

Even when inserted in separate transactions, transaction IDs are sequential and still may leak information due to their proximity ...

Possible solution

To cover xmin tracks you might UPDATE periodically (like weekly?):

UPDATE "UserList" SET email = email;
UPDATE "UserData" SET vote_2012 = vote_2012;

This writes new row versions for the whole table at full cost without changing user columns. But it sets a new xmin, thus covering all tracks. You might follow up with CLUSTER (also removes table and index bloat from rewriting all rows) and VACUUM ANALYZE to make it complete.

If your tables are big, consider dropping all indexes before you do that and add them back after: cheaper overall.

OR just write new tables and drop the old ones, ordering rows randomly in the process - if you don't have many dependencies making that a pain. Faster than the above and it would serve the purpose perfectly.

6
  • You raise very interesting points, thank you very much ! About "track_commit_timestamp", it seem to be minor since the setting is "off" by default according to the doc. So as long as it remain "off" I guess it is safe. About "xmin" this seem more troublesome... Do you think it could be fixed by doing the inserts independantly (2 transactions) with added between "noise" operations (a very fast one repeating around 4 billion times) so that the UserData Unique Random field xmin counter always has the same fixed value (counter reset) ?
    – Jane1386
    May 14, 2019 at 23:08
  • @Jane1386: No I do not think so. xmin is an internal field, essential to handling concurrency. It can't be the same for all, you won't be able to run 4 billion transactions it a short period of time, and if you were, you'd run into transaction ID wraparound issues. A more practical approach: periodically UPDATE all rows (without changing values), that sets a new xmin for all. Still expensive, but manageable ... May 14, 2019 at 23:18
  • Awesome, periodic update it will be then ! Updating "UserData" only should be enough, I just want to break the relation between the tables (the order in which emails were added is not confidential). One question about your "OR" option : would I need to delete the entire old table (structure included) or is it ok to simply empty it (keep just 2 versions "A" and "B" and migrate entries back and forth) ? Last question : no other log or transaction history I should worry that could be used to retrieve the old xmin (no track left) ? Many thanks again (about to mark as solved) !
    – Jane1386
    May 15, 2019 at 0:44
  • Dump & restore or write to a new table or rewrite rows in the same - the two important items are to write new row versions and to reorder rows physically. Default logs would not leak information unless you change settings to log SQL commands. Logging errors that contain data might be a corner case issue. May 15, 2019 at 1:23
  • I don't see how periodic update solves your problem -- your data are vulnerable to de-de-identification between the updates, rendering this approach useless, since you can't control when the malicious actor penetrates your system.
    – mustaccio
    May 15, 2019 at 2:06
0

Rows inserted at the same time, particularly in the insert-only use case such as yours, will very likely reside next to each other on disk and as a result will have tuple IDs indicating that. They will remain so until you CLUSTER the table using your unique_random1 column as the index key. You will need to run CLUSTER periodically to shuffle newly inserted rows.

Another bit of information that potentially correlates inserted rows is their transaction ID (XID), which might remain unchanged after the original commit, unless these rows at some later time are updated by separate transactions. I don't believe CLUSTER changes row XIDs.

Basically the same information -- the transaction ID, along with the row data, -- will also be stored in the write-ahead log (WAL). WAL segments will get overwritten at some point, depending on your database's checkpoint frequency.

TL;DR: You probably shouldn't rely on Postgres internals for reliable deidentification of your data.


1 -- Although, what's truly random, cannot have guaranteed uniqueness. You probably meant some sort of a hash.

1
  • Thanks for the CLUSTER clue ! If I understand the doc correctly, it is kind of similar to a disk defragmentation : data is re-ordered (physicaly moved) so its position does not reveal any meaningful info afterward, right ? Nothing else to worry about, like in the logs, internal hidden timestamp, ... ? About the randomness, I did not mean a direct hash (that would be trivial to crack since the User ID is such a limited range). I plan to use pgcrypto "gen_random_bytes" or a similar OS CSPRNG, search if already used, then gen another one if needed (uniqueness guaranteed by retries).
    – Jane1386
    May 14, 2019 at 21:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.