Add secp256r1

[leighmcculloch]

Starting a discussion thread for discussing the proposal to add secp256r1 signature verification to the Soroban host functions in a future protocol.

The proposal is here: https://github.com/stellar/stellar-protocol/blob/master/core/cap-0051.md

[leighmcculloch]

Use Cases

If you have a use case for using ecdsa secp256r1, beyond webauthn, please post about it in reply to this in the thread of this comment.

[Nathanofzion]

Hello Leigh this is amazing I’ve forked your repo but this would be great if it was integrated into the Soroban platform, so as Tyler said you don’t have to use Docker

I think for me if I was to use this functionality It would be for signing cross chain contracts Bridging but really it could be applied for anything that need signing right?. Once I’ve got through the soroban challenges i’d like to be at the stage where we’re ready to submit a new project to SCF using Soroban Smart contracts with this functionality As an option to sign for cross chain swaps. Let me know what you think?

[mozartpay]

Dear Leigh,

I hope this message finds you well. I have been closely following the development of CAP-0051, "Smart Contract Host Functionality: Secp256r1 Verification," and am impressed by the initiative to enhance the Stellar ecosystem's capabilities, particularly in supporting secp256r1 for Webauthn applications. Your work is paving the way for innovative and secure implementations within the Stellar network, and I believe there is an opportunity to further leverage this functionality.

I would like to propose an additional use case that could significantly benefit from the integration of secp256r1 verification into Soroban smart contracts: Decentralized Identity (DID) Based Payments. This concept utilizes ECDSA secp256r1 for secure identity verification, enabling a new paradigm for payment processes that are secure, private, and efficient. By associating DIDs with Stellar accounts and leveraging the cryptographic strengths of secp256r1, we can facilitate secure and seamless transactions, streamline KYC/AML compliance, and support cross-border payments with enhanced privacy and reduced costs.

I believe this use case aligns well with Stellar's goals of increasing accessibility to financial services and promoting security and privacy in digital transactions. It could also serve as a compelling addition to the range of applications supported by CAP-0051, demonstrating the versatility and impact of the proposed enhancements, and we would be more than happy to pioneer the implementation of this solution in our Mozart project.

I'm keen to hear your perspective on this concept. My enthusiasm for contributing to the development of this CAP is strong, and I believe that integrating DIDs into our discussions could unlock fresh opportunities for innovation within the Stellar network.

Thank you for considering this use case idea. I look forward to your feedback and am hopeful for the opportunity to contribute to the Stellar community's efforts in advancing secure and versatile blockchain solutions.

Best regards,
Olvis E. Gil Ríos

[jayz22]

A few questions and suggestions regarding the input arguments to the host function:

The public_key parameters is a BytesObject that must have a length of 65-bytes, being the ECDSA secp256r1 public key SEC-1 encoded.

The public key can be either compressed or uncompressed, and the 1 prefix byte specifies the it. By declaring it 65 bytes, I assume it is only accepting the uncompressed form (1 byte prefix + 32 byte x component + 32 byte y component)?
Alternatively, we can also accept both formats. For the compressed signature, additional computation is required to compute the y component, which must be accounted for by metering (so there will be two variants of cost parameters, which is less ideal). But accepting both forms provides most interoperability.

The msg_digest parameters is a BytesObject that must be a hash of the message, and must have been produced using a secure cryptographic hash function, otherwise an attacker can potentially forge signatures.

I think we should in addition require the hash length to be 32 bytes. As far as I understand, if the hash length is longer than 32 bytes (the order of p256 curve), additional bytes are truncated. Using a shorter hash is less secure.
A main benefit in fixing the hash length is it makes host function metering significantly easier, it can just be a constant term (instead of having to calibrate wrt different hash length to extract the linear factor).

The signature parameters is a BytesObject that must have a length of 64-bytes, with the first 32-bytes being the R-value big endian integer, and the second 32-bytes being the S-value big endian integer.

We should also restrict the S to be in the lower range to prevent signature malleability. It is pretty standard practice in blockchain to prevent malleability attack by rejecting the higher variant (e.g. in bitcoin). We are also doing the same in our current k256 implementation. I'm not sure if it is standard practice on the "source" side though e.g. if the hardware module or WebAuthn signing libraries to mandate low S value as well.

It would be beneficial to have someone with cryptography background to also chime in.

[leighmcculloch]

Got it, thanks for making that clear.

Fortunately, malleability makes compatibility with hardware signers a non-issue: when my device gives me back (r, s), I can just check if s is greater than (q-1)/2 and if so my signature is (r, q - s) (where q is the order of the group).

In the case @jayz22 raised, of the possibility that a hardware signer produce a non-canonical signature, is that a valid concern or would that be considered an incorrect implementation? If it is a valid concern, who typically should do the "I can just check if s is greater" logic?

[kwantam]

Right! This is a good (and subtle!) question :)

As long as the person sending the signature (in this case, the owner of the hardware device) is the one who canonicalizes the signature before releasing it, this is completely fine. For example, if my Ledger gives me back non-canonical (r, s) when I'm interacting with a smart contract, I'd just compute (r, q - s) before submitting the signature to the contract.

In short: the person who owns the secret key is welcome to adjust her signature before posting, but anyone verifying a signature made under someone else's secret key must never adjust the signature, and must reject if the signature is non-canonical.

