ed25519

README

ed25519 - Optimized ed25519 for Go

This package provides a drop-in replacement for golang.org/x/crypto/ed25519 with the aim to improve performance, primarily on systems with a low cost 64 bit x 64 bit = 128 bit multiply operation.

This implementation is derived from Andrew Moon's ed25519-donna, and is intended to be timing side-channel safe on most architectures.

Compilation requires Go 1.12 or later due to required runtime library functionality.

Features

• Faster Ed25519 key generation, signing and verification.
• Batch signature verification.
• Faster X25519 key generation (extra/x25519).
• Support for RFC 8032 Ed25519ph, Ed25519ctx.

Benchmarks

Comparisons between this package, golang.org/x/crypto/ed25519, and golang.org/x/crypto/curve25519. Numbers taken on a i7-8550U CPU (@ 1.80GHz) with hyper-threading and Turbo Boost disabled.

benchmark                    old ns/op     new ns/op     delta
BenchmarkKeyGeneration-4     101526        45700         -54.99%
BenchmarkSigning-4           103660        47647         -54.04%
BenchmarkVerification-4      275115        163693        -40.50%

BenchmarkScalarBaseMult-4    80279         44429         -44.66%   (X25519)

Batch verification on the same system takes approximately 5082764 ns to process a 64 signature batch using the crypto/rand entropy source for roughly 79418 ns per signature in the batch.

Notes

Most of the actual implementation is hidden in internal subpackages. As far as reasonable, the implementation strives to be true to the original, which results in a slightly un-idiomatic coding style, but hopefully aids in auditability.

While there are other implementations that could have been used for the base of this project, ed25519-donna was chosen due to its maturity and the author's familiarity with the codebase. The goal of this project is not to be a general purpose library for doing various things with this curve, and is more centered around "do common things reasonably fast".

The following issues currently limit performance:

• (All) The Go compiler's inliner gives up way too early, resulting in a lot of uneeded function call overhead.

• (All 64 bit, except amd64, arm64, ppc64, ppc64le) Not enough of the math/bits calls have SSA intrinsic special cases. For the 64 bit codepath to be safe and performant both bits.Add64 and bits.Mul64 need to be constant time, and fast.

  See go/src/cmd/compile/internal/gc/ssa.go.

• (All, except amd64) Key generation and signing performance will be hampered by the way subtle.ConstantTimeCopy is re-implemented for better performance. This is easy to fix on a per-architecture basis. See internal/ge25519/movecond_[slow,unsafe].go.

• (amd64) This could use a bigger table, AVX2, etc for even more performance.

While sanitizing sensitive values from memory is regarded as good practice, Go as currently implemented and specified makes this impossible to do reliably for several reasons:

• The runtime can/will make copies of stack-allocated objects if the stack needs to be grown.

• There is no memset_s/explicit_bzero equivalent provided by the runtime library (though Go up to and including 1.13.1 will not optimize out the existing sanitization code).

• The runtime library's SHA-512 implementation's Reset() method does not actually clear the buffer, and calculating the digest via Sum() creates a copy of the buffer.

This implementation makes some attempts at sanitization, however this process is fragile, and does not currently work in certain locations due to one or more of the stated reasons.

TODO

• Wait for the compiler to inline functions more intelligently.
• Wait for the compiler to provide math/bits SSA special cases on more architectures.
• Figure out solutions for speeding up the constant time table lookup on architectures where the fallback code path is used.

Documentation

Overview

Package ed25519 implements the Ed25519 signature algorithm. See https://ed25519.cr.yp.to/.

These functions are also compatible with the “Ed25519” function defined in RFC 8032. However, unlike RFC 8032's formulation, this package's private key representation includes a public key suffix to make multiple signing operations with the same key more efficient. This package refers to the RFC 8032 private key as the “seed”.

Index

• Constants
• func GenerateKey(rand io.Reader) (PublicKey, PrivateKey, error)
• func Sign(privateKey PrivateKey, message []byte) []byte
• func Verify(publicKey PublicKey, message, sig []byte) bool
• func VerifyBatch(rand io.Reader, publicKeys []PublicKey, messages, sigs [][]byte, opts *Options) (bool, []bool, error)
• func VerifyWithOptions(publicKey PublicKey, message, sig []byte, opts *Options) bool
• type Options
  • func (opt *Options) HashFunc() crypto.Hash
• type PrivateKey
  • func NewKeyFromSeed(seed []byte) PrivateKey
  • func (priv PrivateKey) Public() crypto.PublicKey
  • func (priv PrivateKey) Seed() []byte
  • func (priv PrivateKey) Sign(rand io.Reader, message []byte, opts crypto.SignerOpts) (signature []byte, err error)
