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

[aaronc]

We are rejecting, see https://github.com/cosmos/cosmos-sdk/blob/master/crypto/keys/secp256k1/secp256k1_nocgo.go

[tarcieri]

Cool, so yeah, the logic is all there, it just needs to be parameterized over curves

[frumioj]

Having investigated this further this morning, I guess I have a number of concerns:

1. The issue is not signature malleability, it is transaction malleability; that is the use of signatures as identifiers in transactions, where a deterministic signature is needed, because the identifier needs to be deterministic. Unless the signature over transactions is used in a particular way, we won't have this problem. I have no particular knowledge of cosmos transactions to know whether the signatures are used beyond being signatures, but unless the signatures are used as identifiers, we don't need them to be deterministic. The "issue" with ECDSA is that the same message can result in two valid signatures, NOT that two different messages can result in one valid signature. So the signature itself is not broken. There's also some research that suggests that the Mt Gox attack was not even as the result of transaction malleability.
2. The cosmos code for secp256k1 is a different code path entirely (based on tendermint, and thus btcec) from the sec256r1 code (based on the standard ECDSA go-lang code).
3. Tony's proposed fix requires that the signature is broken out into its r and s components, as it works specifically on the s integer. In order to apply that fix, it looks like we would either have to a) override/replace the internal (ie. private) go-lang ECDSA sign function (e.g. https://cs.opensource.google/go/go/+/refs/tags/go1.16.6:src/crypto/ecdsa/ecdsa_noasm.go) to work on s using the code Tony provided, or we would have to use the existing signature code which provides an ASN-encoded signature with r and s already concatenated. That means first ASN decoding the signature, extracting r and s, low-s normalizing s, reassembling r and s in valid ASN, before returning the signature.
4. As Tony mentions, two s values are possible for all ECDSA signatures, so ideally, working with the key-specific curve params to get the curve order for a specific key would be the best general solution rather than hard-coding for one curve at a time. To do this would require some refactoring in cosmos, and either changing the tendermint/btcec code to be more general, or writing our own more general but go-specific code.

In summary, I'm not convinced this is a major problem (unless signatures are used in a specific way) and I also believe it requires a bit more work to implement in a reasonable way than just plopping in the code that Tony gave us.

[tarcieri]

we would have to use the existing signature code which provides an ASN-encoded signature with r and s already concatenated. That means first ASN decoding the signature, extracting r and s, low-s normalizing s, reassembling r and s in valid ASN, before returning the signature.

A bit of a sidebar, but...

If possible, I'd suggest using a fixed-width ECDSA signature encoding for ECDSA/P-256 signatures, with 32-byte r and s big endian scalars concatenated, similar to the encoding currently used by ECDSA/secp256k1, rather than encoding as ASN.1 DER.

DER encoding adds needless complexity, although FWIW a proper canonical encoding is described in BIP62 as well, and also works for P-256 as it has the same octet-sized modulus:

https://github.com/bitcoin/bips/blob/master/bip-0062.mediawiki#der-encoding

It would also make it easier to unify code with ECDSA/secp256k1.

[aaronc]

The issue is not signature malleability, it is transaction malleability; that is the use of signatures as identifiers in transactions, where a deterministic signature is needed, because the identifier needs to be deterministic. Unless the signature over transactions is used in a particular way, we won't have this problem.

We are using signature bytes to determine the transaction bytes and these are used as unique identifiers by clients currently. So as @tarcieri has pointed out, this is unfortunately exploitable.

[frumioj]

We are using signature bytes to determine the transaction bytes and these are used as unique identifiers by clients currently

Can you tell me where that code is? I have to admit that I am uncomfortable in changing a signature mechanism instead of fixing the actual issue (use of a non-deterministic thing to create a thing that needs to be deterministic) - why not just hash the signature to create the transaction identifier, for example? (yes, I know that's a strawman, and is based on no knowledge of the code that uses a signature to create a mapping from some transaction content to an identifier in a deterministic way).

[aaronc]

The tx hash is used in lots of places by lots of client code. Also to index by signature which I think is a good idea, we do need a deterministic signature which is what this is about right?

[frumioj]

The tx hash is used in lots of places by lots of client code. Also to index by signature which I think is a good idea, we do need a deterministic signature which is what this is about right?

"index by signature" = only one signature in the index must map back to the set of transactions that were signed?

"Deterministic" in this case, means that a unique input text will produce exactly one valid signature value. ECDSA signatures do not have that guarantee. ECDSA signatures can produce two valid signatures for a unique input text.

Indexing sets of transactions by signature might require that the reverse mapping is possible - that exactly one signature maps to one unique piece of signed content. Indexes though can also sometimes allow multiple different keys in the index to map to the same value - is that OK here?

[aaronc]

Yes in the indexes we can have one key map to several values, and many keys pointing to a value. That's how the current tendermint event indexer works.

[alexanderbez]

Correct. Pretty much the primary key/index in the Tendermint tx indexing is the tx hash, and that hash is the SHA256 sum of the raw tx bytes -- which includes the raw signature bytes. Different signature, yields a different tx hash even though the txs are the same.