2016 - Ignat Korchagin - Enforcing Web security and privacy with zero-knowledge protocols

hello everyone am i speaking loud enough okay so today we're going my name is it not I work for cloud fair and today I'm going to tell you about how to enforce security and privacy on the web with zero knowledge protocols so here we go why do we want to do that so most of you probably use at least some kind of internet service so the basic workflow there if you register from for the service you most of the time I'll required to submit your personal then compiled information there we will call VI and well when you register if you like not lazy enough to read terms and conditions the service professional usually promises to take all relevant measures

to store your pii securely and also the service provider promises to make your user experience secure to allow you to secure the begin to your website view your information to make amendments so but unfortunately in reality we see many leaks so you see database leaks we see leaks API itself most of them happen because there's actually there is no clear definition of water relevant measures means and how to run what storing information securely means and most of the time and your service provider implements all the measures which are required being compliant with some security standard but the service provide doesn't really care much about security one recent example from myself was that I looked any place recently and a sensor

my internet provider was not providing any service there I subscribed to another one and after that I got a call from their credit check department and say hello where and ready check of this internet service provider and we want to confirm your address I say okay okay yes please sell it tell us your dress hey I'm not you I'm not a native English speaker but I understand the world confirmed as you tell me that resin icing yes or no and you're basically calling from some unknown number I mean it then it turned out to be a legitimate cold but this is a typical example where a service provider actually imposes you're insecure workflow that anybody can call you from an unknown

number and ask for your address and when I refuse to tell them my dress the lady was surprised at like we always do that stop doing that and also a source provider may take advantage of your pie and the total legitimate example is bank credit reference agencies where they submit your pi/2 credit reference agencies to do some checks and finally your user experience is not very secure and we see that user passwords gets term learning and we see pike website spy plugin prawns and we see that some providers when implementing web authentication do not have SSL or TLS so let's take a look from a security point perspective so when you subscribe to a service you're probably like some

Alice user and they ask you for a passport you just make up a password and submit one but and is and later you want to login to your service and you submit your password again they authenticate you with the password but do you think that HTTP authentication is secure let's take a look here so actually what happens we have HTTP basic authentication scheme so when you log into a website you send your username a custom string called VL and your password in clear text and the subtle just verifies yet this is the same password i have in my David actually if you think of it this scheme is not very secure although it's simple the passport

is sent in clear text and that's why security aware users will never enter this password if the website is sort of an unsecured channel so you have to look for you this green lock in the browser HTTPS is required and also there is a drawback that if server database leak it compromises your password and if you reuse passwords in many different websites these attackers can try the same password on your other services so to mitigate that another skin was introduced it's called digest authentication where server instead of viewing password spells the hash V about grab value and how it works so a user requests protected resource and server generates anome's user submits hash of the password hashed

again with distance and the knowns the user generated in response so this game is better passwords are not scented the attacks anymore this scheme is protected from replay attacks because he used to nan says here servers do not lead to store passwords themselves anymore so several database leagues only compromises the authentication information for this specific resource or real as they call it in a digestion issues class but it's still vulnerable to mitm attacks it's this scheme is still vulnerable to spoon websites so if you try to log it so not nowadays attackers grade and clones of legitimate websites like Google is like a slightly different and one letter difference in the domain name and try to trick users logging on the

website and actually leaking their password to this to the website the malicious website all so this scheme still requires HTTPS and this game is vulnerable to dictionary attacks and although it's considered more secure than basic authentication if you read the current RFC which describes the sub syndication scheme it doesn't it specifies directly that this scheme cannot be used with user passwords it can only be used with machine generated password to authenticate services between each other so it says like the password has to have like at least 128 bits of entropy such password typically cannot be memorized by humans so none of the HTTPS current htpc in words using the plasmid actually and they also specify that it should be it

authentication should deliver secure channel like HTTPS and so we see that HTTPS is key to everything so we need implement HTTPS Everywhere in modern internet and this is right thing to do but the problem is it's hard so modern web page is not served from internal servers nowadays but it's like a combinations of many resources taken from different parts of the internet so you have problems with an ex content you have you still have the problem of spooked website so if somebody makes a clone to your website he can legitimately get a certificate for this website and treat you if the website has same look at field as I'd like a major of the website you the attacker can

still treat you putting your credential there you have spoofed certificates of link to this in this blog post and describes a way how and small vulnerability in the Komodo certification authority where an attacker can social engineer domain owners to issue a certificate for their domain for this attacker and we have compromised keys and certificates so HTTPS is the EPI based web infrastructure so basically you it's very complex you to get the full security of this infrastructure to deal with revocation and if currently not called a mobile special mobile device do it very well so we have problems with bi we have problems this password authentication so can we do better yes we can so we can

