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

[C0rWin]

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

$ go 1.19

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

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"

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.

[pfi79]

Tests
go 1.19
go 1.18

[seankhliao]

cc @golang/security

[gopherbot]

Change https://go.dev/cl/424929 mentions this issue: crypto/x509: error Verification of ECDSA signed x509 cert

[rolandshoemaker]

This seems to be working as intended, signatures are intended to be ignored when eliminating certificates that share subjects and public keys during path building (see RFC 4158 section 2.4.2). In particular, since ECDSA signatures are both malleable (as shown here) and non-deterministic, relying on byte-for-byte signature matching would mean we (almost) never exclude duplicates (such as cross signatures).

What is the use case here?

[C0rWin]

In some permissioned blockchains, x509 is used to capture the identity of the network entities with their affiliation, to make sure one certificate will identify only one person, credentials pass sanitation, e.g., signatures normalized to lowS. Now, the problem is that you initialize the cert pool with sanitized root CA certificates, but then you are trying to extract the identity you first need to sanitize, to sanitize, you need to find a parent cert to lookup for curve parameters. So, if you are getting leaf certs, it works as intended. However, if you get an identity with root CA cert, it fails due to the reasons I have described inside the issue.

The problem here we are trying to avoid is that the user can produce two valid x509 certs without intervention from the CA side.

[rolandshoemaker]

crypto/x509 is generally designed for use with the Web PKI, and as such may make some decisions that are not compatible with other uses of X.509, I suspect this is one of those cases.

Allowing these duplicate certificates (as defined in RFC 4158) in chains creates overly verbose chains that contain self-referential loops which we'd rather avoid.

[pfi79]

Do I understand correctly that in go 1.19 our case is not a bug?
That we are using the Verify method incorrectly?

[C0rWin]

Allowing these duplicate certificates (as defined in RFC 4158) in chains creates overly verbose chains that contain self-referential loops which we'd rather avoid.

Well, this sanitation process is basically to prevent duplication of certs and to reduce verbosity. The problem I guess is that in 1.18 you could validate self-signed ECDSA certs whenever they are lowS or highS, which is no longer possible now with 1.19.

[pfi79]

@rolandshoemaker be so kind as to answer the question.