k256 disrepency in secp256k1 key recover

[rakita]

There is disrepency between 0.13.1 and 0.13.2 with a recovery of following signature.

sig:
73b1693892219d736caba55bdb67216e485557ea6b6af75f37096c9aa6a5a75feeb940b1d03b21e36b0e47e79769f095fe2ab855bd91e3a38756b7d75a9c454901
msg:
0x18c547e4f7b0f325ad1e56f57e26c745b09a3e503d86e00e5255ff7f715d3d1c

Previously it was throwing error:

        let recid = RecoveryId::from_byte(sig[64]).expect("Recovery id is valid");
        let signature = Signature::from_slice(&sig[..64])?;
        // recover key
        let recovered_key = VerifyingKey::recover_from_prehash(&msg[..], &signature, recid)?;

Relavnt code path: https://github.com/bluealloy/revm/blob/aa5667764890bc554ea6392ea1e84e3e1991be6d/crates/precompile/src/secp256k1.rs#L20-L24

But in 0.13.2 it is returning:

recover_key: VerifyingKey { inner: PublicKey { point: AffinePoint { x: recover_key: VerifyingKey { inner: PublicKey { point: AffinePoint { x: FieldElement(FieldElement5x52([934325660672829, 3548642670627580, 159500637258998, 2956994059304877, 64120665032303])), y: FieldElement(FieldElement5x52([2734956072898995, 4335590221684941, 2147356337188867, 65576761325467, 141230998108636])), infinity: 0 } }

Not related but eth test error is: static_CallEcrecover0_completeReturnValue.json

[tarcieri]

More details please?

[rakita]

More details please?

Just updated, clicked publish by accident

[tarcieri]

Were you expecting an error or for it to recover a key? Does the signature verify?

[rakita]

It was recovering previously, i switched versions in original post, just run it again:
0.13.02 returnes: recover_key: Err(signature::Error { source: None })
0.13.01 returnes: recover_key: Ok(VerifyingKey { inner: PublicKey { point: AffinePoint { x: FieldElement(FieldElement5x52([934325660672829, 3548642670627580, 159500637258998, 2956994059304877, 64120665032303])), y: FieldElement(FieldElement5x52([2734956072898995, 4335590221684941, 2147356337188867, 65576761325467, 141230998108636])), infinity: 0 } } })

[tarcieri]

The issue appears to be the signature is not low-S normalized, which was previously allowed due to a bug in the signature verification logic.

If you try the low-S normalized version of the same signature, it works:

73b1693892219d736caba55bdb67216e485557ea6b6af75f37096c9aa6a5a75f1146bf4e2fc4de1c94f1b81868960f68bc842490f1b6bc98387ba6b57599fbf801

[tarcieri]

Closing as by design

[kayabaNerve]

To clarify, is this low-S as in s < l or as in s = min(s, -s)?

If the former, ACK. If the latter, I don't believe ECDSA has that requirement and it's an additional canonicity rule added by select systems. I don't see why recovery should globally enforce that rule. I'd ask where this design change was discussed so I can gain better insight into the decision causing it.

[tarcieri]

@kayabaNerve it's specifically that s < p / 2, conditionally negating s if it that isn't the case, as described in BIP62: Dealing with malleability.

Note that this was the behavior of previous versions of k256. It regressed in v0.12 as noted in #908, and was introduced in #675.

It was further highlighted in the NCC audit here: https://research.nccgroup.com/2023/08/30/public-report-entropy-rust-cryptography-review/

[rakita]

@tarcieri I see, thank you for the shift response!

if we normalize the S I am assuming that we need to flip the RecoveryId, is this statement correct? It is passing eth tests, but would appreciate if you can take a look. The code is question is here:
https://github.com/bluealloy/revm/pull/870/files#diff-35ad1cec3da3b1c5d68700c00b2f755bf3a8b7715fded4ad067c87128dd1b777R25-R26

[tarcieri]

Yes, see here for an example: https://github.com/RustCrypto/elliptic-curves/blob/5c829a4/k256/src/ecdsa.rs#L193

I'm curious about the provenience of these signatures. I would not expect them to verify in an EVM context.

[rakita]

Yes, see here for an example: https://github.com/RustCrypto/elliptic-curves/blob/5c829a4/k256/src/ecdsa.rs#L193

I'm curious about the provenience of these signatures. I would not expect them to verify in an EVM context.

Sigs are from tests, so probably they are testing edge cases for EVM precompile contract (ecrecover).

[kayabaNerve]

EVM ecrecover allows non-low-s. It's only a sometimes-used OpenZeppelin library which doesn't (ignoring sporadic custom impls of low-s-checks).