ZK10: Symmetric Pitfalls: How to use ciphers and hashes in Zero Knowledge - Dmitry Khovratovich

Transcript

foreign [Music] hello everyone it's great to see my co-authors colleagues and friends in this room yes I'm super happy that you come here too uh support me and so that I'm not alone in in given the talk so today I will talk about some problems of using ciphers and hashes in their knowledge well the problems they don't uh specific to zero knowledge but people who work in Decay they they face them

sometimes they face them without noticing that they face them and I think it's important to draw attention to this at some points uh feel free to interrupt me with questions and walkovers so it's totally fine okay so we'll know that there is a lot of cryptography in projects we are working on and most of this cryptography is what people call public crypto or protocols and I'll be talking today about symmetric crypto symmetric crypto is actually not uh not that popular but still it

constitutes a good portion of hash functions vdfs and encryption so we may think that in public blockchains like for example ethereum and others we don't have a lot of encryption but in fact we do we do use it on the client side to store secrets to encrypt the storage to derive secret keys and also occasionally in applications so many applications even when the data is transmitted to blockchains they're asked sometimes use cases when uh the data is not for everyone but for certain people like for example in zcash

when you transfer money transfer coins from one person to another the recipient must know some content of the coin this content is encrypted and actually that's one of use cases and since we use encryption we know we have to know how to use it and what's the most popular problems here so cement to crypto is commonly known as the place where the secret key if it exists is just known to all the parties well when you are not anniversary it's known to you so pretty much the same person who decrypts who encrypts same person decrypts or they both know if there are different people they both know the secret key

and examples are blocks and Sim ciphers hash functions message authentication code and certain kind of signatures and there are many names here that you have seen in different contexts from AES to Sphinx they all belong to symmetric cryptography in the interesting thing that there are some practitioners they've used semantic cryptography very differently so for actual users and developers symmetra Crypt is something that is really fast and this hasn't changed much since you started developing because meaning like as and child libraries are around and

say an open SSL for decades really however for cryptographers who get used to rigorous definitions formal reductions and proofs this is something like kind of vaguely defined some really elusive thing that you try to attack it and then you figure out you can't really attack because that's nowhere defined what you have exactly to attack so so many names things get broken and unbroken every year so many designs are like mess of something and you don't understand why is this mess all around um

this views are very different and they of course both are true as we have us in our real world okay so let me start with ciphers first because ciphers are often uh overlooked so we often promote our new hash functions for example but ciphers are very interesting beasts and I think I would like to draw even more attention to them on this talk so aside first basically whenever you need an encryption you need a cipher you want to protect from something when you encrypt and there is nevertheless not always easy to Define what exactly you protect and from what you protected from

what kind of attack you protected what is an attack in your context what is not um every time you feel there is some asset that needs protection and symmetric case you have to answer several questions like a part of them from the asset you protect but also what are the performance requirements you have to satisfy because sometimes the application is so requiring that you don't uh you're not able to I find a really good solution or the good solution that you have doesn't satisfy the requirements uh sometimes you are restricted in the in the language in the set of libraries and in

the maturity maybe of of a design you oh well I definitely should have waited more [Laughter] okay I'll I'll have a short a short pause yes okay for those who have just come a short recap of previous episodes so we have been talking about symmetric

cryptography that in cement to crypto we have ciphers and hash functions and sometimes PDFs but videos we will not be talking about and I've just started to talking about uh why we need encryption and in case you do need encryption uh which questions you have to answer first before you actually do start encrypting something or even start selecting your perimeter so um you have many questions and I would like now to highlight some important difference between the the user experience of encryption and what's actually happening when you try to encrypt something what happens or

should happen in the correct Library so how we want to see it we want a very simple API with just two functions encrypt and decrypt which may fail of course occasionally but in general we don't want nothing more than that but whenever you encrypt what should happen first of all there must be a secret key somewhere this secret key must persist it's not usually some one-time key but it's it's a key that must be generated from somewhere or and must be stored somewhere it should be retreated from there second many encryption schemes they need either Randomness to start or they need kind of announce or a counter so they're kind of

stateful they are stateful between encryptions so there is some State you have to inherit from a previous encryption session this is the something that you have to not only store you have to retrieve it securely you have to check that for example if there's nons the very much Definition of nonsense is that something that used once you have to care that you use it once you have to update it after you use it you have to may have to be 100 sure that you never use the same notes twice because otherwise you may break the security of your uh encryption I think totally so sometimes repeating a nonce is uh almost as bad as licking a

