ECDH is underspecified and not x-only

[Sjors]

The spec requires two ECDH operations:

1. between both ephemeral keys
2. between initiator ephemeral key and responder (upstream) static key

But it doesn't specify exactly how to do this.

Both ephemeral and static public keys are serialised as x-only. Note that being x-only does not imply that the y-coordinate is even. Depending on which ECDH algorithm is followed, this can cause two sides to get a different cipher.

This is because you don't know if the other side has an even or odd public key, so you don't know if the resulting combined point should be even or odd, which leads to totally different hash (i.e. key).

The current Bitcoin Core Template Provider implementation treats the other side's x-only key as if it's a compressed key and assumes the y-coordinate coordinate is even (0x02 prefix). It also negates its own private key if its corresponding public key is odd.

I haven't looked at the SRI code yet, but I assume it does the same thing. This strategy works if both sides follow it.

Currently libsecp's ECDH module can only perform ECDH between a private key and a compressed public key. Part of its algorithm is to hash the resulting point. That hash includes whether the y-coordinate is even.

Option 1: clarify the spec with the above

(see also @jakubtrnka's comment)

The above procedure of negating the private key works. But it's not elegant. It's also ambiguous, because you could either do it at generation time, or only temporarily when performing ECDH. Note that for the signed certificate no negation is necessary, because the BIP340 scheme works with x-only keys.

Option 2: "clarify" the spec to use x-only ECDH

There is a pull request https://github.com/bitcoin-core/secp256k1/pull/1198 to the libsecp libary that adds x-only ECDH. It uses a hash that does not cover the y-coordinate. This would remove the need for negating the private key.

Technically this would be a "clarification" of what "ECDH" means in the spec, but in reality it's a breaking change.

It also requires waiting for that PR to be updated, merged and released.

Option 3: change the spec to use EllSwift: #66

If we make a breaking change anyway, then we might as well use EllSwift like BIP324 does. It's x-only by design and has the extra benefit of making the handshake pseudo-random. Currently the ephemeral key exchange is not pseudo-random because only ~50% of possible 32 random byte sequences represent a valid public key. EllSwift fixes that.

The code for it is already merged, available in libsecp releases and afaik also in the rust bindings (haven't checked).

Option 4: change implementations to follow the current spec

(added on 2024-01-22, see comments below)

Implemented in https://github.com/stratum-mining/stratum/pull/724

---

My current plan is to make a draft implementation of (3) on the Bitcoin Core side and propose a spec change. But I don't know yet if this is difficult on the SRI side. I also don't know what other components are already out there in the wild, how they currently interpret ECDH and easy it is to port them to use EllSwift.

[Fi3]

SRI just make sure to have even key at gen time discarding odd ones. https://github.com/stratum-mining/stratum/blob/dev/protocols/v2/noise-sv2/src/handshake.rs#L27

[Sjors]

I implemented option 3 in https://github.com/Sjors/bitcoin/pull/28 which was fairly straight-forward.

[Sjors]

On the Rust side it requires updating secp256k1 from v0.27.0 to v0.28.1 to get access to: https://docs.rs/secp256k1/latest/secp256k1/ellswift/index.html

Attempting this library update in https://github.com/stratum-mining/stratum/pull/714

[jakubtrnka]

Thanks for interesting input @Sjors.

On closer look the specification actually is correct: note the following:

1. The definition of ECDH in the spec doesn't prescribe hashing the raw diffie-hellman output. Instead, it says it should output X-coordinate of the resulting point directly:
   1. quote: The output is X-coordinate of the resulting EC point
   2. https://github.com/stratum-mining/sv2-spec/blob/main/04-Protocol-Security.md#441-cipherstate-object
   3. in secp256k1 rust lib, secp256k1::ecdh::shared_secret_point should be used. Using the library primitive with implicit hashing is incorrect (against the current standard)
2. All ECDH results are fed directly into the HKDF (in a MixKey noise step) - so the key already is being hashed and doesn't need to be hashed twice (first implicitly after DH and subsequently in HDKF).
3. This would work because the parity of the resulting X-coordinate of the EC point doesn't depend on parity of public keys of either participants.

I'll look on the EllSwift. This looks very interesting.

[Sjors]

@jakubtrnka thanks for the clarification! I just noticed that in the Bitcoin Core implementation the call to secp256k1_ecdh sets hashfp to NULL. That indeed causes it to return the point without hashing.

In that case I'm puzzled why it didn't work without key negating.

The output is X-coordinate of the resulting EC point

Ah, I misread this as being descriptive (and incorrect by default) rather than prescriptive.

I just opened a PR that shows what the spec would (approximately) look like with EllSwift.

[Sjors]

Oh no, I read it wrong again:

https://github.com/bitcoin-core/secp256k1/blob/master/include/secp256k1_ecdh.h#L36-L57

/**  hashfp:     pointer to a hash function. If NULL,
  *              secp256k1_ecdh_hash_function_sha256 is used
  *              (in which case, 32 bytes will be written to output).

When not providing a hash function secp256k1_ecdh doesn't return the public key, it falls back to the default secp256k1_ecdh_hash_function_sha256, so it returns a hash. And that hash includes a bit for the odd/even-ness of the y-coordinate.

So why did the handshake between Bitcoin Core and SRI succeed?

Here's the SRI code.

    fn ecdh(private: &[u8], public: &[u8]) -> [u8; 32] {
        let private = SecretKey::from_slice(private).expect("Wrong key");
        let x_public = XOnlyPublicKey::from_slice(public).expect("Wrong key");
        let res = SharedSecret::new(&x_public.public_key(crate::PARITY), &private);
        res.secret_bytes()

The SharedSecret::new() also uses secp256k1_ecdh_hash_function_default: https://docs.rs/secp256k1/latest/src/secp256k1/ecdh.rs.html#42-56

So it seems nobody implements the spec correctly (as you say in 1.iii)

[jakubtrnka]

You are right.

These are identities that are valid:

#[test]
fn key_parity_test() {
    let (a_secret, a_public) = make_even_key();
    let (b_secret, b_public) = make_even_key();

    let a_odd_result = secp256k1::ecdh::shared_secret_point(
        &a_public.public_key(secp256k1::Parity::Odd),
        &b_secret
    );

    let a_even_result = secp256k1::ecdh::shared_secret_point(
        &a_public.public_key(secp256k1::Parity::Even),
        &b_secret
    );

    let b_odd_result = secp256k1::ecdh::shared_secret_point(
        &b_public.public_key(secp256k1::Parity::Odd),
        &a_secret
    );

    assert_eq!(b_odd_result, a_odd_result);
    assert_eq!(a_odd_result[..32], a_even_result[..32]);
}

fn make_even_key() -> (secp256k1::SecretKey, secp256k1::XOnlyPublicKey) {
    let mut rng = thread_rng();
    let secret = secp256k1::SecretKey::new(&mut rng);
    let ctx = secp256k1::Secp256k1::new();
    let (x_public, parity) = secret.x_only_public_key(&ctx);
    let secret = match parity {
        secp256k1::Parity::Even => secret,
        secp256k1::Parity::Odd => secret.negate(),
    };
    (secret, x_public)
}

Only the X-coordinate should be used. The first 32 bytes.

This should be definitely more clarified in the specification.

[pavlenex]

Test