search

alxdavids / voprf-poc

Proof-of-concept implementation of the (V)OPRF protocol in https://datatracker.ietf.org/doc/draft-irtf-cfrg-voprf/
23 stars 8 forks source link

Implement curve448 #12

Closed claucece closed 4 years ago

claucece commented 4 years ago

Implementing curve448 functionality.

alxdavids commented 4 years ago

Hey @claucece! Did you get a chance to take a look at the remaining issues with this PR? I would be happy to take a stab at completing it, if that would be alright with you?

claucece commented 4 years ago

Hi, @alxdavids !

I will solve the conflicting files on the weekend. I kept working on the issue that was remaining with some tests but I couldn't find why. So, I started an implementation with 25519 (https://github.com/claucece/voprf-poc-x25519) to see if it is a problem with the cofactor of those curves. I'll finish it off on the weekend and let you know if I found anything ;)

alxdavids commented 4 years ago

Great! Let me know if you hit any issues regarding the changes that have been made recently.

claucece commented 4 years ago

Hi, @alxdavids !

I resolved all the conflicts! ;)

But, even with the new library from @armfazh .. the process of blind and unblind with curve448 stills fails, and it still surprises me. Maybe we can check it together?

Thanks!

claucece commented 4 years ago

So, I also just finished an implementation using 25519 and the built-in golang functions of it: https://github.com/claucece/voprf-poc-x25519/commits/master It fails on the blind and unblind, as curve448, so it might be something missing with these kind of curves.... I will keep looking over the week.

alxdavids commented 4 years ago

@claucece Hmmm that is puzzling, I will also try taking a look at the branches and see if I can find what the issue is. Thanks for investigating with 25519, that should be helpful in finding the root cause!

alxdavids commented 4 years ago

@claucece It seems that ScalarMult is producing points that are no longer valid? For example at https://github.com/claucece/voprf-poc/blob/master/go/oprf/oprf.go#L261 if you insert an IsValid() check it returns true on T. However, after you create P by running ScalarMult() this check no longer passes. On closer inspection, it seems that the point T has both an x and a y coordinate, but after performing scalar multiplication the y coordinate is set to 0. I'm not exactly familiar with how IsOnCurve works for Curve448, but it seems like these points where y = 0 do not pass the check?

Perhaps the test is failing because on unblinding, the point that is recovered has a 0 y-coordinate, whereas the comparison point is the result of EnclodeToGroup(), which has non-zero y coordinate?

claucece commented 4 years ago

Hi, @alxdavids ! Thanks so much for reviewing! ;)

So, ScalarMult as defined in RFC7748 for Montgomery form for curve 448, defines that only the coordinate u is the result of the operation (https://tools.ietf.org/html/rfc7748#section-5). In order to be compatible with this implementation (with the interface), I still keep the v coordinate but I set it to zero, as there is no v coordinate as a result of x448 function. I call the u coordinate x, and the v coordinate y to be compatible.

I'll check why the P fails on the validation ;)

armfazh commented 4 years ago

Both coordinates are needed for the protocol. So using Montgomery ladder (as in RFC7748), will only calculate the x coordinate. However, y can be recovered, see Alg.5 of ia.cr/2017/212. Alternatively, you can calculate scalar multiplication using projective coordinates, or calculating the multiplication in Edwards and then convert to Montgomery.

alxdavids commented 4 years ago

Both coordinates are needed for the protocol.

This makes sense Armando, so it sounds like it should be a relatively straightforward fix, just depends where we want to implement it. We use the same curve interface for curve448 in this repo, so it may need to happen in the underlying package. What do you think @claucece?

claucece commented 4 years ago

Hi, @armfazh and @alxdavids !

I already have the edwards multiplication on the curve448 package so I will do that over there and push it ;)

Thanks so much!

claucece commented 4 years ago

also, maybe this plus the other recommendations will be nice to be added to the privacy pass document.. I can make something and create a pull request for it.. what do you thin @alxdavids ?

alxdavids commented 4 years ago

also, maybe this plus the other recommendations will be nice to be added to the privacy pass document.. I can make something and create a pull request for it.. what do you thin @alxdavids ?

This would be very useful, thanks!!

claucece commented 4 years ago

