CRYPTO AND PRIVACY VILLAGE - Revolutionizing Authentication with Oblivious Cryptography

Video thumbnail (Frame 0) Video thumbnail (Frame 1793) Video thumbnail (Frame 2396) Video thumbnail (Frame 5242) Video thumbnail (Frame 6053) Video thumbnail (Frame 9630) Video thumbnail (Frame 11544) Video thumbnail (Frame 12893) Video thumbnail (Frame 15019) Video thumbnail (Frame 18138) Video thumbnail (Frame 20248) Video thumbnail (Frame 25049) Video thumbnail (Frame 26441) Video thumbnail (Frame 28856) Video thumbnail (Frame 29644) Video thumbnail (Frame 30498) Video thumbnail (Frame 31227) Video thumbnail (Frame 32260) Video thumbnail (Frame 33037) Video thumbnail (Frame 39245)
Video in TIB AV-Portal: CRYPTO AND PRIVACY VILLAGE - Revolutionizing Authentication with Oblivious Cryptography

Formal Metadata

CRYPTO AND PRIVACY VILLAGE - Revolutionizing Authentication with Oblivious Cryptography
Title of Series
CC Attribution 3.0 Unported:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Release Date

Content Metadata

Subject Area
Authentication Implementation Demo (music) Authentication Demo (music) Expert system Password Data storage device Student's t-test Expert system Cryptography Pulse repetition frequency Revision control Goodness of fit Cryptography Software Password Information security
Email Slide rule Key (cryptography) Direction (geometry) Data recovery Password Computer network Database Data storage device Philips CD-i Data dictionary Pulse repetition frequency Architecture Online service provider Password Website
NP-hard Email Standard deviation Multiplication sign Data storage device Password Database Bit Database Food energy Field (computer science) Twitter Hash function Password Hash function Computer hardware Order (biology) Iteration Website Information security Address space Row (database)
Point (geometry) NP-hard Scripting language Slide rule Server (computing) Functional (mathematics) Code Multiplication sign Virtual machine Password Database Maxima and minima Function (mathematics) Cryptography 2 (number) Facebook Process (computing) Hash function Semiconductor memory Password Right angle Information security Resultant Row (database)
Implementation Server (computing) Functional (mathematics) Building Service (economics) System administrator Virtual machine Rotation Web 2.0 Facebook Web service Cryptography Different (Kate Ryan album) Single-precision floating-point format Energy level Information security Multiplication Computer architecture Physical system Rotation NP-hard Key (cryptography) Information Server (computing) Data recovery Volume (thermodynamics) Maxima and minima Database Cryptography Pulse repetition frequency Process (computing) Personal digital assistant Password Right angle
Context awareness System administrator Mehrplatzsystem Function (mathematics) Web 2.0 Facebook Pulse repetition frequency Bit rate Query language Encryption Position operator Scripting language Rotation Injektivität Algorithm Email Data recovery Data storage device Public-key cryptography Pulse repetition frequency Process (computing) Hash function Website Normal (geometry) output Resultant Server (computing) Functional (mathematics) Perfect group Sequel Connectivity (graph theory) Data recovery Password Control flow Login Prime ideal Intrusion detection system Queue (abstract data type) Software testing Matching (graph theory) Key (cryptography) Information Server (computing) Database Cryptography System call Query language Password Homomorphismus
Randomization Group action Multiplication sign Numbering scheme Function (mathematics) Client (computing) Inverse element Information privacy Mathematics Cryptography Pulse repetition frequency Query language Encryption Information security Partial derivative Rotation Email Mapping Constructor (object-oriented programming) Pulse repetition frequency Electronic signature Category of being Data mining Message passing Hash function Order (biology) output Right angle Encryption Quicksort Resultant Sinc function Reverse engineering Slide rule Functional (mathematics) Server (computing) Service (economics) Random number generation Proxy server Divisor Similarity (geometry) Theory Number Power (physics) Element (mathematics) Operator (mathematics) Authorization Bilinear map Integer Communications protocol Proxy server Key (cryptography) Information Server (computing) Commutator Primitive (album) Planning Cryptography Leak Pseudozufallszahlen Elliptic curve Function (mathematics) Password Communications protocol
Server (computing) Functional (mathematics) Randomization Service (economics) Open source Code Multiplication sign Real number Function (mathematics) Client (computing) Discrete element method Product (business) Neuroinformatik Web 2.0 Revision control Prototype Semiconductor memory Energy level Information security Service (economics) Information Key (cryptography) Demo (music) Server (computing) Constructor (object-oriented programming) Gradient Virtualization Cartesian coordinate system Pulse repetition frequency Demoscene Pseudozufallszahlen Password MiniDisc Website Right angle Quicksort Communications protocol
Standard error Server (computing) Dependent and independent variables Computer file Information Demo (music) Dependent and independent variables Server (computing) Bit Electronic mailing list Line (geometry) Function (mathematics) Client (computing) Mereology Password Default (computer science)
Proof theory Information Dependent and independent variables Server (computing) Password Multiplication sign Data center Revision control Client (computing) Directory service Fehlererkennung Mereology
Dependent and independent variables Server (computing) Password Multiplication sign Password Directory service Density of states Error message
Personal identification number Server (computing) Dependent and independent variables Demo (music) Dependent and independent variables Patch (Unix) Server (computing) Mountain pass Password Client (computing) Total S.A. Bit Limit (category theory) Number 2 (number) Oscillation Thetafunktion Query language Intrusion detection system Quicksort
Local area network Multiplication sign Set (mathematics) Client (computing) Rotation Neuroinformatik Web 2.0 Mechanism design Web service Cryptography Pulse repetition frequency Bit rate Single-precision floating-point format Core dump Query language Encryption Information security Rotation Scripting language Service (economics) Data recovery Digitizing Data storage device Bit Public-key cryptography Pulse repetition frequency Connected space Type theory Digital photography Process (computing) Befehlsprozessor Internet service provider National Institute of Standards and Technology Right angle Encryption Quicksort Row (database) Server (computing) Functional (mathematics) Service (economics) Computer file Divisor Line (geometry) Virtual machine Password Data storage device Theory Number 2 (number) Revision control Architecture Goodness of fit Computer hardware Energy level Medizinische Informatik Computer architecture Graphics processing unit Standard deviation Key (cryptography) Information Server (computing) Chemical equation Interface (computing) Database Scalability Software Query language Password Iteration Window Local ring
please welcome our next speaker Adam is going to be talking to us today about revolutionising authentication with oblivious cryptography take it away Adam [Applause] thanks Rihanna good evening everyone thank you for coming into crypto village thank you for coming to see my talk and I'm gonna talk about a technique that we call oblivious password hardening oblivious password hardening or oblivious password protection alright first some introductions I'm Adam ever saw oh hi I'm the cryptography expert at a software technology company called uptake in Chicago but when I'm presenting today is some work I did when I was a PhD student at the University of Wisconsin and that's joint work with these gentlemen some of these folks are here Sam Scott is here in the audience and all these folks are now at Cornell Tech and lastly I'm gonna give a live demo of implementation of this technique later in the talk in it that live demo is developed by virtual security who actually is an open-source version of this and the founder of urgell is here to meet you Dane is here so if you have any questions about the software the technology come talk to me afterwards I'll introduce you to Dmitry so we use
passwords every day so I think the key to our devices and to online services but the way we store those passwords is fundamentally broken because databases are compromised and when they are there's no way to stop offline dictionary attacks today I'm going to present to you a new direction a solution that not only eliminates these attacks but also enables compromised recovery well let's start with a concrete example alright so maybe you've
gotten an email like this scumbag polar-bear connect wants to connect with you on LinkedIn you send you an email you navigate to a website that looks
like this now in order to log in to LinkedIn you must provide an email address a password and of course LinkedIn has to store that password in some way so they can tell if it's the same password every time here are the typical ways that websites store passwords they have a store passwords in plain text no joke this happens ask Twitter they perform a salt they're sorry they perform a hash of that password and store the hash they perform a hash with a salt and then they store the salt and the hash in a database they do something because I'm kind of like iterated hash function like you may apply the hash function say ten thousand times in a row and then store the salt in the hash ok so pop quiz there's a little bit of a trivia who here knows how LinkedIn was storing passwords in 2012 two people somebody I don't know right there you wanna guess unsalted hash that's true now the reason we know this is now because LinkedIn had a press release it's because attackers broke into LinkedIn in 2012 they stole something like a hundred million passwords they leaked some of those online those hashes online and when they did security researchers have a field day they were able to crack most of those passwords in just two weeks with off-the-shelf hardware now the reason those attacks were so devastating and so fast was because they were using unsalted hashes but what I want to point out to you is those attackers have a hundred million passwords even if LinkedIn was using the what's considered like industry standards today like the best protection which is some kind of iterated hash function or hard hash function this doesn't actually stop offline attacks it just slows them down which means attackers just throw more iron at the problem so all the techniques that are storing plaintext passwords we basically call hashing hope you're hoping the attacker is not getting spend enough time and energy to crack those passwords because if they do they will crack all those passwords alright so I'm picking
out LinkedIn but let's just say password
database compromises are really not that uncommon right and what I want to point out is these aren't just like fly-by-night startups these are sophisticated technology companies they're repeatedly breached these passwords are stolen they have the technology they have the motivation they have the skillset to stop these database breaches and yet they are often unable to do it okay so of course we want to limit these breaches whenever possible but even when they do occur we want some kind of protection right we want to move beyond hash and hope so this look at a different way to protect passwords in
January 2015 Facebook presented this slide at real-world crypto conference in London this slide is pseudo code of how password of how Facebook processes a new or changed password when you log into Facebook all right so I'll give you minutes take a look at and then we'll talk through it okay so this is what Facebook does they take your password they run it through a deprecated hash function called md5 random 25 salt they take the output of md5 plus the salt they went through a deprecated hash function called HL 1 they take that results in it to a remote machine applies remote h smack sha-256 with a secret sensor result back they run that through a memory and hard function called s script take the output of a script by 3/8 mega shot 256 got that all right so it's a little confusing you might be wondering why would facebook who presumably knows something about security do something like this well the reason they do this is historical once upon a time facebook had 800 million passwords sitting around a database predicted by md5 security said holy f we have 800 million passwords sitting around a database protected by md5 how are we gonna fix this well Facebook doesn't want to make you change your password they don't want to wait for all 800 million users to log in so they can rehash those with say H max shot 2 so instead the security team says let's do this take all the existing passwords choose a random 20 bytes salt run them through HTML 1 write that back to the database cool we're done right two years later they at one point 1 billion passwords they say holy F we got one point 1 billion passwords stored in HL 1 of the database what are we gonna do but look we solved this problem before at hmar the secret doing good right all right so some time later they want do something better they add s script now the output of the script is really long so finally they run it through H Mac shot 2 literally just to compress it literally just to compress it down so if it's in the database better ok so what we're left with is this pseudo code which is now an archaeological record of Facebook struggling to protect passwords alright but I want to point out something interesting here something most technology companies do most of this processing happens on the same server but at some point during this processing Facebook reaches out to a second server that server applies an H max out to Z 6 with a secret held only on that server and sends the result back and that's actually really neat that's neat because it leads to a different
kind of architecture at a high level the architecture looks like this user submits a password web server to some local processing connects to the crypto server crypto server replies that sends it back the reason we like this architecture this is now critical information is split between at least two different machines so if I break into a web server I get passwords but no key if I break into a crypto server I get a key but no passwords okay this is already better but there's still some problems with Facebook's implementation first off there's a cryptographic key right security people might say how do I rotate that kid well the dirty little secret inside Facebook is they can never rotate that key right it's in the middle of a bunch of one-way functions if you change that key you effectively deletes all two billion passwords in that database so if you want to change the key you have to keep adding these like h max out 256 is to the end of the process okay so that's not good secondly because of this particular API the way requests come in it's really difficult it's actually impossible in some cases for a crypto server to tell the difference between a large volume of legitimate requests like 10000 different people are logging in with different passwords versus one attacker sending 10,000 guesses for a single sis admins account okay so for the rest of this talk I'm going to leave
behind the state-of-the-art I'm gonna talk about our contribution to this problem so we like this architecture we're gonna we're gonna start with this architecture I'm going to rename the crypto server to the pipi of server and we're gonna fix some of those problems we're gonna change the API we're gonna change it in a way that allows the crypto server to detect online attacks we're gonna build in support for key rotation and key rotation is going to be really powerful this is going to allow us to recover from compromises and also proactively rotate keys and when we rotate keys it's actually gonna allow us to cryptographically erase information that's been stolen all right finally we wanted to design a service that's not just for Facebook or people who have these huge security teams and they could run their own service we want to build a modern multi-tenant web service that allows even small companies to take advantage of the system all right so let's see how it works I'm gonna talk
through how apatheia query works when a new user logs on to a website and their websites using didn't do so user logs in the normal way username password sent via HTTP POST protected by TLS web server chooses a ran value we'll call that value t is gonna be a user rating he then takes that password and passes it through what's called a cryptographic blinding function think about this as encryption actually is its key homomorphic encryption we'll get into the details later but just know that this protects the password web server sends a query query has these components has the web servers ID it has the users ID it has a blinded password an encrypted password that Pythias server perfect key out of a database that keys associated with only this webserver and then applies cryptographic PRF a key pair a for that key and uses those inputs the user ID and the blind password we'll call that result why that result gets back sent back to the web server the web server then applies the unblinding function and then stores those we call the unblinded value the final value of the protected password think about this is the same output from the Facebook algorithm when you've applied s script and a bunch of other deprecated hash functions and of course when the user logs in web server does the same thing again produces a new value Z Prime if the new value matches the date in the database the password is the same it doesn't match it's the wrong password alright let's talk about how
compromised recovery works so let's say an attacker breaks in steals a copy in the database well this web server is in a better position because the attacker can't do offline dictionary attacks without that key now he does have enough information to do online accounts online attacks but notice that the API is changed the API requires the requester to specify the user ID if you specify the wrong user ID you get the wrong result and your guesses aren't gonna work this means the Pythia server can now tell if you're getting 10,000 requests for a single user account and it can do something right it can throttle requests and lock accounts it can send out alerts this is admin to say hey someone else has your password database alright so admin goes in he cleans up a sequel injection and instead of the normal process of email all your users tell them they're screwed they have to go change their Instagram passwords even though you're not Instagram instead he does something different he contacts the Pythias server and says hey i need to do a key rotation I need a new key the server generates a new key and sends to the web server will call update token and this update token allows the web server to update update the exist protected passwords from the old key to the new queue the important thing is here the webserver doesn't have to know the original password I don't wait for the user to log in I can do this whenever I want and also the underlying password hasn't changed we're just changed we're just changing the key that's being used to protect that password alright webserver finishes updating its database test to make sure it works context the Pythia server tells them I'm done erase the old key if that key is gone and there's no copy of that key in a in anywhere else in the HSM or anywhere else and remembering that password database is useless right it's based on encrypted values for which there is no key so even if you break into the Pythia server if the key is gone you don't have enough information to recover those passwords we say that password databases cryptographically erased you not have a big blob of useless data and some user names and user IDs okay so there may be some cryptographers in the audience even if you're not we're gonna talk about the
properties that we need to build this kind of a service so we need a scheme that's gonna be deterministic even the same key same user ID same password these produce the same result every time that's how we know if we got the password correct we need to keep that pseudo-random and really by that I mean password should look like random numbers that shouldn't leak in there sorry protected password should look like random numbers they shouldn't leak anything about the inputs we need this weird property it's like partial message privacy I want to hide the password but I want to require you to specify in the clear the correct user ID and finally we need key rotation right hopefully it's obvious how how very powerful that is to operators okay so when we started doing this work in 2014 we looked around at existing schemes there's things like pseudo-random functions like H Mac there's oblivious pseudo-random functions partially blind signatures which give you this kind of partial message privacy there's a bunch of techniques for key updatable encryption proxy encryption but in 2014 at least when we were working on this actually 2015 we're working on this there actually was no scheme that provided all four of these properties simultaneously so we the authors of Pythia we had to invent a new scheme we called a partially oblivious PRF it's a sexy name right forgive me I'm a cryptographer I'm not a marketer all right so let's go through let me give you a high-level into intuition about how we're gonna build such a scheme so how do you build an
oblivious PRF well the first thing we need is to secure a secure reversible blinding function so I can apply some function some planning function usually with some random input think of that as like a key and of course if I apply the unblinding function that should give me the original value back now I need a secure reversible blinding function that commutes mathematically with a pseudo-random function and by that I mean if I blind the password and then apply the pseudo-random function it's the same as if I were to do in the opposite order I applied the Saran function first and then blinded it if I have these three things I can build an oblivious PRF it's like blind a password the client blinds the passport sends it to the server server has the key place the key to a random function to the blinded input since it back to the client the client applies the unblinding function right and then should it be clear that we can rewrite it like this and hopefully then it's still clear that blinding and unblinding cancel out at the end of the protocol the client who initiated the protocol learns the output of a keyed pseudo-random function of our password but he doesn't learn the key and on the server side the server side can apply the key but never sees the password okay so let's know believe is PRF math warning I have one slide of math so for those you need to check your email and don't like math go into it for those of you like in math sorry it's only what's like all right so here's our partial oblivious PRF construction there have actually been sort of a number of similar constructions and the academic literature since but is my talk so screw you guys I'm presenting mine all right so we need to use something called a bilinear appearing and by that I mean three elliptic curves will call them G 1 G 2 and G T and a function that takes inputs from 2 and maps them into the third and this function has this property if I take a to the power X and B to the power Y run them through the blinding function it should be the same as if I were to send a and B through the blinded function and raise that to the power X Y ok with this we can now build our Pythia protocol works like this the webserver hashes a password to turns it into a group element an elliptic curve element raises the power of R where R is just some random integer this is a blinding function and this is really strong information theoretic security okay so here's our blinding function send this value to the Pythia server Pythias server then hashes the user ID passes the user ID and the value X through the pairing function raises the whole thing to the power of K that's our keyed pseudo-random function the unblinding function is then I compute the inverse of R and I raise the whole thing to the power of R if I write it out it looks like this and then hopefully it's clear you can see that the blinding factor and the deep low unblinding factor cancel out and what I'm left with is hash of a user ID hash the password passed the repairing function raised to the power of a key K and this thing is deterministic right the same inputs it always produces the same outputs okay the rest of you guys who don't like math and are busy checking email you can wake up all right
so that was a deep dive let's pop up for the high level let's talk about what this construction gives us on the Pythia side using this construction means the service has enough information to technolon attacks you have to specify the user ID and you have to be right about it can't play shenanigans within because if you specify the wrong user ID you get the wrong output every time but importantly he can apply the pseudo-random function never learns anything about the password on the web server side he can compute through this protocol this key to a random function but he never sees the key right this is key because if you break into the web server you scrape memory you steal a disk you know everything the web server knows and if the web server has the key anywhere then the attacker probably has the key to all right so our goal was to as an academic my goal is to publish this paper but now our goal is kind of get this in the world and and get people to use it and so so a company called
Virgil security has built sort of our production grade that sort of in build a production grade version of Pythia that's way better than my research prototype you can find out more about it this website Pythia DEP virtual security comm they have a full open source application you get the stuff from github the code is very good and I'm gonna give you a demo of this if anyone is brave enough and has going on your computer you can follow along in this demo and I promise that there's no shady stuff in this code I've never looked at the care but I promise there's no shady stuff in it ok what I'm doing is downloading via golang I'm downloading the package for this sort of demo version the Pippi client but it hits a real live Pythia server it's running the Pythia protocol and now I'm gonna set up a client ID so all I'm doing here is choosing random ID and this is gonna be my like you let web server ID so my random web server ID so there it is very exciting so here's the
tool it's designed to be very simple obviously right you can get help you can protect a password you can check a password right this is really all we need to do okay so what I've done is said I want to
protect a password here's the username of course my voice is my passport and then it's hard to see what I've redirected the output to a file and what the client is doing is exposing the standard error a little bit of demo information so we kind of get some idea of what's happening right so the first value is that blinded password that we talked about this is the response we get back from the server this is the first part of it the response we get back from the server and it finally is the deep line to value the protected password
okay so here's my protected password it's not obvious but this first part here should match espousal I use the long path but finally but the first part is a password and the rest is actually like a zero knowledge proof and some other fancy information which I totally skipped over because we don't really have time to cover that stuff but essentially this is the protected password
big surprise password matches alright so now let's insert an error let's say your voice is my passport password okay password does match right big surprise alright so let's do this a bunch of times right if
the pin theist server has some policy on
it we should only get a certain number of these queries before we get some kind
of response okay so there we go so the
Pythia server is is monitoring these inbound user IDs and after you get say 10 or so checks they put a throttle on and they say okay great you have to wait 60 seconds or so right this is a very sort of simple policy that allows us to quickly slow down any kind of online attacks all right so that's the totality of the demo let's go back and talk a little bit more ok so that's how it
works there's some deep theory going on in there there's a very cool very simple interface to use it but let's talk about performance right so if both the Pythias server and the web server on the same local area network and that's important because then network latency so it doesn't factor into these numbers then one can execute a Pythia query in about five milliseconds right you're probably thinking what does that mean right so let me give you some context if you're following the latest guidelines from NIST which is to use say shot 256 hatchet nuts not say it is - you shot 256 hashing hashing with at least 10,000 iterations on the same hardware that takes nine milliseconds if you're using an even fancier function bcrypt is one a script is another let me give an example bcrypt set with a work factor of 11 which is kind of a popular setting for obvious reasons takes about seven milliseconds right so Pythia today is already faster than the current versions and you get things like protection from online attacks and key rotation and I want to point out that as computers get faster we actually make bcrypt slower right because this GPUs get faster we're processing these things on CPUs so keep the work factor so seven milliseconds is kind of like the least amount of processing time but it's CPUs get faster pthew just gets faster right so we're already ahead of these password protection mechanisms and pv is going to continue to outpace them some of the notes about performance on the eight core machine that we tested in ec2 a pantheist server single Pythia server male about 1,300 queries per second feed more queries per second you throw more iron at the problem right you put a little balance there and a couple more servers storage is excellent for a Pythias server right pthey server doesn't store information about users sores information about web servers right so me you an example if a Pythias server is serving a hundred million web servers each with those each of those web servers with an arbitrary number of clients say 100 million clients maybe of serving is about 20 gigabytes right that's enough information to store keys for individual web servers and a little bit of extra information for rate limiting that information is a ephemeral all of this is to say we can deploy Pythia today on standard hardware alright so most of this talk isn't about web servers that's kind of a very compelling is for Pythia but really the Theia is really good whenever you have a password and a network connection and also like security so maybe two more examples just at a high level first is file encryption right commonly today you log into a macbook or a Windows machine you type in a password it grinds away on your password uses that for a key that's good unless you lose your password anywhere that someone's gonna crack it now if it only has like say your Instagram photos on there that's not a big deal but it's got like client data health information financial records that might not be good enough right so instead you could use a password connected Pythia use it to generate a hardened password and then use that for an encryption key and then if you lose your device or say the FBI takes it if you can get to the Pythia server and say hey I had lost my device will you please delete that key that means you can actually cryptographically erase that device even if that device is offline or powered off right because it needs a key and that key is not on that device alright so the last sort of compelling use is something called a Bitcoin brain wallet right so bitcoins are very valuable sorry Bitcoin wallets 10 be very valuable because of the sort of skyrocketing price of these things and there's a question of like sort of how do you protect this digital asset right so you can imagine I could take a generator a very complex password run it through a script they could grind away for a long time and just hope that somebody else out there doesn't grind away harder and find my password because oh the public key is sort of sitting somewhere not sitting somewhere it's sitting up on the blockchain you can imagine using Pythia for this right you type in a password possibly combined with a local secret connected Pythia use it to apply and another key and get it back and use that to either protect your brain coin wallet or use it directly as your Bitcoin wallet okay so let's wrap this up
passwords storage is broken because databases are routinely compromised when they are using current techniques there's no way to prevent offline dictionary attacks but what I presented today is a new solution in architecture for protecting passwords built around the Pythia PRF and Pythias design it's a modern web service it lets clients of this service inherit the security of the service provider without just handing over sensitive to the sensitive information to the service provider and just hoping for the best and with that thank you and I'd love to hear any questions