x/crypto/curve25519: pure Go implementation mismatch with BoringSSL

[mmcloughlin]

I believe there is a bug in the pure Go implementation of curve25519. Comparison between the pure Go and assembly implementations demonstrated a mismatch. Further testing showed that the pure Go version fails test vectors generated with BoringSSL. Full details are in the mmcloughlin/bug25519 repository, but the salient points are below.

Problem

BoringSSL test vectors pass on the amd64 architecture (assembly implementation):

$ go version
go version go1.11 darwin/amd64
$ go test -v -run Current
=== RUN   TestTestVectorsCurrent
--- PASS: TestTestVectorsCurrent (0.00s)
    testvectors_test.go:47: failed 0 of 32
PASS
ok  	github.com/mmcloughlin/bug25519	0.006s

However the pure Go version does not (induced with the appengine tag)

$ go test -v -run Current -tags appengine | head
=== RUN   TestTestVectorsCurrent
--- FAIL: TestTestVectorsCurrent (0.01s)
    testvectors_test.go:39:     in = 668fb9f76ad971c81ac900071a1560bce2ca00cac7e67af99348913761434014
    testvectors_test.go:40:   base = db5f32b7f841e7a1a00968effded12735fc47a3eb13b579aacadeae80939a7dd
    testvectors_test.go:41:    got = 78202e24db99e237f2a14f9ec61b051814ec8fd23a5e8e68add48d66fd09fc12
    testvectors_test.go:42: expect = 090d85e599ea8e2beeb61304d37be10ec5c905f9927d32f42a9a0afb3e0b4074
    testvectors_test.go:39:     in = 203161c3159a876a2beaec29d2427fb0c7c30d382cd013d27cc3d393db0daf6f
    testvectors_test.go:40:   base = 6ab95d1abe68c09b005c3db9042cc91ac849f7e94a2a4a9b893678970b7b95bf
    testvectors_test.go:41:    got = 2ec45ca394a3febc6d63b8995ae63b38c7ba909bafed2a039dd54973f2b5be73
    testvectors_test.go:42: expect = 11edaedc95ff78f563a1c8f15591c071dea092b4d7ecaac8e0387b5a160c4e5d

Approximately half of the test vectors fail.

Fix

Comparison of the individual fe*() functions against the ref10 implementation suggests the problem is in feFromBytes(). By eye we see the Go implementation is missing a mask. The following patch appears to fix the problem.

diff --git a/curve25519/curve25519.go b/curve25519/curve25519.go
index cb8fbc5..75f24ba 100644
--- a/curve25519/curve25519.go
+++ b/curve25519/curve25519.go
@@ -86,7 +86,7 @@ func feFromBytes(dst *fieldElement, src *[32]byte) {
        h6 := load3(src[20:]) << 7
        h7 := load3(src[23:]) << 5
        h8 := load3(src[26:]) << 4
-       h9 := load3(src[29:]) << 2
+       h9 := (load3(src[29:]) & 0x7fffff) << 2

        var carry [10]int64
        carry[9] = (h9 + 1<<24) >> 25

See the corresponding line in the reference implementation. Note also that RFC 7748 specifies:

   The u-coordinates are elements of the underlying field GF(2^255 - 19)
   or GF(2^448 - 2^224 - 1) and are encoded as an array of bytes, u, in
   little-endian order such that u[0] + 256*u[1] + 256^2*u[2] + ... +
   256^(n-1)*u[n-1] is congruent to the value modulo p and u[n-1] is
   minimal.  When receiving such an array, implementations of X25519
   (but not X448) MUST mask the most significant bit in the final byte.
   This is done to preserve compatibility with point formats that
   reserve the sign bit for use in other protocols and to increase
   resistance to implementation fingerprinting.

[gopherbot]

Change https://golang.org/cl/161257 mentions this issue: curve25519: mask high bit when loading group point

[gopherbot]

Change https://golang.org/cl/161277 mentions this issue: curve25519: add testvectors from boringssl

[dgryski]

@FiloSottile

[josharian]

Re-opening this as a reminder to update the version vendored into the standard library. @FiloSottile is it ok to wait for 1.13 for that or does it need to happen in 1.12?

[FiloSottile]

Let's do it in 1.13, there seems to be no security implication.

[FiloSottile]

This got imported in Go 1.13.

go/src/vendor/golang.org/x/crypto/curve25519/curve25519.go

Line 89 in 09c9bce

h9 := (load3(src[29:]) & 0x7fffff) << 2