Thread: 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@postgresql.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:
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
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.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=4344This 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, 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@agliodbs.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@~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@pooteeweet.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:
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
Dwelling on this issue *way* more than I think it deserves:Lukas Kahwe Smith <smith@pooteeweet.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.
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