Re: FPW compression leaks information

On 04/10/2015 05:17 AM, Robert Haas wrote:
> I bet that there are at least 1000 covert channel attacks that are
> more practically exploitable than this. When this is anywhere near
> the top of the list of things to worry about, I recommend we throw a
> huge party and then fly home in our faster-than-light starships
> which, by then, will probably be available at Walmart.

Let's try to put some perspective on how serious (or not) this leak is.
I'm going to use finding a password hash in pg_authid as the target.

After each checkpoint, we can make one "guess", and see how that
compresses. If we assume ideal conditions, and guess one hex digit at a
time (the md5 hashes are stored as hex strings), you can find a 32 digit
hash in 16*32 = 512 checkpoints. You could possible improve on that, by
doing a binary search of the digits: first use a "guess" that contains
digits 0-8, then 9-f, and find which range the victim was in. The split
that range in two, repeat, until you find the digit. With that method,
the theoretical minimum is log2(16)*32 = 128 checkpoints.

Obviously, the real world is more complicated and you won't get very
close to that ideal case.

For my entertainment, I wrote a little exploit script (attached). I
didn't use the binary-search approach, it guesses one digit at a time.
Testing on my laptop, in a newly initdb'd database with no other
activity, it found a full MD5 hash in 3594 checkpoints. I cheated to
make it faster, and used the CHECKPOINT command instead of waiting or
writing a lot of WAL, to trigger the checkpoints, but that shouldn't
affect the number of checkpoints required. Your mileage may vary, of
course, and I'm sure this script will get confused and not work in many
cases, but OTOH I'm sure you could also optimize it further.

If we take that ~4000 checkpoints figure, and checkpoint_timeout=5
minutes, it would take about two weeks. But if you're happy with getting
just the first 4 or 8 bytes or so, and launch a dictionary attack on
that, you can stop much earlier than that.

- Heikki