Flawed implementation in ecdsa signature

[samngmco]

The signature generated by gnark-crypto/ecc/secp256k1/ecdsa cannot be verified by other libraries (including but not limited to NodeJS). After digging into the problem, this seems a pretty serious flaw, people now can easily find a collision in the signature hash and produce a fake verification.

Use a pretty trivial way to generate a random key and sign a message

privKey, _ := ecdsa.GenerateKey(rand.Reader)
publicKey := privKey.PublicKey

// sign
msg := []byte("testing ECDSA (sha256)")
md := sha256.New()
_, _ = md.Write(msg)
hashedMsg := md.Sum(nil)
sigBin, _ := privKey.Sign(hashedMsg, nil)

// check that the signature is correct
flag, _ := publicKey.Verify(sigBin, hashedMsg, nil)
if !flag {
    fmt.Println("can't verify signature")
} else {
    fmt.Println("signature verification ok")
}

> go run .
signature verification ok
hashedMsg: 918e47e7d1b7b4892fd746e691f8f44f3c9a3cc9a129de06301701895ea9676d
After HashToInt(): 918e47e7
Sig.R: 39da17ee7835a1949ec0e925e77ff42afdea28d67173a74cec4b52fda0cc8ffc
Sig.S: 327c8a6bb44e855e8ff1f11e1f6d98f8d07340059399652198a69979d0d283b7
Pub.X: 3bd2defa93e3a69cefa9765496ac537cc1280990df61e6bf18166863a09e8f39
Pub.Y: 571bff72b6dc52bd7f7bb4dd390feba74460b3ca12eeda2a19d9d185740853d1

Plug the values into a simple Node JS program, it turns out:

// this is sha256 of "testing ECDSA (sha256)
msgHash = "918e47e7d1b7b4892fd746e691f8f44f3c9a3cc9a129de06301701895ea9676d"
console.log(key.verify(msgHash, signature)) // <-- this is false

msgHash = "918e47e7" // <-- the first 32-bit of the above
console.log(key.verify(msgHash, signature)) // <-- this is true!!!!

The complete test code is available in here https://github.com/samngmco/gnark-bug

The root cause:

In gnark-crypto@v0.9.1/ecc/secp256k1/ecdsa/ecdsa.go

func (privKey *PrivateKey) Sign(message []byte, hFunc hash.Hash) ([]byte, error) {
...
if hFunc != nil {
    // compute the hash of the message as an integer
    dataToHash := make([]byte, len(message))
    copy(dataToHash[:], message[:])
    hFunc.Reset()
    _, err := hFunc.Write(dataToHash[:])
    if err != nil {
        return nil, err
    }
    hramBin := hFunc.Sum(nil)
    m = HashToInt(hramBin) <--- always truncated to the first 32 bits only
} else {
    m = HashToInt(message) <--- always truncated to the first 32 bits only 
}

Signature verification is also calling the same HashToInt(), that's why the signature verification passed within gnark-crypto.

[ivokub]

Thank you for letting us know. I implemented the fix in #428.

[ivokub]

Keeping the issue open until new releases can be released.

[samngmco]

Thank you 👍

[ivokub]

Released 0.11.1, 0.10.1, 0.9.2