Repository: go
Issue: crypto/x509: Verification of ECDSA signed x509 cert, sanitized to LowS certs fails verification with go 1.19
Labels: NeedsInvestigation

### What version of Go are you using (`go version`)?

<pre>
$ go 1.19

</pre>

### Does this issue reproduce with the latest release?

Yes

### What operating system and processor architecture are you using (`go env`)?

<details><summary><code>go env</code> Output</summary><br><pre>
$ go env

</pre>
GO111MODULE=""
GOARCH="arm64"
GOBIN=""
GOCACHE="/Users/c0rwin/Library/Caches/go-build"
GOENV="/Users/c0rwin/Library/Application Support/go/env"
GOEXE=""
GOEXPERIMENT=""
GOFLAGS=""
GOHOSTARCH="arm64"
GOHOSTOS="darwin"
GOINSECURE=""
GOMODCACHE="/Users/c0rwin/golang/pkg/mod"
GONOPROXY="gitlab.n-t.io/*"
GONOSUMDB="gitlab.n-t.io/*"
GOOS="darwin"
GOPATH="/Users/c0rwin/golang"
GOPRIVATE="gitlab.n-t.io/*"
GOPROXY="https://proxy.golang.org,direct"
GOROOT="/opt/homebrew/Cellar/go/1.19/libexec"
GOSUMDB="sum.golang.org"
GOTMPDIR=""
GOTOOLDIR="/opt/homebrew/Cellar/go/1.19/libexec/pkg/tool/darwin_arm64"
GOVCS=""
GOVERSION="go1.19"
GCCGO="gccgo"
AR="ar"
CC="clang"
CXX="clang++"
CGO_ENABLED="1"
GOMOD="/Users/c0rwin/workspace/fabric/go.mod"
GOWORK=""
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"
PKG_CONFIG="pkg-config"
GOGCCFLAGS="-fPIC -arch arm64 -pthread -fno-caret-diagnostics -Qunused-arguments -fmessage-length=0 -fdebug-prefix-map=/var/folders/jr/yqzwn3rx4yddkb18shrqycgc0000gn/T/go-build3484858551=/tmp/go-build -gno-record-gcc-switches -fno-common"

</details>

After moving to the go v1.19, validating certificates signed with ECDSA with signature after sanitation to LowS form is no longer possible.  The code which manifests the problem is the following:

```
certpool := x509.NewCertPool()

caFileBytes, err := os.ReadFile(rootCAFile)
if err != nil {
   panic(err)
}

caPemBlock, _ := pem.Decode(caFileBytes)
caCert, err := x509.ParseCertificate(caPemBlock.Bytes)
if err != nil {
   panic(err)
}

if isECDSASignedCert(caCert) {
   caCert, err = utils.SanitizeCert(caCert)
   if err != nil {
      panic(err)
   }
}

certpool.AddCert(caCert)
opts := x509.VerifyOptions{
   Roots: certpool,
}

certBytes, err := os.ReadFile(certFile)
if err != nil {
   panic(err)
}

certPemBlock, _ := pem.Decode(certBytes)
cert, err := x509.ParseCertificate(certPemBlock.Bytes)
if err != nil {
   panic(err)
}

_, err = cert.Verify(opts)
if err != nil {
   panic(err)
}

fmt.Println("SUCCESS")
```

Having following certificates 

