Thread: Reconstructing transaction content after the fact

Hi,

I'm a long time PostgreSQL user (since 7.x), familiar with the basics of
PostgreSQL internals and I'm currently participating in an audit of a
software voting solution which should for obvious reasons avoid to store
any link between the voter register and the actual votes.

The software uses a modern version of PostgreSQL (9.6 or later) and uses
a transaction to store a vote and the corresponding register entry in
two separate tables.

There's already an obvious angle of attack to correlate a vote and a
register entry : the WAL. That said the WAL can be configured to be
short lived to minimize the attack surface. By my understanding a low
checkpoint_timeout value should allow postgresql to recycle/remove old
WAL files early unless the system is overloaded. This can become a bit
messy but if the system is tightly controlled I believe the attack
surface can be reduced.

Another angle I could think of are the transaction ids. If I'm not
mistaken they are stored on disk inside the files storing table and
index data (my quick read of the documentation lets me think the txid is
stored in t_xmin in the HeapTupleHeaderData for a row content).
These values might be cleaned up when the data is visible by all
currently running transaction but I think this isn't needed and so
probably not done (this information is stored in the visibility map). So
reading the raw content from disk you should be able to correlate data
in several tables from a single transaction by comparing the txid.

Are txids in table file data indeed a means by which you can recover the
data written by a single transaction (assuming the txids don't overflow
the 32bit limit during the life of the cluster) ?

Are these t_xmin values ever cleaned up (by VACUUM or another mechanism)
? If positive is there a way to configure the approximate time during
which these values can be recovered ?

Is there a way to access these values by connecting to a PostgreSQL
server instead of analyzing in-memory or on-disk data ?

Best regards,

-- 
Lionel Bouton
gérant de JTEK SARL
https://www.linkedin.com/in/lionelbouton/

Lionel Bouton <lionel.bouton@jtek.fr> writes:
> Are txids in table file data indeed a means by which you can recover the
> data written by a single transaction (assuming the txids don't overflow
> the 32bit limit during the life of the cluster) ?

They are.  You could reduce the connections between different rows by
writing them in different subtransactions of the parent transaction
(use SAVEPOINT/RELEASE SAVEPOINT, or exception blocks in plpgsql).
But unless there's many parallel transactions writing data, somebody
could probably still reconstruct things by assuming that nearby XIDs
represent subtransactions of a single transaction.

> Are these t_xmin values ever cleaned up (by VACUUM or another mechanism)
> ? If positive is there a way to configure the approximate time during
> which these values can be recovered ?

See VACUUM FREEZE.  You couldn't hide connections immediately after
insertion, but if the idea is to sanitize every so often, it'd help.

> Is there a way to access these values by connecting to a PostgreSQL
> server instead of analyzing in-memory or on-disk data ?

SELECT xmin, ... FROM votes;

            regards, tom lane

Lionel:

On Wed, Sep 2, 2020 at 5:46 PM Lionel Bouton <lionel.bouton@jtek.fr> wrote:
...
> The software uses a modern version of PostgreSQL (9.6 or later) and uses
> a transaction to store a vote and the corresponding register entry in
> two separate tables.
...>
> There's already an obvious angle of attack to correlate a vote and a
> register entry : the WAL. That said the WAL can be configured to be
> short lived to minimize the attack surface. By my understanding a low
....
> Another angle I could think of are the transaction ids. If I'm not
> mistaken they are stored on disk inside the files storing table and
> index data (my quick read of the documentation lets me think the txid is
...
> Is there a way to access these values by connecting to a PostgreSQL
> server instead of analyzing in-memory or on-disk data ?

If you assume attackers can read your disks, or even query arbitrary
tables, you are going to find plenty of potential attacks. Apart from
xid databases tend to lay insertions sequentially on disk, so if your
main way of filling the tables is inserting a pair you've got a nice
probability of correlating them with just two "select * from
voters/entries" ( or just dumping the raw table files if they get file
but not sql access ). In fact even paper voting can be attacked this
way ( in spain they write every voter in the order in which they vote
on a sheet, and if you do not take care to shake the ballot boxes you
can  get a very decent aproximation to the envelope insertion order (
you will need raw access to the boxes, like you would need raw sql or
disk access in your case ) ) .   ( Not sure if ballot box is the
correct term )

For something like that I would try to insure no disk access, no raw
sql access, give the apps a single point of access to the DB
mediating every query/operation with a stored procedure/function,
using accounts with access to only those, even for selects, so you
have tight control and easier auditing.

Francisco Olarte.

Alvaro Herrera <alvherre@2ndquadrant.com> writes:
> On 2020-Sep-02, Tom Lane wrote:
>> See VACUUM FREEZE.  You couldn't hide connections immediately after
>> insertion, but if the idea is to sanitize every so often, it'd help.

> Starting with 9.4 which introduced the use of HEAP_XMIN_FROZEN
> combination in infomask to replace rewriting the xmin value proper, the
> Xids will be preserved by freezing, so that won't help.

Ah, right.

> One option to hide the xids might be to recreate the tables every once
> in a while, with something like

Hmm.  Expensive, but if you were willing to make it even more expensive,
you could also defeat the tuple-ordering attacks mentioned upthread:

   CREATE TABLE votes_copy AS SELECT * FROM votes ORDER BY random();


            regards, tom lane