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

crypto/elliptic: numsp256t1 fails to verify #50938

Closed
pedroalbanese opened this issue Jan 31, 2022 · 4 comments
Closed

crypto/elliptic: numsp256t1 fails to verify #50938

pedroalbanese opened this issue Jan 31, 2022 · 4 comments
Labels
FrozenDueToAge NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.
Milestone

Comments

@pedroalbanese
Copy link

pedroalbanese commented Jan 31, 2022

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

$ go version
go version go1.15.3 windows/386*

Does this issue reproduce with the latest release?

Yes.

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

go env Output
$ go env
set GOARCH=386
set GOBIN=
set GOCACHE=C:\Users\0wner\AppData\Local\go-build
set GOEXE=.exe
set GOFLAGS=
set GOHOSTARCH=386
set GOHOSTOS=windows
set GOOS=windows
set GOPATH=C:\Users\0wner\go
set GOPROXY=
set GORACE=
set GOROOT=c:\go
set GOTMPDIR=
set GOTOOLDIR=c:\go\pkg\tool\windows_386
set GCCGO=gccgo
set GO386=sse2
set CC=gcc
set CXX=g++
set CGO_ENABLED=1
set GOMOD=H:\PGMM\edgetk\go.mod
set CGO_CFLAGS=-g -O2
set CGO_CPPFLAGS=
set CGO_CXXFLAGS=-g -O2
set CGO_FFLAGS=-g -O2
set CGO_LDFLAGS=-g -O2
set PKG_CONFIG=pkg-config
set GOGCCFLAGS=-m32 -mthreads -fmessage-length=0 -fdebug-prefix-map=C:\cygwin\tmp\go-build920491530=/tmp/go-build -gno-record-gcc-switches

What did you do?

Digital signature with NUMS256t1, as is possible with NUMS256d1:

As:

var numsp256d1 = &elliptic.CurveParams{
	P: strbig("0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff43"),
	N: strbig("0xffffffffffffffffffffffffffffffffe43c8275ea265c6020ab20294751a825"),
	B: strbig("0x25581"),
	Gx: strbig("0x01"),
	Gy: strbig("0x696f1853c1e466d7fc82c96cceeedd6bd02c2f9375894ec10bf46306c2b56c77"),
	BitSize: 256,
	Name: "numsp256d1",
}
func Nums256() elliptic.Curve { return numsp256d1 }