```
rootCAFile := `-----BEGIN CERTIFICATE-----
MIICPzCCAeSgAwIBAgIRAONi5v8ImyejqCrCatbAW1QwCgYIKoZIzj0EAwIwaTEL
MAkGA1UEBhMCVVMxEzARBgNVBAgTCkNhbGlmb3JuaWExFjAUBgNVBAcTDVNhbiBG
cmFuY2lzY28xFDASBgNVBAoTC2V4YW1wbGUuY29tMRcwFQYDVQQDEw5jYS5leGFt
cGxlLmNvbTAeFw0xOTA3MDQxNjI3MDBaFw0yOTA3MDExNjI3MDBaMGkxCzAJBgNV
BAYTAlVTMRMwEQYDVQQIEwpDYWxpZm9ybmlhMRYwFAYDVQQHEw1TYW4gRnJhbmNp
c2NvMRQwEgYDVQQKEwtleGFtcGxlLmNvbTEXMBUGA1UEAxMOY2EuZXhhbXBsZS5j
b20wWTATBgcqhkjOPQIBBggqhkjOPQMBBwNCAAQAfjOlLCdB/6SsdPlbDHUsdK+b
gRuEN38QOFZ0Ws3aFAsER8ImqV3UIlsbKi5JnDs+OQnzrr3hrKA8downRRy/o20w
azAOBgNVHQ8BAf8EBAMCAaYwHQYDVR0lBBYwFAYIKwYBBQUHAwIGCCsGAQUFBwMB
MA8GA1UdEwEB/wQFMAMBAf8wKQYDVR0OBCIEIN/hgC0LnghmpjfwtsqvEvhE/2LI
wJbaCUtoY5cFF8WfMAoGCCqGSM49BAMCA0kAMEYCIQDhhgAHx0l7V5uAG2hATgCs
bvsbHiJpHUtiK7f1Qfxf2AIhANeukSgRU+AeGSzyVmAOKhIUS+grsPyspksUwVvB
ehXv
-----END CERTIFICATE-----`
```

and 

```
certFile := `-----BEGIN CERTIFICATE-----
MIICPzCCAeSgAwIBAgIRAONi5v8ImyejqCrCatbAW1QwCgYIKoZIzj0EAwIwaTEL
MAkGA1UEBhMCVVMxEzARBgNVBAgTCkNhbGlmb3JuaWExFjAUBgNVBAcTDVNhbiBG
cmFuY2lzY28xFDASBgNVBAoTC2V4YW1wbGUuY29tMRcwFQYDVQQDEw5jYS5leGFt
cGxlLmNvbTAeFw0xOTA3MDQxNjI3MDBaFw0yOTA3MDExNjI3MDBaMGkxCzAJBgNV
BAYTAlVTMRMwEQYDVQQIEwpDYWxpZm9ybmlhMRYwFAYDVQQHEw1TYW4gRnJhbmNp
c2NvMRQwEgYDVQQKEwtleGFtcGxlLmNvbTEXMBUGA1UEAxMOY2EuZXhhbXBsZS5j
b20wWTATBgcqhkjOPQIBBggqhkjOPQMBBwNCAAQAfjOlLCdB/6SsdPlbDHUsdK+b
gRuEN38QOFZ0Ws3aFAsER8ImqV3UIlsbKi5JnDs+OQnzrr3hrKA8downRRy/o20w
azAOBgNVHQ8BAf8EBAMCAaYwHQYDVR0lBBYwFAYIKwYBBQUHAwIGCCsGAQUFBwMB
MA8GA1UdEwEB/wQFMAMBAf8wKQYDVR0OBCIEIN/hgC0LnghmpjfwtsqvEvhE/2LI
wJbaCUtoY5cFF8WfMAoGCCqGSM49BAMCA0kAMEYCIQDhhgAHx0l7V5uAG2hATgCs
bvsbHiJpHUtiK7f1Qfxf2AIhANeukSgRU+AeGSzyVmAOKhIUS+grsPyspksUwVvB
ehXv
-----END CERTIFICATE-----`
```

The code mentioned above running with the go 1.18 will result in `SUCCESS`; however, it will fail on go 1.19 with panic, because it will fail to build a verification path. The code implementing sanitation is following:

