ECDSA signature verification does not enforce that s is less than half the group order
Description
The BIP-62↗ standard requires that Bitcoin ECDSA signatures have an s value less than n/2 to prevent (R, n-s) from being a valid signature computable from another valid signature (R, s). The ecdsa.Verify↗ function does not enforce this, and while RecoverCompact↗ interprets the first byte of the signature as a code containing a flag that enforces the parity of s relative to the parity of the public key, this flag can also be flipped.
Impact
The following test (which reuses skHex and testMsg from the existing TestECDSA) demonstrates that the current implementation incorrectly accepts negated signatures:
func TestECDSAMalleability(t *testing.T) {
// decode SK and PK
skBytes, err := hex.DecodeString(skHex)
require.NoError(t, err)
sk, pk := btcec.PrivKeyFromBytes(skBytes)
require.NotNil(t, sk)
require.NotNil(t, pk)
// sign
sig := ecdsa.Sign(sk, testMsg)
// verify
err = ecdsa.Verify(pk, testMsg, sig)
require.NoError(t, err)
// Modify signature
sig[0] = ((sig[0]-27)^1)+27
var s btcec.ModNScalar
s.SetByteSlice(sig[33:65])
s.Negate()
s.PutBytesUnchecked(sig[33:65])
// Verify modified signature
err = ecdsa.Verify(pk, testMsg, sig)
require.Error(t, err)
}% go test -run TestECDSAMalleability
--- FAIL: TestECDSAMalleability (0.00s)
ecdsa_test.go:59:
Error Trace: /path/babylon/crypto/ecdsa/ecdsa_test.go:59
Error: An error is expected but got nil.
Test: TestECDSAMalleability
FAIL
exit status 1
FAIL github.com/babylonlabs-io/babylon/crypto/ecdsa 0.205sCurrently, ECDSA signatures are only used by Babylon for proof of possession, which is used to associate staker and finality-provider addresses with public keys. Being able to produce a distinct signature for a valid address does not appear to be an issue in this context, as the address being signed is not modified, so the correct address is still registered if a modified signature is used.
Recommendations
Enforce that s < n/2 in ecdsa.Verify:
func Verify(pk *btcec.PublicKey, msg string, sigBytes []byte) error {
msgHash := magicHash(msg)
recoveredPK, _, err := ecdsa.RecoverCompact(sigBytes, msgHash[:])
if err != nil {
return err
}
+ var s btcec.ModNScalar
+ if overflow := s.SetByteSlice(sigBytes[33:65]); overflow {
+ return fmt.Errorf("invalid signature: S >= group order")
+ }
+ if s.IsOverHalfOrder() {
+ return fmt.Errorf("invalid signature: S >= group order/2")
+ }
pkBytes := schnorr.SerializePubKey(pk)
recoveredPKBytes := schnorr.SerializePubKey(recoveredPK)
if !bytes.Equal(pkBytes, recoveredPKBytes) {
return fmt.Errorf("the recovered PK does not match the given PK")
}
return nil
}Remediation
This issue has been acknowledged by Babylon Labs, and a fix was implemented in commit 1d300ae7↗.