Signature mismatch between Rust and Python versions

[rbdm-qnt]

Cont. of this issue: starkware-libs/crypto-cpp#2

I'm trying to get the ECDSA signature generated in Rust to match the one generated by this Python implementation:
https://github.com/starkware-libs/starkex-resources-wip/blob/master/crypto/starkware/crypto/signature/signature.py

I'm choosing this reference implementation because I've been using it in my application before and it gets verified correctly by the service I'm interfacing with.

Test:

`
// 2 randomly generated hex strings
msg = "0x1f49a1b3be8f253cdce6b3f996b342c6e8d6ad4c4b4f6f4ab6d8d6b48dd2c7"
key = "0x8ad6c4f4b7b6e4ab6d8b6d48e2c7a6f9b2c8d6e4c6b4f6d4ab6d8d6b48dd2c"

// Python version:
// I'm calling it with no seed, so the extra_entropy gets initialized to b'' as you can see in line 111. Not sure what's the Rust equivalent for this, I'm trying to use an empty string
r, s = sign(int(msg, 16), int(key, 16))

// Rust version, wrapped in C++ using the provided CXX example code:
// I made it output R and S concatenated and separated by a semicolon using format!("{};{}", r_hex, s_hex) as the ecdsa_sign return
auto k = generate_k(msg, key, "");
const char* k_c_str = k.c_str();
std::string k_str(k_c_str);
k_str = "0x" + k_str;
auto signature = ecdsa_sign(msg, key, k_str);
`
Python output:
r: 0x698c5654560a84b16d210692ec4207c09a8ecc21df043284a6382cab8c2079d
s: 0x6386bdd3a021350c8218b68118e275885f8138bb44d9e9f400c69fc510c928e

Rust:
r: 0x698c5654560a84b16d210692ec4207c09a8ecc21df043284a6382cab8c2079d
s: 0x7498bb37722fefb1d3c99b5c70c300a461eeb0d8b2faf943b9198b2ec054f6c

The k values generated by Python's generate_k_rfc6979 and by Rust's generate_k match correctly, and it's this:
0x46e17a0e758084beb8fabd15f070b6cdb77f6d6025501a6d0d5f671f75477f2

I noticed the r values between the 2 implementations always match, and the s value never does.
I also noticed that the math inside the signature generation functions seems different, and that's ok, because the recursive math operations in the Python version's logic, even when recreated in C++, are much too slow for my needs, while this Rust version is really fast, if only I could get it to verify correctly.

Any help would be greatly appreciated!

[xJonathanLEI]

Thanks for submitting the issue. Now I see what you're trying to do here. I think you've mistaken what k means. It's k as in the secret scalar in ECDSA, not the "extra entropy" in Python. The "extra entropy" in Python is used to generate k. If I'm understanding correctly, you're using ecdsa_sign wrong.

It's extremely fortunate you noticed the difference instead of just using it anyways. As noted in the bing warning here:

starknet-rs/starknet-crypto/README.md

Line 5 in fc64165

> _You're advised to use high-level crypto utilities implemented by the `starknet-core` crate (or use it through the `starknet::core` re-export) if you're not familiar with cryptographic primitives. Using these low-level functions incorrectly could result in leaking your private key, for example._

, using it incorrectly will leak your private key. You're trying to use an empty (and thus fixed) k, and doing this will lead to leaking your private key (see this).

The function you're looking for is the high-level wrapper in starknet-core ad advised. I will update the example to use high level constructs instead shortly. I expected the C++ audience to prefer low-level libraries but I guess it's just way too easy to shoot yourself in the foot.

[xJonathanLEI]

Example updated: #330

Do note the performance implication here: #330 (comment)

Closing this optimistically. Please feel free to reopen otherwise.

[rbdm-qnt]

Thank you for the quick reply!

I implemented your last commit, now not even R is matching, and I'm still getting a verification failure from the server.
The scalar you are referring to (I think) is the seed from which the extra_entropy variable gets created in the Python version (line 43 here, which the has_func being used being sha256: https://github.com/tlsfuzzer/python-ecdsa/blob/master/src/ecdsa/rfc6979.py ).
But anyway, that was not the issue, as I mentioned in the initial issue the values of k matched between Python and Rust, so that was working great!

As far as security goes, I'm not building a server side application, I'm on the client side trying to get my signature accepted by the server, so security is a bit less of a concern.

[xJonathanLEI]

As far as security goes, I'm not building a server side application, I'm on the client side trying to get my signature accepted by the server, so security is a bit less of a concern.

This is not true. Using k incorrect leaks your CLIENT private key.

[xJonathanLEI]

Are you sure?

Calling with the example values you provided:

ecdsa_sign(
    "0x8ad6c4f4b7b6e4ab6d8b6d48e2c7a6f9b2c8d6e4c6b4f6d4ab6d8d6b48dd2c",
    "0x1f49a1b3be8f253cdce6b3f996b342c6e8d6ad4c4b4f6f4ab6d8d6b48dd2c7"
);

gives: 0x0698c5654560a84b16d210692ec4207c09a8ecc21df043284a6382cab8c2079d06386bdd3a021350c8218b68118e275885f8138bb44d9e9f400c69fc510c928e, which is exactly your expected Python output.

Did you mix up key and message hash?

[rbdm-qnt]

As far as security goes, I'm not building a server side application, I'm on the client side trying to get my signature accepted by the server, so security is a bit less of a concern.

This is not true. Using k incorrect leaks your CLIENT private key.

Yes I fully understood, what I'm saying is I'm more worried about making it work than I am about the exchange stealing my wallet :)

Are you sure?

Calling with the example values you provided:

ecdsa_sign(
    "0x8ad6c4f4b7b6e4ab6d8b6d48e2c7a6f9b2c8d6e4c6b4f6d4ab6d8d6b48dd2c",
    "0x1f49a1b3be8f253cdce6b3f996b342c6e8d6ad4c4b4f6f4ab6d8d6b48dd2c7"
);

gives: 0x0698c5654560a84b16d210692ec4207c09a8ecc21df043284a6382cab8c2079d06386bdd3a021350c8218b68118e275885f8138bb44d9e9f400c69fc510c928e, which is exactly your expected Python output.

Did you mix up key and message hash?

Thanks for trying that out, I gotta go now but I'm gonna run another bunch of tests tomorrow morning and will keep you posted!

[xJonathanLEI]

The scalar you are referring to (I think) is the seed from which the extra_entropy variable gets created

This is not true. It's the other way around. The secret scalar k is (partially) derived from the extra entropy if you want to use rfc6979, and can techinically be any value if you don't care about rfc6979.

[rbdm-qnt]

Are you sure?

Calling with the example values you provided:

ecdsa_sign(
    "0x8ad6c4f4b7b6e4ab6d8b6d48e2c7a6f9b2c8d6e4c6b4f6d4ab6d8d6b48dd2c",
    "0x1f49a1b3be8f253cdce6b3f996b342c6e8d6ad4c4b4f6f4ab6d8d6b48dd2c7"
);

gives: 0x0698c5654560a84b16d210692ec4207c09a8ecc21df043284a6382cab8c2079d06386bdd3a021350c8218b68118e275885f8138bb44d9e9f400c69fc510c928e, which is exactly your expected Python output.

Did you mix up key and message hash?

Yes you are right!! I don't know how it's possible that I rewrote my own signature libraries in multiple languages to get it to work, and then missed this dumb detail lol

Now everything matches and verification works. All is good because we are using a safe k value too in the end. Thank you so much for your time and patience, and quick responses!

[xJonathanLEI]

Np :)

Glad you made it work!