ZK7: Analysing the Frost Threshold Signature - Mary Maller - Ethereum Foundation

Transcript

[Music] now i would like to introduce the speaker on this stage shh guys shh guys guys guys we're starting okay i want to start i want to introduce the speaker on this stage mary mahler from the ethereum foundation who will be talking about analyzing the frost threshold signature welcome to the stage mary sorry hi everyone can you hear me okay

yep okay so today i'm going to be talking about a joint work with elizabeth kreitz myself and chelsea commonly and the title is about threshold signature schemes doesn't sound very zero knowledge but actually i would say that there is one thing that threshold signature schemes have very much in common with zero knowledge schemes and that's that the security proofs behind them they really matter so if we want to have a zero knowledge proving scheme and where they're like okay we have it in theory we have this paper but actually we would like to run it in practice um there are many steps you have to go through to do this and it's quite difficult and i would say as a community

we're still learning the best practices to do this there are some techniques which we use and which to some degree work that we have tried in other projects for example easycrypt is a big one this is a way of formally verifying whether your proof is correct or not and people have done this for tls but it's very complicated it's not easy to do this with more complicated protocols security audits are also a big big part of this so this isn't just are we going to run a security proof over the actual protocol the implementation although that obviously is really important as well but the actual security proof are we going to check the security proof doesn't have a missing minus sign that makes the whole thing

wrong standardization's efforts for this i want to sort of mention that there is a standardization effort for zero knowledge proofs it's called the zero knowledge standards effort and it can be found at zkproofs.org peer review is possibly a least effective method i would say waiting a while is quite a good method though and having different people come up with independent proofs for the same scheme is another tool which is very effective so one um snark which is being run in

practice a lot at the moment is a grout 16 snark this is a scheme that said cache is currently using amongst other projects and this has been a three peer review um there has been an audit in the sense that i have run through the security proof and checked for myself that i agree with the security proof uh it was 2016 when it first came out it's 2022 now so seven years um but we don't have any sort of formal checks in the sense of we haven't checked the proof with any kind of computer model so

probably not a surprise to many of you threshold signature schemes also have very fun security proofs so a threshold signature is basically you want to generate a signature but you don't just want to have one person generate it but say five or ten people generate it and there was a fairly big shock i would say to the community quite recently in the form of an attack this attack won best paper award at eurocrypt it's called on the insecurity of ros and basically this is a concurrency attack so if you have it so that multiple signatures are being generated at the same time then if you just try and do a threshold

snore signature in the obvious way you'll end up with something where people can take advantage of the different iterations of the protocol to run an ros attack in order to break the soundness of the scheme so they can generate signatures without knowing the secret key some of the papers that were vulnerable to this attack had been peer reviewed had been around for a long long time and they did have some independent proofs as well one thing i want to sort of make really clear here is when we say there are rrs attacks we don't just mean theoretically you could run

these are very scary so i actually implemented one of the attacks against the original music scheme and this was just python code written by myself i'm not an expert hacker and in less than 100 lines of code and in about 4.6 seconds including the time to simulate the signer i was able to generate a forgery so if you imagine what this would be like on actual good hardware with good code so these multi-signature schemes had

incorrect security proofs there were also some threshold signature schemes with a very similar structure which were also vulnerable but actually they never proved concurrent security they only ever claimed to have security in the singles session setting the problem with the security proofs basically related uh boils down to how people were instantiating something called the one more discrete log assumption so the discrete log assumption just says given some group element i can't extract the discrete log one more discrete log is kind of an extension of that it says given five discrete log challenges if i'm allowed

to query to get four responses i'm not able to compute the fifth response for myself so the way that these proofs were being run they were supposed to be saying okay with four queries i can't extract five logarithms but actually they were querying for the oracle five times so this is then not a hard problem if you query an oracle five times to get five discrete logs you can do that so in an effort to try and move on from this to try and get signature schemes which are concurrently

secure a fairly recent proposal is called music two and this is a two-round signature scheme for chanel signatures channel signatures i should mention are more difficult than bls signatures with bls signatures we can do it in one round but the advantage of this scheme is it is compatible with anything that uses chanel which for example includes bitcoin [Music] also one nice thing about it is that the signing does take two rounds but the first round can be pre-computed before everyone's agreed on the message so you can kind of simulate one round worth of signing with enough pre-computation

