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

Jump to bottom

x/crypto/ed25519: GeDoubleScalarMultVartime returns wrong value for low scalar #34122

Closed
bfix opened this issue Sep 5, 2019 · 3 comments
Closed

x/crypto/ed25519: GeDoubleScalarMultVartime returns wrong value for low scalar #34122

bfix opened this issue Sep 5, 2019 · 3 comments
Labels
FrozenDueToAge NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.
Milestone
Unreleased

Comments

@bfix
Copy link

bfix commented Sep 5, 2019

What version of Go are you using (go version)?

go version go1.12.6 linux/amd64

Does this issue reproduce with the latest release?

Yes

What operating system and processor architecture are you using (go env)?

go env Output
GOARCH="amd64"
GOBIN=""
GOCACHE="/home/brf/.cache/go-build"
GOEXE=""
GOFLAGS=""
GOHOSTARCH="amd64"
GOHOSTOS="linux"
GOOS="linux"
GOPATH="/opt/go/ext"
GOPROXY=""
GORACE=""
GOROOT="/opt/go/golang"
GOTMPDIR=""
GOTOOLDIR="/opt/go/golang/pkg/tool/linux_amd64"
GCCGO="gccgo"
CC="gcc"
CXX="g++"
CGO_ENABLED="1"
GOMOD=""
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"
PKG_CONFIG="pkg-config"
GOGCCFLAGS="-fPIC -m64 -pthread -fmessage-length=0 -fdebug-prefix-map=/tmp/go-build781766841=/tmp/go-build -gno-record-gcc-switches"

What did you do?

Reused package to access internal implementation (internal/edwards25519) for implementing ECDHE with Ed25519 keys. This involves the use of the 'GeDoubleScalarMultVartime()' method to compute the shared secret.

According to the docs 'GeDoubleScalarMultVartime sets r = aA + bB'. This method does not return the correct point 'r' if the bitlength of 'a' is less than 249.

You can check the source code here: https://git.wauland.de/brf/gnunet-go. The relevant code is in src/gnunet/crypto/key_exchange.go

What did you expect to see?

The correct Ed25519 curve point for any value of 'a'

What did you see instead?

A wrong curve point if 'a' has its most significant byte set to zero.
@gopherbot gopherbot added this to the Unreleased milestone Sep 5, 2019
@FiloSottile FiloSottile changed the title x/crypto: (ed25519) error in internal 'GeDoubleScalarMultVartime()' method x/crypto/ed25519: GeDoubleScalarMultVartime returns wrong value for low scalar Sep 5, 2019
@FiloSottile FiloSottile added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Sep 5, 2019
@FiloSottile FiloSottile self-assigned this Sep 5, 2019
@FiloSottile
Copy link
Contributor

Can you provide an example vector with inputs and expected output?

@bfix
Copy link
Author

bfix commented Sep 5, 2019 •
edited

How to reproduce the problem:

(1) Generate two Ed25519 private keys and store their private factors 'd_1' and 'd_2' (derived from seed). Make sure that the bitlength of one of the 'd's is smaller than 249 (MSByte set to zero).
(2) Get the corresponding public keys pub_1 and pub_2
(3) Compute the shared secrets ss_1 and ss_2 as:

GeDoubleScalarMultVartime(&r, &a, &A, &zero)
ss = r.ToBytes()

with a=d_1, A=pub_2 for ss_1 and a=d_2, A=pub_1 for ss_2.

(4) Evaluate results: ss_1 and ss_2 don't match; only one is the correct point.

@bfix
Copy link
Author

bfix commented Sep 7, 2019

Since the problem only occurs when setting the private scalar directly (and not derive it from a seed the Ed25519 way), I don't consider this an issue anymore (in the standard Ed25519 use case).

For my purpose (experimental software) I wrote a simple, less performant Go implementation of Ed25519 I will use in the project (https://github.com/bfix/gospel/tree/master/crypto/ed25519).

@bfix bfix closed this as completed Sep 7, 2019
bfix added a commit to bfix/gnunet-go that referenced this issue Sep 18, 2019
@bfix
Simplified DHE test case for reproducing issue.
309a558 
(see golang/go#34122)
@golang golang locked and limited conversation to collaborators Sep 6, 2020
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees
No one assigned
Labels
FrozenDueToAge NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.
Projects
None yet
Milestone
Unreleased
Development

No branches or pull requests
3 participants
@bfix @FiloSottile @gopherbot