proposal: x/crypto: add elligator2 mapping

[x0wllaar]

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.

[seankhliao]

cc @golang/security

[Yawning]

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