CG - Have You Distributed Randomness? - Yolan Romailler

all right good afternoon welcome to common ground the next talk that we have is called have you distributed randomness by Yellin roll my a before we begin we'd like to thank our sponsors especially our inner circle sponsors critical stack and Valley Mail and our stellar sponsors Amazon the National Security Agency and secure code warrior is with their support along with our other sponsors donors and volunteers that make this event possible these talks are being streamed live and as a courtesy courtesy to our speakers and audience we ask that you check to make sure your cell phones are set to silent and we will do questions at the end and if you have a question I I will

bring the audience microphone which I am holding over if you raise your hand and this is so you tube can hear you and with that let's get started welcome Yulin thank you so hello everybody so today I'll be talking about distributed randomness so written one maybe so I'm Alan from koloski security in Switzerland not to be mixed with Sweden and it's not the same country at all we got chocolate and as I got a key anyway I'm mostly a cryptographer so I'm doing cryptography on the daily basis at kudos key security working and code audits and other fan cryptography things sometimes block trains but anyway also I like to play CTF I saw there was a nice CTF next

door but couldn't try it today anyway so today I thought it was a 20-minute talks so since it's instead one hour I will just say everything three times so you will really get everything right so I'll briefly cover the idea of distributed randomness and then I will discuss D run which is a software implementing the concept we'll cover first and at the end there won't be any question since I will set everything three times right so let's run them nests I don't know if it's something you have yourself sometimes but as a cryptographer when we say randomness usually we mean binary strings and it's actually equivalent to saying random numbers because you can cast a binary string to a number and

vice versa so anyway so I've pulled a couple random strings and just lied so do they look really random to you well not really right but that's the thing with randomness any string of a given length is as probable as any other string of the same length so you cannot really know if I draw those at random or not what might be you know a bit telling here is that they look really like easy to compress and they're called makarov complexity is not so high I mean the entropy of the strengths doesn't looks high so it's probably not random right anyway so what do we do we randomness and good questions so we do a lot of

cryptography actually a lot of protocols be signature scheme encryption diffie-hellman TLS everything is using random numbers usually in cryptography but inside cryptography we also need randomness for other purposes such as you know batteries election if you want to choose at random somebody and yeah computer games because you don't want the same monster to spawn at the same place every time you play the game right next is the idea of distributed and variable randomness so what is it exactly what do I mean so I will just take an example for a shared randomness or distributed randomness so if you take the Tor network actually if you want to hide the hidden services correctly you don't want people to be able to do

popularity attacks again them and so on what's happening in tor is that they generate a new you every day and it's relying on that shirt random value for the world network to hide the services as they want and another couple examples from the blockchain space because blockchain is usually you know distributed and so distributed randomness obviously means more to them if you want to do shorting so you take a lot of nodes or master nodes whatsoever and you want to select the one that will maybe mine the next block for example what happens in some crypto currencies or blockchain technologies is that you sharp the network into shards and you want to do it at random so that you're sure there

is no you no malice shooter or whatsoever and you need to do it in a distributed way on the network so that everybody agrees with what had what's happening other example could be smirkin factories but anyway what's variable randomness so it's a random value that you can check has been randomly selected so why is it important I don't know if you know about the NIST do you see your GB problem it was a elliptic curve parameter selection which was biased somehow and random parameters were not that random so it allowed them to a some nice attack and in that case if we had been able to verify the random values had been generated really at random we

would have been able to travel interesting so people sometimes just take you know the ash of zero the ash of one the ash of two and so on until they find a random value or at least a value that looks random so that it works for their purpose but so it's an example of who you could generate - you know I use but anyway random variable random function that I ETF draft so you can check it out it's cool and we'll be discussing a bit more about later

so as we can see there is a need for random values there is a need for a distributed and variable randomness so there is probably also a need for a randomness beacon that will you know provide you with random values that are distributed or generated by a distributed network and that are variable so you can track them in a public way and what do we want is a randomness beacons to do is well basically be unpredictable bias resistant variable decentralized so that no single entity could you know my ass the values and available so that whenever you need randomness you could you know ping one of the randomness beacons and I would give you some random

value that hold those that has these properties and there were randomness beacon back in 2011 I think NIST released its very own randomness beacon and the results of this website random.org which is providing random values publicly but problem with those sites and services were you had to trust a single third-party bit NIST or random.org or whatsoever and it's maybe something you don't really want to do you know like nobody well not everybody like NIST so the idea we'll be discussing today is dear and it's a software which is implementing all those nice properties we've seen in a way that allows you to run a network of random beacons that provide all those nice features so durand is an open

