who's up working on Rocky's it would
need you help you remember well go on
okay hey mrs. sound good in the back
alright silo ladder let's try how about
that that's hang it shame ok I'll try
speak with my big boy voice we'll see
how that goes ok good evening everyone
thank you for coming to this talk I'm
Adam ever small I'm a soon-to-be former
PhD student at the University of
Wisconsin by that I mean I'm hope to be
graduating not that I'm dropping out I
study cloud security and applied
cryptography and i'm here to talk to you
today about some fairly exciting new
research some new cryptographic
primitives and a protocol for using them
with passwords which we think is going
to really improve the way that passwords
are used today this is work originally
presented at usenix security back in
2015 this is joint work with two other
PhD students will Chatterjee and Sam Sam
Scott Rahul's at Cornell Tech Sam
Scott's at Royal Holloway in London and
also to professors re jewels and Tom
rishton part both of which are in
Cornell Tech ok so we use passwords
every day we use these things to
authenticate to our devices and we use
these things to act at access online
servers sorry let me do this one more
time a range manage two displays when I
can see all my notes all right and what
about now ah now you guys are you seeing
the secret side let's try this way it's
no fun now you guys get to see the good
stuff get the trick we'll see if not
I'll fly with no notes you see how it
goes ok not going to work will do this
you like it ok so we use masters every
day we use these things to log on to our
devices and our online services but the
way we're using these passwords the way
we're storing this passwords is
fundamentally broken and the reason for
that is password databases get stolen
and when they get stolen it's too easy
to crack these passwords so what I hope
you to present to you today is a new
direction so a new architecture for
protecting passwords something built
around a cryptographic pseudo-random
function provide provided as a service
and this is going to not only prevent
offline attacks but this is going to
enable a password people who use
passwords to be able to detect online
attacks and do something about them so
they can rotate keys and they can
cryptographically erase information once
it's been stolen all right so first let
me lock down some terminology so I'm
going to use the term PRF which is sort
for pseudo-random function but i'm going
to say PRS because i'm lazy ok so PRS is
really simple it's going to take an
input some arbitrary input imagine that
document or in our case is a password
and it may or may not take a secret key
right and it's going to produce some
fixed length output and this output is
going to be for more or less it's going
to look like a random string right so
think hash functions in fact hash
functions are pseudo random functions so
shot to shot three or keyed hash
functions like H Mac and when we're
talking about passwords things like
decrypt and s script these things are
all pseudo-random function so you takin
some input run them through some
algorithm you get some fix like the
output ok so let's talk about a
motivating example if you go to LinkedIn
the only way to access linkedin is you
provide them an email address and a
password now of course linkedin has to
store this password in some way so when
you come back they can check if your
password is so same alright so pop quiz
how was linkedin storing passwords in
2012 this is a multiple choice question
someone in this someone in this room
knows this answer that'd be that'd be
weird to do all the above okay they
weren't starting plain text after thank
goodness some people are though it turns
out in 2012 they were storing unsalted
hashes of passwords of course the reason
we know this is because in 2012
attackers broke in they stole a large
corpus of passwords and then they then
leaked them online of course once they
lead them online because they were
unsalted security researchers had a
field day in two weeks worth of cracking
security researchers recovered most of
the passwords now the reason it was so
efficient is because they weren't
salting passwords but I'd like to point
out that even if Lincoln was following
industry best practices if they were
using salt and these iterated hashes
that are harder to compute this doesn't
actually stop this offline dictionary
attacks it only slows them down all
right it sounds like I'm picking on
linkedin a little bit but these password
database breaches are common surely you
guys read the internet and occasionally
on the internet we hear about these
kinds of things and these don't just
happen to mom and pop shops these are
sophisticated technology companies these
are news companies these are all kinds
of companies who are experiencing these
password database breaches so our
observation is that password database
preachers are common now of course we
want to limit these breaches from
occurring if possible but when they do
occur we want the data owners that have
some recourse and we don't want the
recourse to be sorry your account has
been locked also probably instagrammed
counties been also broken into because
I'm sorry use the same password
everywhere and I have to log in and
change your password we want something
better all right so let's look at a
slightly better approach in January 2015
Facebook presented this slide at
real-world crypto in London so I'll talk
to you really briefly through it this is
how facebook process is your password we
actually log in and type your password
so they take your plaintext password
they run it through md5 then take a 20
bytes shell they create a 20 bytes salts
they run that through an H Mac rishabh
one they then connect to a remote server
run that with HTML shot to on a secret
hello and that service and the result
back run that through a script run with
or hmx out to and then store them in
database
everyone got that okay so you're
probably thinking why is this so
complicated and why why would Facebook
do this do this this way the reason they
do this this way is actually historical
so let's walk through it one at a time
so once upon a time Facebook had 800
million passwords that were md5 hashes
stored in a database they thought
rightly so hmm this is probably not a
good idea we should improve our strategy
but we have 800 million passwords in a
database it's unreasonable for us to say
hey all facebook users login on Tuesday
give us your password we'd like to
update our code and our database all in
one day so what do they do so they want
to move to assaulted sha-1 hash so
instead what they decided to do is take
the existing md5 hashes add a 20 bytes
salts wrap them and sha-1 and write them
back to the database few years later
shell 1 is broken and they think okay
now what reimaging well we're going to
do the same thing we're going to switch
the shot to in this case on another
machine with a secret a little bit later
they decide this isn't good enough yet
so we're going to add s script a script
is kind of like a hard hash function I
it takes a lot of computation to compute
so they add this to the existing
database but the S script output is
really long and they don't want to throw
that in a database so then they run it
through shot to to make it smaller and
put it back in the database and what
we're left with is this code code is now
an archaeological record of Facebook
struggling with password storage
technology but I want to point out
something really interesting there's
something here that most tech companies
dump too and that's this so at some
point during processing your password
facebook connects to a remote server
still owned by Facebook put another
machine ask that machine to apply an H
max shot to you with a secret that's
held only on that machine and then get
the result back the reason this is
interesting is this leads to a different
kind of architecture so architecture is
more like this so at a very high level
the user provides the password to the
web server which provides some of that
pre-processing at some point it connects
to this crypto server the crypto server
runs this age
I shot two with a secret and sends the
result back the reason this is nice
because now critical information is not
only on one machine it's now on two
different machines so if an attack of
breaks and any seals either the password
database word of the secret but not both
the attacker now has insufficient
information to crack those passwords we
need to attack both machines to do it
okay so this is a nice architecture but
there are still some limitations so
people who do cryptography might say oh
I see a secret the first question I
might ask is how am I going to rotate
that secret the dirty little secret
inside Facebook is actually cannot
change this secret if they change the
secret they're going to eviscerate their
entire database of whatever it is 1.4
billion passwords at this point right so
there's sort of stuck with the secret
for us okay so that's not so good the
second problem is if an attacker breaks
in and steals the password database and
has access the crypto server you can't
run offline attacks okay so that's good
but if you tackle is actually the crypto
server he might be able to run online
tax and because of the way Facebook has
set up the API it's really difficult for
the crypto server to tell the difference
between a large volume of legitimate
traffic a passwords for different user
accounts and a bunch of guesses for the
same user account because every guest
with distinct in the way descriptive
server API looks okay so we like this
architecture but we want to fix these
problems all right so for the rest of
the talk I'm going to leave behind the
state of the art I'm going to talk about
our contribution to how we protect
passwords and we're going to sort of
start with this architecture and then
we're going to fix those problems that
we saw ok so the crypto server is now
again be called a Pythia PRS server and
we're going to change the API in such a
way that now the crypto server can
detect online attacks and when it
detects online at AXA can do something
about it and we also want to when we do
something about it we're talking about
is probably rotating the secret so we
can recover from compromises and even if
we don't detect compromises we can
proactively rotate secrets and when we
rotate secrets that will give us
cryptographic erasure meaning we're
going to invalidate stolen databases
through this key rotation and finally
what we want to build is not something
just for big tech companies like Google
and Facebook we want to build as a
multi-tenant service one of them
something that a service provider can
build it and allow players of all sizes
to use this to protect their passwords
and yet not have to outsource all their
security like I'll just give you all my
passwords and hope that you don't get
compromised we want some better balance
than that okay so what I'd like to do
for the next few minutes is take you
through a high level view of how how
Pythia PRS service works and then I'll
dive into some nitty gritty details okay
so we'll start with we have a web server
it's using Pythia to harden passwords
how does it n roll a new user so the
user logs in the Norway provides the
user name and probably a really crappy
password that's also used on a bunch of
other websites the web server is going
to choose a random value will call that
T this is going to be a user ID and it's
going to run the password through a
blinding function i'll define this later
we'll call that result X the web server
is going to connect to the 50th server
and issue a query the query is going to
contain the following it's going to have
a value w this is just a web server ID
it's going to have that user ID that we
just established and it's going to have
this blinded password so the Pythias
server is going to look up in a key
table and it's going to fetch a key
that's assigned specifically to this web
server it's then going to run the user
ID and the blinded password through this
function this F sub K and this is going
to be a this is going to be our key PRS
and I'll define this in a little bit and
the result is why and it's going to send
the result back to the web server the
web servers then going to run an
unblinding function and it produces some
value Z we called Leah protected
password think of it as you know the
output of iterated hash or decrypt or s
script and then I'm going to write this
to a database you can write the user
name the user ID and this protected
password and then when the user logs on
again later the web server once
essentially the same protocol it
produces some new guy uz prime when Z
prime equals Z web server knows ah this
was the original password and when it
doesn't match it just knows no that's
not the right password okay so that's
and ruling a user and checking a
password let's talk about compromise
recovery okay so web server is this big
database to protect the passwords that
guy breaks in maybe it's a sequel
injection who steals seven million or in
the case of Yahoo two billion or not
just want to blame one and a half
billion passwords so the nice thing is
if you're using Pythia the attacker
can't immediately run offline attacks
but technically he's got all the same
information you could probably run
online attacks but here the API is
different right the attacker has to
specify the web server ID and the user
ID which makes it really easy for the
Pythias server to see online attacks
right maybe you get 10 or 20 guesses on
a single user account before the Pythia
server realizes like oh this is not
right you can't you can't try 100
different passwords the computer server
can do something about it it can ban the
ipe it can throttle account it can lock
accounts probably most importantly you
can send a consent an alert to the admin
that says hey we see suspicious activity
using your web server ID so he sends an
alert to the web server the admin
realizes there's a problem he cleans up
the web server probably patches is a
sequel injection and the web server
context the Pythias over and says hey I
need a run key rotation so it produces a
new key K Prime 50 server then sends a
compact update token will call this
Delta that's going to enable the admin
to update his password database from the
old key K to the new key K Prime okay
and so the way the admin runs this
process if they saw Lizzie eyes to see I
Prime's I want to note that the admin
does all of this offline in the sense
that he doesn't require user interaction
he doesn't ask his users to log in and
change the password is enough to lock
their accounts you can do all of this
themselves it doesn't need the original
password and the the users password
doesn't change actually we're just
updating the encryption to earn your
king when he's done in contacts the
Pythia server and says hey the key I'm
done with key K so I want to delete it
and at this point when the 50 server
deletes it we're now in validating an
old password database okay so if there's
any cryptographers in the obvious
audience you may already be thinking
about like what kind of primitives do we
have
what kind of properties we need to
implement this okay so let's go quickly
through the list of requirements so we
need a scheme that's deterministic given
the same user ID key and a password of
course we need to produce the same
output we need the output to be
pseudo-random we need this weird
propagators partial message privacy we
want to require users to specify the
user ID in the clear to the 50th server
but we want to hide the password so if
you break into a 50 server you don't
actually see passwords it's kind of
weird property and of course we need key
rotation this enables us to recover from
compromises okay so a bunch of schemes
exist at least in 2015 when we did this
work pseudo random functions oblivious
to the random functions called partially
blind signatures it's a couple other
schemes they give us updateable
encryption but in 2015 when we did this
work if you looked at the intersection
of all of these turns out there with no
existing schemes so we had to create a
new scheme something we call partially
oblivious pseudo-random functional ok so
I'm tempted to go into serious details
there's only two slides with math so for
those of you who don't care about the
details it's only two slides hang with
me for a little bit ok so I'll tell you
how we build our partial you believe is
PRS we build our is using something
called a bilinear pairing and that's a
function E which maps inputs from two
groups onto a target group and it has to
satisfy this function maybe more
importantly each of these groups we have
something called the computational
diffie-hellman assumption moving given a
and X it's easy to compute a and X but
if i give you the value ada a to the X
it's hard to get it's hard to get back
either a or X it's called discrete log
hardness ok so given such a bilinear
pairing this is how we build our scheme
this is the blinding function you take
the password we hash it onto a group and
we raise it to the power of r where r is
just some random blinding factor it's
going to be selected uniquely for each
query this is going to perfectly hide
the password so the Pythias server
doesn't see doesn't wear any information
about passwords
send this in 50 a server and then the
50th server applies this key PRS so we
take the value X we hash the value T and
we raise the run it through the BI
linear function where is the whole thing
to the power K and then the unblinding
function is really simple it's we take
the inverse of our and we raise the
results of that if you write out what
this looks like you'll see that the
blinding factor and the unblinding
factor cancel out naturally and what
we're left with is a deterministic
computation using the inputs we wanted
precisely so so the password and user ID
always to the power of some secret key K
and that secret key K is known only to
the Pythias server ok so that's
enrolling user and verifying a password
compromised recovery is really simple so
we send the fraction k prime over K does
leak any information about either key
updates are really simple you take this
value raised to the power of this update
function if you write out what that
looks like you'll see that the old key
cancels out and only the new key is left
and so after an update function we have
the same user ID same password but now
under a new key and no residue from the
old king ok so that was a really deep
dive let's let's look at the big picture
and let's talk about what all this buys
us so first off we have a fiftieth
server that only sees blinded passwords
meaning it never sees the individual
passwords and it has enough information
meaning to check online tax meeting that
that you have to provide correct web
server IDs and user IDs in order to get
the right answer so it's going to be
easy for a 50th server to tell the
difference between legitimate traffic
and in legitimate traffic on the web
server side the web server never learns
the secret key and this is really nice
because if someone breaks in and they
steal everything in your web server you
want them to be missing some information
ok so we built one of these things
itself is open source we built it using
open source it is just a prototype but
we built it using engine acts we did the
implementation in Python sort of key
table in Mongo
you can get the source code on github
check out my website for information to
find these things there's even a test
and development server which don't
recommend for reductions you could go in
and gay but you know you can build it
via clients and you can use our server
if you want to test your clients so real
quick let's talk through some
implementation or some evaluation
details essentially 50 is fast and
scalable so if the Pythias server and
the web server are on the same network
so there's essentially no network
latency to worry about we can do PPO
queries in 5.2 milliseconds right that
might not mean anything without context
but to put this in context if you do it
erated hashing if you follow miss
current guidelines of 10,000 iterations
of sha-256 that's going to take you
depends on the cpu implication because
going to take you about 10 milliseconds
nine milliseconds right so Pythia is
going to be competitive with iterated
hashing and get a very different
security property actually in practice
you can actually use iterate hashing and
pity it together there's no reason you
have to use one of the other so
throughput is good if you're hosting
your own Pythia server we can on a
single a core machine we have a max
throughput of a little over 1,300
queries per second and storage on a 50
server is excellent right so on the
Pythia server it only has to remember
for each of its clients its clients now
our web server is not users right so i
have to the Pythia server needs to
remember a web server ID and key a
little bit of extra information for
detecting online attacks but this is
going to be independent of the number of
users behind that web server so to give
an example if i had a hundred million
web servers using a single Pythias
server the key table for that is less
than 20 gigabytes right independent of
how many users are using those hundred
million web servers right each hundred
million web server could itself have a
hundred million users and still I only
need 20 gigabyte SSD to store my key
table of course should probably keep
that key table very secure okay so
Pythia is fast and it's scalable
today I've mostly been talking about web
servers and that's because I think web
servers are the most natural use for
Pythia in our using paper we talked
about some more interesting ideas one of
the ideas we talked about is I mean
really you can use Pythia to secure
anything that's using using passwords in
the sense of security and you have an
internet connection so one of the things
we talked about the paper is called a
Bitcoin brain wallet and the idea here
is that there's a Bitcoin wallet you
don't want to store the key somewhere so
you create some passphrase or some
complex password and then in the past
people will try to learn these
passphrases through an iterated hashing
function use that output to be your
Bitcoin private key of course the
problem is if somebody cracks your
password in the same way then they now
own your Bitcoin wallet so you can
imagine doing the same pissy at work you
take a password but instead of running
through iterated hashing you connect to
a Pythia server you run this blinded
protocol you get some result and use
that result as your Bitcoin private key
and then when you want to update your
Bitcoin wallet you actually don't even
have to change your passphrase you just
connect with the Pythia server and have
it rotated key periodically and you
transfer funds from one wall to the next
so that's a fun idea and the other very
straightforward idea is you can imagine
and file encryption this way right so it
would require an internet connection but
you can imagine you put data on a remote
hard drive or on a laptop or phone and
you want to encrypt that data with a
passphrase but you want to use picea to
harden that password and the nice thing
is if you lose that device and you want
to race that data you don't have to wait
for that device to come online if you
have access the Pythia server you go to
the pity of serving you say hey I want
you to delete this key I'm going to
delete that key it's going to erase this
device whether or not that device is
online is a very nice property okay so
what does it take away from all this I
claim password storage is broken
password databases get breached and when
they do get breach it's too easy to
crack passwords we can fix this we fix
this using Pythia which not only
prevents offline attacks but it'll it
enables us to detect online attacks and
when we detect online attacks we can do
something about it we can rotate keys
that allows us to cryptographically
erase old and from
and then continue operating forward and
finally because we're using a service
architecture the idea is that this
should be this should be accessible to
more than just people with lots of
technical infrastructure this should be
enabling people of if you have some
service providers providing 50 of
services you can imagine a whole range
of people with taking different
technical sophistication being able to
gain the power of this strong
cryptography and with that thank you for
your time and I would love to hear your
questions do I have a link to the white
paper um you can find it let's see if i
can find this slide you can find it on
my webpage if you also if you search
Google for Pythia prf there is probably
not too many different responses since
you slow let's yeah I'm uh there we go
yeah so this is this is my web page and
you can find the paper from here Pythia
see if I remember this correct it's been
a while since we're neighbors so Pythia
is the name of it's the name of the
Oracle at Delphi right so it's supposed
to be this kind of random Oracle you ask
an inscrutable question you get
inscrutable answer unfortunately the
very heavily used name so there's a lot
of pythias in the world yeah
yeah so let me review the question so
the question was this seems nice and
tailored to a business setting you know
just going to work for the everyday
person I hope so this is our plan we
actually when we started this what we
wanted to do was protect passwords on
the user side in able to protect
particularly like my safari database of
local passwords sadly we got sidetracked
and we ran off under this other problem
I think so but of course somebody has to
be supporting this key server so you can
imagine if Google or Amazon or even one
password we're running their own Pythias
server and then individual people had
software that use those services it does
seem feasible of course somebody has to
stand those things up and operate them
yeah question what's how is the best
attack relative you brute force so we're
using provable security here and so the
strength of security we get here is you
know sort of no less than you're going
to get from the elliptic curves that
you're using underneath it if that makes
any sense ok so this is a very astute
question ok so let's see if i can find
that slide to demonstrate this ok so if
I understand the question it was if if
you tricked the server if you took the
Pythias server into running a key
rotation essentially is this going to
create a denial so around the web server
and in the the answer is of course
absolutely right which is a huge problem
right so the thought here is that you
know use one level of authentication to
verify queries and mean obviously a much
stronger level authentication to be able
to do things like fetch Keys destroy old
keys that kind of thing and the hope is
that
that that's a little more laborious to
do that work but you only have to do it
periodically yeah I mean this is
cryptographic erasure right if I break
in I delete the key and that's the key
you needed yet you're in trouble but
it's a different problem because the
keys are small it right you can imagine
the attacker breaks and erases your
database and passwords you're also in
trouble unless you have backups right so
it depends yes now the 50 server is like
outside of your data center and I have
to deal with you know it's this other
person being protect as well so yeah
there are problems hearing yeah any
other questions yeah yeah so the it so I
can repeat the question it's this seems
the seams form fit for people like AWS
Google cloud platform to be building the
service providers and yes when you think
that's absolutely true do I have any
plans to do so I do not unless the right
number of investors happen to be in this
room in which case I do there is a group
at Cornell Tech who's working on this
thing it's not clear how successful
they'll be although i should say that
software is not patented the software is
open source if you guys want to stand up
your own services you're more than
welcome to i actually will be happy to
volunteer to help with technical
expertise to get these things off the
ground but yeah this is our dream is
that if you're a neat if your AWS
provider you don't have sore passwords
yourself or you don't have to do all the
work bathroom stuff you can just
subscribe to AWS is picky of service and
then you can harden passwords as well
if you're running a Pythia server yeah
of course you can you can well any curve
is too strong so our construction is
based on a bilinear pairing and so
there's only certain sets of curves that
work this way since we did this work
there's been a little bit more work that
doesn't necessarily have to use that so
you have a little more flexibility and
curves but if you use our particular
construction you're stuck with curves
that are compatible to bilinear pairings
but beyond that yet you can use whatever
curves you implement all right guys
thanks for time