key and the thing is this nonsense not always obvious so sometimes you can generate it randomly but for many reasons some libraries don't generate it randomly when it's not generated randomly and there's a counter you have to make sure that the counter is updated right after you you have done your data thing you have to zeroize every memory segment because there can be some remnants of the secret key there can be some remnants of the state during the encryption and so on and so forth that's actually very non-trivial so that's probably the deal of uh low-level developers but up until recently it was not even not it was not trivial even in

the C language to guarantee erase an array uh of data because compilers nowadays are super smart and whenever they see you feel something with zeros they badly want to optimize it because it's clear that you don't need this data anymore okay let's go into the security properties you have to care about so the very simple thing that you need from encryption is that uh you have to preserve confidentiality so the one way to define kind of confidentiality is something that informally if you don't know a key then you can't say anything about the

message when you look into the cipher text then any message can be uh could be a plain text if you don't know the key or if you rephrase it in a more formal way then whenever you encrypt two different messages then the ciphertext are and you you are given only one of encryptions then the ciphers you can't figure out uh what was encrypted of the two this actually is not sufficient for for most of use cases of encryption because to preserve confidentiality is one thing but to decrypt back is another in

the simplest modes of operation for ciphers when you just encrypt something without an additional guarantee it may be possible that an adversary just simply changes whoever is able to tamper with the ciphertext if there is no Extra Protection then basically you can just flip a bit it may happen that in the result in plain text just a single bit will be flipped because in the most optimized Cipher that's actually what happens that the diffusion between plain text and ciphertext is very small and it may happen that as a a simple kind of fault attack on the ciphertext will result in a very small change in plain text what you need if you do care about the so-called Integrity of the plain text or

of the ciphertext that you need that uh whenever something new ciphertext is produced something that was not a result in encryption then it must not decrypt or it decrypts the garbage whenever whatever you decide so all together these properties are called authenticated encryption and this is must be default option whenever you use a cipher in the ziki context or any other context so there is very very little uh very small area of use cases when pure confidentiality is enough but instead you should aim for authenticate encryption and authenticate encryption is

uh uh Missing in popular mode of operation like a counter mode for example so you don't you shouldn't aim for counter mode but you should aim for some more advanced version of encryption so uh we whenever you implement authenticate encryption there are problems that developers of popular encryption libraries like openssl they have come over in the last decade but since we are in the environment and like in the zika environment when new libraries appear because we switch to new languages we like like solidity or rust or something

and we we write pretty much the same functionality but in a new way we sometimes forget the lessons that of the past and one rule for example when you decrypt something since you may work with a very large amount of data when you decrypt a large amount of data you know that if there is a kind of a temper if the date has been tampered with that eventually it should decrypt to an error but when you start decrypting it may be okay like you decrypt one kilobyte it's okay they create second kilobytes okay megabyte gigabyte in the end there will be an error but what we have done in the first uh with the first megabyte you should

not release this data to the user so your intermediate State you should never release until you finish your decryption in full and figure out if there is an error or not because there are some very subtle attacks when software releases the kind of intermediate results of decryption because well basically informally the chain in between the parts of the data is not diffusive enough to protect us from certain kinds of attacks um there are other interesting uh properties like for example key commitment but fortunately for uh the

ziki environments is not uh very uh kind of common so the thing is if a ciphertext can be decrypted onto two different keys in certain use cases it can be a problem there were like practical attacks on password recovery whenever it was possible in the software to be decryptable by two different Keys certain schemes prohibit this kind of functionality but certain ones allow whenever you implement an encryption for your protocol you have to think whether this so-called key commitment property is a property you have to fulfill if if so you have to be triple care about

selection right side receipt um okay so one more interesting point I would like to highlight here in the context of ciphers is that there is a very long distance actually from the cipher itself how we know it for example if any of you have looked into how AES looks like and how it looks in the code modes of mode of operation there are very many modes of operation developed over Years starting with CBC and CTR which are discarded nowadays for good reason because there are confidentiality only and prone to certain kinds of attacks GCM is something more secure but

you need care with nonsense there is a mode built up top of GCM which doesn't need nodes but it still requires well basically it's SIV it's called synthetic IV kind of a synthetic nonce and it derives its synthetic from actually the data that it encrypts so you shouldn't encrypt the same data twice because otherwise this will be seen But if if you don't then it's perfectly fine and can free you from not handling uh this is a nice picture I like to show it it demonstrates this the mode of AES GCM

