Wrong local sig is generated, when the first byte of a hash input is 0.

Question

Wrong local sig is generated, when the first byte of a hash input is 0.

Opened this issue 5 years ago · 10 comments

Current LocalSig generation code in src/protocols/thresholdsig/bitcoin_schnorr.rs uses a hash function which get input values as BigInt. However, if the first bytes of input is 0, the BigInt omit the 0. So the final hash value is going to be wrong.

I tried to create signature with this crate and i got some wrong signatures. It couldn't be verified on other schnorr signature verification code like this.

This is a simple test case for the hash function. The assertion is failure.

extern crate curv;
extern crate sha2;
extern crate hex;

#[test]
fn test_hash() {
    let message: Vec<u8> = vec![0, 1];

    let target = {
        use curv::cryptographic_primitives::hashing::hash_sha256::HSha256;
        use curv::cryptographic_primitives::hashing::traits::Hash;
        use curv::BigInt;
        use curv::arithmetic::traits::Converter;

        let big_int = BigInt::from(&message[..]);
        HSha256::create_hash(&[&big_int]).to_hex()
    };

    let expected = {
        use sha2::Sha256;
        use sha2::Digest;

        let mut hasher = Sha256::new();
        hasher.input(&message);
        hex::encode(hasher.result())
    };

    assert_eq!(target, expected);
}

I think that the signature compute code should use other hash function implementation or fix it.

Answer 1 · 2020-02-03T10:10:14.000Z

Hi @rantan !
thank you for bringing this up.
Here is the right way to use curv hash function to hash vector of bytes :

    #[test]
    fn test_byte_vec(){
        let message: Vec<u8> = vec![0, 1];
        let big_int0 = BigInt::from((message[0] as i32));
        let big_int1 = BigInt::from((message[1] as i32));

        let result  = HSha256::create_hash(&[&big_int0,&big_int1]).to_hex();
        let mut hasher = Sha256::new();
        hasher.input(&message);
        let result2 = hex::encode(hasher.result());
        assert_eq!(result,result2);

This issue is more relevant to curv create. The hash function we use is wrapped in such inconvenient way to accommodate the most common use case of hashing we use in our protocol, namely Fiat Shamir Transform.

Here is the relevant tests that compare this hash to known test vectors:
https://github.com/KZen-networks/curv/blob/master/src/cryptographic_primitives/hashing/hash_sha256.rs#L54

If you feel that some usage of this hash function is not covered by the tests (probably the one above): I encourage you to open an issue for it in the curv create, even better - create a PR :)

Answer 2 · 2020-02-03T10:43:35.000Z

Thank you for your response.
I understood the way to use the hash function correctly.

How about this part. https://github.com/KZen-networks/multi-party-schnorr/blob/master/src/protocols/thresholdsig/bitcoin_schnorr.rs#L188

When creating localsig, it converts message bytes array to BigInt. According above way you showed, I think it should convert each byte to a BigInt value.

Answer 3 · 2020-02-03T11:07:04.000Z

This is a solid question.
Please see https://github.com/KZen-networks/multi-party-ecdsa/tree/master/audits KZM-F-03 for more details.
In short: We assume that the message inputted to this function is a vectorized z = H(m) . We pass it as a vector to support serdes and not being bounded to our BigInt. In the function we reconstruct a bigint out of the vector.

As you can see from the report, this is the convention we use in all our libraries. However we do intend on changing it at some point, just didn't find the right excuse.

How critical it is for the operation of your code?

Answer 4 · 2020-02-04T05:04:11.000Z

Thank you for the information. I read it and I could understand probably ;)
Your libraries assume that the message inputted to computing signature function is hashed value.

However, I think this issue and the KZM-F-03 is little different.
It is special that the Schnorr signature algorithm uses a hash function in its process.

It is the problem that the input data passed into the hash function is going to be changed through converting to BigInt in LocalSig::compute() and re-converting to Vec in HShar256::create_hash().

This is an example to show that the message hash is going to be changed if the first byte is 0. The assertion is failure.

#[test]
fn test() {
    let message: Vec<u8> = hex::decode("00908debc0c1426a7fa1b830348974f7be2b3978698e2259f4ac75a8adce707f").unwrap();
    let bi = BigInt::from(&message[..]);
    assert_eq!(BigInt::to_vec(&bi), message);
}

It means that a message what LocalSig::compute() actual commits is different from a message what the user of LocalSig::compute() want to commit, if the message bytes user passed starts with 0.
Given a hash value for message, I think that wrong signatures are generated with 1/256 chance.

Answer 5 · 2020-02-04T05:11:12.000Z

I think you are right. We will fix it.

Answer 6 · 2020-02-04T07:22:59.000Z

Thank you!
Can I try to create a PR for this issue?

I think there are 2 way to fix.

Use other hash function like sha2 crate.
Create BigInt array from each message byte.

Which do you prefer or others?

Answer 7 · 2020-02-04T08:37:57.000Z

YES, go ahead.
I think option 2, if it works for you is the easier and cleaner of the two options.

Answer 8 · 2020-02-10T19:08:01.000Z

Hey @rantan
please let me know if this answers your issue?
https://github.com/KZen-networks/multi-party-schnorr/blob/master/src/protocols/thresholdsig/bitcoin_schnorr.rs#L190

Answer 9 · 2020-02-12T04:57:03.000Z

Hi.
I created test case below because i'm not sure by only reading the codes.

#[cfg(test)]
mod tests {
    use curv::{GE, FE, BigInt};
    use curv::elliptic::curves::traits::{ECPoint, ECScalar};
    use curv::elliptic::curves::secp256_k1::Secp256k1Scalar;
    use protocols::thresholdsig::bitcoin_schnorr::{LocalSig, SharedKeys};
    use sha2::Digest;

    #[test]
    fn test_compute_localsig() {
        let g: GE = ECPoint::generator();

        let local_ephemeral_key = {
            let prev = Secp256k1Scalar::new_random();
            SharedKeys {
                y: g * prev,
                x_i: prev
            }
        };

        let local_private_key = {
            let prev = Secp256k1Scalar::new_random();
            SharedKeys {
                y: g * prev,
                x_i: prev
            }
        };

        let message =
            hex::decode("000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f")
                .unwrap();

        let sig = LocalSig::compute(&message[..], &local_ephemeral_key, &local_private_key);

        let expected: LocalSig = {
            let beta_i = local_ephemeral_key.x_i.clone();
            let alpha_i = local_private_key.x_i.clone();

            let mut hasher = sha2::Sha256::new();
            hasher.input(&local_ephemeral_key.y.get_element().serialize()[..]);
            hasher.input(&local_private_key.y.get_element().serialize()[..]);
            hasher.input(&message[..]);
            let bn = BigInt::from(&hasher.result()[..]);
            let e: FE = ECScalar::from(&bn);

            let gamma_i = beta_i + e.clone() * alpha_i;

            LocalSig { gamma_i, e }
        };

        assert_eq!(expected.gamma_i, sig.gamma_i);
        assert_eq!(expected.e, sig.e);
    }
}

According to this test, the LocalSig is correct for my issue. Thanks!

Answer 10 · 2020-02-12T06:28:58.000Z

great, feel free to create a PR with the same concept and apply it to other places in the code that you think might be exposed to the same issue