[Music]
hey everyone my name is dan draper and
i'm the ceo and founder at citch and
today i'm going to be talking about
practical attacks on encrypted databases
so the first question you might ask
yourself is why do we actually bother to
encrypt the database what kinds of
things are we protecting ourselves from
so there are some threats to consider
as to why we would want to encrypt the
database
number one is
let's say we're afraid of an attacker
who learns the database connections
trick there's only one database
connection string for a database
typically and if that's breached then a
user could potentially get access to the
database we might be concerned about an
attacker who gains access to the host
server the actual machine where the
database is running
we might be afraid of an attacker who
retrieves a database dump or a backup
that's actually relatively easy to
achieve in in many cases and quite
common
and one final one which we often don't
tend to think about is a trusted user an
insider in this case a trusted database
administrator who maybe we want to be
able to access the database but not
necessarily be able to read all of the
the data stored in the tables
before we go on i wanted to make a quick
mention to
um assistant professor paul grubbs who
was the co-author of a paper from back
in 2017 called why your encrypted
database is not secure a lot of the work
in this talk is based on that paper
and trying to take a more practical
approach so that it's accessible to a
wider audience
but certainly a big thanks goes out to
paul and his co-authors for writing that
paper
so given this what leads to exploits
certainly one of the major things is
this idea of a query cache as
things like mysql and postgresql use
query caches quite heavily for
performance but that can leak
information leading to an attack
logs query logs system logs
writer headlogs many databases use this
idea of a writer headlog to ensure
consistency and reliability
but that comes with the potential to
reveal information to an attacker
an obvious one but worth stating
nonetheless is poor key management poor
key management is true of any
cryptographic system
and no less in this case
shortcomings in the cryptography itself
and we'll talk more about that
and some examples of shortcomings like
those
in this talk
certainly that's a major part of why
data is lost
and finally poor assumptions about data
sensitivity what kinds of data
should we actually consider to be secret
what kinds of data might we be thinking
of quite innocuous but could lead to
leverage for an attacker
and i would also like to mention that
the techniques and attacks in this talk
please use for good
don't just go start attacking random
servers or databases on the internet um
it's probably legal and not really a
nice thing to do so use this just for
your own educational purposes or in test
environments only please
all right let's get started with the
first kind of encryption that i want to
talk about today which is called
transparent data encryption now this is
the formal name for what we often refer
to as encryption at rest so what is
encryption at rest or transparent data
encryption
transparent data encryption is
encrypting the file system for the
machine where the database is running
and so because when the database boots
up it needs to get access to the data it
also means that the keys to perform the
decryption need to run on the same
machine
and actually all the data that the data
needs to manage gets loaded into memory
and is available in the clear so
transparent data encryption actually
doesn't protect us from a whole lot
certainly if and certainly if an
attacker gets access to
um
the machine itself the host um or even
the application
that's accessing that database
transparent data encryption doesn't
protect us
and what i wanted to do is just show you
a very simple attack that demonstrates
uh really how useless tde is in practice
and that is through this idea of sql
injection so really nice simple easy
attack to get us started you've probably
heard of sql injection if you haven't
i'm about to show you what it is
we'll get into some more interesting
attacks and advanced attacks later in
the talk
with a single injection attack i
actually don't need access to
the
client application client or application
and i don't need access to the database
host all i need is the ability to
enter particularly crafted queries and
for the developer of the application
that i'm querying
to have not sanitized their inputs
properly and this is a very common sadly
still very common problem in our
industry
so i've created a postgresql instance in
amazon's rds it's their relational data
service
and you can see from the configuration
here that i've enabled encryption this
configuration is in the story section so
amazon are trying to make it clear that
this is only applying to the file system
and not to all of the data stored
nonetheless a lot of people assume that
tde is going to protect them for a whole
bunch of things which it won't
so if we jump into the database console
now using psql
i can see i've got a few tables here
and i can just do selects on the data
like there's no encryption whatsoever
this is a
a products database that i've created
just for a simple you know ecommerce
application written in ruby on rails
and i've got a products table as you can
see and a customers table
one feature in this application
is a search capability very common for
an e-commerce application
um i've got some products in here that i
want to search i'm a big fan of sony
cameras so i'm going to search for sony
and you can see the results come back
now i'm going to exploit this
search bar to do a sql injection attack
first thing i want to do is find a query
that prevents any
search results product search results
coming back so i'm going to find a query
that matches nothing and that's xx that
gives me no results so let's start with
that
then what i'm going to do
is
close the quote
so that
that signals to the database that that's
the end of the constraint
i'm going to union those results with a
query that is the same shape as the
products query
so but this time it's going to come from
a different table so i'm going to select
from
name email and i'm going to say as
description
so that the union query thinks it's the
same it's the same shape data
from
customers
i'm going to end that query as i
normally would and then i'm going to use
this dash dash
syntax which signals to the database
query parser that everything after that
should be treated as a comment and
essentially ignored and so that means
that if there are any anything there was
anything else left in the query um after
this input string it'll basically get
ignored so my uh code here will will
take precedence so let's see what
happens
okay i run that and i get
all of the customers instead of the
products and as you can see this is a
very simple
example of a sql injection attack but
the point here is that transparent data
encryption protected us from nothing
okay so what if an attacker does have
access to the host server how can we
protect ourselves maybe they've got
access through a remote code execution
or maybe they're even a trusted insider
or a semi-trusted insider
one technique we can use in the
postgresql ecosystem is called pg crypto
it's an extension that adds some
additional functions
so how does it work
pgcrypto provides a whole bunch of
functions but one example
is the pgp sim encrypt function
pgp sim encrypts uses the
pretty good privacy library underneath
the hood
performs a symmetric encryption using a
pre-shared key and in this case i'm
using it to encrypt
my
name and email address for the data that
i'm storing in the table
so i've created a little demonstration
database here called
pgcryptodemo
just has a users table inside it and
when i query the users table you can see
that everything inside that table has
been encrypted so if an attacker was
able to get access to this database in
theory they wouldn't be able to get
access to any of the underlying
information it's been fully encrypted by
this pgcrypto library
but i'm going to show you how to attack
it
so attack two
direct memory access
in this attack as mentioned this relies
on the attacker getting access to the
database host that's been compromised
so to demonstrate this attack i've set
up my mac on my right hand side here and
i'm going to connect to the database
running on my linux box which is on my
left hand side and show you that i can
actually extract some of the information
over the wire as it's being inserted
to do that i'm going to use a tool
called avml or acquire volatile memory
for linux ironically this tool has
actually been created by microsoft
it's been very useful in these kinds of
tests
so the first thing i'm going to do is go
over to my mac here
and connect to my linux box on my local
network
and connect to the pg crypto demo
database
okay
you can see it's got the same users
table in it
so i'm going to run a query that i ran
before and this is going to insert into
the user's table name and email
it's going to use that pgp sim encrypt
function that we talked about before
it's just going to encrypt the
name here homer simpson with the same
key
and the email homer at springfield.com
once again with the same key so i'm
going to run that
insert
and then when we select from the users
table you can see that now there are two
rows and they're fully encrypted i can't
see any information now what i'm going
to do is take advantage of the fact that
postgres stores some of these queries in
a query cache
so using the avml tool on my linux box
which is hosting the database
i'm going to run
as root using sudo
avml
and then i'm going to
push the output onto one of my local
drives here
avml.lime
it's going to take a while to run
thankfully this is pre-recorded so we
can skip ahead to the end
okay so that's just finished uh my
machine here is 64 has 64 gig memory so
took about six or seven minutes
now i have this file on my b volume here
called avml.lime
lime is a particular format and there
are tools that can read it but we
actually don't need to use any of those
tools we can do something really
just brutal and nasty
so i'm actually just going to cat and
grip
this avml file
i'm using a grep alternative here called
silver surfer which is a bit faster but
same basic idea
and i'm actually going to search just
for illustrative purposes
for the
query that we inserted or the data that
we inserted before which was homer
at
springfield.com
now remember that this is running on the
database machine and the query was
actually performed from my mac
it's going to kill that you can see here
that the exact command i used
on the mac to do that insertion
was stored in a query cache
uh in postgres on the server so
immediately i've now got access to the
key
now if i didn't know what data to grip
for i didn't know what i had been
inserted i could actually just grip for
say a regex of a hex encoded string
which would give me a key
there's all kinds of different things
you can do so i can search for
let's go pgp
sim encrypt
and as you can see there's all of the
previous attempts at getting this
working coming through in the logs
so really this is quite terrifying and a
pretty clear demonstration that tools
like pg crypto
are actually not as safe and secure as
you might think and that's because
you're sending the keys across the wire
via psql to be processed on the server
side
and because of the way pg postgres query
caching works a lot of that data gets
stored and potentially for really quite
a long time
so we need to do something better
all right so let's look at a third class
of encryption and this is called
deterministic encryption so
deterministic encryption is essentially
the idea that every time we encrypt a
particular value or a plain text if you
like with a given key we'll always get
the same result so in this case i've got
the encryption of cat under the key k
let me get that that ciphertext
dog gives me a different one obviously
then i encrypt cat again and i get the
same
safe text output and so that's what
makes it deterministic it's always going
to be the same output value
now why would we do that why is that a
good thing why is it useful
let's say we want to look at a database
like this where we're keeping
email addresses stored using
deterministic encryption in the table
let's say we want to look up a person
based on the email address we don't want
to send the email address to the server
as we've seen in the previous attack
that can be problematic
so we actually want to hash or use it to
terminate the encryption scheme to
encrypt the email address first
before performing the query and just do
the query on the site text rather than
on the plain text so it can be very
useful
however
deterministic encryption has some pretty
major drawbacks there was a study from
some researchers in 2015 and navid at al
and i'll link provide a link at the end
of the talk that showed that
deterministic encryption schemes
are vulnerable to what's known as
infants attacks so that's when the
distribution of the scythe texts mirrors
or is closely related to the
distribution of the plain texts so you
can see in this
bottom example the uh for a gaussian
distribution of of data the output
domain looks very very similar to the
input domain in terms of the
distribution
a really simple way to visualize that if
you've done any cryptography before i'm
sure you've seen this image
um
when you have a an output distribution
that looks the same shape has a similar
distribution to the input distribution
it doesn't really hide anything
you can use statistical methods and in
this case just visual inspection to see
that the encryption hasn't really worked
what we want is randomized encryption
but we'll come to that later
so attack number three but actually i'm
not going to do an inference attack i'm
going to do another kind of attack on
deterministic encryption schemes called
a chosen plaintext attack
this kind of attack relies on
the attacker being able to see the
results of the system encrypting
particular plaintexts or particular
values that we want to experiment with
that we want to test
there's lots of different ways you could
do that certainly if an attacker got
access to the database host itself they
could do that but i'm actually going to
use the
the database
right ahead log
and a previous like an older database
backup that i've managed to extract from
a compromised nfs server
so here's my copy of the
database dump it's for a medical
application
i've already imported that into a into a
database here
called medical app development
you can see it's got quite a bit of data
in it
and
let's take a look at the
patients table
as you can see all of that data is
encrypted it's it's unintelligible so
all of this data was encrypted using um
a in a ruby on rails application using
the encrypted record function um so that
has a particular format that wraps the
wraps uh the site text and the related
information inside json
you can also see that there's a
prescriptions table now the
prescriptions table is not encrypted
instead what this does is link
a patient id which has obviously
encrypted information associated with it
just to a
drug name
so we want to see if we can work out
if a particular individual is taking a
particular kind of drug
okay so now to to do this i'm actually
going to go to the public part of this
medical application it's running on my
local machine here for demonstration
purposes but in practice this would be
running on a on a public website
somewhere and i'm going to go and create
an appointment for the user that i'm
interested in learning more information
about
so on the new appointment screen i'm
going to
so i'm going to try i'm going to enter
the email address of the user
and i'm going to send an appointment
doesn't matter when
let's do it at 2 25 in the morning
and go ahead and create this appointment
now as i previously mentioned i've been
able to get access to the write ahead
logs
for the database that's powering this
application
so i'm going to take advantage of that
fact now
i know that because this is a rails
application and it's using uh encrypted
record i know the format for the
ciphertext or at least for the iv part
of the ciphertext is base64 encoded so
i'm going to grab four base64 encoded
strings inside the writer headlock
so i've got my writer head logs
available here
i'm going to
cap
them i'm going to grab for a regular
expression that matches should match a
base64
encoder string
of at least 12 characters long
and there we go we've got a few of them
now the latest one
we're looking for the iv
that's the initialization vector
so i'm going to use that iv value
which should be unique um to see if i
can find
the associated patient record and thus
the medications that they're taking from
my medical database
so to do that i'm going to use a query
that looks a bit like this
so we know that the
the data is going to be stored as a json
string
it's how rails
stores the data
so we're going to use postgresql
json functions here we're going to
extract
the initialization vector
out of that json payload we're going to
compare it to the string we found in the
writer head log
so remember we're comparing this to
the database dump that i i've managed to
steal it was a few days old
and yes we found a matching record so
you can see the json here the way that
encrypted record stores it
it's got this this hash key with the iv
and that's the iv that we found in the
writer head log and so now all i need to
do is find the prescription the user
with that id
inside the prescriptions table
so two seven
four nine
and there we have it
so we can see this patient's been
prescribed a disulferum which i if you
look it up is actually a drug
that helps people with alcohol
dependency
so that would be considered pretty
sensitive information and we've just
managed to get it despite the fact that
the database has been fully encrypted
and has been encrypted
before it's been sent to the database
server
i should mention that the way that rails
encryption does deterministic encryption
is it uses a fixed iv
that's the the initialization vector
here
um and that's what i was searching for
in this case
all right so we mentioned uh randomized
encryption before deterministic
encryption has issues so let's go all in
let's see how we can attack randomized
encryption so that is essentially the
best possible encryption
so attack 4
we're going to use a re-identification
attack
to perform this attack we don't need
access to either the client application
or the db host
all we need is a relatively recent dump
of the database like a backup and
actually this would seem fairly feasible
because if the data database has been
encrypted using randomized encryption
the dba may have just decided that an
additional encryption step wasn't
necessary because the data was already
encrypted in other words the
database dump may not necessarily be
considered sensitive
so in this example we're going to use a
check-in app uh something that
everyone's probably very very
unpainfully familiar with at the moment
and in this case we've got two data
types
one called a person which is fully
encrypted and one called a location
which is also encrypted with a small
caveat which i'll come to in a moment
and to
manage check-ins we're literally just
tracking in a check-in join table
the person id of the person who
checked in
and the location to which they're
checking in
so the data might look something like
this but there is a big problem here and
the database designer or the application
designer may never have realized how
much of a problem this was
and it's a common problem what's
happened here is we've encrypted fully
encrypted using a non-deterministic or
randomized scheme the name of the
location as as we have done for all the
information we store about it per person
but because we want to be able to do
geospatial queries
the location table also has longitudes
and latitude stored in plain text
and if we were to encrypt that data we
would no longer be able to do geospatial
searches so
for example you've got an outbreak of
covert and you want to find
all of the
people that have checked into venues
within say a 200 meter radius
i'm not sure if that's actually what
health professionals do but i can
imagine that would be a useful
useful kind of query
and actually this idea of storing
uh
what seems to be
in not sensitive data in a database
alongside
sensitive data that's been encrypted
um is actually very common but there's a
major issue when it comes to location
data in particular there was a study
back in 2013 that showed that
only four unique points what they call a
trajectory for a person are required to
identify a unique individual
they can do that with 95 confidence and
so we're going to take advantage of that
fact in this attack
now the way that we do that is by using
a related data set so actually i happen
to this is all hypothetical of course
and not real but
i've in this example in this
demonstration i've come across
a data set that has been leaked from an
online dating app that online dating app
was tracking location of all of its
users
it wasn't encrypting the data so now i
have a data set that's been linked to
the dart website
with a
person's email address and a whole set
of longitudes and latitudes
their trajectories if you like now while
this may be fabricated this example this
is based on many real world attacks for
example there was a new york times
journalist a few years ago who was able
to use an attack very similar to this to
learn an enormous amount of information
about people that they were profiling
and some of whom were even
in the
office of the president of the united
states so it's very real attack this is
just a demonstration showing something
very similar
so as i mentioned i was able to get a
copy of the check-in
app
database dump and so i've imported it
into a database on my local machine here
you can see there's a few tables you can
see the location table and people table
and the check-ins table
if i have a look at the people table
you can see that all of that data is
encrypted name and email address are
both encrypted
it can be a little bit tricky to see if
this is deterministic or randomized
encryption generally speaking if
something is randomized you should never
see any repeating values
or whereas deterministic you sometimes
will see repeating values if they're
repeating plain text in the database for
the locations table
you can see that the location name is
encrypted
but the
long and latitude longitudes and
latitudes are not
now as i mentioned
i also have a
reference data set from this
dating site
you can see that this has just got a csv
of longitudes and latitudes
mapped to email addresses of the of the
user
first thing we might want to try is look
for
common data points from our reference
csv file
in the check-in database
dump restore
let's so let's try one let's try this
first one here
and set the lat and the long values from
the reference csv row
and we don't find any values
now i'll let you in on a secret there
are no longs and lats here that match
exactly and this is actually quite a
problem for long beaches and latitudes
because they are
very very high precision numbers and to
find something that matches exactly can
be very challenging
so we're going to use a concept called a
geohash and what a geohash does is it
buckets
a longitudinal latitude down into a
particular kind of cell
of a certain precision depending on on
how wide a range of uh locations we want
to we want to assess so we're going to
see if if there are longs and lats from
the from the reference data set and the
target data set that fit into the same
geohash and use that as a proxy for
being the same location
so written a little script in ruby here
which
loads the reference data set
and creates a
hash of the
reference email addresses along with all
of their points i.e their trajectory
then it iterates each person
in my target database the checkin app
database
and tries to
find a person that matches us some of
those points ideally four or five of
those points before we have the sort of
confidence
relative confidence that that that
person is the same person
i'm just using this person similarity to
function which uh internally uses the
the geohashing technique to try and find
matching points
uh happy to share the source code for
anyone who might be interested in having
a look at it so let's go ahead and run
this code
so i'm going to call the correlate
function it's going to call this
correlate script and i'm going to pass
it the reference csv which remember was
the data from the leaked dating app
as you can see it's it's starting to
work through each of the records in the
target database um and we can see that
for id record one there was no match so
we weren't able to to learn who that
person was for id2 however found three
matching points so that's a reasonable
confidence level it's probably 70
confident
that's this person here further down
we've got
another person record id4 that found
four matching points so that's really a
very high confidence level probably 95
percent uh and continues to to go
through you can see that a few were not
found at all some had reasonable
confidence a few more had very high
confidence this one had five
and so on and so forth
so this is a very naive approach to go
through a thousand records would take
quite a while certainly if you've got
databases of hundreds of thousands or
millions of records this would be a very
inefficient way to do it
there are much smarter techniques for
example there's an algorithm called the
hungarian algorithm which is from
combinatorics and that allows you to do
things um
that allows you to do tests like this
much much faster
there are also more sophisticated ways
to assess similarity i can look at uh
not just the locations that a person has
been but what times of day they've been
what days of the week
how recently they've been versus
you know
somebody that's been very recently to a
location versus they haven't been there
for a while may indicate something about
that person so there are quite
sophisticated techniques that that
really motivated attackers can start to
apply and we've taken advantage here of
the fact that a very small amount of
seemingly innocuous data
was included in the database
despite the fact that all of the other
data was encrypted
so what have we learned from these four
attacks
number one i think it's pretty clear
encryption is not a silver bullet
and that even a small advantage matters
any small opportunity that an attacker
has to gain an advantage
will
potentially give them access to data
also what's really interesting going
through exercises like this is you
realize the security of your data can be
limited by the security of systems you
don't control as soon as you have any
information that is available to an
attacker they can cross-reference that
with data that's been leaked from
systems much less secure than yours
so how do we solve these problems
well number one
generally speaking the rule of thumb is
always encrypt everything and i mean
everything everything you possibly can
with randomized encryption so for
example aes running in gcm mode with a
256-bit key that is really the the best
possible encryption available we can use
things like strong surgical encryption
and what i mean by strong is it should
be randomized non-deterministic
but that's actually
really a very new technology
it's partly what we're working on at
scistash
and isn't isn't really generally
available yet but certainly those kinds
of these kinds of technologies are
coming
and similarly with order revealing
encryption and homomorphic encryption
these these um technologies promise to
allow us to
add encryption to systems
uh in ways that we haven't been able to
before and in particular
for example the case of the longitudes
and latitudes that we left unencrypted
because we wanted to do geospatial
searches on them things like homomorphic
and auto review and encryption
allow us to fully encrypt those data
points as well so we really get the the
best of both worlds
and it really goes without saying but
i'll repeat it nonetheless
always use a threat model and get pen
tests regularly from people who
understand this space
so finally i'll leave you with some
resources
there's the paper from paul grubbs and
his co-authors there's a really
interesting relatively digestible video
by a channel called computer file on
youtube which talks about this
re-identification problem using location
data
and then another paper by navidad al
from brown it talks about inference
attacks it's really interesting paper
quite heavy mathematically but if you're
interested in this kind of thing it's a
really good place to start
so thank you i hope you enjoyed this
talk and learned a few things about
encrypted databases and some of the
pitfalls you can follow me on twitter
danieldraper feel free to email me if
you're interested in talking about this
topic or if you want to learn more
and you can check me out at my workplace
at sivestatch.com
thanks for listening and talk to you
soon