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.205s
Currently, 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↗.