proposal: x/crypto/curve25519: new X25519 API

[FiloSottile]

Current API

func ScalarBaseMult(dst, in *[32]byte)
func ScalarMult(dst, in, base *[32]byte)

The names are the same as the elliptic.Curve methods, but with different function signatures.

The main issue with the current API is that there is no way to return an error from ScalarMult for low order inputs, which are a serious problem in certain protocols.

See #31846 and the linked paper, where it was only the Go implementations that were actually exploitable, due to our lack of safety checks, which is the opposite of what we want to achieve.

Proposed API

package curve25519

// Basepoint is the canonical Curve25519 generator.
var Basepoint []byte

// X25519 returns the result of the scalar multiplication (scalar * point),
// according to RFC 7748, Section 5. scalar, point and the return value
// are slices of 32 bytes.
//
// If point is Basepoint (but not if it's a different slice with the same contents)
// a precomputed implementation might be used to speed up the computation.
func X25519(scalar, point []byte) ([]byte, error)

X25519 is the name of the function as specified in RFC 7748.

Basepoint is identified by slice equality (as opposed to bytes.Equal) to avoid a timing side-channel when the point might or might not be the basepoint.

The implementation of X25519 would just check if point == Basepoint, and invoke the ScalarBaseMult or ScalarMult implementation (the latter followed by the missing check).

Why slices

There is a split in Go crypto APIs between slices (like ed25519) and array pointers (like curve25519). Both have their advantages, but over time I decided I prefer slices: arrays require a new variable and a copy at most uses, and I often saw bugs due to making short copies into the array.

var dst, scalar [32]byte
copy(scalar[:], inputShorterThan32)
curve25519.ScalarBaseMult(&dst, &scalar)

So while type safety is nice, the failure mode of arrays in practice is worse. Slices cause an error at runtime, but if the code is ever tested, that condition should be caught more easily than the example above.

Open questions

Should we have Scalar []byte and Point []byte types to prevent mixing up scalar and point arguments?

Does this function always allocate, or will inliner and escape analysis be able to figure out that if the return value is quickly disposed of it can live on the stack?

Should we deprecate the unsafe ScalarMult in favor of X25519? For most uses of ScalarMult the unsafe corner-case doesn't really matter, but on the other hand most common uses will be in other standard or x/crypto packages. If an application uses it directly, they might be doing something complex where low-order points matter.

Considered alternatives

Adding an error

This package lives in curve25519, so we could add an error return value to ScalarMult. Since it currently doesn't have a return value, it would be a fairly low impact.

The problem is indeed that it would probably go unnoticed for existing code.

Adding a check function

The unsafe inputs generate recognizable results, so we could add a CheckOutput(p []byte) error function.

This is the opposite of secure by default.

Replacing only ScalarMult

We could just deprecate ScalarMult and replace it with an identical function with an error return value.

I could honestly not think of a good name, and it seemed like a good opportunity to switch to slices and the naming of the RFC.

/cc @agl @rsc

[FiloSottile]

Discussed with @rsc, comments inline.

Should we have Scalar []byte and Point []byte types to prevent mixing up scalar and point arguments?

This wouldn't be very useful, as unnamed types and equivalent named types don't conflict.

Does this function always allocate, or will inliner and escape analysis be able to figure out that if the return value is quickly disposed of it can live on the stack?

It should be possible to write it such that it does not allocate. Will write an experiment and a test.

Should we deprecate the unsafe ScalarMult in favor of X25519?

Deprecation for ScalarMult, just a note for ScalarBaseMult.

[tv42]

Basepoint is identified by slice equality (as opposed to bytes.Equal) to avoid a timing side-channel when the point might or might not be the basepoint.

The implementation of X25519 would just check if point == Basepoint, [...]

https://golang.org/ref/spec says

Slice, map, and function values are not comparable.

Perhaps you need to say len(point) == len(Basepoint) && &point[0] == &Basepoint[0] or some such.

[FiloSottile]

Good point, but we can compare the pointer to the beginning of the slice.

https://play.golang.org/p/oz9-ed0R86Y

[tv42]

I'd really suggest comparing the len too. Basepoint[:2] would be pretty confusing otherwise.

[FiloSottile]

The inliner trick is working. For example in the following code, the main() function does not allocate dst on the heap.

package main

import (
	"crypto/subtle"
	"errors"

	"golang.org/x/crypto/curve25519"
)

func main() {
	scalar, point := make([]byte, 32), make([]byte, 32)
	res, err := X25519(scalar, point)
	if err != nil {
		panic(err)
	}
	println(res)
}

func X25519(scalar, point []byte) ([]byte, error) {
	var dst [32]byte
	return x25519(&dst, scalar, point)
}

func x25519(dst *[32]byte, scalar, point []byte) ([]byte, error) {
	var in, base, zero [32]byte
	if len(scalar) != 32 {
		return nil, errors.New("bad scalar length")
	}
	if len(point) != 32 {
		return nil, errors.New("bad point length")
	}
	copy(in[:], scalar)
	copy(base[:], point)
	curve25519.ScalarMult(dst, &in, &base)
	if subtle.ConstantTimeCompare(dst[:], zero[:]) == 1 {
		return nil, errors.New("bad input")
	}
	return dst[:], nil
}

[FiloSottile]

This seems like a good path forward. Going to keep this open for another week and then consider the proposal accepted.

[FiloSottile]

A week has passed, accepting this proposal.

While at it, we should also add an example of a DH flow, and a lot of docs. I used the current curve255219 package this weekend and it was not a good experience.

[gertcuykens]

This is way out of my league so I depend on the mercy of examples how to DH a secret key from point a to b using X25519

[gertcuykens]

PS This other package looks excellent to me? https://godoc.org/github.com/aead/ecdh

[gopherbot]

Change https://golang.org/cl/205157 mentions this issue: curve25519: implement new X25519 API

[gopherbot]

Change https://golang.org/cl/205158 mentions this issue: curve25519: implement new X25519 API