ECDSA/secp256r1 transaction malleability

[tarcieri]

This is in regard to the newly proposed support for ECDSA/secp256r1 (NIST P-256) account keys. See #7718 and #8899.

An important detail to capture with these signatures is malleability. For comparison, ECDSA/secp256k1 signatures are almost always low-S normalized in order to make them non-malleable. However, P-256 signatures are not typically used in consensus-critical applications and therefore are not normalized.

Normalization is a relatively simple procedure: if an ECDSA/secp256r1 signature is 64-bytes structured as r || s, if s is greater than half of the field modulus (i.e. curve order), subtract s from the modulus. It can be retroactively applied to signatures generated from HSMs and other hardware devices.

Primarily this impacts the verification rules: signatures which are not low-S normalized MUST be rejected. Doing so will prevent malleability-related issues with ECDSA/secp256r1 signatures the same way the similar procedure prevents them with ECDSA/secp256k1 signatures.

[aaronc]

Thanks @tarcieri. This sounds important. Note that secp256-r1 is not just proposed - it is ready to be deployed. So let's make sure we address this before it goes into production. @AmauryM @robert-zaremba do we need to make updates for the 0.43 release?

[frumioj]

"Primarily this impacts the verification rules: signatures which are not low-S normalized MUST be rejected. Doing so will prevent malleability-related issues with ECDSA/secp256r1 signatures the same way the similar procedure prevents them with ECDSA/secp256k1 signatures."

+1

[aaronc]

Could someone explain what issues this malleability could actually cause? I don't think it can break consensus because tx bytes from tendermint aren't malleable after they've been included in a block.

[tarcieri]

Offhand I'm not aware of how transaction malleability bugs would/could apply to Tendermint/Cosmos SDK.

The core problem is that if the signature itself is included in the transaction hash, it makes it possible to generate duplicate transactions with different transaction hashes. However, they'd have the same sequence number, so anything indexing according to that should be OK (although unfortunately sequence numbers aren't an explicit part of the signed data).

Some background on the attacks in Bitcoin:

https://en.bitcoin.it/wiki/Transaction_malleability

This manifested in various different ways, for example, tricking a system into believing a particular transaction was not confirmed. In particular it adversely impacted things like exchanges, by confusing their transaction indexing systems:

https://link.springer.com/content/pdf/10.1007%2F978-3-319-11212-1_18.pdf

(at least allegedly, who knows with Mt. Gox)

Even if there isn't a concrete attack that's immediately evident, I'd still consider making signatures non-malleable a best practice.

[frumioj]

