Date: Thu, 29 Aug 2013 13:09:59 -0400
From: Stephen Frost <sfrost@snowman.net>
To: Kohei KaiGai <kaigai@kaigai.gr.jp>
Cc: "ktm@rice.edu" <ktm@rice.edu>, Alexander Korotkov <aekorotkov@gmail.com>,
 Oleg Bartunov <obartunov@gmail.com>, Greg Smith <greg@2ndquadrant.com>,
 PgHacker <pgsql-hackers@postgresql.org>
Subject: Re: [v9.4] row level security
Message-ID: <20130829170959.GU2706@tamriel.snowman.net>
References: <51E8ADD9.5020600@2ndQuadrant.com>
 <CAEZATCXdj4E8uPHxq7jiE=1gGVB0xyeHtE8wUjHoX385sHhx4Q@mail.gmail.com>
 <CADyhKSWw1RY01tyuhRzu2HAa_+B9Z5qS6Jv+HEA1w0C9Ua2QLQ@mail.gmail.com>
 <521D1C2B.8090503@2ndQuadrant.com>
 <CAF4Au4xDXzACfC_KrXXpu=4et3XhUe5NtK=6y6yq39Cs2U0XKg@mail.gmail.com>
 <CADyhKSWkHrPqbRsFK0LjPMOOTsbKGWOuN75GqYJrxCDO3CKWtA@mail.gmail.com>
 <CAPpHfdsgMrBnzu9um48O6kwY=_pRFuRrBrHqnA03fCAo8x3-Gg@mail.gmail.com>
 <CADyhKSUpcYKNm3rQRwCFqkTZfO3_ZrqYKjAqDxKeA6WeLezSbw@mail.gmail.com>
 <20130829142321.GA30496@aart.rice.edu>
 <CADyhKSUD7qdQeTndZ6mDpp05V6MnRBzQO1FmYBq1+Zp37oyRrg@mail.gmail.com>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha1;
 protocol="application/pgp-signature"; boundary="jd3i04tXUCH+oY1c"
Content-Disposition: inline
In-Reply-To: 
 <CADyhKSUD7qdQeTndZ6mDpp05V6MnRBzQO1FmYBq1+Zp37oyRrg@mail.gmail.com>
User-Agent: Mutt/1.5.21 (2010-09-15)
Precedence: bulk
Sender: pgsql-hackers-owner@postgresql.org


--jd3i04tXUCH+oY1c
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline

* Kohei KaiGai (kaigai@kaigai.gr.jp) wrote:
> Although I didn't touch this task by myself, my senior colleague said that we
> calculated some possible bandwidth of leakage as an evident when we ship
> supercomputer system with MAC feature for customer who worry about security.
> I'm not sure how to measure it. However, if we assume a human can run up to
> 5 query per seconds, he needs 2-3 seconds to identify a particular integer value
> less than 10000, it means bandwidth of this covert channel is less than 5bps.
> I'm not sure whether enterprise-grade dbms has to care about these amount
> of covert channel.

A human isn't necessary in this particular scenario- you're doing a
simple binary search through the space, which computers can be awful
good at.  Using the type's bounds (eg: an 'integer' field is only
32bits) and forcing index scans, you could tell how many records exist
and then break down how many exist in the first half, second half, and
then split those..  Eventually, you could work out every value in the
column.

That could be applied to variable length values also, though it'd be
more costly to get down to the exact values.

I don't have a solution to these issues offhand except to suggest that,
in such an environment, having a "don't allow these users to run
EXPLAIN" and similar options would probably be welcome.  Even then there
are potential timing attacks, but that certainly increases the level of
effort involved.

	Thanks,

		Stephen

--jd3i04tXUCH+oY1c
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.12 (GNU/Linux)

iEUEARECAAYFAlIfgGcACgkQrzgMPqB3kihe6gCWPPr5W6H07DMvE8YjhVdyZOV7
WACcDQ8z5cUaFAONxtdS2GiD6gR1VPU=
=a65t
-----END PGP SIGNATURE-----

--jd3i04tXUCH+oY1c--