ZK11: Common Pitfalls & Optimization for Modern Cryptographic Protocol Implementations - S. Agrawal

Transcript

[Music] hello everyone I am sh and today I'll present common pitfalls and optimizations for modern cryptographic protocol implementations just a disclaimer I'm not a cryptographer I am just a crypto Enthusiast who has been working with a bunch of cryptographers and blockchain scientists to audit cryptographic protocol implementations and this talk is sort of a rant on how you know space is moving and exploding and building so much cryptographic new New cryptographic Primitives with so much added complexity but our Engineers are still very slowly picking up and maybe they don't even talk the same language and things which

are obvious to one side is not so obvious to other so most of the things that I'm going to present is going to be much more intuitive and simple than what you guys have probably uh you know heard during the day let's go on so first I'm going to present to sort of pitfalls um so first is uh let's say Prime Fields right these are very nice um algebraic objects uh we use it a lot in cryptography and I mean intuitively these are very simple like similar to just having a integer but then it just wraps around once it reaches reaches the order so let's just build a simple implementation to just warm up right you

have a FP a prime field with order P which is let's say it's a 128bit uh order and then for now we have addition and subtraction and you know it's very simple we just add and then do a module of p and similar for subtraction as well the only thing is it might overflow right so you need to make sure that you typ cast it to a bigger type so that it doesn't overflow then do a module op and then you can get it back to your original type and for the subtraction you can have negative values but uh in a prime field it wraps around so you you can just do a p+ so that you can get the negative values uh you can use just the uint value to also

represent the negative values so this is quite simple and you know if you would find some definition somewhere this is probably how it's going to be written but then let's let's put some more engineering functions to this implementation right some things that you know probably a cryptographer would not mention it on his paper right so we we put let's say serialize in caliz so you have we want to we want to use a bite 16 for calization and distalization so calization is simply you know you take your FP and as as it is you can give your bite 16 but then let's have a derealize and for deiz I mean so for all the operations we are just doing mod P so we get the bytes we check we convert

it into u18 and then we do a mod P like everything else very intuitive and now we've built a big protocol and we've raised a lot of money we want to do an airdrop so we build a protocol where we have uh you know a claim function and we will use our FP implementation uh it's very simple we have a nullifier you can pass your field element and this checks if this you know the air drop corresponding to this field element has been claimed or not if it it's is not it throws an error otherwise it decentralizes using a desized function does some operations and you know gives you the money the developer was very happy he thought that he built something cool what's the catch

here anybody do you exactly so uh as you said if you look carefully right the wrapping around and this derealization is a problem because what's happening is essentially there are some numbers which are um bigger than p uh but on once you do the mod operation it wraps around so there are some small numbers which have two different

representations in you and 128 right U this is exactly a I think there's multiple ways to fix it uh one of the possible ways is to just fix distalization so only allow for canonical uh like canonical representation which is you have one to one mapping uh if you do it this way then you can make sure that you know higher level protocols don't have to think about it right uh the fix is very easy you check if the number that you got is actually lower than the order otherwise you throw an error okay now this is another similar problem but it's a little bit more tricky so you want to do you know

uniform Randomness and you again do the same thing right you just sample 128 bits and then you just do a mod P now this is biased right because again you have the wraparound problem and this is the fix for it so you can just um sample until unless you get a number which is lower than your order and then you can use that so generally the you know the first sort of fit fall that you know I would like to conclude on is for serialization and der serialization we need unique representation and this is kind of operation that sort of a cryptographer would not mention clearly on his paper he would just say okay this is sent over

the network but then an engineer has to implement it out where you know you can have these kind of mistakes uh this leads to the second Pitfall that I want to discuss Frozen Heart the death of Fiat sh meristics by the way the death of fistic was not said by uh Jim Miller I just uh you know added it to make it sound a little bit dramatic as if it's a movie uh whatever um uh there was a talk by open Zeppelin this morning on a similar issue fat Shamir I mean the problem with Fiat Shamir has been known since since 2012 uh when you know there was clear discussions on weak and strong Fiat Shamir but we are still in 2024 10 years after that fact and we still see

implementations doing wrong so I think people are still missing the intuitive understanding of where you know this protocol lacks okay so I'm going to try to build a little bit of intuitive understanding here and I'm going to use uh some nice Graphics by the uh by the trail of bit steam so you have let's say A prer and A verifier right and the pr wants um the the uh yeah the verifier wants to know if the prover is a good tennis player right and the pro wants to convince the verifier if it's a good tennis player so what the they they do a game right so they play a game where the pr plays against the verifier and every round the

