oasisprotocol / ed25519 Goto Github PK

In keeping with the "drop-in replacement" design goal, there are additional forthcoming upstream changes that need to be folded in.

• proposal: x/crypto/curve25519: new X25519 API (golang/go/issues/32670)
• crypto/ed25519: reject low order points (golang/go/issues/31846)
• crypto/ed25519: Implement Ed25519ph (golang/go/issues/31804)
• crypto: add Equal(PublicKey) bool method to PublicKey implementations (golang/go/issues/21704)

32670 includes the RFC 8422 check for contributory behavior. There's some dissenting opinions about how useful this is (See section 12 of the Noise protocol spec for one).

The second issue, despite it's title at the time of this writing, applies to doing the appropriate checks in the ed25519 code.

These should wait till the relevant changes are merged upstream, support for ed25519ctx/ph was merged early because we were thinking about using it.

communicating through a global for testing is a little ugly. consider something like:

func isNeutralVartime(p *ge25519.Ge25519) bool {
  return isNeutralVartimeTestInterface(p, nil)
}
func isNeutralVartimeTestInterface(p *ge25519.Ge25519, saveBatchY []byte) bool {
  if saveBatchY != nil {
    curve25519.Contract(saveBatchY, p.Y())
  }
  ...
}

which should, if go compilers ever get that level of optimization, allow generation of an if saveBatchY-free version of the code for callsites where the isNeutralVartime is used. also, if golang testing ever changes to allow running tests concurrently (seems unlikely), this eliminates the potential debt.

Currently the batch verification only supports Ed25519pure. It would be good to support Ed25519ctx and Ed25519ph there as well. The code for doing so is trivial, writing test cases probably will take longer than implementing the variant support.

As the scalar basepoint multiply implementation is based around using a table that stores pre-computed results, a fast constant time copy is required for optimal performance.

The amd64 target has an optimized implementation written in assembly language.
All other platforms will use unsafe (falling back to subtle.ConstantTimeCopy) once #19 is merged, but could be improved further.

• Merge #19.
• Figure out which architectures are sufficiently indifferent to alignment such that the runtime library fallback never needs to be used.
• Add assembly implementations for commonly used targets.

Build tags do not seem to take into account for the Raspberry Pi. It runs on an ARM Cortex-A72 chip. Is this intended?

github.com/oasislabs/ed25519/internal/curve25519
../../go/pkg/mod/github.com/oasislabs/[email protected]/internal/curve25519/helpers.go:35:32: undefined: Bignum25519
../../go/pkg/mod/github.com/oasislabs/[email protected]/internal/curve25519/helpers.go:37:12: undefined: Bignum25519
../../go/pkg/mod/github.com/oasislabs/[email protected]/internal/curve25519/helpers.go:40:2: undefined: SquareTimes
../../go/pkg/mod/github.com/oasislabs/[email protected]/internal/curve25519/helpers.go:41:2: undefined: Mul
../../go/pkg/mod/github.com/oasislabs/[email protected]/internal/curve25519/helpers.go:42:2: undefined: SquareTimes
../../go/pkg/mod/github.com/oasislabs/[email protected]/internal/curve25519/helpers.go:43:2: undefined: Mul
../../go/pkg/mod/github.com/oasislabs/[email protected]/internal/curve25519/helpers.go:44:2: undefined: SquareTimes
../../go/pkg/mod/github.com/oasislabs/[email protected]/internal/curve25519/helpers.go:45:2: undefined: Mul
../../go/pkg/mod/github.com/oasislabs/[email protected]/internal/curve25519/helpers.go:57:20: undefined: Bignum25519
../../go/pkg/mod/github.com/oasislabs/[email protected]/internal/curve25519/helpers.go:73:31: undefined: Bignum25519
../../go/pkg/mod/github.com/oasislabs/[email protected]/internal/curve25519/helpers.go:45:2: too many errors

Note: Low priority since the one architecture that actually matters to the vast majority of people, has appropriate intrinsics, so the unsafe behavior of the fallback code never comes into play.

When the Go math/bits issues get resolved (one way or another, though I'm of the opinion that the functions should be constant time, with explicitly vartime alternatives provided separately), change the implementation to enable the 64 bit code path on more architectures.

See:

• golang/go#31229
• golang/go#31267

Description of the bug
Possibility of an infinite loop with small scalar value in function multiScalarmultVartimeFinal. It seems we should be skipping zero values and not non-zero values. At https://github.com/oasislabs/ed25519/blob/a426dcc8ad5f012f981f4acce812b0c7c1b7b625/batch_verify.go#L185

The topbit finding algorithm at L189 loops infinitely as a consequence.

Additional information
This was found on a deployed testnet in our testing environment.