We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

Elliptic curves in FOSS

00:00

Formal Metadata

Title
Elliptic curves in FOSS
Subtitle
More curves to the set
Title of Series
Number of Parts
542
Author
License
CC Attribution 2.0 Belgium:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Identifiers
Publisher
Release Date
Language

Content Metadata

Subject Area
Genre
Abstract
Since the first implementation of elliptic curves over finite fields for the GnuPG and the implementation on OpenSSL of the curves over finite and binary fields, back in the 2000s, many things have happened over this mathematical construction. We've witnessed instances like the birth and death of certain isogenies or searching for algorithms that resist quantum computing, which are only a few to mention. We moved from the NIST curves on the P1363 to use Edwards variety, and there is a recent proposal with Double-odd curves. So the assortment is increasing, but we need to squeeze them more. For each new curve, all users always share the same group. This talk will review the path walked and evaluate the progress in implementing the Double-odd Jacobi Quartic in Libgcrypt and GnuPG.
14
15
43
87
Thumbnail
26:29
146
Thumbnail
18:05
199
207
Thumbnail
22:17
264
278
Thumbnail
30:52
293
Thumbnail
15:53
341
Thumbnail
31:01
354
359
410
CollaborationismCurveEllipsePoint (geometry)Congruence subgroupOpen setExecution unitTorsion (mechanics)Local GroupSubgroupCryptographyPositional notationInfinityDiskreter LogarithmusKörper <Algebra>Koblitz, NealIndependence (probability theory)Form (programming)Reduction of orderNormal (geometry)CryptanalysisPrime idealVorwärtsfehlerkorrekturStandard deviationComputer fontPresentation of a groupKernel (computing)RSA (algorithm)Address spaceRevision controlEuclidean vectorEquivalence relationPublic-key cryptographyPrimality testVector potentialBuildingImplementationMilitary operationEncryptionJacobi methodKörper <Algebra>EllipseImplementationElliptic curveCurveFunctional (mathematics)Multiplication signDifferent (Kate Ryan album)Address spaceVariety (linguistics)Connectivity (graph theory)SubsetPresentation of a groupTorsion (mechanics)CalculationPhysical systemElectronic signatureStandard deviationWell-formed formulaMathematicsParameter (computer programming)Level (video gaming)Point (geometry)Axiom of choiceCongruence subgroupElement (mathematics)Galois-FeldBoom (sailing)MappingRevision controlOrder (biology)SoftwareBitHash functionEvolutePublic-key cryptographyNumberCASE <Informatik>Beat (acoustics)Domain nameCryptographyPlotterCubeStatement (computer science)Real numberEuklidische GeometrieFinitismusCharacteristic polynomialComputer fontInfinityGenerating set of a groupMedical imagingFreewareIndependence (probability theory)Service (economics)Set (mathematics)Zyklische GruppeForm (programming)Point at infinityAbelsche GruppeNational Institute of Standards and TechnologyDegree (graph theory)Kernel (computing)Normal-form gameCryptanalysisPatch (Unix)Constraint (mathematics)Operator (mathematics)Open sourceEquivalence relationLatent heatSingle-precision floating-point formatParity (mathematics)Condition numberSlide ruleVideoconferencingDiagramComputer animation
CollaborationismMilitary operationEncryptionJacobi methodOpen setOperations researchTexture mappingTransformation (genetics)Group actionCurveCodierung <Programmierung>EllipseMathematicsLatent heatRandom numberFunction (mathematics)Hash functionInclusion mapFormal verificationParameter (computer programming)Streaming mediaCryptographyAxiom of choiceCryptanalysisVorwärtsfehlerkorrekturElectronic signatureElliptic curveMatching (graph theory)Streaming mediaMatrix (mathematics)1 (number)Group actionParameter (computer programming)Service (economics)CryptographyPlotterVariety (linguistics)Point (geometry)Communications protocolShape (magazine)Internet der DingeCurveOperator (mathematics)Körper <Algebra>WeightStandard deviationCategory of beingMultiplication signHash functionRandom number generationHyperelliptische KurveOpen sourceOrder (biology)Information securityDirection (geometry)VideoconferencingComplete metric spaceRecursionHomomorphismusSoftwareImplementationFreewareResultantElement (mathematics)DemosceneCycle (graph theory)Data miningLevel (video gaming)NumberTransformation (genetics)MappingConfidence intervalMathematicsExtension (kinesiology)Set (mathematics)Computer animation
VorwärtsfehlerkorrekturComputer animationProgram flowchart
Transcript: English(auto-generated)
Hello and welcome to the Forstens Security Dev Room, this is a talk about elliptic curbs in free and open source software. The room's audio and video wasn't recorded properly so I will record my voice on top
of these slides trying to fix it. My name is Sergi Blanc-Tournay and I do this activity as a member of Collabra. Here is the overline of the presentation and the first thing that we will do is an overview of elliptic curbs themselves. The first question to talk about is the what, so what's an elliptic curve, and this will
follow everything else in this talk. An elliptic curve is a function and a very finite field is understood as a congruency with a odd number and it must satisfy the condition to not have singular points, mathematically we know that because it has a non-zero discriminant. This is how an elliptic curve plot in the real plane looks like, perhaps even it's an
image that looks familiar, but if we plot it over in a small finite field this is how it looks like, so you will see that the real numbers extend to the infinity but this is not happening over a finite field. So to later do the maths we need to union this set of points to the point of
infinity to set something that is complete. Once we have a set of points of an elliptic curve with this point at infinity we can define a cyclic subgroup that is where the crypto will happen. An important thing to mention is the notation, if you see here is different than the crypto
over finite fields that we may use to, but the difference is that here we are using additive notation instead of the multiplicative one, perhaps you already seen before. The same way in elliptic curves we have a generator of the cyclic group that we provide as the strength required to do crypto, the order or the size of the cyclic group must
be big enough and there is a relationship between the number of points of this elliptic curve and the order of this cyclic subgroup, this is called the decofactor and this is a very important parameter that would affect almost everything later on. Until here the hard math, I don't need for this talk to enter further to explain the
torsion points or even isogeneous. The first proposal to use elliptic curves and cryptology comes from an independent proposal from Koblitz and Miller. The functions commonly used here are the Weierstrass reduced form and they are different
when it is defined over a primary field or when it is defined over a field extension, but they are subsets of the parameterization of the Weierstrass normal form. A common variety of the elliptic curves are the Montgomery curves that follows this formula and these curves are used together with the map to the Edward curves and you
will often hear about if they are twisted or not. There is a recent proposal to use what so called double odd curves that takes benefit from another map to Jacobi quartic curves and these last two mappings are very important for the current evolution of the elliptic cryptography.
Next question is why? Why elliptic curves are better to set up cryptography than the common generalized use of finite fields? The first benefit is the size of this prime p that is required to be much larger in finite fields, 2000 up to 4000 beats nowadays, when in elliptic curves you can have the
equivalent sizes between around 250 and 500 beats. This statement has a but that has to be remarked here. The size of the finite field over which the elliptic cube is defined is smaller, so the operations are over the smaller numbers, but the operations between the points required
much more operations over the underlying finite field, so don't expect them to be much different in time. Another difference is that elliptic curves can be defined over more fields than the finite ones, as they are the characteristic to file extensions, but the most important
advantage that elliptic curves gives us is the possibility to use different elliptic curves over the same finite field. This is a huge impact over the cryptanalysis, because one cannot use efficiently the cryptanalysis made over one curve when you are using a different one, and the main beneficiary of
this feature is the embedded systems that doesn't need to change the size of the calculations by resetting the curve. Next element in the outline is the standards defined for the elliptic curves cryptography. The first standard that I know about were from the 2000s, in the text of the NIST
or the ANSI, standardized specifics on single elliptic curves for different sizes. It is important to mention that x962 specifically mentioned that shared elliptic curve means to share the cryptanalysis. With them, more elliptic curves come to the scene, and newer standards that specify
different curves but over the same variety. In the two decades that passes, many more standards come to the scene, but fundamentally fixing single elliptic curves for a specific finite field size. I couldn't do this presentation without remembering xkcd.
Let's go talk on the main thing on this presentation, that is, the implementations. Here is a non-exhaustive table of different tools and packages that I know that they have elliptic curves implemented. First implementation is the OpenSSL, because if I'm not wrong, it was the first implementation
of elliptic curves in free software. They made the implementation in both underlying fields, finite fields and characteristic tool. The next one is the libgcrypt that promotes a patch that I've made in the baccalauret degree for the GNU PG 1.4.
And then many other implements the elliptic curves like GNU TLS and later on the kernel itself. After that the boom happens, and many more implements this cryptographic setup. And with the proposal of the new elliptic curves of using edu-verse curves, almost
all of them have also included the math to work with this elliptic curve. One place where the elliptic curves are present for the general public is the Tor network. I haven't listed them before, because from my point of view, it's a very special case. The onion addresses in the version 2 of the specs use a truncated hash of an RSI key
embedded within the 16 characters of the onion address. With this version 3, there is no truncation, and it contains completely the public key. And this public key is a point of an elliptic curve using the standard curve. With this concatenation, we have these 56 characters currently used in the onion addresses.
So much more tricks has been necessary because the torsion component of this curve that is related with the fact that it has a cofactor 8. There could be multiple equivalent addresses pointing to the same service.
So continue with those new elliptic curves and more standards that are coming. First of all, this Edward curve that is a Montgomery curve with a variational map with two other curves, one is twisted and the other is non-twisted. And as explained in the standard, there are some constraints to have better choices
in the range, so those are the parameters proposed. And this standard gives us one specific curve for the 255 bits, and a second curve with a bigger strength of 448 bits. Both using this map to other curves to move the domain of some operations to the curve
that can do it better and faster to later go back to the elliptic one. Following this idea of plotting elliptic curves, you can see here the plot over the real numbers, as well as the same plot, the same curve, but over a small finite field.
The last curve I plotted here is the pair of twisted and untwisted curves. What makes those curves special is that they have been designed to avoid common issues we learn with implementations of elliptic curves. So they are designed to be immune to timing attacks.
There is a relatively new proposal to use another Montgomery curve. This time the prime p to define the finite field is different depending if the purpose is to encrypt or if the purpose is for digital signatures. And in this case, we have a much better cofactor than these two. In this proposal, they are taking benefit also from the mapping to the Edward curves.
In this case, a plot over the real showed a very different shape with coordinates origin in the most left-hand side of the curve. By the way, this is something you don't see visually in the plot over a small finite field, but it's an interesting property of this variety.
Even more recently, it has been proposed to upgrade this with the use of another mapping to a Jacobic hortic curve that improve the coordinates transformation and the operations in the map much better. It makes operation faster and signature shorter. Then let's go to see if we can choose our elliptic curve.
There is a draft talking about the ristretto and the calf and later we will talk about zoo. The calf is a technique mainly thought to construct elliptic curves with a small cofactor, but bigger than one. And then comes ristrettos, an extension of this technique for the variety of curves where the Edward curves in 255 bit are.
This proposal takes advantage from both mappings, so this is proposing to use the variety of elliptic curves taking benefit from the advantages of those two maps, Edwards and Jacobic hortic. And this is not to specify a single curve. This is a very important step. This is to specify and standardize the maths and operations to work with
a complete variety of elliptic curves. Perhaps some smart cryptographers have started to move in the direction to give us the possibility to not share elliptic curves between each other. This reminds me a paper from 2015 from Leinster and Velowski that talks about the zoo.
A zoo of actors in this proposal to have a public and auditable generator of elliptic curves. So let's go into the details which are the members of this zoo. First of all is an important sloth and this is a hash algorithm that requires time. It is slow by design.
There is a unicorn that comes to the scene and this is a special random number generator. It is not the usual random number generator because it is made to allow all of us to influence the result. We can influence and verify that our contribution is included. What makes it good is that a counter contribution is hard,
so it is hard for another participant to prepare a contribution and counteract all at once. The next element in this zoo is the T-R-X. I am not sure if this is a real way to pronounce this T-R-X. This member of the zoo uses the unicorn to stream a trusty random generator of elliptic curves parameters
fitting the cryptography requirements. With this, we all can influence the generator of a fresh elliptic curve and verify our contribution. But no one can counteract our contribution effectively. The result cannot be known beforehand and cannot be manipulated to provide previously known results.
This prevents prior kryptanalyses and also provides confidence about how the parameters were selected. Linked to the ANSI X962 about the fact that we are sharing elliptic curves, we are sharing also kryptanalyses together with the fact that it is expensive to generate an elliptic curve cryptographically good
and also together with the movement to standardize a variety of elliptic curves but not a single one, we can set as a corollary that by saying that there is a movement to fix this small set of elliptic curves that we've been struggling during two decades. It seems that we are working a very nice path in elliptic curves
and Free Software is the only actor that can provide this trusty elliptic curves generator. So that's all and now the video and audio from the room gets back. So that's all from my side in this little review on the elliptic curves itself and thinking in the implementations in Free Software.
Hi, you were talking about standardization of curves but with a lot of new cryptography techniques like zero-knowledge, homomorphic encryption, MPC, VDFs and then even when you start talking about recursion
and curve cycles and pairing friendly curves, each time it seems people try to standardize curves and then discover like there's some new property like maybe unknown order groups or hyperlyptic. I think the movement of this restricted one, the curve, goes in the direction instead of standardize an elliptic curve itself,
it is standardizing a variety of elliptic curves. Then you have the operations and the match to work with any elliptic curves in this variety. So this will bring us the possibility to have this like another service that is providing random elliptic curves on the net
and you can pick one from there and forget about the thing that we are sharing the same elliptic curves of this. The way that all the current standards that exist are fixing an elliptic curve, one or another, but fixing in a specific way.
I answered it because you say about homomorphic but homomorphic is huge, it's a very interesting field but it's a huge field. Okay, I can see another question.
In many protocols and also in IoT devices, you are bottlenecked by speed and also by signature size. You said that with the jacobiquatic curve you can go faster and also smaller. How much faster and how much smaller? I have in the paper of the jacobiquatic people, the speed is explained, I don't have the numbers on mine now.
I have the numbers on mine about the size because the sizes in signatures in elliptic curves are 64 bytes and the schema they propose for the jacobiquatic is 84 bytes, so it's like a third smaller.
But it's still bigger than BLS signatures who are about 32 to 48 because you only need a single point on the curve. In the signature, you are not putting only the point. There are three, if I remember correctly.
BLS signatures, it's only one point. Which signature? BLS from Dan Bonnet. But it's shorter than 48 bytes? It depends on the base curve you use but it's only, so if you
use, well, 32-byte signatures are not deemed secure enough because you have pairing issues but 48 bytes provides 128 bytes of security. What I know is that in the Edward Kirp's variety, the signature is 64 bytes.
Okay, are there any questions? Have you looked at Genes II curves? Because I saw that they outperform Genes II.
They outperform Genes I. I saw DJB was really into them. You are? Hyper-elliptic curves? Yeah, the Picard group. This is a very nice subject also. I think banks are the ones that are putting more money in hyper-elliptic curves.
They are not using points, they are using a matrix that is Jacobian of the point. By now, I only heard about banks putting money there. I haven't seen an implementation in open source.
Any other? No? Thank you.