source software which is nice and its goal is primarily to provide public randomness it can also provide private randomness but then you need to trust beacon you are asking your aquarium but it's a detail so what the main goal of Iran was really to make it so that fetching a random value that's very few able has been generated in a distributed way by multiple parties and so on it as easy as fetching time on an NTP server and that's really the goal of the year and becomes so a bit of history maybe so everything as I said started in well that everything that in 2011 NIST sorted a random beacon and there was not much happening between

2011 and 2015 when ever Sita researcher together with the deadest team at EPFL so EPFL is the engineering school of Lausanne in Switzerland started working on scalable bias resistant distributed randomness which gave a paper published in 2017 so next in 2017 what happened is that the same team of researchers started working with the Definity blockchain team and it's a really important point here they integrated the pairing library which had been developed by Definity into the teddies cairo liberal and next in September of the same year Nicola guy was the creator of Duran the main programmer in developer who was at the time a PhD student at EPFL started started coding around the software using the tiber libera which is

just a liberal way of cryptographic primitives meant to ease process of implementing cryptographic protocols so in 2018 we there was a nice blockchain summer school at EPFL a lot of people came here and we met with many other people there and we decided to know tmap and ran randomness beacon network together with a cloud phlearn east EPFL protocol labs a couple other people University of Chile also and so on and in June of 2019 to around yeah I think it was one year after the summer school we finally published and released Iran and launched the league of entropy which I'll cover at the end of my talk so Iran and its network is currently running so

I will deep dive a bit into the theory behind Iran so what does do how does it work why does it work so it's mostly based on the paper I mentioned earlier but it's always taking the simpler path whenever it can so in the paper a lot of different techniques or discussed and urine really tries to make things as easy as possible so you run as a couple building blocks which I'll cover so I won't be covering all of these but it's just you know so I can this case cryptography because I like it and also so you get an idea of what's going on so I will be discussing today for first points so that's variable secret sharing

the Pattersons distributed key generation I will cover really quickly pairing based cryptography especially the pls signature scheme and oh it enables you to do threshold signing and then D run also features reshoring and it it's using SES so elliptic curve integrated encryption scheme to provide private randomness if you want to use that feature but it's not really the main purpose of Iran so I won't be covering private randomness today so secret sharing I don't know if you've ever heard about it or not I will try to cover it fairly simply I know it's a wall of text but it's just so that you can read it at home if you want to come back to it so secret sharing the base

idea is really that you just need to point on a plan to define a give a line uniquely and if you got three points its defining a parabola you got four points its defining a cubed and so on and that's a really nice feature of polynomials and the idea behind secret sharing is that you've got a secret you want to share into multiple shares between shareholders and you want you what you really want is that it requires at least members of a group of n people so that they can reconstruct the secret actually it's not people it's chairs so you need you want to be able to basically say okay we are five people five shareholders we were splitting the

secret into five shares so that at least three shares are required to build to reconstruct the secret we are sharing and it's really it's a really nice idea I got a little picture on the next slide to explain it a bit more and there are a couple caches so the dealer has to be trusted because the dealer which will be providing the shares to each member of the group has to know the secret so it can construct the polynomials he needs to construct it out in order to do the secret sharing and also if the dealer is managed to use that could lead to problems so there is another kind of secret sharing scheme which are called

VSS so variable secret sharing which are basically enabling the user holders to verify the shares if you generated in a way and that's non money shoes and not really so oh that is really work secret sharing so the laser pointer is not working so I will just move around so you got four points here which are uniquely defining the dashed curve and the secret you want to share between every shareholders is basically the value of the curve at the point 0 so that curve is a polynomial and these points here are the share that each shareholder owed so the blue one is the point a given member faulds and so on for the other points and whenever you

want to reconstruct the wall secrets so find the value of the polynomial F at point 0 F of 0 what you need is just basically the value of each points and then you do a Lagrange interpolation which is giving you those nice polynomials which cancel out in each points of the other values but that detail and out of those polynomials you can interpolate the main dashed line and find again the value of the polynomials and then evaluate it in zero to find the actual secret so that's roughly the idea so what can we do with secret sharing a good question right so we can do a lot of things like share a secret between multiple members or make it so that