Worth nothing that Ethereum fixed the specific related issue they had (transaction serial #), rather than disallowing some signatures: https://github.com/ethereum/EIPs/blob/master/EIPS/eip-2.md

…

On Jul 19, 2021, at 1:34 PM, Tony Arcieri ***@***.***> wrote: Offhand I'm not aware of how transaction malleability bugs would/could apply to Tendermint/Cosmos SDK. The core problem is that if the signature itself is included in the transaction hash, it makes it possible to generate duplicate transactions with different transaction hashes. However, they'd have the same sequence number, so anything indexing according to that should be OK (although unfortunately sequence numbers aren't an explicit part of the signed data). Some background on the attacks in Bitcoin: https://en.bitcoin.it/wiki/Transaction_malleability <https://en.bitcoin.it/wiki/Transaction_malleability> This manifested in various different ways, for example, tricking a system into believing a particular transaction was not confirmed. In particular it adversely impacted things like exchanges, by confusing their transaction indexing systems: https://link.springer.com/content/pdf/10.1007%2F978-3-319-11212-1_18.pdf <https://link.springer.com/content/pdf/10.1007%2F978-3-319-11212-1_18.pdf> (at least allegedly, who knows with Mt. Gox) Even if there isn't a concrete attack that's immediately evident, I'd still consider making signatures non-malleable a best practice. — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#9723 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAABJG4FUFOV3GGXD7Z5XVTTYROYXANCNFSM5AT47JCA>.

[aaronc]

So it seems like because we have account sequences that are signed over and the tx bytes are deterministic, this account malleability isn't really an attack vector. Does that sound accurate?

The only thing that could happen is that two semantically identical transactions could be created due to this malleability, but only one of them would succeed because of the account sequence.

If there is a real security concern, I would like us to get clarity on this ASAP because we will need to patch the 0.43 release line. Does anyone see a way this can actually be exploited?? Maybe @zmanian @alexanderbez any thoughts?

[tarcieri]

So it seems like because we have account sequences that are signed over and the tx bytes are deterministic, this account malleability isn't really an attack vector. Does that sound accurate?

It depends how transaction hashes are calculated. Are they a hash of TxBody, or do they include AuthInfo (i.e. Tx/TxRaw)?

If transaction hashes do include AuthInfo, then it's possible for an attacker to malleate the AuthInfo, producing a second signature with the same contents and sequence number as the first, but a different transaction hash.

In such a scenario it might be possible for an attacker to trick a victim into thinking the original transaction failed (e.g. passed CheckTx, assigned transaction hash, but DeliverTx or afterward fails).

It really depends what the victim is doing and how they are keeping track of transactions. An attacker might be able to convince a victim (e.g. malicious P2P relay node who is able to obtain a signed transaction and malleate it in the mempool) that the original transaction delivery failed and convince them to auto-retry, even though it succeeded, which is what (allegedly) occurred during the Mt. Gox attack.

[tarcieri]

Also if you'd like to address this, I can write up a description and provide a small amount of self-contained Go code which will check that a signature is low-S normalized as well as low-S normalize it if it isn't.

[aaronc]

Okay, the attack scenario you've laid our seems somewhat unlikely to me initially... but if it's what happened with Mt Gox, we should definitely avoid that!

It would be great if you're willing to share that go code. Thanks 🙏

[tarcieri]

Been awhile since I've written some Go, but I think this should do the trick:

import (
	"crypto/elliptic"
	"math/big"
)

func p256Order() *big.Int {
	return elliptic.P256().Params().N
}

func p256OrderDiv2() *big.Int {
	return new(big.Int).Div(p256Order(), new(big.Int).SetUint64(2))
}

func IsNormalized(sigS *big.Int) bool {
	return sigS.Cmp(p256OrderDiv2()) != 1
}

func NormalizeS(sigS *big.Int) *big.Int {
	if IsNormalized(sigS) {
		return sigS
	} else {
		return new(big.Int).Sub(p256Order(), sigS)
	}
}

Signature verification needs to call IsNormalized with the S-component of the ECDSA signature and ensure it's true.

Signers will need to call NormalizeS on the S-component of the signature to ensure it's in normal form.

[aaronc]

Thanks @tarcieri 🙏.

I think we should try to get this into 0.43 for better or worse @robert-zaremba @AmauryM

I just want to note that tx hashes are malleable in a number of other ways at the Tx envelope level. Notably, the proto parser will accept a reordering of the top level fields. If this hash manipulation is a concern, we should probably disallow it in the future.

[frumioj]

Note that Tendermint includes a check for this in their crypto lib: https://github.com/tendermint/tendermint/blob/68ffe8bc64e4efc8b50ee9ad2b857cecd0ca6c8d/crypto/secp256k1/secp256k1_nocgo.go#L13 but cosmos crypto doesn’t seem to use tendermint crypto for this… - johnk

…

On Jul 19, 2021, at 6:54 PM, Aaron Craelius ***@***.***> wrote: Thanks @tarcieri <https://github.com/tarcieri> 🙏. I think we should try to get this into 0.43 for better or worse @robert-zaremba <https://github.com/robert-zaremba> @AmauryM <https://github.com/amaurym> I just want to note that tx hashes are malleable in a number of other ways at the Tx envelope level. Notably, the proto parser will accept a reordering of the top level fields. If this hash manipulation is a concern, we should probably disallow it in the future. — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#9723 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAABJG44KK7YR7CAAT6VUCLTYSUK5ANCNFSM5AT47JCA>.

[tarcieri]

@frumioj yes, but that's for secp256k1, not NIST P-256 (secp256r1)

That said, it should be possible to write common code for both if it accepts e.g. CurveParams or the curve order as a parameter.

[aaronc]

So that means secp256k1 signatures are currently malleable as well?

[tarcieri]

I believe I've had Tendermint/Cosmos SDK reject signatures that aren't low-S normalized but I'm not certain