Re: Black Hat: New database attack revealed

New timing attack doesn't need application bugs to work

http://www.computerworlduk.com/management/security/cybercrime/news/index.cfm?RSS&newsid=4344

Am Donnerstag, 2. August 2007 13:31 schrieb Robert Bernier:
> New timing attack doesn't need application bugs to work
>
> http://www.computerworlduk.com/management/security/cybercrime/news/index.cf
>m?RSS&newsid=4344

This is complete BS, as evidenced by this statement:

"""
their attack involves performing record insertion operations, typically
available to all database users - including anonymous users of front-end web
applications - and analysing the time it takes to perform different kinds of
insertions.
"""

In principle, attacks of this kind would be possible, but it's not quite as
simple as they make it appear.

--
Peter Eisentraut
http://developer.postgresql.org/~petere/

Peter Eisentraut wrote:
> Am Donnerstag, 2. August 2007 13:31 schrieb Robert Bernier:
>> New timing attack doesn't need application bugs to work
>>
>> http://www.computerworlduk.com/management/security/cybercrime/news/index.cf
>> m?RSS&newsid=4344
>
> This is complete BS, as evidenced by this statement:
>
> """
> their attack involves performing record insertion operations, typically
> available to all database users - including anonymous users of front-end web
> applications - and analysing the time it takes to perform different kinds of
> insertions.
> """
>
> In principle, attacks of this kind would be possible, but it's not quite as
> simple as they make it appear.
>

That was roughly my thought as well.

In our case, would it even be possible given WAL?

Regards, Dave.

On Thu, Aug 02, 2007 at 01:27:22PM +0100, Dave Page wrote:
> Peter Eisentraut wrote:
> > Am Donnerstag, 2. August 2007 13:31 schrieb Robert Bernier:
> >> New timing attack doesn't need application bugs to work
> >>
> >> http://www.computerworlduk.com/management/security/cybercrime/news/index.cf
> >> m?RSS&newsid=4344
> >
> > This is complete BS, as evidenced by this statement:
> >
> > """
> > their attack involves performing record insertion operations, typically
> > available to all database users - including anonymous users of front-end web
> > applications - and analysing the time it takes to perform different kinds of
> > insertions.
> > """
> >
> > In principle, attacks of this kind would be possible, but it's not quite as
> > simple as they make it appear.
> >
>
> That was roughly my thought as well.
>
> In our case, would it even be possible given WAL?

From how I read it they rely on the time to insert into BTREE indexes (or
to lookup for unique keys etc). I don't see how WAL would change that (well
the values changes, but you would still see timing differences in cases
with lots-of-equal-keys-in-the-index or such things)

But I'd say that the simple act of fsyncing after every commit would in
most cases destroy any difference between these key lookups - that random
element coming in from different platter locations would be much higher
than the btree difference in my guess...

//Magnus

Magnus Hagander wrote:
>> In our case, would it even be possible given WAL?
>
>>From how I read it they rely on the time to insert into BTREE indexes (or
> to lookup for unique keys etc). I don't see how WAL would change that (well
> the values changes, but you would still see timing differences in cases
> with lots-of-equal-keys-in-the-index or such things)

Yeah, my reasoning was a little screwed up - now corrected by Greg :-)

> But I'd say that the simple act of fsyncing after every commit would in
> most cases destroy any difference between these key lookups - that random
> element coming in from different platter locations would be much higher
> than the btree difference in my guess...

Yeah.

Regards, Dave.

Dave Page wrote:
> Peter Eisentraut wrote:
>> Am Donnerstag, 2. August 2007 13:31 schrieb Robert Bernier:
>>> New timing attack doesn't need application bugs to work
>>>
>>> http://www.computerworlduk.com/management/security/cybercrime/news/index.cf
>>> m?RSS&newsid=4344
>> This is complete BS, as evidenced by this statement:
>>
>> """
>> their attack involves performing record insertion operations, typically
>> available to all database users - including anonymous users of front-end web
>> applications - and analysing the time it takes to perform different kinds of
>> insertions.
>> """
>>
>> In principle, attacks of this kind would be possible, but it's not quite as
>> simple as they make it appear.
>>
>
> That was roughly my thought as well.

Also given varying load, things moving in and out of cache buffers etc.
I am not really sure if this is at all relevant for anything but
database systems with very few concurrent users.

regards,
Lukas