Hi, @alxdavids ! Just to give you an update: I'm implementing now with projective coordinates and adding a section to the document ;) I should have all by next Monday.. hope that is ok ;)

claucece commented 4 years ago

Hi, @alxdavids , sorry for not pushing but I found a bug on the ed448 library that I'm solving. I'm also reviewing the privacy pass drafts, so once I have all of that, I'll send it along the mailing list ;)

alxdavids commented 4 years ago

Hi, @alxdavids , sorry for not pushing but I found a bug on the ed448 library that I'm solving. I'm also reviewing the privacy pass drafts, so once I have all of that, I'll send it along the mailing list ;)

No problem! Thanks for the update and also for taking the time to review the Privacy Pass drafts 👍

claucece commented 4 years ago

Hi, @alxdavids !

It is done ;) Now, it works perfectly. The scalarmult is now using the double and add method. I might implement it with jacobian in the future to make it safer.

One small question I have:

There is a function that serializes the point into a byte array. In the case for curve448, I'm following RFC7748 and serializing only the u coordinate. But idk, if that is ok...

armfazh commented 4 years ago

There is a function that serializes the point into a byte array. In the case for curve448, I'm following RFC7748 and serializing only the u coordinate. But idk, if that is ok...

Look at RFC8032, there are defined encoding/decoding functions.

alxdavids commented 4 years ago

For point serialization we'll probably need to use the method here: https://tools.ietf.org/html/rfc8032#section-5.2.2, that Armando mentions. Does this fit with what you do already?

claucece commented 4 years ago

For sure, I will implement that! The only difference between RFC8032 and what is there is that RFC8032 determines a point as a 57-octet string, while here it is 56, following the montgomery standards. But I will tweak it ;)

claucece commented 4 years ago

After thinking about this further:

It depends on what you want it to be compatible with.

Following RFC8032, will be on the edwards form of the curve, while here it has been used the Montgomery form, following the privacy draft. This is ok, as the Montgomery can be transformed to Edwards and be encoded as such.

The second thing that can be done is to encode as RFC7748 specifies: 

   The u-coordinates are elements of the underlying field GF(2^255 - 19)
   or GF(2^448 - 2^224 - 1) and are encoded as an array of bytes, u, in
   little-endian order such that u[0] + 256*u[1] + 256^2*u[2] + ... +
   256^(n-1)*u[n-1] is congruent to the value modulo p and u[n-1] is
   minimal.  When receiving such an array, implementations of X25519
   (but not X448) MUST mask the most significant bit in the final byte.
   This is done to preserve compatibility with point formats that
   reserve the sign bit for use in other protocols and to increase
   resistance to implementation fingerprinting.

So, it depends from an API level on how a point will be sent and how it will be handled.

claucece commented 4 years ago

Hi, @alxdavids !

All is solved now and working.

I'll make a new pull request with the serialization.

Thanks!

claucece commented 4 years ago

Hi, @alxdavids !

I'll submit a new pull request with something else as well: the library h2c-go-ref from @armfazh is outdated here, and go mod is unable to update them due to some invalid chars on some file names (https://github.com/golang/go/issues/28001). If you run GOPROXY=direct GOSUMDB=off go get -v github.com/armfazh/h2c-go-ref, you will see it. I will summit a pull request to https://github.com/armfazh/h2c-go-ref, as well, if you are ok with me changing that char to -.

I'm adding some test vectors as well, that I'll send as part of the new PR.

alxdavids commented 4 years ago

Hi, @alxdavids !

All is solved now and working.

I'll make a new pull request with the serialization.

Thanks!

Awesome!! 💯 I'll merge now

Hi, @alxdavids !

I'll submit a new pull request with something else as well: the library h2c-go-ref from @armfazh is outdated here, and go mod is unable to update them due to some invalid chars on some file names (golang/go#28001). If you run GOPROXY=direct GOSUMDB=off go get -v github.com/armfazh/h2c-go-ref, you will see it. I will summit a pull request to https://github.com/armfazh/h2c-go-ref, as well, if you are ok with me changing that char to -.

I'm adding some test vectors as well, that I'll send as part of the new PR.

That sounds like a good idea to me, please do submit a PR! @armfazh is the person in charge of that particular repo.