try to use a class of protocols which are called zero knowledge so the knowledge group or protocol is describes a method or an algorithm by which one party we will call this part a brewer can improve to another party the verifier that need know some secret or private information like in case of our salute and syndication can prove the knowledge of the past the user can prove the knowledge of the castle to the server zero knowledge way and zero knowledge probably the protocols come with bunch of useful properties the cross properties completeness so basically would stage if the statement which the promo tries to prove is true is the honest verifier will be a convinced of

this fact by nanas cover so if you do know the password the server will authenticate you people the server will be sure that you do not indeed know the password so the soundness so which stays if you don't know the password the server will know that that you don't know the password except there is a small cheat probability here which will i will describe a little bit later but if you think of it more than authentication schemes also have a cheap probability so you can try to guess the users password and you can cheat the server that you need know the password when out indicating on the use of service so the first two properties

describe a more general class of interactive proof systems and we use it every day now so for example pls authentication scheme is an exam of interactive courses and worry you prove to this where the several proves to you that server now some kind of a private but which which the thing which makes zero knowledge protocols difference is the salt property is the zero knowledge property so which basically states if the statement is true and the verifier is dishonest and the verify learns nothing from the fact that the fact and she learns nothing except the protocol alpha outcome so if you have a case with malicious server and you enter your password there the protocol guarantees

that not a single bit of your password will be leaked to the sorry so let's just review it by example so this is a textbook example of zero knowledge protocols and major you have this cave with a magic door and the door opens when somebody tells this magic secret work and imagine we have approval he wants to go she wants to prove to the verifier attention all this way and magic port so what does she do she picks randomly in the past to enter to the cave aob so in this particular case and approval have children be then the verifier goes into the cave and shout also randomly chooses a or b and shout so in this case the verify shouts pass a

so and the prover needs to reliably appear on the past which verifier has chosen so in this case the cooler just uses her knowledge of the magic world opens the door and [Music] appears on past a butt and the verifier scan is satisfied with the proof but here we have you may notice the problem what if in the first step the prover will choose but a and the verifier will also choose plus a so in that case the pooper doesn't even need to use or know the magic word to open the door and the prover can also reliably appear on pass a so this introduces a cheap probability and in this textbook protocol the chi

probability is fifty percent so you can just try to guess what the verifier will choose at the end enter this enter this path so if we review this protocol as only being one round and we consider all rounds independent so we can just run this pod called several times and we can reduce this cheap probability to an arbitrary small value as we want so for example if we do run this protocol 120 times our G probability it would be to power minus 128 which is as secure as is so just by repeating at the protocol several rounds we can reduce the small sheet probability so it's ok now of course a real-world zero-knowledge protocol a little bit more complicated

and one notable example I want to show is socialist millionaire so basically this protocol describes the problem where two people want to check whether their wealth is equal so transfer to authentication scenario weather like client and server possesses the same password so they can authenticate each other so the way how it works you can be implemented over a little cryptography so imagine you have a common set of cryptographic parameters you have Alice and Bob do this like usual and the server and they both want they both possess some secret information x and y and they both want to know whether x equals y so but they do they do couple of computation and exchanging of intermediate values how

they do three rounds of computation and exchanging values so you don't have to dive into the mass here I just put it at a reference you can check it out later and at the end they basically check this equation and if this equation holds each of the four them reliably knows that the other party way possesses the same secret so for interested people if you do enroll the last equation it will look something like that and you can just see here if x equals y the last term will be 0 and the equation walk home so this protocol is more complex bug has some useful properties so it's protected from passing attacks so a passive attack

on loans nothing about the protocol or its caltrain of the passer attacker is the one who monitors your network for detection so it is mi-tm protected so mitm can loop can do no better than a passive attacker except just disrupting the communication channel and prevent you from communicating it even if one party is dishonest these this party known learns nothing about the other party secret not a single bit so this is useful for this is what I told about the zero knowledge property of the protocol and actually unlike the textbook zero knowledge protocol which we saw earlier this protocol does not require several several rounds to reduce the ship probability so it requires constant only