dpage(at)postgresql(dot)org (Dave Page) writes:
> Peter Eisentraut wrote:
>> Am Donnerstag, 2. August 2007 13:31 schrieb Robert Bernier:
>>> New timing attack doesn't need application bugs to work
>>>
>>> http://www.computerworlduk.com/management/security/cybercrime/news/index.cf
>>> m?RSS&newsid=4344
>>
>> This is complete BS, as evidenced by this statement:
>>
>> """
>> their attack involves performing record insertion operations, typically
>> available to all database users - including anonymous users of front-end web
>> applications - and analysing the time it takes to perform different kinds of
>> insertions.
>> """
>>
>> In principle, attacks of this kind would be possible, but it's not quite as
>> simple as they make it appear.
>
> That was roughly my thought as well.
>
> In our case, would it even be possible given WAL?

That's only one of many things that would be likely to affect this.

- If there are multiple users doing work, that'll throw in load, in
general, to make it harder to distinguish timing information.

- Inserting has several effects, including:

- Throwing the new tuple onto a page. Several possibilities
ensue...

- Maybe it goes at the end of the DB file, in which there is a
risk of lock contention on that page that will throw timing
off.

- Maybe the location of the tuple was determined by the FSM, in
which case, it takes some time to look up that location, and
there *shouldn't* be lock contention on the page.

- If PCTFILLED is less than 100% (e.g. - we're trying to keep
space free), there's some extra scattering effect.

- I'll bet the upcoming "trying to keep tables CLUSTERed"
functionality affects behaviour...

- Then come index updates.

- If there are few indices, then effects should be low.
- If there are multiple concurrent updaters, there may be
timing effects from page locking.

Lots of "maybes" here, but certainly lots of things *likely* to happen
that will throw off attempts to time things. Configuration would also
have big effects on timings; more cache would generally make some
operations take less time, thereby drawing timings together, and
cutting down on the variations that the "attacker" is trying to
measure.

Unlike the RSA attacks, it's not evident that an attacker would
deterministically know terribly much about the contents of the
database based on having this timing information.

This might be significant if:
- you had just one or two streams of updates coming in, and
- you were running a database without cache.

Maybe there are Competing Products We Oughtn't Name that have somewhat
more deterministic timing behaviours, but this seems like a terribly
dubious attack to me...
--
output = reverse("moc.enworbbc" "@" "enworbbc")
http://cbbrowne.com/info/multiplexor.html
"The entire structure of the antitrust statutes in this country is a
jumble of economic irrationality and ignorance. It is the product: (a)
of a gross misinterpretation of history; and (b) of rather naive, and
certainly unrealistic, economic theories."
-- Alan Greenspan

Peter Eisentraut wrote:

>Am Donnerstag, 2. August 2007 13:31 schrieb Robert Bernier:
>
>
>>New timing attack doesn't need application bugs to work
>>
>>http://www.computerworlduk.com/management/security/cybercrime/news/index.cf
>>m?RSS&newsid=4344
>>
>>
>
>This is complete BS, as evidenced by this statement:
>
>"""
>their attack involves performing record insertion operations, typically
>available to all database users - including anonymous users of front-end web
>applications - and analysing the time it takes to perform different kinds of
>insertions.
>"""
>
>In principle, attacks of this kind would be possible, but it's not quite as
>simple as they make it appear.
>
>
>
In addition, the only information I can see getting out of this sort of
attack is the number of entries in the table, and *maybe* the sizes (but
not the contents) of the individual fields or rows. In the
cryptographic sense, this is leaking information, but I'm not sure most
people would be that worried about this information leaking. Foobar
Inc. may be very secretive about their customer list- but knowning that
they have exactly 12,345 customers, and that customer 1's name is 12
characters long, etc., doesn't tell their competitors much.

In addition, I bet the presence of optimizations, like the WAL or
vacuuming in Postgresql, signifigantly complicate the analysis. At
which point you don't need to be all that vigilant against this sort of
attack- for it to work, the attacker would have to run so many queries
and/or inserts against the database that they'd be blatantly obvious.
If someone wants to suck down all your database bandwidth for months at
a shot, then you probably need to talk to them, even if they're not
trying to perform a timing attack on the database...

Brian

All,

> Lots of "maybes" here, but certainly lots of things *likely* to happen
> that will throw off attempts to time things. Configuration would also
> have big effects on timings; more cache would generally make some
> operations take less time, thereby drawing timings together, and
> cutting down on the variations that the "attacker" is trying to
> measure.

Heh, I never thought our unpredictable response times would be an asset ...

