Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

proposal: x/crypto/ed25519: add montgomery/edwards key conversion #20504

Open
SamWhited opened this issue May 26, 2017 · 28 comments
Open

proposal: x/crypto/ed25519: add montgomery/edwards key conversion #20504

SamWhited opened this issue May 26, 2017 · 28 comments
Labels
NeedsFix Proposal-Crypto
Milestone

Comments

@SamWhited
Copy link
Member

@SamWhited SamWhited commented May 26, 2017

I would like to start building an XEd25519 implementation.
XEd25519 is a signature algorithm that is fully compatible with Ed25519. It gives you the ability to use the same key for signing and ECDH. I'd like to start by implementing the conversion between points on the equivalent Montgomery and Edwards curves in the golang.org/x/crypto/ed25519 package:

// FromMontgomery converts a montgomery private key to a twisted edwards keypair.
func FromMontgomery(mont []byte) (publicKey PublicKey, privateKey PrivateKey) {}
// ToMontgomery converts a privatekey to its montgomery form.
func (privateKey PrivateKey) ToMontgomery() (mont []byte) {}

// PublicFromMontgomery converts a montgomery public key to an edwards public key.
func PublicFromMontgomery(u []byte) PublicKey {}
func (publicKey PublicKey) ToMontgomery() {}

It is currently difficult to do this outside of the x/crypto codebase because the edwards25519 package is internal (and this is where all the subtle math that I don't want to reimplement lives). If it is not desirable to have this conversion be in the x/crypto package, an alternative might be moving the edwards25519 package up a level to make it public (and adding a comment that indiciates that the API is not stable, and maybe never will be; this feels poor though).

Open Questions

  • If accepted, maybe this should live in its own xeddsa package in case curve448 support is implemented later and we want to generalize the implementation over both curves? Or maybe this should only be for if a full xeddsa implementation (not just key conversion) is ever implemented.
  • Maybe add PublicKey and PrivateKey types to the curve25519 package and assume these are always in montgomery format? It would add a dependency loop that would have to be resolved, but might make the API nicer.
  • There is some ambiguity about the sign bit when doing the montgomery to edwards conversion; XEdDSA solves this by always setting it to zero [Jivsov], but some other scheme might do this differently; maybe we need a generic way in the API to pick the value of the sign bit. There's also a mechanism for cramming it into the signature, but I haven't thought that far ahead yet; it might be worth considering for the API implications though.

/cc @agl

@SamWhited SamWhited added this to the Unreleased milestone May 26, 2017
@dgryski
Copy link
Contributor

@dgryski dgryski commented May 26, 2017

@agl

@gopherbot
Copy link

@gopherbot gopherbot commented May 27, 2017

CL https://golang.org/cl/44334 mentions this issue.

@agl
Copy link
Contributor

@agl agl commented Jun 2, 2017

The linked CL is marked DNR so I won't look too closely, but I think those functions could reasonably go into the ed25519 package.

@SamWhited
Copy link
Member Author

@SamWhited SamWhited commented Jun 2, 2017

@agl I didn't want people to review it too closely until we'd had a chance to chat about the API and what fits where, but the little bit that's there which I started as an experiment does work. How do you feel about the "Open questions" above (or the API in general)?

@rsc rsc changed the title proposal: add XEd25519 implementation to x/crypto/ed25519 x/crypto/ed25519: add XEd25519 implementation Jun 5, 2017
@rsc
Copy link
Contributor

@rsc rsc commented Jun 5, 2017

Marked as accepted, leaving @agl and @SamWhited to work out details.

@gtank
Copy link
Contributor

@gtank gtank commented Jun 6, 2017

Relatedly, I'm seeing more and more projects built on the ed25519 curve as a general group setting [1][2][3]. I needed interoperability with magic-wormhole for another project of mine, and thus recently wrote a version of ed25519 (using @agl's internal field math) that satisfies the elliptic.Curve interface: https://github.com/gtank/ed25519

How would you all feel about exposing an ed25519 Curve? For example, lifting the field operations and a group interface into x/crypto/edwards25519 like the partial interface at x/crypto/curve255519 and leaving the actual (VX)?EdDSA signature schemes in an x/crypto/eddsa package?

@SamWhited
Copy link
Member Author

@SamWhited SamWhited commented Jun 8, 2017

How would you all feel about exposing an ed25519 Curve?

I would also find this useful, but if I understand what you're proposing it's orthogonal to this issue.

and leaving the actual (VX)?EdDSA signature schemes in an x/crypto/eddsa package