nobody no single entity is able to sign a given file using the main key or whatsoever but one of the nice thing we can do is a distributed key generation so this repeated key generation is a way to trash all the eyes so basically to make it so that when you want to do digital signature or a symmetric actual encryption or whatsoever the threats you are using to do operation you want to do is shared between multiple members and you only need a subset of the members to be able to reconstruct the actual strat and how does it work well German is using the Paterson distributed generation which is based on the variable secret sharing

scheme we've seen before and the idea here is really that you will be running your people secret sharing stream in parallel so that's a slide from Nicola guy at EPFL I've stolen it which is explaining really well oh it works distributed generation so what's happening is basically that each member of the group can generate can be a dealer of the secret sharing scheme and so each member has a chance of being malicious or not but we expect in the threat model that there are no more than half of the members of the team which formal issues and everybody is generating is doing the secret sharing and everybody is receiving ensures ok well what you can do then is just

basically some points you got from everybody and through another library interpolation you will get a new polynomial and nobody will know and its own the value of the secret because the secret is always a value of the first coefficient of the polynomial because if you take f1 of X evaluated at 0 the X will cancel out all the other elements are coefficients except for the first ones secret so each node has generated the secrets and then at the end you some everything together basically by because each member will sum its own share and what's happening is that the final secret is unknown nobody knows what it is but we are able to reconstruct that secret when we work together using

Lagrange interpolation to reconstruct the actual we need and that's really awesome because it means we have a way to create a key that nobody will know but that we can use together so how do we use that key good question right so we use it using pairing based cryptography so I need to explain a little bit what's appearing first so pairing based cryptography is quite new and it's really nice because it's working with pairings so what's the pairing so a pairing is a matter that is mapping to elements of the group's G 1 and G 2 which are additive groups unto another group GT which is a multiplicative group and it's mapping those elements in a way

that is similar to a linear function so accept a pairing as 2 input so it's reality that we want so what does it mean billionaire Ricci it basically means that whenever you have the function of the pairing of two elements P and Q if you multiply any of the two elements with a given value the end result will also be multiplied linearly but by the same value and if you multiply both by use both input value at the same time the output value will be multiplied by both and there is just a trick since we're working on a multiplicative group we need to use exponential notation anyway so the pairing also needs to be none

deteriorated it just mean it must not map everything to one because otherwise it's kind of useless right and for practical purposes we want appearing to be efficiently computed by computer so that you can actually use it in practice so pairings are really nice piece and there are usually constructed by researchers in universities so we won't be generating new ones or whatsoever we just use what's existing and when do we use pairings well we will use them to do digital signatures so do you recall and digital signatures it's all about aving in the case of public key cryptography because you can have signatures using H Mac for symmetric key but anyway in the case of public key cryptography it's all

about you have a keeper a secret key and a public key you keep the secret key for yourself you release the public key and whenever you have a file or something you want to sign you use your side your secret key to sign the file and produce a signature that you can release and that anybody can verify has been generated using your secret key by checking its verifying under your public key and it's really nice because I'm yeah so what we want with signatures is that it's not easy to forge a new signature out of old signature because otherwise you know I got a message I release the signature and some adversary want to sign I don't know with a double

of my message if you could just take my signature double it and publish it it would be meaningless because anybody could Forge signatures so we want signatures to be difficult to forge and we also want the signatures to be so that it's impossible to recover the secret key out of the public key is a message and the signature obviously so there is a signature scheme which is called BLS by the name of its author it has been published in 20 2004 by Bernie aluminum so BLS was part of Lynn PhD thesis and it's using pairing cryptography it's using pairing based cryptography to produce senators and BLS has actually a couple of really nice features because thanks to the pairing

and the linearity of the pairing it enables you to do signature aggregation so you can you know like when you get Bitcoin and you want to sign all those transactions and then you want to sign the wall block it's a bunch of signatures it's taking a lot of space well with BLS you can aggregate the networks into a single signature which verify only if all the other one verifies which is nice and it also enable using the billionaire recharge the pairings the threshold signing so that means if you've got a group of n people you just need T people in the group to sign something the same thing with her share of the key so that at the

end the signature is valid for the wall group for the public key of the group of the wall work and finally it's detail but for durin it's actually important the signatures are well distributed over the signature space here the space it just means the the as a group and to which we map with the tearing that so a little picture maybe so here on the right you can see G which is a generator of elliptic curve and we have a private key PJ so what we do is we multiply the generator by PJ to get a public key which we can release on and everybody can know the value of P big P which is a

