0
$\begingroup$

If I were to supply arbitrary values to an ECDSA recover function on secp256k1, is there some likelihood that the function would fail to return some value for the public key?

I am specifically trying to create signatures for an Ethereum transaction whereby the private key is unknown to me (single use transactions). Please assume that I will choose the values for the signature to optimise success (I.e., only enter sane values).

Edit: to clarify what I’m trying to achieve, see this post https://medium.com/@weka/how-to-send-ether-to-11-440-people-187e332566b7. In summary: create a transaction with some invented signature, do ecrecover on that signature to find it’s public key (and Ethereum address), fund that address with another transfer then finally submit the original transaction. Achieves a net result of sending a transaction from an address without knowing it’s private key. Not overwhelming useful, but interesting nonetheless.

Improve this question
$\endgroup$
2
  • $\begingroup$ Both answers to this might be of interest. But in any case, "trying to create signatures (..) whereby the private key is unknown to me" should be impossible for a pre-existing public key, and is trivial for a newly chosen public key. What are you trying to achieve exactly? $\endgroup$
    – fgrieu ♦
    Commented May 24, 2018 at 6:26
  • 1
    $\begingroup$ Thanks. I found this article earlier and it was helpful. I have updated the question to include a more detailed description of what am attempting to achieve. $\endgroup$
    – paulhauner
    Commented May 24, 2018 at 7:30

1 Answer 1

Reset to default
2
$\begingroup$

Yes.

Non-ethereum elliptic curve signatures result in the numbers r and s, both of which need to lie in the range [1,n-1], where n is the size of the order of the elliptic curve base point. See Wikipedia - Elliptic Curve Digital Signature Algorithm.

Ethereum transaction signatures, use the secp256k1 curve (which has a fixed n value) and requires the numbers v,r and s. r has the same range as above, however unlike standard elliptic curve signatures, s is restricted to the range [1, n/2+1] (see the Ethereum Yellow Paper - Appendix F). Any values of r and s outside these ranges will generate an invalid signature.

Assuming we stick to r and s values within this range, we must also supply a v value for an Ethereum transaction signature. EIP-155 specifies v = CHAIN_ID *2 + 35 or v = CHAIN_ID*2 + 36.

The r value represents the x-value of a point on the scep256k1 curve. Fundamentally, v, represents the parity (even or odd) of the y-value of the point given by r (i.e the corresponding x-value). This parity determines whether to use 35 or 36 in the specification of v above. The value v is used as the recoveryid or recid in this library for ECDSA recovery on line 89 which is used by go-ethereum. Incorrect v values may make this recovery incorrect and give invalid resulting public keys. Thus, if one were to keep v fixed, and randomize r and s (or equivalently, randomize all numbers) within their range of validities and we were to assume an equal chance of getting an odd or even number, we would expect on average, 50% of signatures to be invalid (because we have an incorrect parity).

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanks! This is the conclusion I came to originally (but with less elegance). I doubted though wether or not the parity can be “wrong” if there was never a public key in the first place (because we randomly chose the signature). If it can be identifiably wrong in this case, then wouldn’t that make including v redundant (except for optimisation purposes) in all cases because you could try one parity, identify it as wrong and then try the other parity? Maybe this is the case and v exists for optimisation? $\endgroup$
    – paulhauner
    Commented May 24, 2018 at 5:27
  • $\begingroup$ We could test my theory using an eth node by flipping v and seeing what happens. I’m at a theme park now, though. $\endgroup$
    – paulhauner
    Commented May 24, 2018 at 5:39
  • $\begingroup$ I've since been going through the implementations. Ethereumjs line 395, simply checks if v is 0 or 1 then sends r and s to the standard secp256k1 to return the public key. geth line 181 does a similar thing. For geth, the actual implementation is in this library. Haven't tracked down the verification of v yet $\endgroup$
    – Age
    Commented May 24, 2018 at 6:09
  • $\begingroup$ Seems to me, that you could just put r (the x-value) into the curve and calculate the parity. $\endgroup$
    – Age
    Commented May 24, 2018 at 6:25
  • $\begingroup$ v gets set in the signing process on line 294 here (recid = v is the recovery id)... It seems to only be used in the recovery for optimisation. See line 89 here. The parity seems to allow specific calculations if the y value is odd or even in the recovery process. Performing the wrong one may end up in invalid pub keys $\endgroup$
    – Age
    Commented May 24, 2018 at 6:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.