I also think this would be sensible, but I'd rather not have the scope of this proposal creep into reworking the ed25519/curve25519 packages to fit the more standard interface or to creating a full eddsa package. If AGL wants that to be done though, this proposal could surely wait for that API to exist first.

@SamWhited SamWhited changed the title x/crypto/ed25519: add XEd25519 implementation x/crypto/ed25519: add montgomery/edwards key conversion Jun 15, 2017
@SamWhited
Copy link
Member Author

@SamWhited SamWhited commented Aug 28, 2017

@agl ping, the open questions could still use your consideration. If this isn't something you want to do or have time for, I will close this for now since I'm done with the project I needed it for. Let me know; thanks!

@agl
Copy link
Contributor

@agl agl commented Aug 29, 2017

I'm afraid this is fairly far down my Go tasks for 1.10 and unlikely to happen if people are waiting for me to do it.

@SamWhited
Copy link
Member Author

@SamWhited SamWhited commented Aug 29, 2017

@agl I'm happy to do the work, I just want to make sure the API is something you're comfortable with.

@leslie-wang
Copy link

@leslie-wang leslie-wang commented May 5, 2018

Is there any progress on this issue? It would be very useful if this package can provide this function.

@FiloSottile FiloSottile added the Proposal-Crypto label May 5, 2018
@ALTree ALTree removed the Proposal label Sep 22, 2018
@mikedanese
Copy link
Contributor

@mikedanese mikedanese commented Oct 3, 2018

Private key conversion from curve25519 to ed25519 is not possible since the private scalar of curve 25519 is an intermediate value of computing the signature generated by applying SHA512 as KDF to the ed25519 private key:

https://github.com/golang/crypto/blob/master/ed25519/ed25519.go#L130-L135
https://tools.ietf.org/html/rfc8032#section-5.1.6

ToMontgomery would be more useful if you want to use the same keys for signing and ECDH. It looks like the proposed change only implements FromMontgomery:

https://go-review.googlesource.com/c/crypto/+/44334

@dtitov
Copy link

@dtitov dtitov commented Feb 13, 2020

Is there any progress on this? I'm looking for the functionality like this: https://libsodium.gitbook.io/doc/advanced/ed25519-curve25519

@dtitov
Copy link

@dtitov dtitov commented Feb 13, 2020

I have also found an implementation here: https://godoc.org/github.com/agl/ed25519/extra25519

@riobard
Copy link

@riobard riobard commented Feb 25, 2020

@FiloSottile Since age has this internal function to convert from ed25519 to x25519 public key as well, is it possible for you to take over the issue so we could rely on x/crypto instead of copying code?

Meanwhile, @agl's extra25519 has implemented Elligator 2 to generate x25519 public keys with uniform representatives. The process also involves conversion from ed25519 to x25519. Unfortunately @agl's blog post endings did not show (much?) confidence in the implementation.

Having public keys with uniform representatives is very useful. If possible could we have this ability in x/crypto as well? Or should I open a separate issue for this?

@FiloSottile
Copy link
Contributor

@FiloSottile FiloSottile commented Feb 25, 2020

Having public keys with uniform representatives is very useful. If possible could we have this ability in x/crypto as well? Or should I open a separate issue for this?

That's definitely a separate issue, and I would strongly recommend ristretto255 for that use case.

@riobard
Copy link

@riobard riobard commented Feb 25, 2020

@FiloSottile Thanks for the suggestion! Would you recommend https://github.com/gtank/ristretto255 or something else for now? The API is a bit low-level (like edwards25519) and scaring for non-cryptographers to use.

@FiloSottile
Copy link
Contributor

@FiloSottile FiloSottile commented Feb 25, 2020

@riobard
Copy link

@riobard riobard commented Feb 25, 2020

@FiloSottile Great! Filippo-approved crypto is highly appreciated! :)

@jorrizza
Copy link

@jorrizza jorrizza commented Feb 27, 2020

Especially now @agl has removed github.com/agl/ed25519/extra25519, there is no "easy", clear way for non-cryptographers like me to convert Ed25519 keys to Curve25519. It would be extremely useful, for example with golang.org/x/crypto/nacl/box and golang.org/x/crypto/nacl/sign using the same Ed25519 key, like libsodium does. Wouldn't it make sense to add the key conversion to golang.org/x/crypto/nacl instead?

@jorrizza
Copy link

@jorrizza jorrizza commented Nov 6, 2020

I have created github.com/jorrizza/ed2curve25519 as a stop-gap solution for this. It is 100% compatible with libsodium as far as I have been able to test.

