🔬 CIRCL: our Go library now includes pairings and quantum-resistant cryptography.

Good morning, good afternoon, or good evening, whatever it may be. Welcome to Circle, our Go library, now includes sparrings and quantum-resistant cryptography. Before I explain that, let me introduce our fellow speakers. Watson Ladd, he's a cryptographer at a research group. He has a PhD in mathematics and he's a contributor to Circle. Welcome, Watson. Hello. We have Armando Faz Hernandez, he's a cryptography engineer at the research team as well. And he's the maintainer of the Circle Go library. And I'm Bas Westerbaan, I'm a research engineer, also at the research group, and I hold a PhD in quantum computing. Okay. So, this week, the research team has been taken over the Cloudflare blog, and you have seen many exciting research topics, such as connection coalescing, passive RTT measurement, encrypted client hello, privacy pass, geokey manager, marder get pwned, OPRFs and other things concerned are way forward for passwords, and with many more other things to come. And what a lot of them share in common, the latter half, is that they involve advances in cryptography and cryptography implementation. And today we talk about Circle, which is a cryptography library on which many of these exciting products and research topics are built. So, to start, Armando, can you explain what Circle is? Yeah, I'm very happy to be here and then try to explain a little bit about this Circle library. First of all, this is a library written in Go. Go language is heavily used in different companies, and here at Cloudflare we use it a lot. So, yeah, so we started Circle as a way to integrate some other algorithms, mainly cryptographic algorithms, into a library that they are not appear on the standard library. So, basically, this is like a complement of the standard library that everyone can use because it's an open source project. And then they can instantiate some very recent algorithms, which are like either like some of them are experimental, some other are like more, has more relevance, or some other have more performance improvements, which is something that we want to achieve with this. So, yeah, so for this week, we are very proud to announce a new version of the library. And since we launched this project, so we have included a lot of algorithms, mainly on post-quantum cryptography, but also on the computation of bilinear pairings for cryptography. So, let's talk a little bit about the pairing stuff. So, some important differences that whenever we write crypto code or security code is that we need to be careful about the latency of the operations. This means like how much time it takes to compute some operations. So, usually people think about this about is the performance of the application, but also we need to take care that some optimizations, they can lead to some, not all optimizations can be applied by the matter of security of the implementation. So, in that sense, I think, so we need to protect the cryptographic implementations against some side channel attacks. And this is, yeah, it's a main concern of the crypto library. Okay. Okay, so the, so it's. So, who's the intended user of the circle library is. Yeah, exactly. So, we have included some algorithms for elliptical cryptography, so much of the PKI that you can do like, you know, signing certificates or generating keys, cryptographic keys. So, some, some of these functions that are already provided there so the only that you need is like, try to integrate circling in, in your, in your goal compilation, and then that we're ready. So, also, other type of users for for the circuit library are those who want to experiment with the with new algorithms or with new primitives that we will talk later. And, and you can you can get certain assurance that that the code there is, is a carefully written, and then you can get a better agility in your cryptography. But experimental cryptography so what are the expectations on API stability that the user may have. Yeah, so we have, we have defined an API but it is likely, depending on the feedback we get from from people and ourselves. This is something that happened in my library so this is, this will allow us to iterate a bit more, whenever, whenever we do a change so we can iterate faster on this and then, yeah. So, so we will try to keep the API as much as possible freeze but yeah, it is unsuspecting that things will change. Not too much. Okay, so let's get to, it's now, I think, two years old now, and a few days ago, we released the second version. And what's new, can you give a summary of that. Yeah, I can give you a summary. So basically, we have, we have new algorithms for groups that are that are based on elliptic curves. So for example, you can, you can instant many, many, many cryptographic protocol required like prime group, where you can do operations like you know exponentiation or scalar multiplication, and then we just wrote like a model, a package that can implement this group operation, very easily. This so important part of these groups is, for example that they hash into curve so you can hash arbitrary strings into elements of the group, this is something, something new the library. We also have other high level protocols which has the bilinear pair is that we will talk in a minute, HP key I hybrid public key encryption. This currently on on the track for for standardization, we have also a BOP RF verifiable oblivious of the random function that allows you to to compute. It's a protocol between server and client that allows to compute that also the random function. Another important part is the post quantum algorithms. We have a new one new chem which is Kyber, and one digital signature which is the lithium. So both of them are currently contended on the on the next competition for this one. Okay, so let's let's move deeper into the, into the pairing so Watson, could you could you explain what pairings are. Sure. So, when we have a elliptic curve. We can think about we do we have points on the elliptic curve and we can multiply and add these points. And this lets us do a great many things so public key encryption and signatures and all those fun things, but sometimes it's useful to be able to take two different so we have, we have two related curves, and we have a point on one of them and a point on the other and want to multiply them and get a point that that's sort of a value in a field. And this is called the pairing and the pairings by linear, meaning that if I multiply a point, and then do the pairing is the same as doing the pairing then then exponentiating the result. And this is useful in protocols like Anthony and she's tripartite Diffie-Hellman, where instead of if you have three people and they all want to agree on a shared key stuff passing around incrementally a Diffie -Hellman value, they can all just announce their values, and they do a pairing calculation and exponentiation to get the same key. We've used pairings at Cloudflare to power our GeoKey Manager, and we've, our implementation in Circle uses a different stronger curve than the one that we had in the past. This is due to new developments in the attacks on pairings. It's also using formally verified implementations of the field, they're automatically generated, and they come with a proof of correctness. So this is a big step forward in the assurance we have that our library is correct. And pairings have many, many uses. They can be used to identify identity based cryptography, where your public key is a function of your identity. So you don't need to have a PKI, you just need to have a key distribution system. It can be used for zero knowledge proofs that are simpler and faster than any, well I shouldn't have said simpler, there's nothing simple about snarks, but very fast verification and very compact ones. So all these applications are, can be built on the foundation we have in Circle. So, to summarize, what, no well, to say what is special about our implementation, you already mentioned a few points, we use formally verified field arithmetic. We have good performance. Are there other parts to our implementation which are special worth mentioning? So a lot, we did look at existing libraries out there, and I'm not going to be specific about but there were, we sort of have an API that is much closer to what you'll write for other elliptic curve operations across library, and that's definitely an advantage. We've also really tried to be comprehensive in the, in what we support in terms of functions. So, all the, all the groups, you could want all have similar functions for scalar multiplication and multiplication or addition. The fact that the name is multiplication one place addition another place has a technical thing. But you know we did make it, we thought carefully about making that choice of how to represent it. We've really worried a lot about things like validating, making input validation secure and performant and ensuring that we deal with all exceptional cases and side channel security. Very nice. So, back to you Armando, what do you think is the future direction of Circle? What can we expect in the future? Yeah, well, this is, this is like a long path like we need to accompany with the recent proposals, the new algorithms that emerge every day or every year. So, something that we would like to have is like more, more support for formal verified crypto. That's include, for example, assembly. In some parts of the, of the, of the code, when you have like some function that takes a lot of time so one, one way to make the run faster is that then you go to assembling in order to exploit the capabilities of all the matching that you have, right. So, you don't, you don't want to waste like cycles, trying to compute things in an old fashioned way when you can do it by assembly. The issue with assembly sometimes is that, well, not many people know how to review the code or how to debug if some problem exists. So, yeah, of course this is this an issue. But what we can do in to counter and attack this problem so there is this new tools that are being developed in, in the area of compilers, which allows to give a description of what, whatever you want to compute, and they produce assembly that is that is verified by by a formal language that's that is framed by by some very well known primitives. Right. And yeah, so in that case we can produce a something that is sufficient because it is written assembly, something that we have a certain guarantees that will work and it has less prone to bugs. And, yeah, and something that can be that can be integrated easily on circle, and then many people can use it just by using the package. Another direction of circle is the inclusion of quantum algorithms. So I think this is a, we're like in the middle of this competition, and then we want to give support for this. The final is algorithms. And yeah, so I think this, this are mainly to to to big the direction that we have in circle, but we also are happy to welcome a request or future requests that you, what kind of algorithm, you, you would like to see on on the, on the next release. So, yeah. And how can people reach us to request new futures are suggested. Yeah, so we have a web page is research.clubher .com. So there you can go to the project section and you will see a list of circle, and then there are like a contact information that you can do there. If you want, like, more want to propose some change or want to address an issue on the repository so we have hit hub.com club. Yeah, you know the club for slash circle, where you can you can find the repository. Okay, exciting. Are there more points you want to add on circle, which we haven't discussed yet. Yeah, well I think, like, something that we haven't discussed is about like the quantum crypto. So I think this is, this is something that we can talk next about it because, you know, right now making making the transition is something important in order to be protected for the future. What's. Well, I boss you should you should tell us about all the all the hard work you put in the post mom algorithms over the past. Got how I don't know how many months, you originally wrote some of the implementations that we have, if I remember. Yes, yes, that's correct. The, the, the, the previous time I. So I returned that class there and the previous time it was for an internship. Well, fellowship and somewhere in between. And there I bought the the Kyber and lithium implementations, which, which are released now. Well, the. Yeah. So what are Kyber and lithium. So Kyber is a is a key encapsulation mechanism. So, and the lithium is a signature scheme. So key encapsulation mechanism is a bit is a bit of a new is a bit of a new thing. But it's just very actually very familiar. It is very similar to just public key encryption, but instead of being able to encrypt anything you can only encrypt a share a fixed size shared secret which is automatically generated for you. But this is exactly what you need when you do TLS. So, when you hear Kim just think about public key encryption that's it's essentially the same thing. So, so there's this NIST competition where, which has been running for several years now, which is looking to pick out a chem and a signature scheme, or more, which are post quantum secure. And there are several candidates now. Two dozen together as approximately. And so the question is, why, why out of them, we chose Kyber and lithium. Well so the, the chems, they're all very much alike. There are some outliers, but the majority of them, they are very similar in performance in size and properties. So they're the choice. So there there's many options. And what, what is it they do that makes that why, why is the underlying problem hard for what is the underlying problem behind the security schemes and why is it hard for a quantum computer to solve. Ah, yes. That is just like everything in security, we, we, we are not most things we're not completely sure about, about that but we hope it so that there are several different underlying problems. A lot of them are based on problems concerning lattices. And they have been studied for a long time already. And parts of the competition is also to look at these underlying problems more carefully, whether they are as hard as we originally believed. But you have lattices, you have code based, you have some based on asogenies, but there's several different ones but for the, for the, for the security of the underlying hardness assumption that's one thing that is important, but also to actually deploying it all the aspects are also very important, ease of implementation, how well does it perform in hardware. How big is it, how fast is it, and these things can also be subtle. So how big is it, well maybe some have big public keys and small private keys and all the way around, or big ciphertext, small. So it's quite different, although for the cams, it's relatively similar, but it's the signatures which are quite different. So in the signature schemes there's really quite, quite big variations, some of them, verifying as fast, signing as slow, flipped around. Implementation details vary a lot, some of them even require floating floating point arithmetic, which is a quite a new thing for us cryptographers. So there's a lot of variation in the signature schemes, but one thing they have in common is that they are all rather large. So, almost all are rather large. And when we say rather large, what, what are we talking about we're talking megabytes, are we talking kilobytes. So in the signature schemes, most of the signatures are well above two kilobytes, whereas in elliptic curves you have signatures of 64 bytes, and with RSA you have signatures of 512 bytes. So that's, that's, that's quite a step up. This is like 100 times bigger than the signatures we're using today. Yes, it depends on which one exactly but it's, it is about 100. Yes. So among the signature schemes, there's, there's basically two which, which, which, which are feasible, or free. So you have dilithium, which is a bit larger, it's around two and a half kilobytes for signature. But it's pretty fast signing and verifying. And then you have falcon, which is smaller, only 666 bytes for a signature, but signature generation is a bit more difficult, it's a bit slower, it's slower. But one problem is that falcon uses floating point arithmetic to actually have a reasonable signing time. So in, for our, we are very much interested in TLS for the web. And with TLS, it's, you have to make signatures on the fly, so when you make a connection, there's a signature made on the handshake. And we were worried initially about using falcon there and because it has to run on all clients, on all floating point things. So that's why we, which, let me name a third one. The third one is rainbow, which is actually very small signatures as well, but has rather large public key, 100 kilobytes, which is very large. So out of those, we thought that dilithium would be best for handshakes. So there are two kinds of signatures in TLS. So you have the one which you do every time, we call this online signatures. And then you have the ones which are already done in advance. So in the certificate chain, the things for certificate transparency and a few others, but they are done in advance by certificate authorities. And so for, so because we need to have both, we thought, and we didn't want to mix multiple schemes, if we don't have to, we thought dilithium is a good all round choice. But now we think that perhaps with, there's research going on where we replace the handshake signature by a chem using implicit authentication. And so now it seems that actually maybe Falcon would have been a very nice one to have as well. But that's the reason we chose dilithium initially. And Kyber is a chem, which is based on a similar hardness problem as dilithium is. So that's why it was a logical combination for us that when we implement dilithium, we also implement Kyber, because then the underlying security assumption is very similar. And do the implementations end up sharing code because they're sort of using the same things? Theoretically, on paper, you could, but in practice, there's very little shared code. There is, it was very, once I implemented dilithium, it was much easier to implement Kyber because you get more used to the techniques used. But the code, if you want to make it performed, is actually different. Yes. Yeah, I want to add that, what Bas just mentioned, that for the specific case of TLS, so in TLS, it is performing a signature online. So during the protocol, and this, as Bas already mentioned, there are different schemes in which the case of computing a signature is costly, right? So there is this new approach that is a chem TLS is just, let's not use signatures in order to prove that the server holds the key, but let's use a chem for that. So, yeah, this is a recent idea by some researchers that they have this proposal to let's use chems everywhere in the TLS. And this could be helpful in order to get some small code base, you know, because you only need to implement one algorithm and then you're done, right? So, but I'm pretty sure that there are some other cases where you really need like signatures, right? Yes. And we also, and changing protocols is a more difficult affair. And we also try to be ready in case we couldn't change the protocols in time. So it definitely sounds like there's a lot of, also, you've mentioned this NIST competition. Can you say more about it? Yeah, so it's close to wrapping up now. Well, what is it? So the NIST is a standards body of the United States, and they hold several standards also related to cryptography. And they, a few years ago, they started the competition to find a suitable post quantum signature scheme and chem. We're in the third round now. They are accepting comments until the end of the month. And they are, we expect that they might announce which schemes will be their endorsed post quantum schemes in a few months. So that's January, February, maybe? It's just guessing. So we're very excited to see what will come out. And of course, we will work to implement the ones that are chosen. Yeah, we have a few more minutes. So let's perhaps summarize. We have a new version of the Circle library with great new improvements. Bearings, very useful, more secure, good performance, great API, carefully written. Other additions, post quantum cryptography, Kyber and Dalithium, and several more great additions. And they are out now. You can use them. You can have a look. And if you have any suggestions or requests, you can reach out to us on research.Cloudflare.com. We look forward to seeing what you do with our code. Yes. Yeah, hope you like this episode. And something I want to add about the post quantum algorithms very shortly is that we have in mind to include some hash rate signatures, which is something that we haven't put some time on there. But yeah, it's on our list, so next thing to do. Oh, if we're taking requests, ski sign. For those who don't know, this is an isogeny based scheme with very compact signatures, hideous signing performance, and reasonable verification for some definitions of reasonable. Yes, people like it because it lets you it lets them use all the math they learned about quaternity and algebras and elliptic curves still. Yes, it's already has like isogeny based crypto, which is psych. We have psych and CSIDH. But yeah, these are like camps. So it could be like a good feature request. So this actually is likely to announce a fourth round with a ramp up for newer signature schemes, because it's still really tough to fit in the current signatures. And we actually have measurements incoming probably before the end of the month to see how they will actually do. So lots of things still coming. And we are excited about it. And I hope you will be too. And where where can our listeners find out more about these measurements and all the other work that we're that we're doing? blog.Cloudflare .com. Just keep an eye on it, subscribe, or follow the Cloudflare Twitter. And of course, our research team website at research.Cloudflare.com. Transcribed by https://otter.ai