Implement Curve448 ciphersuite

[alxdavids]

The Go PoC implementation in this repository currently includes prime-order group instantiations based on the NIST P-384 and P-521 curves. This gives us (V)OPRF instantiations using two of the ciphersuites detailed in https://datatracker.ietf.org/doc/draft-irtf-cfrg-voprf/ but not the third: VOPRF-curve448-HKDF-SHA512-ELL2 (see https://tools.ietf.org/html/draft-irtf-cfrg-voprf-02#section-6.1).

Implementing VOPRF-curve448-HKDF-SHA512-ELL2 ciphersuite would complete the PoC implementation of draft-irtf-cfrg-oprf-02 in Go. The task can be split into a set of different milestones:

• [x] Implement Curve448 group operations using the same syntax as defined in the struct Point.
• [x] Implement the necessary operations for performing hash-to-curve as specified in curve448-SHA512-ELL2-RO- (see https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-05#section-8.7). The hash-to-curve function should accept bytes and deterministically map them to a uniformly distributed Curve448 point. It may be possible to use the implementation of elligator2 written here: https://github.com/armfazh/hash-to-curve-ref/tree/master/go-h2c/mapping/elligator2, but the interface for performing curve operations is a little different. The elligator2 operations are also detailed here: https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-05#section-6.8.2.
• [x] Create a Curve448 implementation that implements the PrimeOrderGroup interface (using the point syntax and hash-to-curve method from above). Ideally, this would explicitly use the GroupCurve design for performing group operations over Curve448 points, but it can also be done using a different design.
• [x] Add unit tests that verify both the Curve448 functionality and the hash-to-curve ciphersuite.
• [x] Support Curve448 as a valid ciphersuite in both the client and server (V)OPRF implementations.

Things to note:

• The definition of label wrt to hash-to-curve in draft-irtf-cfrg-voprf is incorrect, and is replaced in this implementation by a string relating to the ciphersuite that is being used.

[claucece]

Hi, @alxdavids !

This is very nice!

I already have an implementation of ed448 here: https://github.com/otrv4/ed448; but this is, of course, the Edwards version of 448. It correctly exposes most of the functions that elliptic.curve has (https://github.com/otrv4/ed448/blob/master/extended_point.go), and can be efficiently mapped to Point and PrimerOrderGroup. This is a golang implementation of Mike Hamburg's libdecaf (https://sourceforge.net/p/ed448goldilocks/code/ci/master/tree/src/), which uses the Decaf/Ristretto encoding, which means that internally, the library uses the twisted Edwards curve with the "decaf" and "ristretto" technique to remove the curve's cofactor of 4 or 8. Nevertheless, any point generated there can be later encoded in the Montgomery form, as it can be seen here: https://sourceforge.net/p/ed448goldilocks/code/ci/master/tree/src/per_curve/point.tmpl.h#l413, according to RFC7748. There is also an implementation of scalarMultiplication in Montgomery (https://sourceforge.net/p/ed448goldilocks/code/ci/master/tree/src/per_curve/point.tmpl.h#l470).

I also have a start of an implementation of Elligator there: https://github.com/otrv4/ed448/blob/master/elligator.go

My proposal will be to use this golang library by finishing the implementation of Elligator there and by implementing the encoding to Montgomery as well. The golang library is already tested against the libdecaf one and against the RFC8032 test vectors (as it also encodes 'ala' eddsa).

Do you think this is a good idea?

[alxdavids]

Hi!

That sounds like a great idea to me :+1:. It seems like there shouldn't be any problems with the existing interfaces, but if there is then we can always modify them to fit the 448 design.

[claucece]

Hi, @alxdavids !

Just to let you know.. all the needed x448 operations are now implemented and tested here: https://github.com/otrv4/ed448/blob/master/x448.go ;)

[claucece]

Hi, @alxdavids !

The elligator functions are now implemented here: https://github.com/otrv4/ed448/blob/master/elligator.go

They are using the decaf technique internally but can be encoded later to montgomery or eddsa. I was thinking on doing three things on this issue to integrate with this library:

1. Exposing functions with the decaf technique, as this can also be used to expand the draft: "There are also other settings where GG is a prime-order subgroup of an elliptic curve over a base field of non-prime order, these include the work of Ristretto [RISTRETTO] and Decaf [DECAF]"
2. Exposing functions with the montgomery encoding
3. Using the library from @armfazh : https://github.com/armfazh/hash-to-curve-ref

What do you think?

[alxdavids]

Hi @claucece, I think this sounds sensible. As you say, Decaf provides us with a prime-order group which is the setting that is considered in the draft specification, so I agree that this is the best way to go. I also think re-using @armfazh's library for performing some of the hash-to-curve specific functionality is a good idea.

Let me know if you hit any issues!

[claucece]

Just finished tasks 1 and 2:

• Two implementations using the same syntax of Point are found here: one using the Montgomery form (https://github.com/otrv4/ed448/blob/master/elliptic.go#L32) and one using the edwards form with the decaf technique inside (https://github.com/otrv4/ed448/blob/master/elliptic.go#L51)
• The elligator function for mapping has been implemented here: one using the Montgomery form (https://github.com/otrv4/ed448/blob/master/elliptic.go#L251) and other one using the edwards form with the decaf technique as well (https://github.com/otrv4/ed448/blob/master/elligator.go#L12)

I will proceed to integrate with this library and see how it goes ;)

[claucece]

Units tests for the montgomery operations for the Point are found here: https://github.com/otrv4/ed448/blob/master/elliptic_test.go (they are tested with test vectors from RFC7748), and for the edwards/decaf operations are found here: https://github.com/otrv4/ed448/blob/master/extended_point_test.go

Tests for elligator for edwards/decaf are found here: https://github.com/otrv4/ed448/blob/master/elligator_test.go

[alxdavids]

Thanks for the links, I will take a look through it!

[claucece]

Hi @alxdavids ! I just started the pull request as almost all is integrated: https://github.com/alxdavids/voprf-poc/pull/12 . Don't merge it right now as I'm still putting the sage test vectors for elligator2. But if you want to take a look, you for sure can ;)

[claucece]

Hi, @alxdavids !

Sorry for the lots of comments.

So, taks 1-4 are done and 5 is half done.

There is some findings I will like to share:

• The x448 function (used for ScalarMult and scalarBaseMult in accordance to RFC7748) only returns the u coordinate of Montgomery form, while taking as input this u coordinate and the scalar. At some places, this makes it impossible to verify that a point is on the curve, as the function needs the two coordinates of the Point. That is why I have moved the validation of points in some parts of the code.
• The x448 function returns the result as an encoded byte array. That is why there is not a real process happening at the Serialization function for curve448 (https://github.com/claucece/voprf-poc/blob/master/go/oprf/groups/ecgroup/ec.go#L376). The serialization happens at this point in the code: https://github.com/otrv4/ed448/blob/master/x448.go#L142
• Cofactor: The suite for 'encode_to_curve', according to https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-05#section-3 includes a function that clears the cofactor. That draft lists several possibilities for doing so. Nevertheless, the x448 function has its own way of doing so by using what is called 'scalar conditioning' or 'clamping' (https://tools.ietf.org/html/rfc7748#section-5). On the code this is done here: https://github.com/otrv4/ed448/blob/master/x448.go#L99. This makes that any point generated by 'encode_to_curve' will not need (in what I think) to be multiplied by the cofactor, because when this point will be used for an scalarMult, the scalar will be clamped. I kept this reasoning as to be complaint with RFC7748 and other implementations of x448.

I was thinking that these "findings" might be included in an appendix to both 'draft-irtf-cfrg-voprf' and 'draft-irtf-cfrg-hash-to-curve', for someone that implements curv448 in accordance with RFC7748.

About the half finished 5th task: the inside curve448 functions and curve448 'encode_to_curve' work and have been tested against https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve/tree/master/poc, https://github.com/armfazh/hash-to-curve-ref and https://sourceforge.net/projects/ed448goldilocks/. When trying to implement it for client and server as a ciphersuite, I noticed that the blind and unblind functions fail. Might be that they expect the other Point coordinate or something. This I will investigate tomorrow. Everything else works as expected.

Finally, I have the functionality for ed448 and elligator2 with it using internally decaf. I will incorporate later this week in a separate PR, as I think is out of the scope of this and this is basically done for a first iteration. What do you think?

Let me know what you think or any comments ;)

Thanks!

[alxdavids]

Awesome, I just left some feedback on the PR.

The x448 function (used for ScalarMult and scalarBaseMult in accordance to RFC7748) only returns the u coordinate of Montgomery form, while taking as input this u coordinate and the scalar. At some places, this makes it impossible to verify that a point is on the curve, as the function needs the two coordinates of the Point. That is why I have moved the validation of points in some parts of the code.

This is an interesting characteristic of x448 that I had not considered. Indeed there is room to move the validation of points around.

Cofactor: The suite for 'encode_to_curve', according to https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-05#section-3 includes a function that clears the cofactor. That draft lists several possibilities for doing so. Nevertheless, the x448 function has its own way of doing so by using what is called 'scalar conditioning' or 'clamping' (https://tools.ietf.org/html/rfc7748#section-5). On the code this is done here: https://github.com/otrv4/ed448/blob/master/x448.go#L99. This makes that any point generated by 'encode_to_curve' will not need (in what I think) to be multiplied by the cofactor, because when this point will be used for an scalarMult, the scalar will be clamped. I kept this reasoning as to be complaint with RFC7748 and other implementations of x448.

This makes sense. As I said in the PR, currently the cofactor clearance that we do is redundant also for the NIST curves. So it may be better to just indicate that the check does not need to happen in the h2cParams struct.

I was thinking that these "findings" might be included in an appendix to both 'draft-irtf-cfrg-voprf' and 'draft-irtf-cfrg-hash-to-curve', for someone that implements curv448 in accordance with RFC7748.

This is a really good idea and is really useful feedback for the VOPRF draft especially, as there is not so much work in implementing the draft until now.

About the half finished 5th task: the inside curve448 functions and curve448 'encode_to_curve' work and have been tested against https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve/tree/master/poc, https://github.com/armfazh/hash-to-curve-ref and https://sourceforge.net/projects/ed448goldilocks/. When trying to implement it for client and server as a ciphersuite, I noticed that the blind and unblind functions fail. Might be that they expect the other Point coordinate or something. This I will investigate tomorrow. Everything else works as expected.

This is interesting. It would be useful to find out what the source of the issue is, and thanks for providing this explanation.

Finally, I have the functionality for ed448 and elligator2 with it using internally decaf. I will incorporate later this week in a separate PR, as I think is out of the scope of this and this is basically done for a first iteration. What do you think?

I agree that what you have so far would be a good first iteration. Having the edwards + internal Decaf version would be great but I think that can be done in a future change.

[claucece]

Hi!

Thanks so much for the review!

This makes sense. As I said in the PR, currently the cofactor clearance that we do is redundant also for the NIST curves. So it may be better to just indicate that the check does not need to happen in the h2cParams struct.

Yeah.. I agree, should we completely delete it?

This is interesting. It would be useful to find out what the source of the issue is, and thanks for providing this explanation.

I mapped it now to be completely on the Blind and Unblind process. I was thinking that it might be that at some point a point is multiplied by r and by the inverse of r. Maybe that process with having the clearance of the cofactor inside the ScalarMult function interferes... I'll let you know when I find the cause ;)

I agree that what you have so far would be a good first iteration. Having the edwards + internal Decaf version would be great but I think that can be done in a future change.

Awesome! I'll do it for sure ;)

Thanks!

[alxdavids]

I think you've completed everything now, right @claucece? :)

[claucece]

Yes, we have! By the end of tomorrow, I will also have it on the draft ;)