frost is a very similar idea the scheme is almost identical except that this is now trying to run a threshold scheme rather than a multi-signature so in a threshold you would want it to be that maybe five people have secrets but you only need three people to sign the signing also takes two rounds the first round can also be pre-computed like i say it's using pretty much the same structure and one of the big applications of this scheme is it allows users to store backup keys for their cryptocurrency without giving up complete control so there's a lot of interest from certainly wallets and things in this

scheme for this reason there is currently an ongoing standardization effort in the form of a cfrg draft this doesn't include the dkg this which is the method by which you try and generate the public key this only includes signing itself but if you have a trusted person such as the owner of their cryptocurrency to generate the key shares at the start then you would be able to run this standardized well it's not standardized yet but standardized if it gets standardized protocol one thing that the original frost paper

did not have is it didn't have a security proof that didn't rely on heuristic assumptions so heuristic assumption is something which you just like assume to be true without necessarily having a good reason for assuming it to be true so we were looking to try and generate a security proof that didn't do this and our primary concern with the security proof was simplicity we really wanted it to be quite boring and mechanical i mean whether it actually is boring and mechanical i can't say but that was our our aim and to prove the security we really

split it up into two separate proofs i would say so we modularized it in one of the proofs we were trying to simulate the honest interactions with the adversary so if you're trying to simulate what's happening inside a threshold signature scheme there are lots of moving parts you really genuinely care what say user 5 is doing at the same time as what user 3 is doing and how they're interacting and the different ways in which they might talk to each other the other side of it is trying to actually extract a solution to some hard problem from the adversary's responses and this side of things is

also fairly intricate and you really don't want to be worrying about the different user interactions at the same time as extracting that solution so what we did is we just split them up and we have the part where we're trying to extract a hard problem from the adversary and a scheme specific assumption which we then prove and we also have how we're doing the different interactions in the second part of the proof usually introducing a scheme specific assumption is something which cryptographers would frown upon but i would sort of state that we're not really introducing a scheme specific

assumption we are ultimately reducing down to the one more discrete logarithm assumption our assumption we have called the baishnor assumption we're not proud of this name we are open to suggestions um is a the way it works is that we have two oracles which an adversary can interact with the first oracle is just going to return a couple of nonces ideally we would like it to be such that the first oracle is just returning one nonce but that kind of assumption would not be secure there would be an ros attack so we have to go with two

nonces the second oracle is where all of the interesting stuff happens and here the adversary is just going to send a message and it's then going to get back signature on that message which is going to incorporate the two messages from the first oracle in a fun way and there's lots of simplifications going on here i'm just trying to try to get the high level so our biggest concern with this budgenar assumption was in the security proof we really really wanted to be sure that we had counted the correct number of one more discrete log queries because this is the place where previous

security proofs had not counted them correctly trying to count them correctly by hand you have to have a lot of trust in yourself you really have to be sure that you haven't missed one so rather than do that we decided to actually implement the security reduction in python it's simple code this is not equivalent to having a full-on formally verified protocol it is just trying to catch for simple stuff such as have i counted the one the correct number of oracle queries but i actually think that this is

something which is very powerful and something that we should be strongly considering doing in other schemes especially zero knowledge schemes which we are wanting to move to practice so the first thing we did is just count the number of queries and make sure that it didn't exceed we also checked that the extracted solution is correct this again is something which can be quite tricky to check by hand and we also checked that the simulated signatures actually do verify so this doesn't necessarily mean that they're well formed but it's a good indicator that they're well formed for the second part of the proof for

trying to then relate the threshold signature scheme to the bishop assumption our first thought was was that it would be really nice to separate the dkg from the threshold signing process in order to have those two reductions be separate this didn't work this didn't work specifically because the random oracle might be queried in the second reduction and the first reduction and those if those two reductions don't talk to each other then how do you know that the adversary isn't taking advantage of that so we had to do them both together however i would say that the assumptions that we're using for the two different