point on the elliptic curve and whenever we want to sign a message we will take the ash of the message which has to hash on the elliptic curve but there are a couple tricks actually to make it so that whenever you have something you're sure it will arrive on the curb and when you sign a message m and you take the hash of the message on the curve it's a point and then you multiply that point using the same private key used to publish your curly key and you release that us which is another point and elliptic curve and whenever you want to verify the signature what you do is basically thanks to the pairing you verify that the pairing of

the public key together with the ash of the message is equal to the pairing of G the generator together with the signature you released and why does it work well because of the B linearity of the pairing you can see here you get a public key P which is the private key times G is the generator and message the ash of the message but thanks to the B linearity the P key here can be moved on the other side which is equal to the pairing of G and the public key times the ash of the message which is s so whenever that is holding it means you have really been signing the message you want to sign using your secret key which

corresponds to the public key you really used which is P so maybe that gives you a better idea of what's why pairing are so nice so now threshold BL s so the idea here is as I said that you have your shared secrets between all members the end members and you have a threshold T decided during the key generation and whenever you want to sign a message you just need each member of the group to sign the message using its shirt because what's really nice here with BL s and the dkg is that the secret the shares that every shareholder is Olding can actually be used just if it were a regular BL s secret key so you can use

your sure to sign a message and get a valid signature under your shirt and when you combine all those signatures those partial signatures together using Lagrange interpolation again you will get a you which will be actually the signature for the wool group and that is really nice it's a property very which is naturally which we can't find really often in practice so being able to sign together a message without leading everybody to reconstruct the secret first and use the secret we reconstructed is really nice because it means the secret here the main secret is never in memory on any machine it's always hidden behind the computations so why do we need it all those elements while we need it in order

to run around and others it worked Iran so do you run need to be set up first so this phase is really expensive because you need to run the distributed generation which is running a lot of secret sharing which is all the nodes and so on so it's a n square process which is a bit expensive if you remember your algorithmic classes and it doesn't really matter because you just need to run it once and once you've run the setup every load of the network which is running Iran will owed a secret value si which is its own share of the main secret which is still hidden nobody knows about the main secret everybody knows about its very own share and the

public key of the wall group so P here is actually as the main secret times a generator and that's everything you need then to be able to run the run afterwards so whenever you want to generate randomness what's happening is that you will take the signature of the current round together with the previous signature and output it because I a said the signature using BLS is run is uniformly distributed on the signature space which is nice and it also means that it's a shame of randomness so you can verify the signatures there are very few able and you can check that it come from what were they were supposed to come from which is also nice there is a trick

here because I said the signature is uniformly distributed on the signature space which is not the same as being distributed randomly and as unto to the 256 space so it's not random bytes not yet but what you can do to transform the signatures into random bytes is once you verify the signatures you can simply hash it and it will map and random bytes because signatures are uniformly distributed and the hash functions of properties which are quarantine it's not possible to you know predict the values and so on so currently it's not hashing it you run but in the next version we will be directly hashing the value so that you can directly use the value

output by G run so I was speaking about changing the randomness in round so what do I mean so it's not a blockchain because we got no blocks but basically what we are doing is we take seed which is just you know random Elvis quote and for the first round everybody in the group will sign that seed together with the value of the index which is zero and for the next round the round number one everybody in the group will take the previous signature which we just got and sign it concatenated with the round index which is now one and so on and that's basically a chain of randomness which you can check at any time is coming from

the previous values and that's nothing fishy is happening behind the hood or whatsoever and the warranties here are provided by both the fact you can verify the BLS but also by the fact that you can verify the chain of randomness and that's it for the generation of randomness so what's the features of the run so as you can see here Duran is achieving its goal of being decentralized available and there is a threat model that's no more than half of the nodes or mail issues also under the I read the assumption that at no point are less than teeth nodes available because you need to sign using T nodes but that's a detail you can set the parameters as you want so

it's easy to achieve it's unpredictable and biased thanks to BLS it's publicly verifiable thanks to BLS and the fact it's chaining its random values its signatures together and it's fast because the process of the setup is may be slow but afterwards you just need a runtime trip of broadcasting the Pharrell signature your node as created and the Lagrange interpolation of all the partial signature you've got from the other nodes and that's it basically it's also open source as I said so you can check it out on github and it's provided with 12 samples GS and JavaScript example to run it you know as web app and CLI tool to query to fetch randomness from the