Or, put another way: the sign() function can adjust the signature, the verify() function cannot. When using a hardware signer, the sign() function might call the hardware device as a subroutine and then do some other computation before returning a signature. But once the signature leaves the possession of the secret-key owner, no more adjustment should be made and non-canonical signatures should be rejected.

[leighmcculloch]

Got it, so I think I understand the distinction, let me echo this back and see if I'm applying this correctly:

once the signature leaves the possession of the secret-key owner, no more adjustment should be made

For hardware wallets that have a Stellar integration in software form, that software (part of the hardware wallet experience) may normalize the signature, which would still clearly be in possession of the owner.

For hardware keys (e.g. a FIDO key) that operate with, or are driven by, a software wallet (e.g. browser extension) via Webauthn, the software wallet part could do the normalization because it's still in possession of the owner. Even though the browser extension is clearly separate from the hardware key, the browser extension software wallet is still in possession of the owner.

However, if either of the above gave the key [signature] unmodified to a dapp frontend (a web page in a browser, or a third party app in some form) and then that dapp frontend normalized the signature, that would be dangerous, because the dapp is clearly outside the realm of what is in control of the user.

This might be getting too subtle, if so, no worries.

[kwantam]

However, if either of the above gave the key unmodified to a dapp frontend (a web page in a browser, or a third party app in some form) and then that dapp frontend normalized the signature, that would be dangerous

"gave the key" -> "gave the signature"

Yes, this is right! 👍

[leighmcculloch]

Does anyone know if it's common for hardware devices to produce non-canonical s's? I had made the assumption in the conversation about this might be a rare edge case, but to my surprise I get about 50% non-canonical out of an Apple system passkey signer, and @kalepail saw the same thing, so it's not isolated to my system.

[jayz22]

Regarding performance, according EIP-7212:

It is seen that “secp256r1” signature verification is ~15% slower (elaborated in test cases) than “secp256k1” signature recovery

Assuming our host implementation will be in the similar ballpark. The cpu cost of secp256k1 key recovery (RecoverEcdsaSecp256k1Key) is a constant cpu cost of 2.3M instructions. So I imagine the cpu limit won't have to be significantly altered in order to accommodate the secp256r1 verification host function.

(cc @MonsieurNicolas who brought it up in the protocol meeting and @graydon @leighmcculloch who responded)

Edit: I'm planning to perform preliminary calibration analysis of the host implementation, and will post back the results.

[tomerweller]

Not sure if this is useful but might be worth looking at Mystenlabs' fastcrypto library (mostly a wrapper around other high performance crypto libraries).

[jayz22]

Will do!

[leighmcculloch]

The fastcrypto library uses the p256 crate for secp256r1, same as what we had planned I believe, however it does make some modifications atop of it.

[jayz22]

This is interesting!
The fastcrypto library indeed uses the p256 crate for the curve definitions and representation, but it implements the underneath ECDSA verification and recovery (yes it provides both) computations, leveraging the arkworks library. After digging a bit into the development history, here appears to be the rationale:

• These crypto function are used for Sui native blockchain (tx signing and authentication), thus the interface needs to be uniform and standard, based on ecrecover on Ethereum. (They also enforce public keys to be in compressed format, presumably for space saving purpose.)
• The p256 crate at the time of the initial development, did not support recoverable signature. Thus they based their p256-recovery implementation on k256(adapted from recover_verify_key_from_digest_bytes in the k256@0.11.6 crate).
• They later migrated the computation to arkworks, which appear mainly to be motivated by computation performance (resulted in ~40% saving).
• They also noted concerns around lack of auditing in p256 crate. But decided to proceed with it with some testing-based mitigations.

In summary, I do not think this changes our choice of p256 as the underlying library:

• Cryptography host functions are less performance critical compared to cryptography for native tx signing/authentication. We will ensure they are tightly metered to prevent performance slowdown. If performance did turn out to be issue (which I don't expect, see comment above), we will find ways to mitigate that.
• Our host function is mainly aimed for web-authn and non-blockchain use cases, so we are not required to be compatible with ecrecover (even so p256 should already support it).
• p256 still seem to be the overwhelmingly most-popular pure-Rust crate for secp256r1, especially outside the blockchain space (see list of dependents), even though it hasn't been formally audited. (k256 has recently been audited and they share many core dependencies.)

[jayz22]

Here are some calibration results as promised above.

The results are split into 'compute' and 'decode' (since both have to be metered).
Each case is ran with 100k randomly sampled data points (key pair, msg hash), and then taking the average. Cpu instruction as well as time are reported (only cpu insn will go into the calibrated cost parameters).

Compute

Conclusion:

• p256 overall costs about twice as much cpu as k256
• the recovery workflow costs about twice as much as verify
• adding p256 verify host function will not have a significant impact on the overall cpu requirement (the budget), since its cost is similar to k256 recovery (what we have today), way under than the current default limit (100M).

Case	cpu insn	time (micro-secs)
p256 verify	2,995,127	211
p256 recover	6,321,450	462
k256 verify	1,106,383	72
k256 recover	2,312,848	167

Decode

Conclusion:

• Decoding an uncompressed (65-byte) public key is an order of magnitude less expensive than decoding a compressed key (33-byte). (This matches @kwantam's the explanation above)
• We will be going with uncompressed public key, thus decoding will not have a noticeable impact on overall cpu footprint.

Case	cpu insn	time (nano-secs)
Sec1 Decode Compressed	65,376	29
Sec1 Decode Uncompressed	1,882	5