three runs with exchanges of intermediate information and after that all the parties are getting their result and they are satisfied with this is all so you don't have to repeat this protocol like 150 times and interestingly this protocol is relatively new it's already adopted in open source software and have good tracking history one notable example is of the record messaging if you ever used it vo when I looked at it the only problem I saw that in of the record mess and since 0 socialist millionaire protocol is if you have one based so of the record messaging losses and 1536 big group difficult calculations but we all know the log jam attack which explicitly the paper which describes

states that shows that 512-bit is over diffie-hellman is already broken they suspect that 1024-bit difficulty broken by state level at grocery and if you think of it 1536 dated very close and we probably want to more protection that's why I reimplemented this protocol on elliptical cryptography and not just any one but the modern state-of-the-art he 255 19 the implementation has timing attacks protection it's faster and they also it has support for many high-level languages although the basic protocol is implemented see if you do want to adopt it in your next security solution probably a good chance you will find that your high level language is supported and always have been English degraded in this open source could do

graphic library called tennis so here who Lincoln lead have to a welcome to contribute users to comment review and whatever you like and comments out very well so I want to tell about mobile so I told how can protect from how it can be used in household authentication scenario but what about PRI so imagine a typical workflow where we want an account and you asked for this a cup to a bank club on your current account you submit your pii and bank needs to do a credit reference check it's a busy OPI to credit reference agency where they replied yes tomorrow forever and imagine a scenario where you're new to this country or you just

returned from you've been working overseas for a long time just returned to the country and you're not on file on this credit reference agency and the scheme's because a little bit unfair because you apply for a bank account the bank account goes to credit reference agency you're not on file so the credit reference agency replies oh you're not on file and in this country not being on file means that bad histories of the bank literally declines your application but in this scenario you didn't get your account but your personal information was leaked to credit reference agencies so you already in the database careful this is unfair and if imagine if you have the task to make the scheme fair in

such case so what probably most of people would do let's say okay let's do not send the p.i to the credit reference agency a let's say hash of the pr and hash of the p.i so if credit reference agency does not have you on file it cannot revert the hash and you it seems like that your pie is not linked to credit reference agency in case they did not have you on pal if you they do have you on file they can find you by hash in their database and patron that's so it works but until this case so imagine you apply for it in one bank you have submitted to your hash will submit it to credit

reference agency but declined you apply it in another back and they sent the same hash of the p.i to the credit reference agency and now your information was leaked because a p.i is a little bit different than passwords because PRI is essentially a unique identifier and a hash of unique identifier is another unique identifier and basically the leakage of information here is that the bank can now track you the credit reference agency can now track you with your hash valve and now they put the information that was leaked the credit reference agency knows you're at least applied to both of these banks which is bad if you do replace it with socials millionaire protocol and zero

knowledge properties will guarantee that the credit reference agency will not be able to track that's good so when i submitted my implementation i got some feedback from Krypto community and they say that yet this protocol is good it provides most curative features but there is another protocol which literally does the same thing and it's much simpler and the protocol is called spatial so I decided to compare two of them and whether this one is indeed better or simple so spake stands for simple password authenticated key agreement so it's actually not an authentication protocol is a key agreement protocol and it's a slight variation of simple diffie-hellman so imagine again you have to borrow two peers they want to communicate securely

they have this common set of cryptographic public reprographic parameters and elliptic curve and they'll both know some secret w so how can they do that they do this these simple difficult one like computation but instead of just sending the public parts of the difficult man they mix those public parts with this password information the exchange lost values and literally they can compute a shared secret which is also protected from MITM because basically Fidelma is not protected from on with you yeah so it's better it's simpler it this protocol requires much less number of cryptographic operation a symmetric cryptographic operation so it should be faster it's easier to implement and also it provides a negotiated key agreement

of the protocol outcome and the example of this description this protocol loop is here three makes itself as an rfcs opens a drop and versions for you so you can read it it's very small action and easy to read that's good so how do they compare so both of these protocol so I'm doing the comparison in terms of mutual authentication because we want to apply either with a credit reference agency example or this HTTP authentication scenario so they both provide mutual authentication the protocols are symmetric so after the protocol complete both protocol completes each party knows that the other party knows the same secret they are both protected from a my GM socialist millionaire requires three

round trips of exchanging intermediate data and speak to the growers two round trips oh yeah if Lulu ISIL revised social analysis three round trips if we suspect to but you may ask me the picture shows only one round trip but I am again stressing that we compare the protocols in authentication scenario so here the protocol outcome is the computation of the shared secret to use this protocol in authentication scenario you need to somehow verify that the other party computed the same shared secret so you need another round of tea confirmation sure yes in socialist military protocol is more complex its lower is faster I decided to check how much is it slower so I implemented to simple