```
type validity struct {
   NotBefore, NotAfter time.Time
}

type publicKeyInfo struct {
   Raw       asn1.RawContent
   Algorithm pkix.AlgorithmIdentifier
   PublicKey asn1.BitString
}

type certificate struct {
   Raw                asn1.RawContent
   TBSCertificate     tbsCertificate
   SignatureAlgorithm pkix.AlgorithmIdentifier
   SignatureValue     asn1.BitString
}

type tbsCertificate struct {
   Raw                asn1.RawContent
   Version            int `asn1:"optional,explicit,default:0,tag:0"`
   SerialNumber       *big.Int
   SignatureAlgorithm pkix.AlgorithmIdentifier
   Issuer             asn1.RawValue
   Validity           validity
   Subject            asn1.RawValue
   PublicKey          publicKeyInfo
   UniqueId           asn1.BitString   `asn1:"optional,tag:1"`
   SubjectUniqueId    asn1.BitString   `asn1:"optional,tag:2"`
   Extensions         []pkix.Extension `asn1:"optional,explicit,tag:3"`
}

type ECDSASignature struct {
   R, S *big.Int
}

// curveHalfOrders contains the precomputed curve group orders halved.
// It is used to ensure that signature' S value is lower or equal to the
// curve group order halved. We accept only low-S signatures.
// They are precomputed for efficiency reasons.
var curveHalfOrders = map[elliptic.Curve]*big.Int{
   elliptic.P224(): new(big.Int).Rsh(elliptic.P224().Params().N, 1),
   elliptic.P256(): new(big.Int).Rsh(elliptic.P256().Params().N, 1),
   elliptic.P384(): new(big.Int).Rsh(elliptic.P384().Params().N, 1),
   elliptic.P521(): new(big.Int).Rsh(elliptic.P521().Params().N, 1),
}

func GetCurveHalfOrdersAt(c elliptic.Curve) *big.Int {
   return big.NewInt(0).Set(curveHalfOrders[c])
}

func MarshalECDSASignature(r, s *big.Int) ([]byte, error) {
   return asn1.Marshal(ECDSASignature{r, s})
}

func UnmarshalECDSASignature(raw []byte) (*big.Int, *big.Int, error) {
   // Unmarshal
   sig := new(ECDSASignature)
   _, err := asn1.Unmarshal(raw, sig)
   if err != nil {
      return nil, nil, fmt.Errorf("failed unmashalling signature [%s]", err)
   }

   // Validate sig
   if sig.R == nil {
      return nil, nil, errors.New("invalid signature, R must be different from nil")
   }
   if sig.S == nil {
      return nil, nil, errors.New("invalid signature, S must be different from nil")
   }

   if sig.R.Sign() != 1 {
      return nil, nil, errors.New("invalid signature, R must be larger than zero")
   }
   if sig.S.Sign() != 1 {
      return nil, nil, errors.New("invalid signature, S must be larger than zero")
   }

   return sig.R, sig.S, nil
}

func SignatureToLowS(k *ecdsa.PublicKey, signature []byte) ([]byte, error) {
   r, s, err := UnmarshalECDSASignature(signature)
   if err != nil {
      return nil, err
   }

   s, err = ToLowS(k, s)
   if err != nil {
      return nil, err
   }

   return MarshalECDSASignature(r, s)
}

// IsLow checks that s is a low-S
func IsLowS(k *ecdsa.PublicKey, s *big.Int) (bool, error) {
   halfOrder, ok := curveHalfOrders[k.Curve]
   if !ok {
      return false, fmt.Errorf("curve not recognized [%s]", k.Curve)
   }

   return s.Cmp(halfOrder) != 1, nil
}

func ToLowS(k *ecdsa.PublicKey, s *big.Int) (*big.Int, error) {
   lowS, err := IsLowS(k, s)
   if err != nil {
      return nil, err
   }

   if !lowS {
      // Set s to N - s that will be then in the lower part of signature space
      // less or equal to half order
      s.Sub(k.Params().N, s)

      return s, nil
   }

   return s, nil
}

func SanitizeCert(cert *x509.Certificate) (*x509.Certificate, error) {
   expectedSig, err := SignatureToLowS(cert.PublicKey.(*ecdsa.PublicKey), cert.Signature)
   if err != nil {
      return nil, err
   }

   if bytes.Equal(cert.Signature, expectedSig) {
      return cert, nil
   }

   var newCert certificate
   _, err = asn1.Unmarshal(cert.Raw, &newCert)
   if err != nil {
      panic(err)
   }

   newCert.SignatureValue = asn1.BitString{Bytes: expectedSig, BitLength: 8 * len(expectedSig)}
   newCert.Raw = nil

   newRaw, err := asn1.Marshal(newCert)
   if err != nil {
      return nil, err
   }

   return x509.ParseCertificate(newRaw)
}
```