--
Josh Berkus
PostgreSQL @ Sun
San Francisco

josh(at)agliodbs(dot)com (Josh Berkus) writes:
>> Lots of "maybes" here, but certainly lots of things *likely* to happen
>> that will throw off attempts to time things. Configuration would also
>> have big effects on timings; more cache would generally make some
>> operations take less time, thereby drawing timings together, and
>> cutting down on the variations that the "attacker" is trying to
>> measure.
>
> Heh, I never thought our unpredictable response times would be an asset ...

Hey, there's a much more optimistic way to regard this...

A lot of this comes from the developments that diminish the
"spikiness" of system behaviour, generally diminishing variations in
performance, which tend to make system behaviour *more* predictable,
not less.

Cacheing tends to make lots of operations run more quickly, ergo in
"about the same time," for the small, simple queries.

We saw this when we put v8.1 into production; in general, response
times got more predictable, indeed, more nearly constant. And that's
the sort of tendancy that will cut down on the would-be variations
that the attacker, in the described scenario, would be trying to look
for.
--
(format nil "~S(at)~S" "cbbrowne" "acm.org")
http://linuxdatabases.info/info/spreadsheets.html
Rules of the Evil Overlord #161. "I will occasionally vary my daily
routine and not live my life in a rut. For example, I will not always
take a swig of wine or ring a giant gong before finishing off my
enemy." <http://www.eviloverlord.com/>

Chris Browne wrote:

> Cacheing tends to make lots of operations run more quickly, ergo in
> "about the same time," for the small, simple queries.

Well but since the attack is based on inserting data, wouldnt this
likely cause cache invalidation in many cases?

regards,
Lukas

Lukas Kahwe Smith <smith(at)pooteeweet(dot)org> writes:
> Chris Browne wrote:
>
>> Cacheing tends to make lots of operations run more quickly, ergo in
>> "about the same time," for the small, simple queries.
>
> Well but since the attack is based on inserting data, wouldnt this
> likely cause cache invalidation in many cases?

Perhaps to some degree, but it is not at all clear that it will be
material. If they're adding new tuples to a predictable set of
tables, in large quantity, this will tend to lead to a pattern of:

- Allocating a new page (which will throw in a little bit of variance)
- Adding several tuples to that page

The index work will tend to draw a bunch of pages for the relevant
tables into cache, which should tend to stabilize, unless they're
actually throwing so much data at the system that they're really
making the DB larger, at which point I'd expect the "real" data to
start to disappear, washed out by their data.
--
output = ("cbbrowne" "@" "linuxfinances.info")
http://www3.sympatico.ca/cbbrowne/multiplexor.html
"Lumping configuration data, security data, kernel tuning parameters,
etc. into one monstrous fragile binary data structure is really dumb."
- David F. Skoll

Chris Browne wrote:

>Lukas Kahwe Smith <smith(at)pooteeweet(dot)org> writes:
>
>
>>Chris Browne wrote:
>>
>>
>>
>>>Cacheing tends to make lots of operations run more quickly, ergo in
>>>"about the same time," for the small, simple queries.
>>>
>>>
>>Well but since the attack is based on inserting data, wouldnt this
>>likely cause cache invalidation in many cases?
>>
>>
>
>Perhaps to some degree, but it is not at all clear that it will be
>material. If they're adding new tuples to a predictable set of
>tables, in large quantity, this will tend to lead to a pattern of:
>
> - Allocating a new page (which will throw in a little bit of variance)
> - Adding several tuples to that page
>
>The index work will tend to draw a bunch of pages for the relevant
>tables into cache, which should tend to stabilize, unless they're
>actually throwing so much data at the system that they're really
>making the DB larger, at which point I'd expect the "real" data to
>start to disappear, washed out by their data.
>
>
Dwelling on this issue *way* more than I think it deserves:

Any noise in the signal, including caching, vacuuming, other queries,
etc., can be averaged out, given a sufficient number of samples. Even
if the signal is very small and the noise is very large. The more noise
there is (relative to the signal), the more samples you need to average
the noise out, but the existence of noise doesn't disprove the
theoretical capability of the attack.

However, it does introduce a pragmatic concern- basically that the
necessity for large numbers of samples (queries) in order to overcome
the noise problem is itself a very noticeable effect. If you need to
spend days, weeks, or even months hammering a database server to get
enough samples in order to average out the noise, even the most obtuse
admin is likely to notice (if for no other than reason than all of the
other users of the database complaining about the slow performance).

Brian