Real World Crypto conference 2020: session 12

okay welcome back everybody and we have two talks in this mini session on on secure messaging and the first talk will be given by John Milliken from Facebook and he's going to tell us about end-to-end encryption for messenger thank you John thanks Kenny so hello everyone my name is John Milliken and I'm a software engineer on Facebook's messenger privacy team so I'm going to talk to you today about a long-term plan to fully encrypt messenger end-to-end and primarily about how we're thinking about this and some of the challenges involved I'll be honest right now and say that we're still in a place of having more questions than answers well we have made progress in our planning it turns out that and adding end-to-end encryption into an existing complex system is incredibly challenging and involves fundamentally rethinking almost everything so I'm not here today to tell you exactly what we're going to do we've done a lot of thinking about this topic and I'll be sharing some of it but we're really starting out on a consultation process here I'll really be focusing on the reasoning goals and real-world process and challenges of transforming a live system with well over a billion users into something that can run essentially via an opaque encrypted pipe let's start by addressing why we're doing this and this boils down to three major points first is simply that people deserve good security it's undeniable that every major online service has security issues and I imagine many people would give good odds there any service without public security issues simply hasn't found them yet and I'd also note that the more data you have the bigger a target you become so over time as more and more data or masses within major platforms more effort is likely to be put into attacking them in this world who wouldn't want multiple layers of defense and while we do already practice defense in depth especially for messaging data what better defense can be really apt than not even having the data available to us in the first place apart from of course making it impossible for us to even choose to get and I'd be remiss not to highlight the importance of strong security for national security the US Department of Defense has recently stated that they believe maintaining maintaining a domestic climate for state-of-the-art security and encryption is critical to the protection of our national security and the second point unsurprisingly is that privacy is a fundamental human right usually this is considered to mean privacy from governments but we believe that privacy of sensitive communications from companies is also really important and to an encryption may fundamentally be a security technology but it enables this sort of strong privacy and there are instances where server side access to data is necessary to provide a service so I'm not saying that perfect privacy and security should necessarily be blockers for the existence or usage of an otherwise useful service however we believe that messaging need not be one such service indeed we already operate to messaging services whatsapp and messenger secret conversations that use the signal protocol to fully enter and encrypt their data such that Facebook has no access to the plaintext data and so the conclusion we've reached here is that we should aim to end-to-end encrypt our messaging services this would encrypt data such that only the specific endpoint devices could read the contents of communications strengthening the security of data while providing privacy from Facebook ourselves so with that said what's Facebook vision here well in March last year Mark Zuckerberg announced his new vision for privacy phocion focused social networking this frankly took a lot of people by surprise as it focused on seven main principles that people have tended not to associate with Facebook these were private interactions encryption reducing permanence safety interoperability and secure data storage all principles that I imagine people in this room would tend to support but I'm here today to really talk about these top two private interactions and encryption well Facebook has traditionally focused on providing a virtual Town Square through social networking products what we really want from messenger is to provide a virtual living room that is a small intimate space where you can communicate in confidence with those closest to you and in the knowledge that nobody else is watch or listening now the small intimate space is already roughly the product model that messaging apps offer but encryption can serve to provide this guarantee of confidentiality and as I said we believe that this is desirable for all messaging on our services not just whatsapp and messengers secret conversations so that's the vision but where are we with end-to-end encryption and messenger today well at real world crypto 2017 almost exactly three years standing broadly in exactly this spot I spoke about secret conversations are existing e2e product and in this talk I discussed a lot of the reasons why at the time we didn't feel that ETA encryption was a realistic goal for messenger as a whole so what did we have at this point well for starters secret conversations were opted in with the vast majority of messenger users not using them messenger is incredibly feature-rich but many of these features are challenging to build without significant server-side support so for secret conversations the feature set that we provided was pretty limited we had text photos stickers and ephemerality but I think that was pretty much it and only for one-to-one chats so no groups furthermore it only worked on my main Android and iOS maps and for any given account we only supported one device at a time meaning that most people who got new phones simply didn't have it enabled because it was already enabled on their old one although any secret conversations that they were having wouldn't have been transferred over to the new device anyway so as there was no mechanism for transferring conversation history so since then we have made some progress it's otherwise broadly a pretty similar product there so probably the most significant change was adding support for multiple devices on an account meaning that people with multiple phones or those who got a new phone could use secret conversations much more similarly to how they use regular messenger but we also did add a few more features such as sending videos and audio clips we also started to find ways to develop it a little more like how we develop regular Facebook products so with some basic metrics that we collected about categorical data and we did this using local differential privacy and a fair bit of work to make the product just work better and be a more reliable messaging experience but otherwise as I said it's broadly a pretty similar product to what it was and most notably we still don't have group chats and this still no means to transfer message history between devices so that's where we're starting from on the ETA encryption side for messenger now let's look at how we're approaching the task of overcoming and mitigating the the many challenges so that we can expand this to the whole product well primarily having strong end-to-end encryption privacy guarantees sorry having strong end-to-end privacy guarantees is one of our key goals we're not just adding end-to-end encryption to a product we're building an end-to-end encrypted product so for starters that means we cannot have any access to message contents ever unless these have been explicitly willingly and knowingly shared with us for example when abusive behavior is reported engineering wise were investing in security and privacy by design aiming to significantly reduce the likelihood of privacy and security bugs occurring metadata collection is often the elephant in the room when it comes to end-to-end encryption indeed my last real-world crypto talk I think one of the questions afterwards did focus on this is something which was explicitly not covered by or protected by ETA but nonetheless as we're improving the privacy of messenger our goal is to also improve on the metadata that we have available whatsapp for example takes a very principled the position of minimizing collection of metadata and we intend to take this approach for messenger and finally well we do have significant expertise in the company and we're spending a lot of time on getting this right we do intend to gather external perspectives on what we're building because frankly this isn't easy and there are many more viewpoints and use cases that exist just within Facebook so let's dig into this first point of what I meant by having no access to message content so by definition we won't have access to messages in transit that's end-to-end encryption but to provide end-to-end secure it we also must ensure that message content cannot reach us in any other way so some examples of avenues that we'll have to to block and be concerned about are messages being logged particularly in crash reports which are particularly challenging case because frequently the best way to to fix issues that are affecting people in the real world is to have a good idea of what's going on when app crashes do occur we'll also need to make sure that there's no way for Facebook to remotely pull the contents of messages from our own apps and also that the apps enforce that no device can receive any message unless that device has been verified by the sender oh sorry can be verified by the sender and to preempt a likely concern on this point I'd call out that I don't just mean the precise message content here but we're also talking about any data derived from message contents the next point in our approach was security by design and aside from it being a generally good principle why is it particularly important for messenger now well we're a large multidisciplinary organization building a complex and feature-rich products across a number of platforms getting security right is a scaling challenge because even if everyone were an expert in security and cryptography more engineers writing more code just provides more opportunities for bugs to be introduced an effective way of scaling security to a large organization is to ensure that the building blocks that everybody works with are at the right level to provide blanket defenses so this means having frameworks and api's which are secured by defaults and by doing this we aim to make the easiest way to build a feature the secure way to build it and naturally we want everyone to be privacy conscious all of the time but if we were to rely only on expertise to get security right we wouldn't really be practicing defense in depth or security by design within our own engineering practices so for example we don't want to rely on everyone having a good understanding of the signal protocol or exactly how we use it instead if somebody needs to transmit data from one user to another within one of our features we'd much rather provide an API that will do this for them and abstract away the transmission and encryption and one particular call-out I'd make on security by design for ETA encryption is that we're looking to push as much as we can on to the client this is actually a pretty big departure from how messenger works today the vast majority of our features use the server as an active component in how they work it isn't just moving plain text from one device to another it actually contains product logic so we'll need to significantly reengineering messenger features to work primarily on the client but nonetheless we think that this is the most realistic secure design for end-to-end encryption and this means that we'll end up with the server being pretty much a dumb router the next aspect of our approach was consulting with external stakeholders now research is always an important aspect of product development and iteration it's the best way to make sure that we're providing the best tools for our users but what we did differently this time was to publicly announce the plan years in advance of being able to actually ship it and this is because we're conscious of the broad implications of a to encryption and the wide scope of design challenges that we'll need to address with these in mind we wanted to collaborate early with global stakeholders and listen to an experts from a wide range of areas such as industry civil society activist groups academia and of course attendees of cryptography conferences and finally I call that limiting metadata collection and storage as a goal how do we actually want to approach this technically well we're looking into how security by design can be applied here and there are a couple of points that I'd like to talk about on this front the first is that privacy preserving techniques are non-trivial to use at the moment and so if we're going to ask engineers to be applying them it makes a lot of sense to simplify this so for example building logging tooling that allows them to use local differential privacy more easily but we're investigating at the moment how we can more systematically reduce sensitive data logging and storage by building this into logging frameworks so the hope is for example that we might be able to automatically enforce policies that we define data or perhaps detect that certain data is no longer being used and automatically drop it or even potentially examine the queries that are being run to find opportunities under the hood to aggregate or anonymize datasets so the goal here is to pretty much rethink our approach to data collection storage access and usage so that we're going beyond only collecting data that we use and actually automatically minimizing it to so that's the approach that we're planning to take to the problem sort of at a high level let's now look at some specific challenges that we've been thinking about imagine this first example won't surprise anyone preserving message history when changing devices is something that we know people want indeed it's a big value add for messenger at the moment however this is all all data that Facebook cannot have access to in a neater way encrypted world and therefore cannot be in a position to just give directly to the user when they log into a new device therefore providing message history to a new device an accessor tate's that there is some piece of information that Facebook does not have access to be that the data itself or perhaps an encryption key in this space there are some previous examples of storing data on cloud providers for example whatsapp will back messages up to iCloud or Google Drive but we're not actually convinced but this approaches spices for messenger one issue with this is that messenger is inherently multi device and multi-platform so for example I use messenger independently across web iOS and Android all from the same account but there is no cloud storage provider that is easily and widely usable across all of these platforms so one question we were wondering about is whether we should allow users to back their messages up data up to Facebook given that we can guarantee this data will be available to climb any client that we build although naturally if we were to build take this approach we would have to encrypt the content so that it remains inaccessible to us the next challenge we were looking at which I also highlighted last time I spoke here is that of supporting web clients this is especially important to us as web access is another big value proposition for messenger but web presents a number of significant challenges for building end-to-end encrypted apps so we've been thinking about a number of questions in this space for example should we still actually support web clients clients as standalone or should we be looking more to the tethered approach that whatsapp is taken and should web chat be automatically available on facebook.com as it is today or should people have to explicitly opt in to use chat on web then if people do use messenger in web would it benefit them to be notified about the differences they are opting into compared against multiple devices against mobile devices sorry or would this not be broadly useful to people and indeed regarding the code distribution model on web could it be improved by developing binary transparency to ensure that everybody is running the same code indeed is this even a viable technology for browser vendors to build and share and a more recent challenge has been in how notifications work given that secret conversations aims not to keep a permanent record of pairwise threads as we didn't have a technical reason why storing this should be necessary notifications however do rely on thread specific behavior for example bad counts that are displayed by app icons on iOS are calculated based on the number of unread threads and muting a thread requires it relies on suppressing notifications based on the sender of a message so previously for secret conversations we calculated badge counts and we handled muting of threads client-side instead of storing this data on the server but we are starting to see new constraints from mobile platforms requiring that we can control these behaviors from the server and thus requiring that we store sufficient data on the server to to be able to do these sorts of controls and therefore it involves having a bit more metadata about threads stored so the approach that we've taken so far in secret con is to store as little data as we think that we can and format it so that only only certain queries can easily be run so for example you could easily query if I have muted Kenny but not for everybody who has muted him but if as good as we can do is it possible to improve on this so that's just a few of the challenges that we've been looking at as we investigate fully end-to-end encrypting messenger and now let's just wrap up with a few conclusions first I'd particularly stress the complexity of migrating a product like messenger to be fully end-to-end encrypted what's up took years to migrate despite being a significantly simpler challenge than messenger in a number of ways so when people ask why can't you just with respect to end-to-end encryption on messenger quite frankly it almost never applies because the challenge is much more complicated than they're imagining fundamentally we're not just looking at the transport layer change for messages but rather we're looking at a full stack rethink and Ryoka texture of the entire product next I'd stress that we build for people first and building for people at scale means working within real-world constraints for example those introduced by the variety of operating systems platforms distribution channels etc that has software has to run on and remember that our goal here is to deploy end-to-end encryption to the communications of billions of people and to do so we still have to design our product to be usable by billions of people and to wrap up let me just say we are going to ship this it's going to take time to bit to build and to make sure that we're doing it right but nonetheless this is happening we are going to end-to-end encryption S&J thank you very much and do we have time for a couple of questions [Applause] you certainly do and there are people at the mics okay all right thanks for the great talk what road map is there for social graph being put all the way on to the client and being completely off of the server great question I don't think we have anything to share on that at the Ravens hey I think you're the talking does Facebook have any plans to address the sort of threat model where the server pretends that I have a new phone when it's not really my phone so secret conversations at the moment whenever a device is added to a thread will surface that to both to both parties in that thread so it is visible and you can go and verify the keys in that's right thank you further to that could you say any more about the key verification or key transparency or in general how people know that the keys that you're telling them are the right ones so the approach we use today is the approach which is common across most encrypted messaging apps which is allowing people to manually verify keys we have slightly different approaches to this in what's up and secret conversations but they they boil down to essentially the same approach we're certainly tracking developments in this space but to the best of my knowledge no developments have been deployed sort of scale yet hi great talk thank you I remember two years ago I think the original decision was that Facebook it was too difficult and I'm glad to see that it's come this way my question is who exactly does Facebook have an intent on marketing secret conversations and getting people to care about and to end encrypted messaging and explaining why that they should use Facebook's encrypted messenger over non-encrypted messengers and sort of making this the default and actually having them care about it is there like any way that you could explain the threat model to those people and terms that they would understand and care about so I think you really hit the nail on the head when you said about making this the default the idea that the ideal situation really is that people don't need to no one care about this to nontheless get that level of security and so that's what we've already done with whatsapp and what we're hoping to do with messenger right and I think that's great but my concern is like there are people who still for example domestic abusers who will steal Derek they're their partners Facebook accounts or gain access to it and they you know hijack the things that they read and see so I'm curious like exactly how the facebook messenger threat model it kind of intends to have that because obviously their signal and things but not many people use signals they do facebook Messenger and I'm just concerned about those people and how the threat model will be adjustment for them so one thing that I can share about what we do in secret conversations is regarding account switching on a device so if if for example you do log out of messenger you're all of your secret conversations will be inaccessible because they are encrypted besides that we're certainly investing in our privacy roadmap and trying to improve privacy in a number of ways but I'm afraid I don't have a specific product ideas to share at the moment cool thank you thank you how do you handle coordinating keys between multiple different devices or clients we treat every client as a separate endpoint so for multi device under the hood it is a group chat between a series of devices with Facebook user identity superimposed over that thanks so I saw you had a slide where you're pointing to the current problems in like badging notifications being turned is there sort of research that's needed on specific techniques to address these or is it more there there's techniques out there but you need to figure out what the trade-offs are and then pick one very possibly a bit of both we're very interested in learning more about what's possible in this space hi I have two very quick questions one I realized that the number is very small but I'm wondering if you can share any more precise usage usage statistics about secret conversations to date and second I I'd like to hear from you I think I know the answer but I'd like to hear from you how committed is your team to preserving forward secrecy in the final protocol so regarding the first point I don't have any statistics to share I'm not sure I'd characterize that is very small but yeah we don't have numbers to share regarding the encryption we're aiming for the best security that we can achieve while building a usable product at the moment we're using signal signal protocol for this which provides for words secrecy on Facebook for my security so you think that there is a chance that the final protocol won't include forward secrecy I mean you can you can never give a firm commitment but our current plans are not to move away from that thank you thank you thanks everybody for all the great questions we're actually out of time there so let's thank John again for a really insightful talk okay we're just getting miked up here they're still clicker here so if somebody would like to come and claim their clicker or claim somebody else's clicker more than welcome okay great so now we come to the second talk of the session I'm about a ETF MLS effort and the talk will be given by by Joe thanks Kenny so hi my name is Joelle I'm a cryptographer over at wicker I'm gonna tell you about a joint work with Sandra Afghani and Yanis we've been looking at the MLS protocol and we want to tell you about some thoughts on that and some results we have alright so first you know let's get some contacts what is MLS well the goal is here to design a messaging protocol and to unsecure for groups right and groups is kind of really the key point here we want to support really large groups by large you know think fifty thousand people for example this should be asynchronous messaging so in other words think things like SMS or email you know you just come online you read your messages you can send out whatever you want you go offline other people come on and they can read their stuff sessions you know we expect them to last really long years sometimes and group membership therefore is going to be dynamic right during a session people are gonna join and leave the group so challenges here are really I'd say the biggest challenge you know is keeping bandwidth and complexity lo bye lo I mean think logarithmic and group size not linear and really that's what's gonna differentiate MLS from pretty much everything that's out there right now we also want to do you know we want rigorous analysis of the security here and we want to use practical Karima t'v who's who's doing this well this is under the auspices of the IETF so it's being designed by work group also called MLS and I'd say the guiding principle here is really to do for group messaging what TLS did for you know secure communication a synchronous stuff this is a collaboration between academia industry we got more people joining all the time and the the final product is going to be a series of RFC's that define the different aspects the architecture the protocol itself things like that so let's look a little more at the security goals basically in a nutshell we're talking end-to-end security authenticity and privacy the adversarial model here at least for the purposes of this talk is all right and to end security we're talking a man-in-the-middle in particular also corrupt delivery service right we got a delivery service in order to get this asynchronous messaging and in terms of corruption we're looking at state leakage right so when you corrupt a client what we give the adversary is the local state including all the secret keys entropy and everything so that's the corruption model we're talking about an active and adaptive adversary's so you can online make decisions about what to do next and because these sessions last so long we are interested in security notions that talk about corruptions during the session all right in other words forward secrecy post compromised secrecy by forward secrecy or forward security I kind of switched between the two that I'm talking about we want that today's communication will remain secure despite possible corruptions that happen in the future and kind of the flip side of that is PCs which says well if we do have a corruption during the session then continued usage of the protocol will eventually revert us back to a secure state all right so these are kind of becoming like the standards the bar in secure messaging and end-to-end messaging and we you know analyst wants to achieve that as well one thing to keep in mind here is denial of service is kind of at least at the moment is really outside the scope and in particular if you have a completely adversarial network it's not clear really what you're going to do about it anyway at least for this talk and I think it's fair to say for MLS at the moment that's kind of out of scope there are other security notions that are being considered by MLS things like metadata hiding in particular from the delivery service secured against malicious insider so that means like really you know you get malware on your phone and starts actively trying to screw with the protocol and in the future probably a you know deniability is coming up is another notion but for now for this talk it's really end to end off it's an authenticity privacy in particular forward secrecy in pcs so all right what is group messaging as a primitive well it's a you know we'll do the classic thing it's a sequence it's a series of algorithms what can you do what you can initiate a group you can add someone to the group you can remove someone from the group you can do this thing called update which essentially it's like refreshing your local state and this is really where we're going to be getting our pcs from and of course you can also send and receive messages right so the goal here is to have secure communication in this dynamic group using this interface and you can break this interface into two parts the control messages that sort of manage the group state add people remove people refresh the group state and then there's like the application part which is just sending receiving messages and I'm really going to focus in this talk on the control part right and we can isolate this and look at it as its own primitive kind of what you you know key agreement to a secure channel it's it's kind of the same like analogy here and so you know we're looking at just in it add remove and update as the primitive and weak we call this in our in our work we call this continuous group key agreement alright cgk a and and sort of the focus of our work has been on the cgk primitive inside MLS yeah we'll get to that so the the goal of CG ka is kind of to maintain a shared secret or really a continuous stream of constantly updated shared secrets between all the members of this dynamically changing group and why is it okay to just isolate the CG ka as a primitive if we really care about MLS well because there's this nice decomposition that one can do that we've already seen in the two party case so for lack of a better term I'm going to call this the ACD paradigm after the paper where this was introduced and what a CD a CD did for the two party case in particular the double ratchet is it modular rises and generalizes the double ratchet so it modular Rises it into three primitives see ka PRF P G and an AE and sort of forward security ad and it shows how you can compose these three things in to get a secure messaging for the to party case right so this is applied to the two party case and and we realized that one can look at MLS through a very similar lens with with sort of a group variant of the same kind of paradigm so by the way with the addition that we also need signatures or at least MLS uses signatures maybe there's ways to get around it without signatures so one one subtlety here though is that at least for the purposes of MLS at the moment we do want these control messages in other words the CGC gka messages to be delivered in order or at least processed by all group members in order alright and so we we inherit this assumption in our work as well and in particular this is something that cgk can therefore assume about the network and yeah alright so by the way relaxing this is great Avenue for future work alright it's not clear that this is necessary but at the moment this is what MLS does and assumes explicitly that there's this in order processing so when we look at this paradigm we see that okay if you've got CG ka well then you can use these other primitives to essentially build your entire messaging protocol and it's not you know very non-trivial how did the how this duh how this works but it's not that different in the group setting from the two party setting and we know how to do this thanks to signal in the two parties setting basically we're gonna you know keep this entropy pool and seed a bunch of ratchets basically so in this work that's not what we look at we look at the CG ka part because that is really quite different than what's happening in the two party case this asymmetric double ratchet asymmetric ratchet so this the cgk apart is really quite different that's what we focus on and again you know just a the cgk the the point is to agree on a continuous sequence of fresh shared shared secrets for the purpose of this talk we're gonna forget about the dynamic part because everything we say is already non-trivial and relevant if you have a static group so never mind about adding removing people we'll just think of a static group and updating right yeah so all right one thing that's nice about this this modular construction is that it allows us to relax what we need from the network for the cgk in particular we can assume authenticated channels why is that because we get the authentication from the wider construction right from the signatures and the aad they're used in a clever way to basically enforce the authentication from the point of view of cgk so that's nice that means that we we get to make this assumption so now okay let's look at what the adversary is for the cgk well he gets to drive the execution what does that mean essentially the adversary' gets to instruct users at will to perform this update operation and every time there's an update operation this defines a new epoch alright so this term in POC is kind of important this and the next thing the adversary gets to do is also decide to deliver messages right so tell ok user you need to now process this next message but reflecting this assumption about the the ordering one restriction on the adversary is they can only tell a user to do to process update for epoch J if that user is already in epoch J minus 1 so users can be left behind and then catch up so in that sense it's but different than broadcasts is it's weaker but still we want that ordering of course as we said the user the the adversary' can at will at anytime and repeatedly leak the local state of users and finally you can see all the network traffic all right so we've got that man in the middle but for an authenticated network so that's the adversary now what's the what's the security notion that we want here well we want that basically look at Hawkeye we've got this group key for a Pollock eye and we want to ask when when is this key secured by the way group key I say group key or a in the MLS parlance it's actually called the update key all right that's just for those who are already familiar with MLS I use those terms interchangeably so we want to ask ourselves when under what conditions is in a considered secure when is it secure well ideally kind of the minimal thing that we would want this is what we call optimal security for cgk is that anybody who's been corrupted before a POC I has in between that corruption ie when his state was leaked and in Park I itself has performed an update has refreshed his state alright that's pretty much it that's all we really want if that condition is satisfied for a POC I then we want the POC I'd then we want to say a finite park I has to be secure so some things to note here this implies standard sort of forward security and isolation what I mean by an isolation well the notion for forward security is normally you consider only corruptions that happen after a POC I so there are no corruptions before I park I at park I you say is it secure and you look at any corruptions that happen afterwards conversely pcs in isolation is kind of the other side you say well I'm only allowing corrupt I'm only considering corruptions that happen before a park I so so this notion this it combines the two it's it's actually stronger than the two because it allows both before and afterwards all right so that's that's the optimal security we're going for so when we look at MLS they have a CG K and it's it's cool algorithm that's called tricking so this was originally introduced by Karthik Richard and Eric on the MLS mailing list and it's inspired by the art protocol which appeared in CCS last year subsequent to the original introduction on the MLS mailing list there was an update I guess we could call that tree cam with blanks and that's really what I'm gonna be referring to as tree cam in this talk and this is what's currently being used by MLS after you know there's been there's been some follow-up works already around tree cam itself there's been like causal tree cam that was a really cool idea that sort of tries to relax this notion of in order delivery there's came to tree cam which tries to improve the efficiency but I'll be looking at tree camps that's what's in MLS right now so so how does tree cam work well I guess a good way to think about the construction is to look at this shared group state right so every Epoque in in a tree cam execution is given I say you could characterize it by the distributed groups state and this is you can be viewed as a as a binary tree in particular what's called a ratchet tree so this is a left balanced annotated binary tree annotated we're going to be assigning keys and secrets and values to each of these nodes right and and you know it's it's important to understand each of POC has a fixed binary trees the annotation is fixed for that Epoque when we move to the next epoch we're gonna modify the tree maybe some of the annotation and that's going to be the new ratchet tree for the next two talk so how do we annotate it by the way when you see little question marks that's that's meant to be arrows that there's a bit of a font thing so nothing too important there yeah so how do we annotate this tree well the first thing we do is each user in the group is assigned a leaf there as many leaves as there are users each user gets his own leaf so here's the example for four people in a group the next thing is each node in the tree except for the root is also assigned a public secret key pair for that note alright so that's pretty much it in terms of this distributed state but it's distributed so we need to talk about who knows what parts of this state and to that end there's two invariants and really most of the work in tree cam is about maintaining these invariants across a pox the first invariant is about the secret keys who knows which secret keys very straightforward a user knows the secret keys for the nodes that lead from their leaf to the root Alice for example here knows secret key four and secret key to the second invariant is about who knows which public keys it's maybe not the security wise you could say everybody knows all public keys that would be fine too but what's kind of the minimal thing you need for the functionality it's that users know the public keys on their co path co path means the sibling nodes on their path to route so for example Alice should know PK 5 because 5 is the sibling to that that her note for and she should also know PK 3 because note 3 is a sibling 2 - right so these are the two invariants you know the public keys on your Co path you know the secret keys on your path and that's pretty much it in terms of the shared group state so as I said really the the important the most important thing that this kind of is how you do updates and the way tree CEM does updates is as follows all will go by example with Alice doing an update so the first thing Alice does she needs to come up with a new ratchet tree the first thing she does is delete all the nodes on her path to root and now she has to sign new secrets right so first thing she does she chooses a random secret you know with enough entropy and from that using a PRG she's now going to compute a a new secret so from her ass she computes a new secret s Prime as well as a public secret key pair that public secret key pair becomes the public secret key for her node and the secret she derived as prime becomes the new secret for the next node up her path so now we can recurse we take s Prime she again uses a PRG to expand that into a new secret new public secret key pair and so on so forth defining public secret keys all the way up again to the root and in particular when you get to the root this this the the secret that you do that that's get gets defined this way is what's called the update secret is the epoxy-coated self for this new epoch all right so it's all about this secret trying to keep it you know share distribute it to everybody while maintaining these invariants that I told you about with the secret key and public key all right so the question is okay we've defined our new ratchet tree how do we distribute that information to the rest of the users in the group so Alice prepares a packet right a network packet I distinguish between packets and messages just since this is messaging it's a bit of ambiguous packets mean protocol messages here okay so she has to prepare a one-off packet we can't have interaction this is asynchronous so what's you're going to put in this packet well the first thing she does is she in crypts the secrets to the co path right so for example would Bob needs to know to maintain his invariant he needs to know the secret key for node 2 so she knows Bob's public key so she takes that secret for know - and encrypts it to Bob's public key similarly charlie and dave also need to know to see the the group G so this s double prime so she encrypts that to public key 3 because both Bob and sorry Charlie and Dave know that secret key all right so basically you encrypt nodes to the co path all right so this is it and you know the other thing you do is also the the new public keys yeah you also have to distribute these new public keys right for example Bob needs to know Alice's public key so she just includes this new public key as part of this packet so that's how you construct this update packet right we've maintained these two invariants so now we can look at the security of tree can and so so what do we want from so tree camp does achieve pcs and forward secrecy I have to skip this a little bit so sorry in order to understand what kind of forward secrecy is achieved here we have this notion of critical Keys so when can we claim that a secret at the root is actually secure well in order to reason about that we have this definition of a critical key right a secret key in in this ratchet tree we call it critical for a secret S if knowing the secret key and all the network traffic that is transpired in the session allows you to compute the secret s that's what makes a secret key critical for some secret s well with that definition if you've got a ratchet rain you want to ask yourself when is the secret at the root this is pocky when is it going to be forward secret well it's only going to be forward secret if you've removed in in future iterations you've managed to remove all critical Keys from the group stay why is that because if there a group if there is some critical key that's so left and then the adversary' goes and corrupts that person they're gonna learn the critical key and therefore by definition of critical key be able to go back and compute this talk secret in other words for for forward secrecy to kick in we need that all these critical keys are going to be removed so in this particular example critical key for s double prime would be SK 5 and SK 3 because each one of those allows you to decrypt one of the cipher texts that Alice sent out but and this is kind of like the big like Eureka moment for us that we realized this is actually there's recursive critical Keys as well because this this SK 5 and SK 3 in particular SK 3 itself has critical keys in other words if you learned these other critical Keys then you can recompute SK 3 and from SK 3 you can then recompute the secret so there's this recursion in terms of critical Keys and it turns out it's just really not that great if you've got a group of size ends and people in this group it turns out that of the 2 n minus 1 Keys and all ratchet treat n of them are critical and that's not really that good because that means that forward secrecy is really going to take a heck of a long time you're gonna have to do a ton of more updates and modifications is ratchet RIBA for a given Epoque comes forward secret and in particular you think about it in any given update you're only modifying log n keys so you're gonna need at least and over login just just from that observation alone for more Hawks before you get forward secrecy and in fact you can't pick and choose which key so it turns out it's more like linear number of the box whereas optimally we said we wanted immediate forward secrecy within one single epoch so shows tree cam is really quite far away from this optimal notion of forward secrecy and by the way this is best case this n over log n or even n number of plucks if the wrong guy doesn't do an update like your sibling well then you're never gonna get forward secrecy because as long as he doesn't do an update and his leave key is critical no one else can change that leaf key all right so so good so we established the tree cam doesn't have maybe the best forward secrecy really pretty far from this optimal so what can we hope for oh can we do better and it turns out yes we can and basically the big sort of you know change that we make is that we show that well if tree cam uses public encryption you can replace public encryption with this new notion of updatable public key encryption that we introduced and that immediately gives you optimal security right so it's a pretty small change so so what is this optimal updatable public key encryption well it's it's a primitive that is very closely related to what's called key update role PK II which is already being introduced for improving on the double ratchet to party literature and our construction is inspired by a suggestion for this application in fact by Conrad Kovac on the MLS mailing list so we basically ran with that in this paper and intuitively can think about public key encryption a updatable PK e or u PK is giving you sort of a very practical way of getting forward secret PK so how does it compare to standard PK e well it's pretty small change here we've got standard public key encryption and what's the change well basically when you encrypt you actually output now not just the ciphertext but an updated public key and when you decrypt that corresponding ciphertext you output the updated corresponding secret key so in other words the act of encrypting decrypting also re randomizes your public secret key pair at the same time so correctness traditionally is okay any ciphertext you get in a CPA scheme or CCA scheme you can decrypt we now need things to be synchronized we need this in order that's right you have to keep your public secret key pairs as you update them you have to keep that in sync in terms of secret security while standard CPA security you know we all know that encryptions of any two messages should be indistinguishable and now we want that if the adversary gets to choose these updates at will so basically he's supplying cipher texts eventually he says ok now I want a challenge he gets a encryption where he doesn't know the randomness we want that encryption to still secure in the normal CPI sense even if after than the fact he then then you reveal the next updated secret key to him right so so there's the challenge ciphertext and then you do an update with fresh randomness which the adversary' doesn't see and you reveal the new secret key still wants to still want security for the the message in the challenge ciphertext so the construct we have a construction it's very similar to El Gamal basically so it can be generalized across you know pretty much any prime order group and it's it's very practical in terms of efficiency yeah so so basically this new version of tree can we call it our tree cam the takeaway is you take tree can you replace public encryption with updatable public key encryption and you go from you know not great forward secrecy to optimal forward secrecy yeah so so that's pretty much what the picture is there and and you know the reason this this this this helps things is because now we have a second mechanism for replacing keys we don't have to wait for someone need to do an update simply the act of sending them a cipher text and then decrypting already updates those keys so these critical keys are immediately replaced the moment you decrypt the cipher text with a key you replace that key so there are no more critical keys in this tree all right that's why we get forward secrecy within one step so yeah basically there are more results in the paper we look at adaptive security we also have like you know future directions for secure messaging I think you know I agree previous talk there's all kinds of open problems there that we could work on also in a follow-up work that's we show how to do you PK e for the x.25 for 9 X 4 for 8 curves because those are not prime or two groups so you have to do a little bit more kind of working but it's also nice and ficient practical so yeah that's so we're going to move straight on to the next talk I'm sorry if you want to talk to Jill about this paper or this work please catch him at lunchtime we're actually switching now to a slightly different mini session this one on compromised credentials and the first talk in this session will be given by Kevin you all right so thanks to the introduction Kenny and so I'm Kevin and here today I'm going to talk to you guys about protecting accounts from credential stuffing through the use of password breach alerting or all or what I like to call password check up so before I begin I want to mention this was a joint work with a damn Pony at Stanford as well as really a large-scale effort at Google that spanned across many teams across many different locations and it also involved several teams and people that aren't listed here but were integral to the success of the project all right so let's get started so it's sort of to understand the problem with credential stuffing we have to go back and you know go back to the last decade and understand that there's been a lot of breaches of data for several organizations and companies and what's happened is you know the hackers that sort of do the performance data breaches they sort of share and pass around this data through the dark web so like these sort of news articles show that you know these hackers have billions of records and these things in fact the brilliance of breach account credentials so you know using this this large set of breach account credentials what they can do is essentially perform credential stuffing so what they do is literally go to websites and try to log in using these compromised credentials so quit it in almost a jarring statistic for me was that you know let's the online retailers such as Macy's and Nordstrom about 90% of login attempts are actually hackers trying to hijack accounts so it's a real problem is actually quite prevalent and it's it's a something that we really need to tackle so so there are ways to defend against potential so things like defense-in-depth so a great way to defend against these kind of hijacking attacks or 2-step authentication right so even if a hacker has has my compromised credentials which I'm not aware of and they try to hijack my account if I have to factor authentication enabled they wouldn't succeed at hijacking the account unfortunately this only works for really like let's say larger websites because you can imagine there's a long tail of smaller websites for which many people don't even remember they even have accounts at and for which these defense-in-depth sort of protocols are not available right and in these cases would be was a hijack the accountant would be successful essentially and taking over so sort of to get to the you know the actual problem what we believe the real problem is is sort of an imbalance of knowledge so you sort of have on one hand you have these hackers you know who have gone to the dark web and you know they have access to billions of these a compromised credentials and they're able to use them for credential stuffing and whatnot on the other hand you have an average user you know the ones who can already use the Internet but you know maybe are not so well-versed in cryptography or they don't even know how to go to the dark web so they have a list of credentials and they actually just don't know which of the credentials are compromised and which ones are actually secure to use right and sort of this imbalance of knowledge is actually one of the reasons that credential stuffing is so successful so okay so let's in our work we're actually trying to find a way to sort of solve this imbalance of knowledge and we try to do this through the use of what we call password breach alerting or what I like to call typically sometimes as password check out so you can imagine you know on your left you have this sort of server and let's suppose the server is able to also source this list of breached account credentials maybe through the dark web or whatever and sort of you know they have these interests these end compromised credentials so what the password breach alerting protocol would sort of do is expose an API to the general public in such a way that an average user you know let's say an internet user can come and sort of it has a sort of credential that it wants to check whether it's breach or not so what it can you know from a high level what it will do is it'll send something like an encrypted request of its username and password and I'm gonna be very vague here I'll go into more details of what the encryption means so sort of using this encrypted request the server would process of an encrypted response of whether the username and password that was queried by this user it was breached or not alright so now I was very vague about what encryptions what is encryption mean here so let me go deep in and try to exactly define what are the design principles that were necessary for this protocol so the first principle which is now I think the most important is obviously password privacy so going back to sort of this protocol here when this user does this query for his username and password it should be done in such a way that the server who's hosting this API they don't get any knowledge about the query password right so this was sort of the whole problem to begin with is that hackers were able to get plaintext knowledge to the password so to sort of solve this problem and you know that which alerting protocol it must be done in such a way that you know no knowledge about the query password is ever revealed to the server all right so that's sort of the very first design principle of course it's probably the most important a second sort of athough g''l issue but it's actually quite important is actually sort of mitigating abuse risk of the API so you know going back to this server that has this this database of which credentials even though it's sourced it through the dark web the database is actually still quite sensitive right and it shouldn't really be widely spread it shouldn't just be available to everybody who wants to sort of have access to it through the API so what you can imagine is sort of a scenario where a hacker comes you know the API general is exposed to general public so a hacker kernel obviously also use it and what it wants to do is maybe one query or sort of a series of queries to this API and does it in such a smart or maybe some sort of sophisticated way to sort of extract the database of which credentials right and this would be a really bad problem if we like you know if this database which is available to all hackers because now they can go back and do credential stuffing again and again all right so to sort of see what's going on with the problem you have to sort of take a step back and you know take a look at a higher level so of course one wafer hacker is to get these sort of breach credentials is to use the password which alerting API but like I said simultaneously there are other means for this hacker to sort of get this data one is through the dark web right and sort of one the goal that we how we were able to achieve a mitigating abuse Chryst is sort of trying to make sure that sort of the cost of abusing these api by the by these hackers is larger than other the cost of maybe going through the dark web to get this to get this data so for example you can imagine hackers might come up with very sophisticated and expensive sort of ways to sort of use the lies the protocol to get the breach credentials but if that cost is still much larger than what it would be to get on the dark web you know we have mitigated abuse risk if we haven't made it any easier for hackers to sort of get this this sensitive data all right so you know taking a little taking a step back we sort of have to privacy goals right well for the user we want to make sure that the queried password is never leaked to the server and simultaneously from the server's perspective that exposes this API they want to make sure that whenever a user sort korie's for a credential username and password it doesn't or any knowledge about another credential let's say username Prime and password product alright so that was sort of the second design principle and the third one is what I like to call simple but effective crypto and this is very subjective so let me try to get into intuitive the most and carefully like I said before this project Israel it was a really a large-scale effort across many different teams at Google and there are many engineers at Google that are very smart but don't have the expertise or haven't spent the time studying crypto right and since it involves as many so many teams having simple crypto enabled them to be able to utilize the library easily right and this is a very important thing because you can imagine there are reliability teams that need to make sure the machines are running and they actually need to understand the crypto protocol and simple crypto enables such a such sort of reliability another sort of aspect that's very important was developed with velocity or implementation time as we sort of all know implementing crypto is quite difficult right and it takes a long time to implement it correctly try to make sure to vet it and make sure all its secure and sort of simple crypto sort of enables this at a faster rate and with more trust and in the code so I would I guess what I'm trying to say is that simple effective crypto is not necessary for launching this product at such a large scale but it really makes it a lot easier and it's a very important part at least in my opinion all right so given that we have these three design principles let's go ahead and try to and I'll try to explain to you how we achieve design principles in our protocol so again we have let's say these Google servers on the Left who have this set of n compromised credentials as a u 1 P 1 all over the U n P n so the first step essentially is how will the server pre-process this database in a way that it can it can readily sort of serve requests from users so we do essentially is we sort of take each credential and we take his username and keep it there and we sort of take the concatenation of the username and password and hash it using some hash each prime I'll discuss what H prime is a little later but let's say I do this for all and bridge credentials that are big that exist on the database the next step is the server sort of generates a secret key K and essentially encrypts encrypts each of these hashes of username and password concatenations by simply exponentiating it so sort of going back to this this hash H Prime what it's really doing it's sort of mapping strings tune elliptic curve right and in particular we have to choose an elliptic rib obviously where diffie-hellman is hard so that this is actually an encryption all right so that's sort of a completely pre-processing for the second tuple in each in each pair let's go back to the username which is the first tuple in each pair free for this username what we're gonna do essentially is take an uncute hash let's say H we can think of is you let's say shot two three six and so just simply hash it to the usernames so the password breach protocol is actually parameterised by some positive integer B and this B comes in right here where essentially what we're gonna do is we take the uncute hash and just take the first b bits of it we're gonna drop everything beyond the the first PPS and just keep the b bits and so these b bits will actually act as a bucket in the fire so we're gonna do actually is we're gonna have two to the b buckets and each bucket is uniquely identified by a b bit string and we're gonna sort of bucket eyes all of these encryptions using this bucket and fire so for example here let's take this example here you have the third you know the third compromised potential u 3 and P 3 since I went to the bucket that has you know zero B's or be zeros what it essentially means is that the on keyed hash of U 3 the first B bits of that was all zeros and actually that turns out that's all we need to do sort of pre-process the database to get ready for for queries and I guess something I'd like to mention is that this is sort of easily sharable and you'll sort of see why but you can sort of have many machines sort of handle different buckets alright so let's let's go on to the query algorithm and how a user who sort of comes with a specific username and password that it wants to query can now send a request and sort of get these responses so the first step of a query algorithm is that the user will generate an ephemeral key so this ephemeral key R is per session it doesn't have any it doesn't have stored long term as anything like that and sort of what it does next is it'll send two things to the server in an encrypted request the first is it takes the username that it wants to query and does the same sort of on keyed hash let's say you shot two to six and just takes the first be bits and that'll be sent to the server the second thing it does is also takes the concatenation of its username and password and hashes it to the elliptic curve and encrypts it using this ephemeral key arm and that's the entire encrypted Qwest by the by the user so now let's suppose you know this request has been sent by the user and the server sort of receives it so what it first does it sort of takes the B bits of the unkeyed hash and simply sort of identifies the bucket that's core that that's that's corresponding to this B bits and then once it finds this sort of a correlated bucket it sort of just returns all the encryptions in this bucket to the to the user so that's the first part of the encrypted response and the second part is it sort of takes the the encryption of the username and password that was sent by the user encrypted by this by the user secret key R and sort of re-encrypt sit so you can sort of think of this as an almost an oblivious PRF where it's going to sort of use a commutative encryption but what it does is sort of takes this username password carnation encrypted under R and it Rhian crips it so that's now encrypted under both R and K where K is server secret key all right so that's actually the entire cryptid response by the server so given that now this encrypted response comes back to the user the user has to do the following two steps to determine whether this whether it's using the password we breached or not the first step is this sort of decrypt it's a secret key R so since it generated the ephemeral key R it knows our inverse and can simply sort of exponentiate or decrypt by our inverse to sort of get its username and password encrypted under only the server secret key and you can view this essentially an oblivious pseudo-random function and then the second step all it does is actually you know takes this username and password that are encrypted under the server's secret key K and simply checks if it exists in the bucket that was returned by the server and it's not hard to see that you know if you and P did exist in the bridge database it would have been encrypted under the service key and appear in this bucket because of course hash the hash of the username was first P bits will be the same and actually this is the entirety of the protocol so this is it sort of very straightforward very simple and I hope I've sort of convinced you it's sort of simple because I've explained it in probably less than 10 minutes so let's go back to the design principle it sort of said it's simple crypto let's go back to the design principles to make sure that we've sort of achieve what we wanted she remembered the first thing we talked about which was the most important was password privacy in that whatever request was by the user should be encrypted in a way that the server gains no knowledge about the correct password so let's take a look at the protocol again more carefully the user sort of sends two pieces of information to the server clearly the first bits of the hash of the username contains no information about the password so there's no information there so the only bit that contains information about the password was actually this H prime u P but it's encrypted under this user secret key R so assuming you know diff the diffie-hellman problem is hard in the elliptic curve we chose you can actually show that you know the server doesn't gain any information about the password alright so sort of the second sort of design principle we wanted to do was sort of mitigate abuse risk right and that when it's when a user does a single query for username a password you shouldn't learn information about other credentials let's say username Prime and password Prime so taking a look at this side you can sort of look at what's being responded by the server to the user so even though the cert the user sort of gets this bucket of all these encryptions under the secret on this server secret key K it only gets one double encryption of its username and password of the using even has a bit query so even though it gets sort of this bucket it can only test its specific user name and password whether it's it's in the street or not so it sort of satisfies this growing sense but there are actually even more stronger ways to sort of achieve mitigating abuse Chris and one way we actually did was sort of sort of a limit the demand the number of queries that a user can perform by replacing this H you know I said before shot you to six you could imagine it being replaced by more expensive hash functions which she let's say are gone too so you know if a user if is if a hacker wants to come and try to perform many many queries to the to the API it sort of has to pay the cost of computing this expensive argonne to hash over and over again and in addition to sort of using expensive hash functions you can also use things like rate limiting and stuff like that to ensure that we mitigate abuse risk all right so that's actually you know I hope I convinced you guys that you know the protocol is simple and you know it satisfies all the design principles that we wanted ahead of time so let's move on to the actual implementation of the protocol and and where it's implemented so the first thing that we need to figure out is you know where did we get this breach account credentials right where did this password where do these breach passwords come from so actually there's a fabulous counter abuse teaming in Google that actually works on this stuff and they have a paper from CCS 2017 that describes you know that gives more details about how to get this database but this database contains more than four billion unique user names and passwords from breaches and this is what will be used went from the API when serving for the API alright so I'll talk about the first feature that we launched earlier in 2019 that sort of exposed the password breach alerting API to the general public and it was through the use of the password checkup extension so right now this was just very recently it has over a million users at this point in time so what happens is you know a user goes and when they download this extension what happens is the extension would automatically detect login forms so let's suppose you know a chrome user sort of downloads this Chrome extension so every time it sort of logs in a username and password to a form the Chrome browser extension would automatically detect it and automatically perform a password reach alerting protocol and you know you get one or two notices you know if if you're the you know the account credentials you use to login with we're secure you would get sort of no no notice and if you sort of clicked on the extension you'd see that none of the passwords you recently entered were detected in their data breach on the other hand in the bad case when you know you you log in with a breach credential you automatically get sort of this red notice immediately telling you to change your password on this specific website so for example if I logged in to github.com with some bad credentials it would send you this notice alright so before I like to go I'd like to just quickly mention that the extension actually uses an older version of the protocol and the future and another the other features I'll talk about later use the newer version of protocol and the nuances between the two protocols we discussed in the next talk by Lucy all right so I'm going on we were actually able to you know collect anonymous telemetry from this extension and so I wanted to share with you some very interesting statistics that we were able to deduce using this anonymous telemetry so you know for anonymous and lemon tree we just we got things like you know the domain that of which people were logging into timestamps breach status and you know performance and stuff like that so the first thing I'd like to mention is performance metrics of the extension so I think I mean this might be a little outdated but you know at peak usage is about 20 queries per second happening to the extension with over the million users and I think it's a little more now and sort of the round time late around the round-trip latency of password breach alerting protocol was about eight and a half seconds but this includes all the client work that needs to be done and stuff like that and in particular almost half of this was spent on this proof of work you know this argon to hash we had talked about where we used to live to mitigate abuse risk so in turns it turns out that you know this is even though it seems like large 8.5 seconds it's actually quite quite a lot smaller alright so moving on to like the frequency of warnings by extensions in the first month after we launched the Chrome extension we had about 21 million logins that were scanned and of these 21 million logins that were scanned about 300 16,000 of them had a breach credentials that were detected so sort of extrapolating this sort of data out it seems like about one and a half percent of logins on the web are breached but this might be a little skewed because of obviously the people who are who download the extension are privacy conscious people to begin with but sort of this is a this is a general idea of you know of a cool statistic so now this is this I'd like to call out to be a much more open problem is that user response to warnings by extensions we're not actually great you know every time you sort of log in and you have a breach credential you would sort of see this red notice and we wanted to you know keep track of how many people actually adhere to the notice and change their password and it turns out only 26 percent of the people actually changed their password so you know password check up is great but it doesn't really work unless users change their password so I really wanted to call this out as a really an open problem that we really need to solve to make sure this sort of password checkup works better and you know I'd really love for people to work on this alright so this looks like bad news on the other hand we have much better news on the other hand so you know we'd only have like 20 60 percent of people who actually change their passwords when they see this notice but of these 26% percent of people who change their passwords they're newer passwords were strong or stronger than the previous one so in this case this is good news for us right that when when users see this they sort of see that their their their passwords have been compromised they changed their passwords to become stronger in hopes of you know making sure they don't become compromised again alright so that was sort of the first feature we had launched which was early 2019 it was this extension and now we it was a little more experimental in a sense we're trying to get an idea of whether the feasibility of this protocol when we instead of before we deployed it to very large groups of people so now later in 2019 maybe around I think September we actually launched this sort of a pasture breech alerting protocol directly into the Google password manager so if you go to passwords on google.com or those who use the Google password manager you know that they'll sort of show you a list of all the passwords that you have and in particular we launched this password check up sort of a feature so you know if you go to passwords like Google klom you sort of click check passwords it does a bunch of sort of checks for you to make sure that your passwords are strong and they're not compromised so sort of the first line or the first thing that sort of checked is whether your passwords been compromised in data breaches or not right of course other things that are also checked are things like reuse passwords or whether accounts have weak passwords and stuff like that all right so sort of going forward and I think this is probably the most exciting thing that we did was that we you know previously we had this Chrome browser extension that required people to sort a lot to sort of download the extension or sort of opt in so we went ahead and did it was actually implemented this natively into the Chrome browser and this was just recently launched in December of 2019 so last month so what sort of happens now is whenever every signed in user whenever you log in to whenever you know you enter credentials into a login form the Chrome browser would automatically detect that you're logging in to a crawl into a into a into login form and perform the check for you automatically right and you know if again if you sort of have a you sort of log in with credentials with a breached you would sort of get this notice the meetings telling you to sort of change your passwords all right so I mean these are like sort of the three features which are currently available for general public users to utilize the password checkup to help and go and check your credentials all right so going forward I'd like to mention that you know a lot of cryptography it's very difficult implements and it's very important you know that the academic in the outside world the general public sort of that the data so I was sort of at the code so I'd like to mention that all the cryptographic protocols that are used in the in the password in the password breach alerting protocol are available on github and under the private joining compute sort of section so this it contains all the cryptographic elements are the cryptographic implementations but the actually the more general implementation of the actual password breach alerting you can see in the Korean code base which is also open sourced alright so I wanted to come with the conclusion that you know hopefully I've convinced you guys that privacy preserving password check up is actually protecting millions of users from account hijacking around the world and in particular we're trying to solve this imbalance of knowledge where we give users more power and knowledge of which of their credentials are secure into you know which they can feel comfortable with and which ones are breached and should be changed so thanks for taking listening and talking I'll be happy to take any questions so we're already a little bit behind schedule so I'm gonna limit the number of questions just to a few so let's start on this side thank you very very very cool work and I'm really happy to see Google working on this my question is it seems really crucial to the security properties of the protocol that there's this association between the username and the password but what if all you have is a bag of passwords have you thought about that problem yet right so this is this is a great question it's something we actually considered so one of the principles that we came up with when coming with this protocol was that we didn't want any false positives so we felt what I mean by false positive is the following you have a very strong password which sort of give you a false positive that oh your password is compromised you should change it right as we know it's already very hard enough to come with a strong password and if you keep asking people to change it you can sort of they might enter weaker passwords or ones that they'll forget so going back to this idea of just doing password only checkups suppose you know you can imagine a situation where I actually have a strong password and you know maybe only one other person in the world somehow shares the same strong password of me and they're how credentials were breached right so in this sense is it really does your confidential is actually compromised and in our sense we believed it's actually not and it was safer for us to keep to make sure that users kept their old passwords I think so though if an attacker can guess the password that it knows if it if it can do like an online attack to you know it thinks it's highly likely that you might have that password I don't I just don't know if the risk is totally addressed that's fair enough I think I think we still believe that the usability this false positive stuff was much more important in the sense we don't have to go change the passwords thank you so the server reveals a list of hashes to the power K and at the same time the server can be used as an Oracle to raise anything to the power K so can it be abused by an adversary to find a weak password of someone yes so that's a that's a great question and that's that's one of the problems we we were addressing so one of the ways we said we talked about before which you could actually use these sort of to limit the number of queries that are being performed to like you know usually raising to the power of K with the Oracle you can use sort of argon to or expensive hash functions right so sort of it makes a actors sort or like hacker sort of have to really spend the computational time to make that happen right other ways we do this are things like rate limiting so for example the Chrome browser right now only allows signed-in users to sort of perform queries and we have rate limiting for each account and it sort of cost people money or like those there are cost and guards against creating many accounts so we sort of rate limit to prevent these sort of attacks from happening okay I'm gonna take one more question from this site and then we're gonna color line so my question is somewhat related to the first one I'm wondering if you consider using stronger privacy guarantees under username so for example if you ask for if you check our best world enemy at depth I'll use your time to connect to under private connection then you can easily in fact that that reason I mean is being used for that connection yes so absolutely we always look at trying to improve the privacy of everything we do but in this case it turns out to be a sort of a feasibility versus privacy sort of trade-off right to sort of gain very strong guarantees for private for username at least to my knowledge they required a significantly more efficient like efficiency losses right sort of having almost not real time checks cuz you have to you know we can go into this a little more detail but you know it costs more to sort of hide more bits at the username so there's a trade-off of whether we have you know whether the current disk and on India that we provide for usernames suffice is for the data and we believe he does so because usernames are less private than passwords right but on the other hand having the feasibility and enabling users in the general public to have real-time password check out we believe was much more important so we were able to sort of sort of find the right balance we believe Thanks okay thank you very much Kevin let's thank the speaker again Anna will now move to the the last talk of the session and it's a short talk and it's going to be given by a by Lucy I'm just setting up okay so a talk is about protocols for checking compromised credentials and the talk is given by Lucy Lee from Cornell so today I'll be talking about the same general topic as Kevin's talk and Kevin talked about the details of Google's implementation of a compromised credential tracker and I'll be taking a look at these types of further calls as a whole so like what we want security wise and to what extent existing for other calls meet that goal so as we've all heard about there been many passwords reaches over the years which has led to attacks called credential stuffing and these attacks can be dangerous because around 40% of users we use passwords across different websites meaning that even if an attacker has your credentials from another website they might be able to log in as you on a different website so one way to mitigate the problem of credential stuffing is to use a third-party to check if a user's credentials have been previously leaked and we call these third-party services compromised credentials checking services so using this service we have a client which can be some individual or another online service and the compromised credential checking server maintains a copy of a leaked credentials database so a collection of usernames and passwords that have been previously leaked and the client has a credential which can be either a password or username password pair and they want to find out whether or not their credential is present in the servers weak password database so the main question we want to consider here is can we use a third-party checker and still preserve privacy of user credentials to big initial deployments of services with this goal in mind or have I been pwned which checks to see if your password is present in a non dealer breach and Google password check up which we just heard about which checks if you use the name password pair is present in a breach so to answer this question in our paper we made the following contributions we gave a formalization of these c3 protocols and talked about the threat model and we show formally and empirically that have I been pwned and the initial Google password checkup protocols leaked information all passwords so I'll be differentiating between what I call GPC v1 and v2 the one that we just heard about is the second version which is an improvement upon the first version the first one used a different vocalization protocol which I'll talk about in a minute and we give new c3 protocols that leaked less information about passwords in the username password setting this is ID based bucket ization which is now the second version of the Google password checkup protocol and we both arrived at this new protocol independently and in the password only setting we introduced a new protocol called frequency smoothing bucket ization so today I'll specifically be talking about our empirical results that motivate the move from the first version of GPC to the ID based bucket ization and hopefully from the have I been poned protocol to frequency smoothing vulcanization and we give an overview of frequency smoothing bucket ization which is our new password only c3 protocol so to take a quick look at our threat model it's pretty similar to the one that Kevin just described so there's a lot of potential other issues but in this talk I'll focus on the key challenge which is protecting a client's password against a potentially malicious server so obviously this means that we're not going to send the password and the clear to the server and in the ideal case this means no information about the password is leaked because any partial information enough about the password that is leaked to the server could speed up online guessing attacks of this password so more specifically suppose see through service obtained some password leakage associated with a known user Alice and the service could then use this information to improve the efficacy of an online guessing attack in which they have cue tries to guess the guessed Alice's password before they get locked out and knowing any partial information about Alice's password can be the difference between guessing it correctly in Q tries versus not being able to guess it at all so one main issue as we saw when designing compromised credentials checking protocols is the large amount of information a server has to store and search through on request from a client so typically a c 3 server could store hundreds of millions of passwords or even billions of user name/password pairs so they need to be able to handle client requests efficiently one way to achieve this kind of efficiency is to divide the entire credential space up in the buckets so here in this example the list of passwords held by the c 3 server has been split into a few different buckets when a user wants to check for their password in the database they send the bucket identifier in this case it's the color orange to the C 3 service the C 3 servers can then send back all the passwords that are in the same bucket and we also need to combine this vocalisation with some way of hiding the passwords like some sort of private set membership protocol similar to the one we saw in the Google protocol so we don't reveal the plaintext to the client and in practice both have I been pwned and Google password check up use some sort of hash prefix as a bucket identifier have I been po news uses a prefix of the hash of the password and in the first version of the Google password check out protocol they use the hash of the prefix but the prefix of the hash of the username password pair so the key security question we want to answer with artwork is how much does knowing the bucket queried help an adversary guess a client's password so one way we answer the security question is through empirical evaluation again we want to know how easily an attacker can guess passwords given bucket identifiers for different see-through protocols we use a breach data set of 1.4 billion username password pairs which we split into a test set and a leak password set and we measure the percentage of passwords an attacker can guess in Q queries with access to the usernames that they're targeting so to visualize our results I've plotted an attackers successful password recovery rate when given 1 to 1,000 password guesses and in the baseline simulation where the attacker gets no information about the password it can recover less than 10% of passwords and a thousand guesses but when we use the have I been poned or the GPC v1 protocols and leaked that bucket information to an attacker they can now guess 60 to 70% of the passwords and frequency smoothing buccal ization which is our new protocol that we propose in the password only c3 model when we give the attacker the bucket information for that protocol the attack only performs a little bit better than the baseline so first I'll take a quick look at the ID password c3 setting which we already heard a lot about and then I'll talk about the password only c3 setting so in the ID password setting we check for an exact username password pair match with a c3 server and the first version of Google password check up initially implemented a protocol that uses the prefix of the hash of the username password pair as the bucket in the fire and as we saw in the empirical evaluation I just showed there's protocols for security if the username is known to the attacker in our paper we also give a formal justification for why this one for what the security loss is and so we eventually both settled on ID based balkanization which uses just the prefix of the hash of the username as the bucket and of the fire which we also give a formal justification about for why this will leak any information about the password so moving on to the password only c3 setting this is where we check if a user's password is present in breach data so the ID Beit ID based bucket ization protocol does work in this setting because we don't have access to user names and a c3 server might want to use this because it could avoid the risk of storing user name/password pairs and potentially making it easier for an attacker to find those so I'll talk about why have I been pwned leaks information about passwords that speeds up remote guessing attacks and I'll go over our new protocol frequency smoothing bucket ization so how have I been pwned works is the user takes the hash of their password and sends 5 character prefix to the server the server then sends the user a bucket of all credentials that start with the same hash prefix and then the user checks to see if their passwords full hash is present in the bucket so to illustrate the issue with have I been pwned I've constructed a small example so users generally choose passwords from a skewed distribution like the one on the left where some passwords are much more popular than other lower probability passwords and there's usually along the tail of low probability passwords with which I haven't shown here but with the probability distribution you see here we might get a bucket ization like the one on the right where each password is matched to one bucket and the colors in the book is here correspond to the probabilities of the passwords given the bucket so if an attacker knows which bucket was queried it's pretty easy to figure out which password is most likely to be the correct one and then they can narrow down the search space to only those passwords that belong in the bucket and then choose the most likely ones from that list to guess in this example even in the case where we have two passwords in one bucket the blue password is much more likely than the orange password so an attacker would guess that one first and have a higher chance of winning so to fix this problem we introduce frequency smoothing bucket ization as a more secure password localization algorithm instead of putting one password in each bucket corresponding to its hash value we add it to a number of buckets proportional to its probability so the passwords in the distribution on the Left might be mapped to buckets in a way that looks like this and you can see that the most popular password the password is split up into is put into every bucket and the least probable password which is the orange password is only added to one pocket so the goal here is that given a bucket the probability of each password in the bucket being the correct password is about the same and how do we actually implement this so frequency smoothing bucket ization is parameterised by an estimate of the password probability distribution as well as Q the expected guessing budget for an attacker and first I'll talk about how this works when Q is equal to one so we have some number B of buckets and we take the most probable password then we add it to every bucket we then add the rest of the passwords to a number of buckets proportional to their probability relative to the most probable password so for example since the blue password is half the probability of the red password we add it to half the total number of buckets and we choose the starting bucket for a password based on some hash function and we add a password to every bucket in the range from its starting bucket to the number of buckets that we're adding it to and a password can be included in anywhere from 1 to be buckets if a client wants to check if their password is in the server's database they can compute the range and select a password randomly from that range so the server when fetching some bucket I just returns all passwords that have ranges that intersect with I so this parameter Q as I said reflects the expected online guessing budget of an attacker so how do we actually implement this when Q is greater than one so what we do is we include the top Q passwords in every bucket and distribute the rest proportionally relative to their probability compared to the probability of the Q the most popular password so for the security of our frequency smoothing bucket ization protocol we show that if an attacker has less than or equal to Q guesses access to the bucket won't give any information won't give any advantage over baseline guessing where baseline guessing is just guessing passwords order of highest to lowest probability and we also give bounds for when an attacker has greater than Q guesses which we show in our paper in general higher values for Q lead to a smaller security loss but also they mean larger bucket sizes for our protocol so when choosing a parameter at Q we have to balance between the two factors and taking a quick look at how all of these protocols that I mentioned perform if we take a look at the password only setting it's pretty clear that have I been poned is more efficient than frequencies moving bucket ization but as we saw it's also much less secure frequency smoothing bucket ization has about the same cost as the protocols in the ID password see-through settings so it's definitely feasible to implement and run and in terms of the ID password C 3 setting they both have similar bandwidth in runtime so it's pretty clear that ID based bucket ization would be the better protocol to use in this scenario and so in conclusion some deployed C 3 protocols leak a lot of information about the user's password to a c 3 server and we recommend using frequency smoothing bucket ization and the password only setting and ID based vocalization and they username passwords I think thank you so we have time for perhaps one question or two questions if they exist we got one coming you can actually actively you accurately model the probability of any particular password how close is that to be to is to exact how close is that to accurate obviously we don't know like that for the real distribution but because there's so much data over like password breaches we have billions of credentials that have been leaked we can see that there's a lot of passwords and there like a lot more likely than other passwords and it kind of forms a easily guessable distribution so in order to compute the range to know what bucket to query the client needs to know the probability distribution yeah how does the client get that so we have a model of the profit probability distribution that's relatively small that we can send to the client so they can compute this okay thank you very much for the talk yep and that's lunch time and we'll see you in the afternoon for a session on machine learning and cryptography