verifier tries to give the most difficult shot it can right and after a few rounds if if the pr can actually play against the verifier he can be convinced that you know he's doing a good job and the verifier is convinced that the pr is a good player okay but then you know prer doesn't want to sweat right so he doesn't want to get out of his house he just want to let's say know if the prer is a good player or not so he is fine watching a stream of the prer playing so he can say tell the prer to play against the wall right and he keeps playing against the wall and as long as you know wall somehow magically you know is returning right or is returning random moves to the prer after some rounds even if the verifier just saw like a video of the prer playing he can

be convinced that you know he's playing a reasonable game in our let's come back to the cryptography world you know for us you know we have prer which is so exactly this is what Fiat shami does so you have most of the um sorry oops oops Yeah so most of the uh cryptographic protocols um the most of the zero knowledge U most of the zero knowledge protocols or even snarks they are originally Interactive and then you apply this Fiat Shere her istics to transform them from interactive to non-interactive and the way you do it

and the wall here is our hash function AK random Oracle I mean there's question of if it's actually random or not but even if it is you know the issue comes so again coming back to the tennis analogy if for some some way the prer knew a particular angle where he could throw the ball and get the ball back in the same angle or in same velocity he could just game the system while by like doing the same move again and again and similarly in in in case of Fiat Shamir if you can somehow figure out uh you can bias what the output is you could uh you know break the system so I'm going to give a concrete example here so the

easiest protocol to explain this is the snores protocol which is let's say you just want to prove the knowledge of X for uh so y = to g^ X so you just want to prove the knowledge of an exponent and here you can just say Y is your public key and X is your private key um the snores protocol is quite simple you can uh basically the the interactive version is you ask the verifier to give you a random value and then the prover itself generates a random value a um and sends bals g^ a and after that the verifier replies with that random value C the Prov then sends zal to a plus CX and then the verifier can check on its local

most of you guys are probably familiar with this now we can convert this into non-interactive version and we can do this by let's say incorrect transformation first which is you know does the the step where the prover uh waits for the verifier for the random value he can just generate it locally by using this random Oracle so just ask the random Oracle here is my b so the with the B and it's uh for now it's just a hash function you get the random value C okay but then uh because somehow your public key is not really linked to the uh random

Oracle output you can compute um a public key after the fact that you have this random Oracle output even though you don't know the exponent or the private key to that public key and you can do that as follows just just pick a random B generate a c for that using hashing and then you can compute y = to g^ z/ B to the^ 1/ C you can do the math works out and then in the end the ver if you send that to the verifier verifier can check and be convinced of this um this is similar to you know how when you write the uh zero knowledge property of the schnor protocol uh when you generate a

transcript this is exactly what you use to uh prove it just to fix that the correct transformation here would be that the hash should be should include both y g and B so the public key the generator and the B so this will make it a strong fat Shir instead of weak so this brings us to the rule of thumb this is the most important part here here so essentially the Fiat sh meristic the Oracle should include all the public values and not only that it should also include all the intermediate values generated so all the commitments that are generated during the interactive process should also be

included in the fat trir uh for every nth round okay so now we've done some pitfalls and now we'll go towards um you know from ranting to actually optimizing things and you know seeing how we can use engineering to optimize uh yeah the cryptography so we have this threshold trick that comes again and again in several protocols uh including Shamir secret sharing dkg read solman coding where you know you have M parties and any n of them can come together and then recover some information or some secret and just to give a primer how this works it's quite intuitive and very nice um you

essentially want to encode your information in a n degree polinomial so your coefficients is your secret or just uh information and then you distribute you sample M points from this polinomial and as long as any n parties come together they can interpolate the polinomial and recover the secret and this is a very elegant trick that is used in several places so the steps are first you have to generate this polinomial with which has the coefficients as your information that you want to encode then you want to sample let's say consecutive points that you want to distribute to the people and then you know these people can come

together and do some interpolation okay so the usual implementation you know of let's say evaluating these polinomial to generate these shares use horns method and I mean this we have probably learned in our algorithms class if you want to do a polinomial evaluation using horns method you can get from n Square multiplication to just n multiplication and N addition it is quite easy but to generate M shares right you need n time M's multiplication and n * m additions so if you think about a blockchain system this m can scale right as the number of nodes are growing the number of shares you want to sample will also grow so can we make this better can we somehow uh you

