Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Closed
mmcloughlin opened this issue Feb 5, 2019 · 6 comments
Closed
Labels
FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done.
Milestone

Comments

@mmcloughlin
Copy link
Contributor

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
Copy link

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

@gopherbot
Copy link

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

@dgryski
Copy link
Contributor

dgryski commented Feb 5, 2019

@FiloSottile

@agnivade agnivade added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Feb 6, 2019
@andybons andybons added this to the Go1.13 milestone Feb 6, 2019
@josharian
Copy link
Contributor

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?

@josharian josharian reopened this Feb 8, 2019
@josharian josharian added NeedsFix The path to resolution is known, but the work has not been done. and removed NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. labels Feb 8, 2019
@FiloSottile
Copy link
Contributor

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

gopherbot pushed a commit to golang/crypto that referenced this issue Mar 13, 2019
This diff extends the curve25519 test suite with some test vectors
generated from BoringSSL.

Updates golang/go#30095

Change-Id: I4e871378c77b46167d162e9eec75fc412596ff7c
Reviewed-on: https://go-review.googlesource.com/c/crypto/+/161277
Reviewed-by: Filippo Valsorda <filippo@golang.org>
Run-TryBot: Filippo Valsorda <filippo@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
@andybons andybons modified the milestones: Go1.13, Go1.14 Jul 8, 2019
@FiloSottile
Copy link
Contributor

This got imported in Go 1.13.

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

@golang golang locked and limited conversation to collaborators Sep 30, 2020
c-expert-zigbee pushed a commit to c-expert-zigbee/crypto_go that referenced this issue Mar 28, 2022
Comparison against BoringSSL-generated test vectors showed mismatches
with the pure Go implementation of curve25519. The problem was narrowed
down to a missing mask in feFromBytes(). This diff adds the mask,
bringing this back in line with the reference implementation and
RFC 7748:

    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.

Fixes golang/go#30095

Change-Id: If7efc0e2acd6efb761d6e3cb89cec359d7d81cb1
Reviewed-on: https://go-review.googlesource.com/c/161257
Run-TryBot: Filippo Valsorda <filippo@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Filippo Valsorda <filippo@golang.org>
c-expert-zigbee pushed a commit to c-expert-zigbee/crypto_go that referenced this issue Mar 29, 2022
Comparison against BoringSSL-generated test vectors showed mismatches
with the pure Go implementation of curve25519. The problem was narrowed
down to a missing mask in feFromBytes(). This diff adds the mask,
bringing this back in line with the reference implementation and
RFC 7748:

    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.

Fixes golang/go#30095

Change-Id: If7efc0e2acd6efb761d6e3cb89cec359d7d81cb1
Reviewed-on: https://go-review.googlesource.com/c/161257
Run-TryBot: Filippo Valsorda <filippo@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Filippo Valsorda <filippo@golang.org>
c-expert-zigbee pushed a commit to c-expert-zigbee/crypto_go that referenced this issue Mar 29, 2022
Comparison against BoringSSL-generated test vectors showed mismatches
with the pure Go implementation of curve25519. The problem was narrowed
down to a missing mask in feFromBytes(). This diff adds the mask,
bringing this back in line with the reference implementation and
RFC 7748:

    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.

Fixes golang/go#30095

Change-Id: If7efc0e2acd6efb761d6e3cb89cec359d7d81cb1
Reviewed-on: https://go-review.googlesource.com/c/161257
Run-TryBot: Filippo Valsorda <filippo@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Filippo Valsorda <filippo@golang.org>
LewiGoddard pushed a commit to LewiGoddard/crypto that referenced this issue Feb 16, 2023
Comparison against BoringSSL-generated test vectors showed mismatches
with the pure Go implementation of curve25519. The problem was narrowed
down to a missing mask in feFromBytes(). This diff adds the mask,
bringing this back in line with the reference implementation and
RFC 7748:

    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.

Fixes golang/go#30095

Change-Id: If7efc0e2acd6efb761d6e3cb89cec359d7d81cb1
Reviewed-on: https://go-review.googlesource.com/c/161257
Run-TryBot: Filippo Valsorda <filippo@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Filippo Valsorda <filippo@golang.org>
BiiChris pushed a commit to BiiChris/crypto that referenced this issue Sep 15, 2023
Comparison against BoringSSL-generated test vectors showed mismatches
with the pure Go implementation of curve25519. The problem was narrowed
down to a missing mask in feFromBytes(). This diff adds the mask,
bringing this back in line with the reference implementation and
RFC 7748:

    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.

Fixes golang/go#30095

Change-Id: If7efc0e2acd6efb761d6e3cb89cec359d7d81cb1
Reviewed-on: https://go-review.googlesource.com/c/161257
Run-TryBot: Filippo Valsorda <filippo@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Filippo Valsorda <filippo@golang.org>
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done.
Projects
None yet
Development

No branches or pull requests

7 participants