I need to do the same with numsp256t1 (http://www.watersprings.org/pub/id/draft-black-numscurves-01.html):

var numsp256t1 = &elliptic.CurveParams{
	P: strbig("0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff43"),
	N: strbig("0x3fffffffffffffffffffffffffffffffbe6aa55ad0a6bc64e5b84e6f1122b4ad"),
	B: strbig("0x3bee"),
	Gx: strbig("0x0d"),
	Gy: strbig("0x7d0ab41e2a1276dba3d330b39fa046bfbe2a6d63824d303f707f6fb5331cadba"),
	BitSize: 256,
	Name: "numsp256t1",
}

func Nums256t1() elliptic.Curve { return numsp256t1 }

I

What did you expect to see?

verify = true

What did you see instead?

verify is always false for signature and verification, but works for ECDH. Sry bad English.

@ianlancetaylor ianlancetaylor changed the title affected/package: crypto/elliptic: numsp256t1 fails to verify Jan 31, 2022
@ianlancetaylor
Copy link
Contributor

CC @golang/security

@ianlancetaylor ianlancetaylor added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Jan 31, 2022
@ianlancetaylor ianlancetaylor added this to the Backlog milestone Jan 31, 2022
@pedroalbanese
Copy link
Author

pedroalbanese commented Feb 1, 2022

To better exemplify, I made two implementations with standard curves, the conflict also occurs:

https://github.com/pedroalbanese/secp128r1 (working)
var secp128r1 = &elliptic.CurveParams{
	P: strbig("0x00fffffffdffffffffffffffffffffffff"), // Prime
	N: strbig("0x00fffffffe0000000075a30d1b9038a115"), // Order
	B: strbig("0x00e87579c11079f43dd824993c2cee5ed3"), // B
	Gx: strbig("0x161ff7528b899b2d0c28607ca52c5b86"),  // Generator X
	Gy: strbig("0xcf5ac8395bafeb13c02da292dded7a83"),  // Generator Y
	BitSize: 128,
	Name: "secp128r1",
}

// Secp128r1() returns a Curve which implements Secp128r1
func Secp128r1() elliptic.Curve { return secp128r1 }

https://github.com/pedroalbanese/secp128r2 (not working)
var secp128r2 = &elliptic.CurveParams{
	P: strbig("0x00fffffffdffffffffffffffffffffffff"), // Prime
	N: strbig("0x003fffffff7fffffffbe0024720613b5a3"), // Order
	B: strbig("0x005eeefca380d02919dc2c6558bb6d8a5d"), // B
	Gx: strbig("0x7b6aa5d85e572983e6fb32a7cdebc140"),  // Generator X
	Gy: strbig("0x27b6916a894d3aee7106fe805fc34b44"),  // Generator Y
	BitSize: 128,
	Name: "secp128r2",
}

// Secp128r2() returns a Curve which implements Secp128r2
func Secp128r2() elliptic.Curve { return secp128r2 }

128r1
P "FFFFFFFDFFFFFFFFFFFFFFFFFFFFFFFF",
B "E87579C11079F43DD824993C2CEE5ED3",
Gx "161FF7528B899B2D0C28607CA52C5B86",
Gy "CF5AC8395BAFEB13C02DA292DDED7A83",
N "FFFFFFFE0000000075A30D1B9038A115",

128r2
P "FFFFFFFDFFFFFFFFFFFFFFFFFFFFFFFF",
B "5EEEFCA380D02919DC2C6558BB6D8A5D",
Gx "7B6AA5D85E572983E6FB32A7CDEBC140",
Gy "27B6916A894D3AEE7106FE805FC34B44",
N "3FFFFFFF7FFFFFFFBE0024720613B5A3",

I believe the problem is the cofactor, help please!

@FiloSottile
Copy link
Contributor

What verification fails? For what key and message?

@pedroalbanese
Copy link
Author

pedroalbanese commented Feb 2, 2022

Fails for* verify digital signature, for all kind of messages/files and any key. I implemented both algorithms in the same way, secp128r1 and secp128r2, but the latter doesn't work like in the NUMS example.

https://github.com/pedroalbanese/secp128r1 (working)
https://github.com/pedroalbanese/secp128r2 (not working)

This example works with 9 algorithms from 128 to 512-bit:

package main

import (
	"crypto/ecdsa"
	"crypto/elliptic"
	"crypto/rand"
	"crypto/sha256"
	"encoding/hex"
	"errors"
	"flag"
	"fmt"
	"hash"
	"io"
	"log"
	"math/big"
	"os"

	"github.com/pedroalbanese/secp128r1"
//	"github.com/pedroalbanese/secp128r2"
)

var (
	derive = flag.Bool("derive", false, "Derive shared secret key.")
	keygen = flag.Bool("keygen", false, "Generate keypair.")
	key    = flag.String("key", "", "Private/Public key.")
	public = flag.String("pub", "", "Remote's side Public key.")
	sig    = flag.String("signature", "", "Signature.")
	sign   = flag.Bool("sign", false, "Sign with Private key.")
	verify = flag.Bool("verify", false, "Verify with Public key.")
)

func main() {
	flag.Parse()

	if len(os.Args) < 2 {
		fmt.Fprintln(os.Stderr, "Usage of", os.Args[0]+":")
		flag.PrintDefaults()
		os.Exit(2)
	}

	var privatekey *ecdsa.PrivateKey
	var pubkey ecdsa.PublicKey
	var pub *ecdsa.PublicKey
	var err error
	var pubkeyCurve elliptic.Curve

	pubkeyCurve = secp128r1.Secp128r1()
//	pubkeyCurve = secp128r2.Secp128r2()

	if *keygen {
		if *key != "" {
			privatekey, err = ReadPrivateKeyFromHex(*key)
			if err != nil {
				log.Fatal(err)
			}
		} else {
			privatekey = new(ecdsa.PrivateKey)
			privatekey, err = ecdsa.GenerateKey(pubkeyCurve, rand.Reader)
			if err != nil {
				fmt.Println(err)
				os.Exit(1)
			}
		}
		pubkey = privatekey.PublicKey
		fmt.Println("Private= " + WritePrivateKeyToHex(privatekey))
		fmt.Println("Public= " + WritePublicKeyToHex(&pubkey))
		os.Exit(0)
	}

	if *derive {
		private, err := ReadPrivateKeyFromHex(*key)
		if err != nil {
			log.Fatal(err)
		}
		public, err := ReadPublicKeyFromHex(*public)
		if err != nil {
			log.Fatal(err)
		}

		b, _ := public.Curve.ScalarMult(public.X, public.Y, private.D.Bytes())
		shared := sha256.Sum256(b.Bytes())
		fmt.Printf("Shared= %x\n", shared)
		os.Exit(0)
	}

	if *sign {
		var h hash.Hash
		h = sha256.New()

		if _, err := io.Copy(h, os.Stdin); err != nil {
			panic(err)
		}

		privatekey, err = ReadPrivateKeyFromHex(*key)
		if err != nil {
			log.Fatal(err)
		}

		signature, err := Sign(h.Sum(nil), privatekey)
		if err != nil {
			log.Fatal(err)
		}
		fmt.Printf("%x\n", signature)
		os.Exit(0)
	}

	if *verify {
		var h hash.Hash
		h = sha256.New()

		if _, err := io.Copy(h, os.Stdin); err != nil {
			panic(err)
		}

		pub, err = ReadPublicKeyFromHex(*key)
		if err != nil {
			log.Fatal(err)
		}

		sig, _ := hex.DecodeString(*sig)

		verifystatus := Verify(h.Sum(nil), sig, pub)
		fmt.Println(verifystatus)
		os.Exit(0)
	}
}

func Sign(data []byte, privkey *ecdsa.PrivateKey) ([]byte, error) {
	digest := sha256.Sum256(data)

	r, s, err := ecdsa.Sign(rand.Reader, privkey, digest[:])
	if err != nil {
		return nil, err
	}

	params := privkey.Curve.Params()
	curveOrderByteSize := params.P.BitLen() / 8
	rBytes, sBytes := r.Bytes(), s.Bytes()
	signature := make([]byte, curveOrderByteSize*2)
	copy(signature[curveOrderByteSize-len(rBytes):], rBytes)
	copy(signature[curveOrderByteSize*2-len(sBytes):], sBytes)

	return signature, nil
}

func Verify(data, signature []byte, pubkey *ecdsa.PublicKey) bool {
	digest := sha256.Sum256(data)

	curveOrderByteSize := pubkey.Curve.Params().P.BitLen() / 8

	r, s := new(big.Int), new(big.Int)
	r.SetBytes(signature[:curveOrderByteSize])
	s.SetBytes(signature[curveOrderByteSize:])

	return ecdsa.Verify(pubkey, digest[:], r, s)
}

func ReadPrivateKeyFromHex(Dhex string) (*ecdsa.PrivateKey, error) {
	c := secp128r1.Secp128r1()
//	c := secp128r2.Secp128r2()
	d, err := hex.DecodeString(Dhex)
	if err != nil {
		return nil, err
	}
	k := new(big.Int).SetBytes(d)
	params := c.Params()
	one := new(big.Int).SetInt64(1)
	n := new(big.Int).Sub(params.N, one)
	if k.Cmp(n) >= 0 {
		return nil, errors.New("privateKey's D is overflow.")
	}
	priv := new(ecdsa.PrivateKey)
	priv.PublicKey.Curve = c
	priv.D = k
	priv.PublicKey.X, priv.PublicKey.Y = c.ScalarBaseMult(k.Bytes())
	return priv, nil
}

func WritePrivateKeyToHex(key *ecdsa.PrivateKey) string {
	d := key.D.Bytes()
	if n := len(d); n < 16 {
		d = append(zeroByteSlice()[:32-n], d...)
	}
	c := []byte{}
	c = append(c, d...)
	return hex.EncodeToString(c)
}

func ReadPublicKeyFromHex(Qhex string) (*ecdsa.PublicKey, error) {
	q, err := hex.DecodeString(Qhex)
	if err != nil {
		return nil, err
	}
	if len(q) == 33 && q[0] == byte(0x04) {
		q = q[1:]
	}
	if len(q) != 32 {
		return nil, errors.New("publicKey is not uncompressed.")
	}
	pub := new(ecdsa.PublicKey)
	pub.Curve = secp128r1.Secp128r1()
//	pub.Curve = secp128r2.Secp128r2()
	pub.X = new(big.Int).SetBytes(q[:16])
	pub.Y = new(big.Int).SetBytes(q[16:])
	return pub, nil
}

func WritePublicKeyToHex(key *ecdsa.PublicKey) string {
	x := key.X.Bytes()
	y := key.Y.Bytes()
	if n := len(x); n < 16 {
		x = append(zeroByteSlice()[:16-n], x...)
	}
	if n := len(y); n < 16 {
		y = append(zeroByteSlice()[:16-n], y...)
	}
	c := []byte{}
	c = append(c, x...)
	c = append(c, y...)
	c = append([]byte{0x04}, c...)
	return hex.EncodeToString(c)
}

func zeroByteSlice() []byte {
	return []byte{
		0, 0, 0, 0,
		0, 0, 0, 0,
		0, 0, 0, 0,
		0, 0, 0, 0,
		0, 0, 0, 0,
		0, 0, 0, 0,
		0, 0, 0, 0,
		0, 0, 0, 0,
	}
}

When I change the library to secp128r2, numsp256/512t1 it fails, but works fine with numsp256/512d1. The DH function always works, but the verification function always fails.

$ ./secp128r1 -keygen
$ ./secp128r1 -sign -key $privatekey < main.go
$ ./secp128r1 -verify -key $publickey -signature $sign < main.go

Theoretically it should work with both curves just changing the library.

@golang golang locked and limited conversation to collaborators May 24, 2023
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
FrozenDueToAge NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.
Projects
None yet
Development

No branches or pull requests

4 participants