parts of this proof are different so for proving the dkg which is the pedestal dkg which is a very standard standard scheme to use we had to use something which we call the general extractor assumption which i'm going to talk about a little bit more in a second but for the actual threshold signing process and the part which is being standardized this is something where we were able to relate it down to the bishop assumption which reduces down to one more discrete log directly the schneider extractor assumption is totally avoidable we know of a million different ways to avoid it

but it would require an additional round the reason it requires an additional round is because schnoor proofs the reduction if you don't rely on the algebraic group model is not tight and this is a really sort of annoying thing because there is no practical problem here there is no attack there's not been an attack in 20 years i'm pretty sure that if somebody is able to break the um proof of knowledge by taking advantage of the fact that it's not tight this would be a big big breakthrough but for some reason cryptographers

really don't like using something which isn't tight despite the fact we have models for it we have the algebraic group model we have um well the generic group model but the algebraic group model is a little bit better than that and as someone who comes from like a snark background this caught me by surprise because obviously we're using the algebraic group model all over the place and these assumptions are much much nicer than that they are just schnoor signatures so when it comes to am i going to add an extra round am i maybe going to use official improve to avoid this am i going to

find a workaround i really think we shouldn't i intentionally just intentionally decided not to i think that kind of thing is far more likely to actually lead to a break actually lead to someone taking advantage of the scheme than just using schnoorproofs and assuming that it's fine so if people come along later and maybe decide they want to do it differently then obviously that's fine but i'm not going to do that however if you are uncomfortable with it then i would say if you don't need a trusted dealer or if you want to use a different

dkg then we can reduce down to one more discrete logarithm directly we also implemented the um the scheme for trying to reduce down from the threshold signature scheme to the bishop assumption in order to again check for some basic bugs and in the process we did find some hazards some things to watch out for almost all of them are relate to when you're selecting the group nonce the biggest one is you absolutely must hash the identities of all of the signers who are taking part in signing so this means that if you want to sort

of say we can simplify it by just assuming two signers you can't you must consider all of the different signs this is different from music too by the way music too you can but for threshold signatures you can't do that you must also hash all of the nonces and you must check that all of the nonces are identical although that last point i should say is due to the fact that we're using the same exponent on all of the second nonces so in the original thrust you wouldn't have had to do that which leads me to my second point which is when doing this analysis rather than finding that we were making the scheme you know less efficient or

adding overhead or making it worse in some way actually it was the opposite we found a way to make it simpler we found a way to reduce the reducer computation just a little bit um which is quite nice it doesn't always go like that when testing the dkg reduction there were again very basic checks that we were looking out for we wanted to know that the adversary's output actually verified this is something that with python you can check

we wanted to check that the simulated dkg responses are correct and again we just checked it we just asked python is it correct print print and tell me if it's not we wanted to know whether the adversary and the simulator were actually working with the same public and secret keys at the end of the dkg we checked this and then when it came to the signing we wanted to check that the simulated signatures verify for a variety of different honest parties remember how i mentioned that you can't just assume two parties you have to generalize we checked with lots of different versions depending on whether the dishonest party goes last or first or in the middle or

controls two people or three people we checked a bunch of different permutations there and we also checked that the combined simulated signature actually does verify so this pretty much finishes my talk minus questions uh the general takeaways i want people to go away with is there is an effort to turn the frost threshold signature scheme into what i would call a battle-tested cryptographic protocol computers are better than humans that checking for simple bugs we should use them and in the snark world this is something that people are considering but there are some challenges

mostly relating to the algebraic group model here you actually have to extract a witness and then check that the extracted witness is correct and there probably are ways to do that but it's not obvious to me what that would look like at this point in time thank you very much nice all right we have a question right here hello nice talk thank you have you considered using the the uc framework to prove concurrent security yes and it's hard um thanks for the talk i was wondering

um when you had the by schneider assumption you have this you have the oracle for like the two nonces that you get how realistic is that and why wouldn't you get like one nonce because you mentioned that would be problematic right just having one nonce from that oracle so you have to essentially enforce it when you're running the threshold scheme later you have to make it so that every single party when they're interacting to decide on the first nonce of the signature they actually give you two nonces and these nonces are always paired and you always work with them together but yes if you were to not do that then the chances of there being an rss attack i would say is through the roof

any other questions all right well if that's the case then thank you so much for the talk mary thank you [Applause]