nodes and verify the signatures and so on so I told you about the League of entropy on one of my first slides so what is the League of entropy well it's a bunch of companies and individuals who decided to collaborate together to run the JIRA nodes and to create a decentralized network of randomness beacons so we was taking part to the League of entropy well cloud fur is EPFL obviously kudos key security since I'm here protocol labs were Nikola is working University of Chile and a couple other individual nodes because some of the researcher involved wanted to render our very own the run node so what's also really nice with Zirin is that you can

integrate any source of entropy into Iran so for example CloudFlare is relying and it's lava lamps to provide the entropy run needs so the node run by cluster whenever it's requiring any randomness is taking it from the pool it got from the lava lamps which is nice the University of Chile also is using seismic data from Chile as well as some radio frequency stuff and so on so I don't know if you got cool randomness or cool entropies foresees but if you do well guess what you could join because as I said in one of the on the building blocks slide they run allows for reshoring so what's the idea of free sharing is that you get

that main secret nobody knows about and there are new members coming and maybe old members going out so you need to research the secret nobody knows about it's bit of a problem right because you need to rerun the distributed key generation but if you do so the secret will change and what what can we do well hopefully they're in some scheme you can check the paper it was on my building blocks slide and that allows you to reassure that unknown secret using the producers into users you can give to the news shareholders and so on and it also allows you to change the threshold value if you need to and so on so it's really

nice so if you want to join us you can you can just shoot us an email at the league of entropy at Google Groups calm and at some point in the future we don't know yet when but we'll send email so everybody and we are going to do a reshoring at some point so if you set up Rudy run load you can join and so on so yeah shoot us an email if you want to join so hyped emote I'm right now I'm kidding so get run has two interfaces I as I said it has a CLI tool but it had also a REST API so here is a couple examples of how you can use Durand

you can simply wear any node so here I am wearing the kudos key security node using the REST API so and tap you can see the query to get the distributed key so what's the distributed key it's a public key of the wall group so it's a public key of the League of entropy which allows you to verify the signatures emitted by the group and when you need to verify the signatures well whenever you get a new random value so that's on the button you can fetch the latest totally random value currently we're at around 90 to 300 and something because I took the screenshot this morning and you can see it's training with the previous signature value so

basically the value of the signature and the bottom is a point on the elliptic curve and it's signing this run number together with the signature of the previous round so you got under screen all the informations you need to verify the signature and the bottom has been emitted correctly as a group and it's a signature that has been created by all members together not just one or two because otherwise it wouldn't verify address distributed key a couple of caveats because it's important to keep in mind Iran is producing public randomness so you can not and you should not use Durant well randomness to produce secret keys you know you want to encrypt your data using

AES well you need to generate a secret key you don't need a public random value to do so also Kiran is in beta right now with prototype so it might not be stable and I really want to stress that Kiran is in beta right now so we don't have any SLS you know like Six Sigma variability or whatsoever it's not because it's run by cloud 4 and a couple other people that we have high high availability right so we are just security researchers we go on vacation if the couple nodes go down it's still working because of the threshold signing but if too many nodes go down well at some point we need to reserve them or

whatsoever so don't build your availability service using the run for now or maybe do it but rather your very own different network so what's coming next so we would really like to replace a current elliptic curve we are using for BLS by another one namely BLS 12 381 because the current elliptic curve we are using is actually vulnerable to attacks which we were not expecting I start run the new attacks I think it's attacked from 2016 or something like that and those attacks are actually acting in the extension field unto which the parent is mapping so the problem here is that PN 256 as a hunting degree of 12 which is mapping onto an extension field

whenever you use your pairing so that was the line on the bottom when we were verifying the signature and on these extension fields the difficulty of breaking the discrete logarithm problem which is basically what's protecting BLS signatures the discrete logarithm problem is not as high we would have hoped so what we will do basically just move away from the end 156 to BLS 12 381 which is a lack of with a higher with a bigger an extension field so it's more difficult to bring basically also we would really like to work on the quality of the dye run software because it's currently lacking a bit of unique testing on such things and so yeah couple things to do building

application using urine is obviously something we would really like to do so I don't know if you want to run a lot free website using Durand go on and finally so quantum computer for coming in the next 150 years who knows so maybe at some point we should consider switching to quantum safe algorithms but it's not there yet because we really need threshold signing and I'm not aware of any thresholds I mean algorithm that is quantum safe for now so we'll see how it goes but it's definitely something we need to investigate further I don't know maybe using ISO Chinese or lattices whatsoever and think that it's so a couple random quotes and yeah I don't

know if you have questions

no questions does anyone have questions I'll walk the mic over to you all right perfect all right thank you very much