k256: v0.13.2 breaking verification

[bhesh]

Updating k256 to v0.13.2 is breaking verification that worked with v0.13.1. A snippet of the code is below. The full example can be found at k256-failure. The key and signatures come from test X.509 data generated by OpenSSL.

let key: VerifyingKey<k256::Secp256k1> = VerifyingKey::from_sec1_bytes(
    &hex!(
        "04bc72f5435bc947f3b79132dab7946159b28be519068960cfb10300c7124776d
         98ab5cb70229f99e149c3c695c301d604bad15e84ee1ed0abbb8c5b8e9782fdb0"
    )[..],
)
.unwrap();

let prehash = hex!("7e0bb97c6efdcb06156b17a56d41741c4b282b1f6840baec169cca08ec461c60");
let sig = Signature::<k256::Secp256k1>::from_scalars(
    hex!("D7597474A3CE9FC900A846DBC40D80D9EF3716C60C008113931990FBAB34E301"),
    hex!("5657331ECCA94B78BD83DE48B53F4A99F9067D90EF9A742E5752E32D1E94EDC7"),
)
.unwrap();
key.verify_prehash(&prehash[..], &sig).unwrap(); // Works with both 0.13.1 and 0.13.2

let prehash = hex!("a9ac0a346a96a91fa6aefb92b65ae6ad0f73ad1d3a113ab4454e4c0e5b25469a");
let sig = Signature::<k256::Secp256k1>::from_scalars(
    hex!("DDBD927A63D95426A1A17E2096EA7B5B3227F12694FE0092B7227A83EFF0487E"),
    hex!("F84A1D9BEC6F304CDB8564F7CE4A2665235FCAE2B1F524F5F4004E793A854808"),
)
.unwrap();
key.verify_prehash(&prehash[..], &sig).unwrap(); // Works with 0.13.1, fails with 0.13.2

[tarcieri]

This was actually a bugfix: #675 accidentally removed checks for low-S normalization which was released as k256 v0.12, which was reported in #908, as well as a recent NCC audit here: https://research.nccgroup.com/2023/08/30/public-report-entropy-rust-cryptography-review/

If you would like for the non-normalized signatures to verify, you need to normalize them first with Signature::normalize_s

[webmaster128]

In order to accept both low and high S, is it safe to do Signature::normalize_s also in VerifyingKey::recover_from_digest? If I recall correctly, low S and high S retruned a different pubkey before.

[tarcieri]

@webmaster128 you'll also need to flip the lowest bit in the recovery ID if sig.s.is_high()

Also hopefully recovery now accepts non-normalized signatures as of this PR: RustCrypto/signatures#793

However you'd have to try k256 v0.14.0-pre as sourced from git.

[webmaster128]

Oh sweet, thanks a lot! Just to double check: this diff correctly restores the 0.13.1 behaviour for recover pubkey and from 0.14 onwards I can remove it again?

--- a/packages/crypto/src/secp256k1.rs
+++ b/packages/crypto/src/secp256k1.rs
@@ -105,18 +105,24 @@ pub fn secp256k1_recover_pubkey(
     let signature = read_signature(signature)?;
 
     // params other than 0 and 1 are explicitly not supported
-    let id = match recovery_param {
+    let mut id = match recovery_param {
         0 => RecoveryId::new(false, false),
         1 => RecoveryId::new(true, false),
         _ => return Err(CryptoError::invalid_recovery_param()),
     };
 
     // Compose extended signature
-    let signature = Signature::from_bytes(&signature.into())
+    let mut signature = Signature::from_bytes(&signature.into())
         .map_err(|e| CryptoError::generic_err(e.to_string()))?;
 
     // Recover
     let message_digest = Identity256::new().chain(message_hash);
+
+    if let Some(normalized) = signature.normalize_s() {
+        signature = normalized;
+        id = RecoveryId::new(!id.is_y_odd(), id.is_x_reduced());
+    }
+
     let pubkey = VerifyingKey::recover_from_digest(message_digest, &signature, id)
         .map_err(|e| CryptoError::generic_err(e.to_string()))?;
     let encoded: Vec<u8> = pubkey.to_encoded_point(false).as_bytes().into();

At least tests seem to be passing with this.

[webmaster128]

I tried using the current version from git, but it fails to compile in sha2 with 0.11.0-pre.2:

error[E0432]: unresolved import `digest::array::ArrayOps`
 --> /[...]/.cargo/registry/src/index.crates.io-6f17d22bba15001f/sha2-0.11.0-pre.2/src/core_api.rs:4:5
  |
4 |     array::ArrayOps,
  |     ^^^^^^^^^^^^^^^ no `ArrayOps` in the root

However, the above diff passes all tests I have currently available using k256 version 0.13.3: CosmWasm/cosmwasm@818ec58

[tarcieri]

@webmaster128 I'll try to get another release out which fixes that, but in the meantime you can do the following:

[patch.crates-io.sha2]
git = "https://github.com/RustCrypto/hashes.git"

[tarcieri]

The version of k256 in git has been updated if you have the opportunity to test it out

[webmaster128]

Very nice, thanks! I got it working in two ways now:

1. k256 0.14 pre-release requires no change to the VerifyingKey::recover_from_digest call: Update to k256 0.14 pre-release to allow high-S in recover pubkey CosmWasm/cosmwasm#2015
2. k256 ^0.13.3 works with by normalizing signatures and flipping is_y_odd (same as k256: v0.13.2 breaking verification #991 (comment)): Fix pubkey recovery to work with high/low s for k256 ^0.13.2 CosmWasm/cosmwasm#2014

Could you confirm the solution in 2. is correct? It passes tests but my math is not strong enough to ensure it's the right thing to do. Would be great to have something before 0.14.0 is out that does not require us to pin k256 to 0.13.1.

[tarcieri]

@webmaster128 yep, that looks fine for now and can be removed in the next release