Now, in go 1.18, the certificate verification compares certs bitwise (`crypto/x509/verify.go:829`):

```
considerCandidate := func(certType int, candidate *Certificate) {
	for _, cert := range currentChain {
		if cert.Equal(candidate) {
			return
		}
	}

	if sigChecks == nil {
		sigChecks = new(int)
	}
	*sigChecks++
	if *sigChecks > maxChainSignatureChecks {
		err = errors.New("x509: signature check attempts limit reached while verifying certificate chain")
		return
	}

	if err := c.CheckSignatureFrom(candidate); err != nil {
		if hintErr == nil {
			hintErr = err
			hintCert = candidate
		}
		return
	}

	err = candidate.isValid(certType, currentChain, opts)
	if err != nil {
		return
	}

	switch certType {
	case rootCertificate:
		chains = append(chains, appendToFreshChain(currentChain, candidate))
	case intermediateCertificate:
		if cache == nil {
			cache = make(map[*Certificate][][]*Certificate)
		}
		childChains, ok := cache[candidate]
		if !ok {
			childChains, err = candidate.buildChains(cache, appendToFreshChain(currentChain, candidate), sigChecks, opts)
			cache[candidate] = childChains
		}
		chains = append(chains, childChains...)
	}
}
```

The code above has been refactored and optimized to:

```
considerCandidate := func(certType int, candidate *Certificate) {
	if alreadyInChain(candidate, currentChain) {
		return
	}

	if sigChecks == nil {
		sigChecks = new(int)
	}
	*sigChecks++
	if *sigChecks > maxChainSignatureChecks {
		err = errors.New("x509: signature check attempts limit reached while verifying certificate chain")
		return
	}

	if err := c.CheckSignatureFrom(candidate); err != nil {
		if hintErr == nil {
			hintErr = err
			hintCert = candidate
		}
		return
	}

	err = candidate.isValid(certType, currentChain, opts)
	if err != nil {
		return
	}

	switch certType {
	case rootCertificate:
		chains = append(chains, appendToFreshChain(currentChain, candidate))
	case intermediateCertificate:
		var childChains [][]*Certificate
		childChains, err = candidate.buildChains(appendToFreshChain(currentChain, candidate), sigChecks, opts)
		chains = append(chains, childChains...)
	}
}
```

the `alreadyInChain` replaces the loop which compares certs by checking Subject, PublicKey, and SAN.

```
func alreadyInChain(candidate *Certificate, chain []*Certificate) bool {
	type pubKeyEqual interface {
		Equal(crypto.PublicKey) bool
	}

	var candidateSAN *pkix.Extension
	for _, ext := range candidate.Extensions {
		if ext.Id.Equal(oidExtensionSubjectAltName) {
			candidateSAN = &ext
			break
		}
	}

	for _, cert := range chain {
		if !bytes.Equal(candidate.RawSubject, cert.RawSubject) {
			continue
		}
		if !candidate.PublicKey.(pubKeyEqual).Equal(cert.PublicKey) {
			continue
		}
		var certSAN *pkix.Extension
		for _, ext := range cert.Extensions {
			if ext.Id.Equal(oidExtensionSubjectAltName) {
				certSAN = &ext
				break
			}
		}
		if candidateSAN == nil && certSAN == nil {
			return true
		} else if candidateSAN == nil || certSAN == nil {
			return false
		}
		if bytes.Equal(candidateSAN.Value, certSAN.Value) {
			return true
		}
	}
	return false
}
```


Compares Subject, PublicKey, and SAN is equal cause we verify sanitized certs. However, the signature is different, and the function call in the example above should have resulted with false. Therefore, my question is whether the `alreadyInChain` should be extended with an additional check for signature equality? 



The code below demonstrates the issue with the test - https://go.dev/play/p/Vaephj6DLOl.