@thomas-maurice
Copy link

@thomas-maurice thomas-maurice commented Jun 30, 2021

Is there any updates on this issue ? :)

@cryptix
Copy link

@cryptix cryptix commented Jul 1, 2021

I took the alternative route and moved to a fork of golang.org/x/crypto where I moved edwards25519 out of the internal namespace, so that I can use the key conversion functions with that instead of the old and unmaintained curve code.

Having to replace x/crypto in all the modules that import my library is quite annoying, tho and keeping the fork up to date also isn't optimal either.

@FiloSottile
Copy link
Contributor

@FiloSottile FiloSottile commented Jul 3, 2021

I know it's been a long time coming, but I have finally set up a way to use the internal edwards25519 package without forking: the filippo.io/edwards25519 module. 🎉 It's not officially maintained by the Go team, but it's the same code as crypto/ed25519/internal/edwards25519 from Go 1.17. It also has a much safer API than github.com/agl/ed25519 or the old crypto/ed25519/internal/edwards25519, and I encourage anything in the ecosystem that needs low-level edwards25519 operations to use it. It accepts PRs for extra functionality even if it's not necessary to the standard library (and that code doesn't get upstreamed).

Case in point, there is a Point.BytesMontgomery method that does the edwards25519 to Curve25519 conversion. There isn't anything to go the other way around because for each Curve25519 encoding there are two edwards25519 points, and there isn't a standard way to choose one. github.com/agl/ed25519/extra25519 and libsodium also only go from edwards25519 to Curve25519.

This is not the same API as Private/PublicKeyToCurve25519 because it operates at the curve level, not at the Ed25519 level. That means it doesn't do the encoding and clamping steps, however it does all the arcane math that would otherwise require math/big or an edwards25519 fork. I'm unsure where the higher level APIs belong. Maybe github.com/jorrizza/ed2curve25519 should switch to filippo.io/edwards25519 as a backend and that's it. Maybe they can go in a Point.BytesMontgomery example.

Anyway, this is now addressed out-of-tree and given how low-level and not necessarily safe this operation is, I think that's the appropriate place for it. Feel free to open an issue at github.com/FiloSottile/edwards25519 if there's anything that can be improved there.

@SamWhited
Copy link
Member Author

@SamWhited SamWhited commented Jul 3, 2021

I would like to request that this issue remain open. While I do appreciate you pulling this out, it is, as you pointed out, not maintained by the Go team (in full) and can't be used in projects that require standard library and subrepos only (like Go itself) and the original issue is about doing something in the subrepos, otherwise I would have just pulled it out myself.

@SamWhited SamWhited reopened this Jul 3, 2021
@FiloSottile
Copy link
Contributor

@FiloSottile FiloSottile commented Jul 3, 2021

Fair enough, happy to put this through the proposal process again then. My general feeling is that this is a lower level operation than what belongs in the standard library, and there isn’t a standard safe way to use it or a common high level protocol that requires it.

What’s the API you’d like to propose? For what package? The one in the description won’t work: converting from a Curve25519 private key is impossible because the Ed25519 one is a hash preimage, and converting from a Curve25519 public key yields two keys. Are you sure you need both directions?

@FiloSottile FiloSottile changed the title x/crypto/ed25519: add montgomery/edwards key conversion proposal: x/crypto/ed25519: add montgomery/edwards key conversion Jul 3, 2021
@SamWhited
Copy link
Member Author

@SamWhited SamWhited commented Jul 3, 2021

It's been a while since I've looked at this, but I think what I needed for the project at the time (since abandoned, but if this were ever solved I'd be able to pick it back up again) was the montgomery to edwards direction. Which sign bit to use is an open question. XEd25519 always sets it to zero if I recall correctly, but I'd need to read up on it to remember why. It may make sense to have an argument to pick which sign you want or return both. I'll try to read back up on it and remember the details.

@FiloSottile
Copy link
Contributor

@FiloSottile FiloSottile commented Jul 5, 2021

XEd25519 is not just a way to convert Curve25519 keys to RFC 8032 keys, that's impossible. What they do is define a new signature algorithm that uses a different key format which can be converted to. (Recent relevant exchange on Twitter.) If that's what you want, you'll also need new signature APIs, which will be a hard sell for the standard library.

To me, it feels like another point in favor of having this advanced functionality implemented in higher-level third-party modules that provide a specific protocol that uses it, like an XEd25519 package.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
NeedsFix Proposal-Crypto
Projects
None yet
Development

No branches or pull requests