as itself is this EK and all this mess around it what constitutes these modes of operation so this mode of operation is not just split the data into chunks encrypt this with that and this with that no you see there are like sewers multiplication in the gala field some some encryptions of zeros out of nowhere and and so on some truncations you see like here you have to creep but then you you have to truncate this small portion of a 128-bit block that's like really super crazy and all these modes are well I would say they are error prone but

mistakes are being found and there are proofs like decades after the things were introduced so thankfully they these things come now with security proofs and in this security proofs people do find bugs so that's how we okay and now I give a simple example that's what I mentioned in the very beginning that we uh there is a private mixer or some well private cryptocurrency and if there is a task to send one coin to another then hell basically you answer the questions that I've mentioned in the very beginning so you have to figure out what you have to protect like the blonde the Blinder or secret however we call it and the

coin the amount uh and then you figure out okay so I protect the amount and the secret do I care about continentality yes I do care do you care about integrity so what happens if someone changes the cipher text on its way to blockchain is it really bad well I would say it's rather bad because this means that the recipient will not be able to decrypt uh the ciphertext or it will decrypt the garbage and this means that the recipient will not be able to span the coin which you sent them so Integrity must be protected so it must not be just simple AES in the counter mode but sometimes more sophisticated apart from that you can select some uh nice Cipher but then for example if you

want to prove that you have encrypted uh the necessary data to the recipient and if you want to prove it in zero knowledge so that you don't intentionally produce garbage in ciphertext then it means that a cipher you use must be somehow ZK friendly if you uh care about proverb performance here so you have to select some Cipher that is more or less likely friendly you don't have actually big uh a number of options there so AES is not particularly ZK friendly it's kind of okay um maybe it's even okay for your protocol depends how how much how fast

the approver has to be an alternative is to use a sponge hash in a duplex mode uh and this is a reasonable way but there must be some care again how to call this sponge in the duplex mode okay uh here's a nice table about uh encryption problems that may appear in the cryptographic part like uh in the research part of a cipher and in implementation and there can be numbers of them I think I would rather skip this table and go to Hash functions because I don't have that much time left

hash functions are a multi-tool and you see they used in in compressions for commitments sometimes for encryption the security of hash functions uh is somewhat easier to formulate basically what we need three things from hash functions we need them to be one way or pretty much resistant we need them to be Collision resistant we need them to be uniform uh meaning producing uniform outputs on unknown inputs all these three properties they don't follow from each other so I like showing this counter examples for example if you use an identity function as a hash then it's

Collision resistant because well it doesn't compress so clearly no collisions there but clearly not premise resistant if you take a secure hash function and prepend the zero it's Collision resistant and it's pretty image resistant but that's not uniform if you take your input and truncate part of the input and hash the rest it's still pretty much resistant if the rest of the input is big enough but not Collision resistant clearly because it ignores the first part and uniform enough so you have to think for example sometimes it's tempting to drop a few bits from an output of the hash function basically meaning that you zeroize them the question is do you need your your

hash function to be uniform enough sometimes you don't sometimes you do so depending on answers to this question you have to I use all the bits you have or not functions are always difficult to choose you can't just make them fast secure and convenient and well tested I have to choose from some things and new hash functions are always in development there will be a call a talk by a colleague of Mine by Roman in an hour I'll be talking about another design so it will be super fast and super new so first for some of us U is not really good because we want to be

conservative it's always good to be conservative uh but it's also fun to create something new so it's a difficult dilemma or even trailer here okay there are a number of problems in hash functions in Old hash functions there is so-called land extension property balancing session property is something how we call it basically if you want if you have a guy with very short hair is it really easy to get from there to a guy with a long hair like a really powerful guy and do it for free without doing any effort so in some hash functions like shutter

56 this is possible because uh what they do they uh when you hash too long messages together a concatenation of two messages it's something like you first process the first message and then you hash into the second message and what it means is that if the first message is some kind of a key then you can produce like key dependent hash without they've even known the key if you simply extend the first message with some suffix so I think I actually gonna skip this stuff so some nice Hessian bugs that's a very very well known uh to many of us is

whenever you use the same hash function in different contexts but in the same protocol you immediately get problems with security proofs and you may have collisions and this collisions they are not something like really breaking your protocol but they may prefer video from make any uh for finalizing the security proof of your protocol so basically we never have multiple random Oracles in the same protocol you must not instantiate them with the same hash function but you must in in reality you have maybe one hash function or two hash functions so there will be must be a way to separate them use some kind of a

