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: add elligator2 mapping #62023

Open
x0wllaar opened this issue Aug 14, 2023 · 2 comments
Open

proposal: x/crypto: add elligator2 mapping #62023

x0wllaar opened this issue Aug 14, 2023 · 2 comments
Labels
Proposal Proposal-Crypto Proposal related to crypto packages or other security issues
Milestone

Comments

@x0wllaar
Copy link

x0wllaar commented Aug 14, 2023

Elligator 2 is a way to obfuscate/hide elliptic curve based key exchanges by mapping public keys into uniformly distributed byte strings and back.

As per https://elligator.org/, Elligator can also serve as a core for other cryptographic primitives, such as verifiable random functions and oblivious pseudorandom functions. It is also instrumental for working with PURBs. Other important uses for this may include implementing certain PAKE protocols, such as CPase (see page 15.)

In addition to that Elligator 2 serves as a building block for cryptographic protocols that are in widespread use, most notably for OTRv4 (off-the-record messaging protocol, https://github.com/otrv4/otrv4) and for obfs4 (https://support.torproject.org/glossary/obfs4/). These 2 protocols are notable for the fact that for both of them, well known Go implementations exist, and, as required by their specs, they also contain internal Elligator 2 implementations.
Since these implementations are internal, they a) generally fragment the ecosystem and harm code reuse, b) have less eyes on them which may lead to subtle bugs appearing in the implementations.

What follows is a small study of the Go Elligator 2 implementations in both OTRv4 (https://github.com/otrv4/ed448/blob/master/elligator.go) and in obfs4 (https://github.com/Yawning/obfs4/blob/master/internal/x25519ell2/x25519ell2.go).

OTRv4's implementation seems complete, but it uses internal data types (I guess from the type when Go's crypto was not as standardized), and is an internal package, which makes reusing it and depending on it a bad taste.

Obfs4's implementation is more closely aligned with the current Go crypto ecosystem (e.g. uses "filippo.io/edwards25519" package for key types), but still is an internal package, w/o clear versioning and compatibility guarantees, making it less reusable.

I think that adding an API for this to the x/crypto package will allow the community to better converge on a standardized (verified and tested) implementation. This will save countless hours of people reimplementing crypto code and will adhere to the DRYOC principle. It should also be noted that libraries providing Elligator exist for other languages as well. Monocypher (C) is the most notable of these, and has full support for Elligator 2. Libsodium (C + bindings to many languages) has a partial implementation (only hash to point, not the other way around).

As for the API itself (and I'm not a very experienced crypto OR Go developer, so this is the weakest part), I think that replicating parts of the Monocypher API for Elligator 2 can be a good way to go here:

package elligator

// ElligatorRev takes a public key and a tweak (must be chosen at random), 
// outputs an Elligator representative that is indistinguishable from random
// Since this does not work for all public keys, this function may fail and return an error;
// in this case, it must be tried again with a new key pair.
// 2 attempts with different keys are needed on average to obtain a representative
// Panics if k.Curve() != ecdh.X22519()
func ElligatorRev(k *ecdh.PublicKey, tweak uint8) ([]byte, error)

// ElligatorMap does the reverse of ElligatorRev.
// Given a representative r, it computes a corresponding 
// ECDH public key (using curve X22519)
func ElligatorMap(r []byte) *ecdh.PublicKey

// ElligatorKeyPair generates a private key  (using Curve25519)
// and a representative of the corresponding public key
// Note that since the function tries to generate keys and compute
// the representatives until it succeeds, its execution time may be
// undpedictable
func ElligatorKeyPair(rand io.Reader) (*ecdh.PrivateKey, []byte)

@FiloSottile, I guess, and thank you for your great work on the Go crypto packages.

@gopherbot gopherbot added this to the Proposal milestone Aug 14, 2023
@seankhliao seankhliao added the Proposal-Crypto Proposal related to crypto packages or other security issues label Aug 14, 2023
@seankhliao
Copy link
Member

cc @golang/security

@Yawning
Copy link

Yawning commented Sep 20, 2023

Obfs4's implementation is more closely aligned with the current Go crypto ecosystem (e.g. uses "filippo.io/edwards25519" package for key types), but still is an internal package, w/o clear versioning and compatibility guarantees, making it less reusable.

That implementation is not intended to be reusable, in particular because obfuscated X25519 is a mountain of foot + guns, and because it is an extremely niche thing to do.

The more common use of the mapping is to implement hash to curve (used for Ed25519 ECVRF). This only requires one direction of the mapping, and is well specified in RFC 9380.

See: https://pkg.go.dev/gitlab.com/yawning/edwards25519-extra.git@v0.0.0-20220726154925-def713fd18e4/elligator2

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Proposal Proposal-Crypto Proposal related to crypto packages or other security issues
Projects
Status: Incoming
Development

No branches or pull requests

4 participants