know remove this quadratic factor from m n * m essentially so I'm going to explain uh an approach which I've not really seen before in cryptography uh the finite difference method and the idea is we we will use the finite differences to calculate the next consecutive evaluations without paying for multiplications so it works as follows let's say we create a simple table and for the first n uh evaluation we just use a horns method so we use the horns method to evaluate the first five indexes and now we want to start uh we want to figure out what's the sixth index without paying for multiplication so first we calculate the

finite differences and the finite differences essentially the for let's say if you take uh D1 so D1 uh the d11 is essentially the sorry yeah d11 is essentially the FJ ff2 minus f one which is one so essentially it's the difference between the the the two entries of the column in the left and you can keep doing that uh until you get this it's just subtractions which is equivalent to doing additions and then once you build this table what you can do is you know that we we can observe that the finite

difference of the nth will be a constant and the n+ one will be just zero uh this is similar to derivative right so if you take the nth derivative it's a constant and the N plus one derivative is just zero and once you have built this table what you can do is you can use this to calculate the next entry by just adding the consecutive values so now we we start doing it from right to left um so for d42 it's essentially summing up 0 and -19 getting -19 and then for d33 it's essentially - 19 - 3 uh giving us -22 and so on and now if you keep doing

that you get the sixth value and this is just doing additions right so now we no more paying for multiplications and you can keep evaluating this for M entries so now somehow you have moved away now the complexity is moved away from n * m multiplication to just n Square multiplication and n * m addition um this was a trick I saw in a compiler's class uh for removing invariance and somehow it applies here as well okay so this brings to the uh last optimization that I want to talk about um we all know that the native operations are very fast in computers so like if you want to do a native

multiplication or an addition it's very fast but then whenever you want to do a virtual operation like a group operation or some other cryptographic object operation is slow or in terms of circuits you can think that when you perform an operation in the native field it's very fast but then if you perform an operation in a in a bigger uh sub field it's it can be much slower so how can we optimize that and to do that a very sort of intuitive trick is to just use the native operations whenever you can and only fall back to non-native operations when really it's needed and for that I'll just show an example of um how you could do do it for lrange interpolation so in

lrange interpolation again you need n consecutive multiplication and the native multiplication is 20x faster than a blsd scalar multiplication so here is a uh implementation and essentially the idea is you have you have the values as u in 2028 and you can multiply them uh if if you you check if you can multiply them in the u28 if it doesn't overflow and if you can then you simply multiply it but if it overflows then you convert it into scalar and then multiply it in the scalar field so you instead of doing a normal multiplication here in

the reduce you have two different accumulators one is the scaler part of it which is actual value and then there's the remaining one which is still in U 128 so every time you have a value you check if it's uh overflows and if it doesn't you multiply it and in the end what you get is the remaining the scaler and then you can multiply the scaler or you can multiply the remaining convert it into scaler and multiply it with the accumulator so this essentially yeah speeds up the concrete implementation um I would like to credit uh miston Labs because a lot of work we you know I presented here was inspired from audits that we did for miston labs

and also uh the frozen heart pictures and also the discovery was done my trail of bits so I would like to credit them and in the end I would like to leave you guys with this note on translational cryptography that you know the space is growing quite a lot and we need more people that can understand more Engineers that can understand cryptography and more cryptographers can which can understand engineers and we need to build more documentations not just white papers where we explain in details what checks and what constraints have to be built to build these systems in production um yeah I'm happy to talk more about this and discuss if you guys

have interesting yeah findings and optimizations yeah thank you [Applause] any questions from anyone yeah up there okay um the one that you said the randomness is biased the like I I saw in ed25519 paper that say if you have 61 bit extra then

is okay yes that is another there's another fix you could do that you could take enough bits and then it uh yeah it's it's not a problem so this one it's a problem because we're just sampling 128 bits but if you take sufficiently more bits that's again uh is not a problem it's another way of fixing it yes can can you give a f Cham failure example that you Amit public values and it fails like if if if like the point and the care both the verifier and prover knows which point is it I I didn't understand your question can you you you you said that the fat Shamir needs all the intermediate steps plus the public values right right yes

um but if the verifier and the approver they agree like if the public value doesn't change and everybody knows them I see H I'm not sure maybe it works out okay