Signature missmatch across implementations

[FssAy]

Description

Signatures produced by both Rust and JavaScript implementations differed with predefined entropy. I've found out it was the case of minor overlooks. This might be also the case for other languages.

Details

1. Message hashing produces empty array.

Click here to see the issue in code. After hashing the message a function .slice(32) is used which returns empty array. I am not sure why that happens, but either way i think we shouldn't slice the hashes as it might be a security risk (2 different hashes with the same prefix will produce the same output when sliced).

2. Wrong Signature format.

Click here to see the issue in code. The signature is not encoded in PEM format, but instead concatenated from both r and s parts (click here), so the Rust implementation adds additional prefix.

Proposed solutions

1. Remove .slice(32) function from JS implementation and don't slice the hashes.
2. Replace serialize_der function with serialize_compact in Rust.
3. Add some document about all the details how signatures should be encoded, use of ECDSA, etc.
4. Examples or integration tests with predefined entropy for each implementation that should output the same data.

[zach-planet-nine]

1. Remove .slice(32) function from JS implementation and don't slice the hashes.

Both Ethereum, and Bitcoin slice their hashes to 32 bytes (this is still 2^256 or 10^77 combinations, so collisions shouldn't happen), and I was always curious why, but never motivated enough to go digging for the reason. But I believe I've found it now:

From the ECDSA spec

Signature generation uses a cryptographic hash function H and an input message m. The message is first processed by H, yielding the value H(m), which is a sequence of bits of length hlen. Normally, H is chosen such that its output length hlen is roughly equal to qlen, since the overall security of the signature scheme will depend on the smallest of hlen and qlen; however, the relevant standards support all combinations of hlen and qlen.

So since private key length (qlen) is 32 bytes, there's no reason to use more than 32 bytes of the hash, and 32 is chosen for speed. Since I'd rather not deviate from the established secp256k1 implementations in the world I say we keep the slice, but fix the js implementation.

2. Replace serialize_der function with serialize_compact in Rust.

serialize_compact is 64 bytes so I'm not sure if this gets us what we need either.

3. Add some document about all the details how signatures should be encoded, use of ECDSA, etc.

We shouldn't need pem for signatures. It's typically used for keys, and I don't think I've seen it used for signatures. But agree we need some standardization on encoding. Now that we know Rust is adding something at the beginning we can take a closer look and see what that is, and if we can just drop it.

4. Examples or integration tests with predefined entropy for each implementation that should output the same data.

Totally. That's what I'm working up on the test branch. It's going to take a while because getting just the languages we have to all work on disparate machines is a challenge, but it'll be worth it.

[FssAy]

collisions shouldn't happen

In that case I agree, but I think we should document this somewhere for other language implementations. (I am not sure if that was done already)

serialize_compact is 64 bytes so I'm not sure if this gets us what we need either.

The Signature produced by the JS implementation is also 64 bytes and matches perfectly the one created by serialize_compact.

[zach-planet-nine]

In that case I agree, but I think we should document this somewhere for other language implementations. (I am not sure if that was done already)

Totally. I'll add that to my PR.

The Signature produced by the JS implementation is also 64 bytes and matches perfectly the one created by serialize_compact.

Perfect. I'll document that too for future us.

[FssAy]

I guess we can close it as the issue is resolved (I think).