benchmarking applications with both protocols and it appears in average in pure see social school in here is 30 times slower but if you think of it again in terms of authentication scenarios if sometimes slowness is even a feature we go as an example modeling a security system I implementing password verification scheme to be to be deliberately slow for example pd kdf to protocol and so the system should be implemented in such a way that it is fast enough for a legitimate user but slow enough for a new force attacker so then they deliberately implement verification and password in a slow manner so when group force attack will try to verify many many passwords they cannot achieve

much efficiency and if you talk to a real world developers nobody will implement a web application in pure see now so label probably you will use some high-level language like Python and in Python associates millinery protocol is only returns for an average because more CPU cycles are wasted on Python runtime Wembley actual cryptography okay almost on the keys yeah spike too is a key agreement protocol so it ago she AIT's a shared secret as the protocol outcome if you take a closer look at social millionaire it can be actually used as the key agreement protocol as well and it actually negotiates to share secret so if you remember the scheme it starts with stupid if you have unlikely

exchanges so basically if the last equation will hold we can catch those intermediate parameters and use them as a shared secret now and the last but not least so socialist millinery is approved zero knowledge protocol so it has this zero knowledge property which is very useful if you handling personal identifiable information speak to is simple but it might have some implementation k vs i'm going to show them here so if you take a closer look if you think of the secret which is being compared secret w if you think of it as a private key the actual values which are used in the protocol are not so the secret is not use directly but actually some derived value from the sea

did you which looks like a public key so eventually if I define an attacker I do not need to know w itself to successfully authenticate using this protocol I only need to know this publicly right value which brings us to the implementation heavier if you're asking your developers to implement speak to in a secure manner one of the requirements will probably be that they should zero up the protocol complaints they should zero all the memory which contain critical information so they will probably zero the memory which contain w but if they will forget 20 all the intermediate values the attacker can dump this memory and use it directly to authenticate using this protocol so you

have to be aware of all yeah and finally where can we use both of this protocol what's wrong with this page yes correctly and if you implement HTTP authentication using one of this protocol you're secure because the property is guarantee you that another great use case for both this protocol if you have a distributed system to distributed systems which communicate over long live encrypted connection it is a good security practice to rotate the keys and the Teddy Keyes is always hard and always create an operational burden but we both of these protocols you can add someone just you running these protocols at specific times you want so as often as you want and so they both renegotiate your key you'll

save your key and you rotate the key so this this scenario can be fully automated and can be performed without any human right interventions so Newton's zero knowledge protocols are useful building blocks or enhancing security and privacy of the web and especially very useful when you're handling p I so it won't your its properties allow you not to leave any bit of VI to grocery you can also use pay course paid to in many use cases if but you have to be aware of its k VX and although socials New Linnell protocol it will bit more complex it what it provides you more security feature so basically you can decide whichever is better for you you're running this if

you're running for speed probably Spade to it the better choice but if you are not consult with that much and you probably want more security features and publish it should blow your knowledge protocol give some useful links so this is original paper which describes socialist millionaire protocol based on elliptic curve cryptography the code on github this is the same thing I showed before if you are more interested in space to implementation actually boring as yourself Google's boring as a self adopted one recently so you can take a look at the implementation there and the interesting part that they both use the same state-of-the-art elliptic curve cryptography ed 255 19 pretty good and fast and secure and

these are links to these two small benchmarking programs i was talking before to check the speed of each protocol there are also available you can check them out you can use them as a starting point or at an example of how to use these protocols for authentication in your applications that's it do you have any questions

going one yes

yes absolute scale depends on the workload on your actual service so let's say we take example of cloud where we serve like millions of requests per second so speed is probably will be more important to us but for like lower low scenarios security might be more important than even you can make this trade-off but there is no the absolute number will also depends on which type of hardware do you have each cpu frequency how many CPUs and etcetera etcetera so you cannot just measure absolute time without binding a software specific hardware vegetation

well I'm action honestly not in dig it dig deep enough for IBM research problem what why I should have children associate millionaire as my target because usually include the graphic community when you trying to push some protocols or like widespread use people are very concerned about a good track history so meaning that this protocol is already adopted and was never breaking because there is no actually theoretical security it's got money in cryptography it's only like practical security so number number of attacks with efficiency fact we shall develop again that of this protocol in this case why he chose socialist millionaire that it will it's already implemented and have been used for some time in open source chakra

that's why I did indeed enough into more research project I want to show that there is a mechanism to improve the authentication on the web now

gold once going twice done you [Applause]