• type PublicKey

Constants

const (
	// PublicKeySize is the size, in bytes, of public keys as used in this package.
	PublicKeySize = 32

	// PrivateKeySize is the size, in bytes, of private keys as used in this package.
	PrivateKeySize = 64

	// SignatureSize is the size, in bytes, of signatures generated and verified by this package.
	SignatureSize = 64

	// SeedSize is the size, in bytes, of private key seeds. These are the private key representations used by RFC 8032.
	SeedSize = 32

	// ContextMaxSize is the maximum allowed context length for Ed25519ctx.
	ContextMaxSize = 255
)

Functions

func GenerateKey

func GenerateKey(rand io.Reader) (PublicKey, PrivateKey, error)

GenerateKey generates a public/private key pair using entropy from rand. If rand is nil, crypto/rand.Reader will be used.

func Sign

func Sign(privateKey PrivateKey, message []byte) []byte

Sign signs the message with privateKey and returns a signature. It will panic if len(privateKey) is not PrivateKeySize.

func Verify

func Verify(publicKey PublicKey, message, sig []byte) bool

Verify reports whether sig is a valid signature of message by publicKey. It will panic if len(publicKey) is not PublicKeySize.

func VerifyBatch

func VerifyBatch(rand io.Reader, publicKeys []PublicKey, messages, sigs [][]byte, opts *Options) (bool, []bool, error)

VerifyBatch reports whether sigs are valid signatures of messages by publicKeys, using entropy from rand. If rand is nil, crypto/rand.Reader will be used. For convenience, the function will return true iff every single signature is valid.

Note: Unlike VerifyWithOptions, this routine will not panic on malformed inputs in the batch, and instead just mark the particular signature as having failed verification.

func VerifyWithOptions

func VerifyWithOptions(publicKey PublicKey, message, sig []byte, opts *Options) bool

VerifyWithOptions reports whether sig is a valid Ed25519 signature by publicKey with the extra Options to support Ed25519ph (pre-hashed by SHA-512) or Ed25519ctx (includes a domain separation context). It will panic if len(publicKey) is not PublicKeySize, len(message) is not sha512.Size (if pre-hashed), or len(opts.Context) is greater than ContextMaxSize.

Types

type Options

type Options struct {
	// Hash can be crypto.Hash(0) for Ed25519/Ed25519ctx, or crypto.SHA512
	// for Ed25519ph.
	Hash crypto.Hash

	// Context is an optional domain separation context for Ed25519ph and
	// Ed25519ctx. It must be less than or equal to ContextMaxSize
	// in length.
	//
	// Warning: If Hash is crypto.Hash(0) and Context is a zero length
	// string, plain Ed25519 will be used instead of Ed25519ctx.
	Context string
}

Options can be used with PrivateKey.Sign or VerifyWithOptions to select Ed25519 variants.

func (*Options) HashFunc

func (opt *Options) HashFunc() crypto.Hash

HashFunc returns an identifier for the hash function used to produce the message pased to Signer.Sign. For the Ed25519 family this must be crypto.Hash(0) for Ed25519/Ed25519ctx, or crypto.SHA512 for Ed25519ph.

type PrivateKey

type PrivateKey []byte

PrivateKey is the type of Ed25519 private keys. It implements crypto.Signer.

func NewKeyFromSeed

func NewKeyFromSeed(seed []byte) PrivateKey

NewKeyFromSeed calculates a private key from a seed. It will panic if len(seed) is not SeedSize. This function is provided for interoperability with RFC 8032. RFC 8032's private keys correspond to seeds in this package.

func (PrivateKey) Public

func (priv PrivateKey) Public() crypto.PublicKey

Public returns the PublicKey corresponding to priv.

func (PrivateKey) Seed

func (priv PrivateKey) Seed() []byte

Seed returns the private key seed corresponding to priv. It is provided for interoperability with RFC 8032. RFC 8032's private keys correspond to seeds in this package.

func (PrivateKey) Sign

func (priv PrivateKey) Sign(rand io.Reader, message []byte, opts crypto.SignerOpts) (signature []byte, err error)

Sign signs the given message with priv. rand is ignored. If opts.HashFunc() is crypto.SHA512, the pre-hashed variant Ed25519ph is used and message is expected to be a SHA-512 hash, otherwise opts.HashFunc() must be crypto.Hash(0) and the message must not be hashed, as Ed25519 performs two passes over messages to be signed.

type PublicKey

type PublicKey []byte

PublicKey is the type of Ed25519 public keys.