ECDSA With Public Key Recovery

[julmb]

I want to use crypton to sign transactions in the Ethereum protocol. This is done via ECDSA but with a parity output for public key recovery in addition to the regular r and s parameters in the signature.

This additional parity output is easily calculated given both coordinates of the pointMul curve k g value. Unfortunately, Crypto.PubKey.ECC.ECDSA.signDigestWith does not expose these and there is no intermediate function either, so I currently have to basically copy most of signDigestWith and make small adjustments to get a version that includes the parity information. In fact, the web3-crypto package does exactly that in its Crypto.Ecdsa.Signature.sign function (see https://github.com/airalab/hs-web3/blob/master/packages/crypto/src/Crypto/Ecdsa/Signature.hs).

Is there a proper way to do this? If not, would it be possible to extend the Crypto.PubKey.ECC.ECDSA.Signature record to include more information?

[kazu-yamamoto]

I agree that the current API has the limitation.
You can modify the API as you like.
Actually, I modified somethings to implement HPKE (#42) recently.
Please feel free to send a PR for your purpose.
I would merge it if the PR looked reasonable to me.

[julmb]

Okay, I looked into this but there are some things I am unsure about.

Key Recovery Information in Signature Type

We could include the key recovery information in the Signature type. However, this would raise the question of whether the verify and verifyDigest functions should check if the key recovery information matches the signature and the public key. However, existing users of these functions will expect to continue to be able to verify signatures consisting only of r and s. Also, since this information is intended to be used for key recovery, maybe it should not be part of the verification process at all.

I am currently leaning towards not including the key recovery information in the Signature type and instead have the various sign* functions return (Bool, Signature) so that users can decide if they need the key recovery information or if they want to discard it.

Recovery Information Size

The hs-web3 package uses two bits of key recovery information and the eth-keys package uses one bit.

I do not understand elliptic curve cryptography enough to know what the correct choice is here. Maybe eth-keys only needs one bit because it only needs to handle the SEC_p256k1 curve? Or maybe it is just a quirk of the Ethereum specification. I am leaning towards one bit since that allows usage of the Bool type and it is enough for my use case. However, I could be convinced otherwise.

Signature Normalization

Both hs-web3 and eth-keys use if 2 * s < n then s else n - s, where the current implementation always uses s.

It seems like verify and verifyDigest do not change their result if s is replaced by n - s, so maybe users would not care about this? From what I have read, it is maybe desirable to have s normalized in this way. However, using this normalization of s would mean having to adjust many of the golden tests in KAT_PubKey.ECDSA. Again, I do not know enough about elliptic curve cryptography to know what the correct way of doing things is here. Do most implementation normalize s or is this an uncommon behavior of hs-web3 and eth-keys?

---

I am willing to make a PR for this but I would be grateful for some input by people who are more knowledgeable about cryptography.

[julmb]

Signature Normalization

Both hs-web3 and eth-keys use if 2 * s < n then s else n - s, where the current implementation always uses s.

Apparently this is related to the problem of "ECDSA Malleability". I do not know how important it is for crypton to avoid this problem. It might also be acceptable to push this responsibility downstream and have users of the sign* functions deal with it. They have access to both n from the curve and s from the signature, so the normalization can be performed as a postprocessing step after the signature generation. In this case, maybe we want to add a small helper function that accomplishes this for the convenience of users.

[julmb]

Another question is if the functions in Crypto.PubKey.ECDSA should also have key recovery information added to them. From what I can tell, Crypto.PubKey.ECDSA offers a type class based interface, while Crypto.PubKey.ECC.ECDSA works with explicit Curve values. I am not sure why this distinction exists in the first place. If there is some explanation to that, it might help with the decision on whether to add the key recovery information to both modules.

[kazu-yamamoto]

What I can suggest is two ways:

Easy way: provide your own new ECDSA module, e.g., Crypto.PubKey.ECC.ECDSA.Parity. This maintain backward compatibility completely.

Difficult way: stop exporting Signature data constructor for future compatibility. Since this breaks backward compatibility , the major version need to bump up. (#42 breaks backward compatibility, so it's very good timing now.) Then you can add parity fields.

If you want to provide signature normalization, the best way is provide test cases to show that the current code is not perfect. Then add a commit to fix it. This convinces me that there is actually a problem and it is surely fixed.

[julmb]

Easy way: provide your own new ECDSA module, e.g., Crypto.PubKey.ECC.ECDSA.Parity. This maintain backward compatibility completely.

Difficult way: stop exporting Signature data constructor for future compatibility. Since this breaks backward compatibility , the major version need to bump up. (#42 breaks backward compatibility, so it's very good timing now.) Then you can add parity fields.

I would like to avoid adding a third ECDSA module if you are okay with a breaking change and major version bump.

In my opinion, the public key recovery information should not be part of the Signature type. Simplified architecture:

data Signature = Signature { r :: Integer, s :: Integer }
type ExtendedSignature = (Bool, Signature)

sign :: PrivateKey -> Digest -> ExtendedSignature
verify :: PublicKey -> Digest -> Signature -> Bool
recover :: Digest -> ExtendedSignature -> PublicKey

I think it would be really strange for verify to take an ExtendedSignature, and impossible for recover to take a regular Signature. So I think it would be good to have separate types for signatures with and without public key recovery information.

I am not yet sure if it would be better to have ExtendedSignature be (1) a proper type, (2) a type synonym, (3) use tuples directly.

If you want to provide signature normalization, the best way is provide test cases to show that the current code is not perfect. Then add a commit to fix it. This convinces me that there is actually a problem and it is surely fixed.

From what I understand, there is no problem that needs to be fixed, and it is just a matter of how the signature is used. Also, the entire normalization problem can just be solved with postprocessing of the signature after it is generated. So the sign* functions do not have to be concerned with normalization. In any case, this is also a separate issue/pull request, so I will work on this later.

[kazu-yamamoto]

data Signature = Signature { r :: Integer, s :: Integer }
type ExtendedSignature = (Bool, Signature)

sign :: PrivateKey -> Digest -> ExtendedSignature
verify :: PublicKey -> Digest -> Signature -> Bool
recover :: Digest -> ExtendedSignature -> PublicKey

One technique to maintain backward compatibility is to provide a new function name:

sign :: (ByteArrayAccess msg, HashAlgorithm hash, MonadRandom m) => PrivateKey -> hash -> msg -> m Signature
sign' :: whatever you want

What do you think?

[julmb]

I think it really depends on how important backwards compatibility is to you. If you do not care about breaking changes, then I think changing the existing sign* functions will lead to a module with fewer functions that is less confusing and easier to understand. I would slightly prefer this, but if backwards compatibility is very important to you, then I am also okay with adding new functions instead.

[julmb]

I can also make a draft PR tomorrow and then you can see what it would look like. Then you can tell me if you think that is okay or if you would rather have additional functions.

[kazu-yamamoto]

I prefer to adding functions since I want to avoid breaking changes if possible.
Anyway, PR is welcome.
I will check if it introduces breaking changes to the tls package.