domain separation and there must be a library that does this domain separation properly that must be a way to produce all these domain separations and that's way how many you need when you uh you hash multiple inputs you have to concatenate them properly because most of our hash functions they take just one input if you use like multiple inputs you must provide a way uh to have fun to distinguish between like one long input and concatenation of two of different inputs so like just just different inputs so there must be some objective a function that does this kind of packing of inputs

and finally one nice thing is about uh what if the hash function works works in one domain and you wanted to Output your number in another domain so to this side the vote uh kind of there is very simple set of rules actually what happens if you output from zp and you need elements of zinc queue while p and Q don't have to be primes here they're just different sometimes it's enough to to take a model or sometimes it's not enough techy models sometimes you have to concatenate the inputs and sometimes not but there are actually very simple rules and they depend on how p and Q relate to each other so you can go to our hack MD and check how how it's done

um there is another misuse that is nowadays popular that when you use a sponge function sometimes you work with the so-called capacity part until you initialize it with simple constants and the thing is you doesn't you should not initialize them with simple constants because it's possible they Collide for different use cases and you can't really make security proof out of it so the safe API that Michaela has just recently covered a little bit provides this kind of protection uh yes so while we have talked already about safe API in the previous calls in the previous uh talks so I will not uh

concentrate about this too much but the idea is that basically you can have all the applications of a hash function inside one library that does all this domain separation paid in concoding decoding and so on field conversions in out of the box Okay so please encrypt decrypt and hash safely this is the way [Applause] thank you very much Dmitry we do have time for maybe one or two questions so raise your hand if you have any okay

actually I have two but I'll just choose one then you talk about ACM GC as GCM and what was the issue with SIV I mean you said can you repeat the issue that you mentioned with a esiv mode over version ah well I said that there's a GCM Sif mode that basically it's SIV stands for synthetic IV so it generates this IV but it's generous it's using the message the data itself that's to be encrypted so it doesn't use internal Randomness and doesn't work with the nons uh this interview uses the nonce and the message is so the problem is usually if

you reuse the nonce then you know you know you have encrypted twice the same message yes but um if you choose a different nonsense every time it's fine actually well if you additionally use the nonce then yes but if you already have a nonce you don't have to use SIV you can you can use just regular GCM this is more about the case when you don't have a nonce but you you have some way to guarantee that messages are unique okay then that is okay so let's give the second question I'll ask you offline okay okay the last one because you raise your hand very quickly and then we'll be done so you talked about different bugs in uh for encryption but you haven't talked

about padding at all which is quite important because it's been teles poodle there's been uh attack well one million uh safer attack so I'm not really sure if there's any new recommendations about padding yes so actually our basic recommendation about padding in particular when you are in ZK is to use Sage API because uh it it cares of the patent in a simple way basically we cover all the use cases when the length is known at runtime and when the link is known at runtime simply kind of what we do informally we just hash it

into uh uh the capacity part of the sponge and this makes uh the state dependent on the length so you just can't uh use it with different lengths it it doesn't decrypt and different message of different lengths produce two different outputs if you encrypt produce different encryptions so basically when you know it at run time and when you basically or in terms of a cipher the IV depends on the length we just hash it into and this takes care of this attacks we think is actually simpler than to introduce

special padding schemes because they are all fairly complicated yes you talked a lot about sponge so what's your opinion on it's quite old and maybe you will say that we should never use it never use it but on the use of compression function and Michael vanguards it was really popular eight years ago something like this well yes because well many modern hash functions even like Blake it uses some sort of a miracle down guard so there are some precautions you make there to prevent all this length extension problems and so on but by certain use of

counter you can work with it just well it's good for kind of incremental hashing but it's not that nice when you use different hash functions in your protocol in many contexts like here is a hash function for commitments here's has function for hash function here's a hash function for encryption and so on so and here like earlier boards when you do fear chamir so we think that the sponge interface and based on that the safe API provides you actually the better it's it sounds but more flexible and less error prone than when you use Miracle dumper but you can plug the Merkel Dam guard hashes

into the safe API so Michaela has this code that does that there are some other construction that do that so you do yeah okay so if you have old hash functions it's still possible to use them in the new API so there there is compatibility there thank you perfect thank you very much guys now it's time for a break so we'll be back here with the next speaker at noon so yeah see you there thanks Dmitry